Inserting Charging Stops in Route Optimization

An optimizer that plans an electric delivery route purely on distance and time windows will schedule stops the vehicle physically cannot reach — it has no concept of a battery running out mid-route. This page covers the narrow step that closes that gap: splicing a charging stop into a route that EV fleet charging-aware route optimization has already flagged for a state-of-charge shortfall, without discarding the stop sequence and time windows the optimizer produced. It assumes the upstream energy model — covered separately — has already produced a per-stop state-of-charge trace; this page picks up from there and is one part of the broader Routing API Automation & Fleet Integration toolkit for automating fleet dispatch.

The problem is narrower than full route re-optimization: given a route where one stop’s projected arrival state of charge drops below a safety reserve, find the cheapest charger to insert between the preceding and following stops such that the added detour distance, queue wait, and charge dwell time do not push any downstream stop past its time window.

When to Use This Approach

Use targeted insertion — rather than re-solving the whole vehicle routing problem — when:

• The optimizer has already committed to a stop sequence and time windows, and re-solving the full problem for one violation is too slow for a dispatch-time decision
• Violations are sparse — typically one or two stops per route breach the reserve, not the majority of the route
• A energy model such as modeling battery-range constraints for EV fleets has already produced a reliable per-stop arrival_soc_kwh trace to evaluate against
• Charger locations near the route are known ahead of time (a static POI table, not live availability lookups on every request)

Reach for full re-optimization instead when a route has multiple simultaneous violations, when the fleet has slack to reassign stops between vehicles, or when charger occupancy is volatile enough that a plan computed even a few minutes ago is stale. Insertion is a repair step; it does not rebalance the route.

Implementation

The functions below take an already-optimized route (a list of stops with an energy-model-derived arrival_soc_kwh per stop) and a static table of nearby chargers, and produce a single best insertion for the first violation found. It does not repeat the energy accumulation logic from the battery-range model — only the insertion and feasibility check.

# requires: none beyond the standard library
# Python 3.9+

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional
import math

EARTH_RADIUS_KM = 6371.0
AVG_SPEED_KMH = 32.0        # urban delivery average, used for detour time estimate
RESERVE_SOC_KWH = 6.0       # safety reserve the pack must never drop below
PACK_KWH = 75.0


def haversine_km(lat1: float, lon1: float, lat2: float, lon2: float) -> float:
    dlat = math.radians(lat2 - lat1)
    dlon = math.radians(lon2 - lon1)
    a = (math.sin(dlat / 2) ** 2
         + math.cos(math.radians(lat1)) * math.cos(math.radians(lat2))
         * math.sin(dlon / 2) ** 2)
    return EARTH_RADIUS_KM * 2 * math.asin(math.sqrt(a))


@dataclass
class Stop:
    stop_id: str
    lat: float
    lon: float
    arrival_soc_kwh: float   # from the upstream energy model, before any insertion
    tw_end_min: float        # end of the delivery time window, minutes from route start
    eta_min: float           # currently scheduled arrival, minutes from route start


@dataclass
class Charger:
    charger_id: str
    lat: float
    lon: float
    plug_kw: float
    occupied_until_min: float = 0.0   # reservation ledger; 0 means free now


def find_violations(route: list[Stop], reserve_kwh: float = RESERVE_SOC_KWH) -> list[int]:
    """Indices of stops whose projected arrival SoC breaches the reserve."""
    return [i for i, s in enumerate(route) if s.arrival_soc_kwh < reserve_kwh]


def candidate_chargers(
    origin: Stop, destination: Stop, chargers: list[Charger], max_detour_km: float = 6.0
) -> list[Charger]:
    """Chargers whose via-detour over the origin-destination edge stays within budget,
    ranked cheapest first. Distances are haversine — a fast pre-filter, not the final cost."""
    direct_km = haversine_km(origin.lat, origin.lon, destination.lat, destination.lon)
    ranked = []
    for c in chargers:
        via_km = (haversine_km(origin.lat, origin.lon, c.lat, c.lon)
                  + haversine_km(c.lat, c.lon, destination.lat, destination.lon))
        detour_km = via_km - direct_km
        if detour_km <= max_detour_km:
            ranked.append((detour_km, c))
    ranked.sort(key=lambda pair: pair[0])
    return [c for _, c in ranked]


def charge_time_min(soc_kwh: float, target_kwh: float, plug_kw: float) -> float:
    """Linear estimate; swap for a taper curve above ~80% pack SoC in production."""
    needed_kwh = max(0.0, target_kwh - soc_kwh)
    return (needed_kwh / plug_kw) * 60.0


