VRP Variants

Electric Vehicle Routing Problem (E-VRP)

The Electric Vehicle Routing Problem extends the VRP to fleets of battery electric vehicles (BEVs). The key difference with a conventional (internal-combustion) fleet is the limited driving range: vehicles may need to visit charging stations during their routes to recharge the battery before continuing to serve customers. The best-known variant is the E-VRPTW — the E-VRP with time windows — introduced by [Schneider, Stenger & Goeke 2014].

What makes it different

Limited range / battery capacity. Each vehicle has a battery capacity Q (in energy units) that bounds how far it can travel before recharging. Energy is consumed roughly in proportion to distance (and load) traveled.
Charging stations. A set of stations is available where a vehicle may stop to recharge. Stations can be visited zero or more times per route, and recharging may be full or partial.
Recharging decisions. The model must decide whether to recharge, where, and how much. Recharging takes time (often a linear function of the energy transferred), which interacts with route duration and time windows.
Energy feasibility. A route is feasible only if the battery level never drops below zero between consecutive recharges.

Formal description

Objective: minimize the number of vehicles and the total travel (distance/time) cost, subject to customer service and energy constraints. Some versions also minimize energy consumption, emissions, or charging cost.
Feasibility: in addition to the VRP/VRPTW constraints (each customer served once, capacity, time windows), the E-VRP adds:
- battery state-of-charge tracking along the route;
- detours to charging stations that consume both time and possibly cost;
- partial or full recharge quantities as decision variables.
Tracking the battery: let $q_k$ denote the battery level on arrival at node k. For each arc (i, j), energy decreases by a consumption c_ij, so it must hold that q_i − c_ij ≥ 0 and q_j = q_i − c_ij (plus any amount recharged if j is a station). A route is energy-feasible if q stays within [0, Q] along the whole route.

Related green variants

Green VRP (G-VRP) [Erdoğan & Miller-Hooks 2012]: routing alternative-fuel vehicles with refueling stations (a precursor of the E-VRP).
Pollution-Routing Problem (PRP) [Bektaş & Laporte 2011]: minimizes emissions by jointly optimizing routes and speeds.
E-VRPTW with partial recharges, nonlinear charging, or mixed fleets: many extensions consider partial charging, nonlinear charging functions, time-of-use electricity prices, and mixed electric/conventional fleets.

Why it matters

Electric fleets are central to sustainable city logistics and last-mile delivery. The E-VRP captures the operational trade-off between shorter, cleaner electric routes and the time lost to recharging, and is a hot topic in current research. See the bibliography on Green & Electric VRP.

Featured application: electric waste collection

Real-world impact. A recent demonstration of the E-VRP in practice is the work of Peña, Dorronsoro & Ruiz (2024), Sustainable waste collection optimization using electric vehicles, published in Sustainable Cities and Society 105: 105343. The paper applies electric-vehicle routing to municipal waste collection, showing how optimized EV routes cut both operational cost and emissions in a real city service — a concrete example of the E-VRP delivering environmental and economic benefits at scale. [citation]