def feasible_insertion(
    origin: Stop, destination: Stop, charger: Charger,
    target_soc_kwh: float, energy_kwh_per_km: float = 0.22,
) -> Optional[dict]:
    """Evaluate one charger between origin and destination. Returns the insertion
    record if it keeps the destination's time window intact, else None."""
    leg1_km = haversine_km(origin.lat, origin.lon, charger.lat, charger.lon)
    leg2_km = haversine_km(charger.lat, charger.lon, destination.lat, destination.lon)

    leg1_min = (leg1_km / AVG_SPEED_KMH) * 60.0
    arrival_at_charger_min = origin.eta_min + leg1_min
    soc_at_charger = origin.arrival_soc_kwh - leg1_km * energy_kwh_per_km
    if soc_at_charger < 0:
        return None  # can't reach this candidate at all

    queue_wait_min = max(0.0, charger.occupied_until_min - arrival_at_charger_min)
    charge_start_min = arrival_at_charger_min + queue_wait_min
    dwell_min = charge_time_min(soc_at_charger, target_soc_kwh, charger.plug_kw)
    departure_min = charge_start_min + dwell_min

    leg2_min = (leg2_km / AVG_SPEED_KMH) * 60.0
    new_arrival_min = departure_min + leg2_min
    new_arrival_soc = target_soc_kwh - leg2_km * energy_kwh_per_km

    if new_arrival_min > destination.tw_end_min or new_arrival_soc < 0:
        return None

    return {
        "charger_id": charger.charger_id,
        "dwell_min": dwell_min,
        "queue_wait_min": queue_wait_min,
        "new_arrival_min": new_arrival_min,
        "new_arrival_soc_kwh": new_arrival_soc,
        "added_min": new_arrival_min - destination.eta_min,
    }


def insert_best_charger(
    route: list[Stop], chargers: list[Charger], violation_idx: int, target_soc_kwh: float = 45.0
) -> Optional[dict]:
    """Score every nearby charger for the edge before the violating stop; return
    the feasible option that adds the least time."""
    origin, destination = route[violation_idx - 1], route[violation_idx]
    best = None
    for c in candidate_chargers(origin, destination, chargers):
        result = feasible_insertion(origin, destination, c, target_soc_kwh)
        if result and (best is None or result["added_min"] < best["added_min"]):
            best = result
    return best


def propagate_and_validate(route: list[Stop], violation_idx: int, added_min: float) -> bool:
    """Shift ETAs for every stop after the insertion point and confirm no
    downstream time window breaks as a result."""
    for stop in route[violation_idx:]:
        stop.eta_min += added_min
        if stop.eta_min > stop.tw_end_min:
            return False
    return True

A dispatcher loop ties the three functions together: find the first violation, insert the best charger for it, propagate the delay, and repeat until find_violations returns empty or an insertion attempt fails — at which point the route needs escalation rather than automatic repair.

Key Parameters and Tuning

Integration Points

Upstream energy trace. arrival_soc_kwh on each Stop should come directly from modeling battery-range constraints for EV fleets, which accounts for grade, payload, and regenerative braking per edge. Feeding this function a flat distance-based estimate instead will misplace the violation index and produce insertions that look feasible on paper but fail in the field.

Speed and energy consistency. AVG_SPEED_KMH and energy_kwh_per_km should be pulled from the same calibrated profile used elsewhere in the fleet’s routing stack — see calibrating speed profiles for electric delivery fleets for how those per-vehicle-class profiles are derived from OSM highway tags and telemetry. Using a generic diesel speed profile here understaples dwell time because EV energy consumption at urban stop-and-go speeds diverges sharply from highway cruising.

Real routing distance before commit. candidate_chargers and feasible_insertion both use haversine distance to keep the search fast across dozens of candidates. Before the insertion is finalized and dispatched, replace leg1_km and leg2_km with actual route distances from an OSRM /route or Valhalla request between origin, charger, and destination — road network distance is routinely 20-40% higher than straight-line distance in urban areas, which changes both energy consumption and drive time.

Feeding the dispatch layer. The insertion record’s new_arrival_min and new_arrival_soc_kwh become the updated eta_min and arrival_soc_kwh for the destination stop, and every later stop shifts by added_min via propagate_and_validate. If a live re-routing pipeline is already in place, this insertion logic slots into it as the energy-aware step that runs before a recomputed route is pushed to the vehicle.

Validation Checklist

1. Violation detection matches the energy model. Run find_violations against a route where the upstream battery-range model already flagged a shortfall and confirm the same stop index is returned.
2. No insertion violates its own destination window. For every accepted feasible_insertion result, assert new_arrival_min <= destination.tw_end_min holds exactly — an off-by-one on inclusive vs. exclusive window bounds is the most common bug here.
3. Downstream propagation is exhaustive. After calling propagate_and_validate, verify every stop after the insertion point has eta_min <= tw_end_min, not just the immediate next stop.
4. Haversine pre-filter does not silently exclude the eventual winner. Spot-check a handful of routes by comparing the top 3 haversine-ranked candidates against real OSRM distances; if the ranking order flips often, tighten max_detour_km less aggressively.
5. Charger occupancy prevents double-booking. Simulate two vehicles converging on the same charger within one dispatch cycle and confirm the second vehicle’s queue_wait_min reflects the first vehicle’s reservation.
6. No-solution case is handled explicitly. Confirm insert_best_charger returning None triggers escalation (detour widening, vehicle reassignment, or manual dispatcher review) rather than being silently dropped from the route plan.

Related

• EV fleet charging-aware route optimization — the overview covering energy modeling, charger snapping, and state-of-charge tracking this page’s insertion logic depends on
• Modeling battery-range constraints for EV fleets — the upstream per-edge energy model that produces the arrival_soc_kwh trace consumed here
• Calibrating speed profiles for electric delivery fleets — deriving the per-vehicle-class speed and energy-consumption profile used in the detour and dwell-time calculations
• Speed profile calibration for heavy vehicles — the broader calibration workflow this EV-specific profile builds on