The Mobile Charging Vehicle Routing Problem with Time Windows and Recharging Services

Shaohua Cui, Hui Zhao, Hui Chen, Cuiping ZhangComput. Intell. Neurosci 2018 · DOI

TL;DR

This paper introduces a mathematical model for the "Mobile Charging Vehicle Routing Problem" (MCVRP) to optimize the routes of electric vehicles that provide on-demand charging services for battery electric vehicles (BEVs). By formulating this as a mixed-integer linear program (MILP) based on the vehicle routing problem with time windows, the authors aim to minimize travel distance while ensuring timely service and considering vehicle battery constraints.

What Problem Does This Paper Address?

The increasing adoption of Battery Electric Vehicles (BEVs) is hampered by "range anxiety" – the fear of running out of battery power before reaching a charging station. While public charging infrastructure is growing, it's not always sufficient, especially for longer journeys or in areas with limited coverage. To address this, mobile charging services (using specialized vehicles, or MCVs) are emerging to provide on-demand charging. However, efficiently routing these MCVs to serve multiple BEVs with specific time window requests, while also managing their own battery levels and potential recharging needs at charging stations, presents a complex operational challenge. This paper tackles the problem of designing optimal routes for these MCVs to minimize total travel distance while satisfying all charging requests within their specified time windows.

Methods

The core of this paper is the formulation of the Mobile Charging Vehicle Routing Problem (MCVRP) as a mixed-integer linear program (MILP). This model is built upon the established Vehicle Routing Problem with Time Windows (VRPTW) framework, specifically incorporating elements from the Electric Vehicle Routing Problem with Time Windows (E-VRPTW). Key methodological contributions include:

  • Modeling MCV Battery Constraints: The model explicitly accounts for the battery capacity of the mobile charging vehicles (MCVs), their energy consumption rate based on distance, and the need for them to potentially recharge at designated charging stations.
  • Partial Recharging Strategy: Unlike some previous models that assumed full recharges, this paper incorporates a "partial recharge strategy," making the model more realistic by allowing MCVs to recharge only the necessary amount of power.
  • Time Windows: The model adheres to the time windows specified for customer service requests, ensuring that BEVs receive charging within their acceptable service intervals.
  • MILP Formulation: The problem is translated into a mathematical optimization model using binary decision variables for route selection and continuous variables for time and battery state. This MILP can be solved using commercial optimization solvers.

Datasets

The paper does not use pre-existing datasets for training. Instead, it introduces a set of 36 small-sized benchmark instances for evaluating the proposed model. These instances are generated based on the well-known VRPTW instances by Solomon [21]. The generated instances are categorized into three classes based on the geographical distribution of charging requests: clustered (C), randomly distributed (R), and a combination of both (RC). For each customer, the model considers the possibility of visiting at most two different charging stations, and these stations are located within a radius of three times the running range of the MCVs.

Key Insights and Ideas

  • The Trade-off Between Battery Capacity and Efficiency: Larger battery capacities in MCVs directly lead to reduced total travel distance and a decrease in the number of MCVs required. This is because vehicles can service more customers without needing to recharge as frequently.
  • The Impact of Recharging Rate: A faster recharging rate for MCVs significantly improves service efficiency, leading to shorter travel distances and fewer vehicles needed. This highlights the importance of efficient charging infrastructure for the MCVs themselves.
  • Service Efficiency Matters: Increasing the service efficiency at customer nodes (i.e., reducing the time spent charging a BEV) also contributes to reducing total travel distance and the number of MCVs.
  • The Importance of Realistic Modeling: Incorporating partial recharging and considering the MCV's own battery constraints are crucial for developing practical and efficient mobile charging solutions.

Key Results

The paper successfully demonstrates the effectiveness of its MILP model by solving all 36 generated instances within a reasonable time limit (7,200 seconds). The results from sensitivity analyses show clear trends:

  • Battery Capacity: Increasing battery capacity from 7x to 11x the average power demand of customer nodes resulted in a decrease in total travel distance. For example, across all instances, the average total travel distance decreased from 305.27 (BC-Case I) to 272.13 (BC-Case III). The number of vehicles and charging stations used also generally decreased.
  • Recharging Rate: Increasing the recharging rate (from 1x to 3x the average BEV charging rate) also led to reductions in total travel distance and the number of MCVs. The average total travel distance decreased from 272.94 (CR-Case I) to 280.04 (CR-Case III), with some instances showing improvements.
  • Service Efficiency: Enhancing service efficiency (e.g., by reducing service time) also showed improvements in total travel distance and the number of MCVs. For instance, in BC-Case I, 18 solutions showed improved traveled distance when service efficiency was increased.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Scalability: The current MILP formulation might struggle with very large-scale problems due to computational complexity. Future work could explore more efficient algorithms like adaptive large neighborhood search (ALNS) or hybrid heuristics.
  • Model Simplifications: The current model assumes a homogeneous fleet of MCVs and requests, a flat terrain, and constant travel speeds. Future research could incorporate heterogeneity in vehicles and requests, consider road grades, and account for varying vehicle speeds.
  • Dynamic Requests: The model assumes static requests. Future work could address dynamic service requests, which would require more complex real-time routing adjustments.
  • Behavioral Aspects: Incorporating behavioral aspects of BEV drivers and exploring behavioral-oriented charging services combined with vehicle routing are also suggested.

Summary updated

BibTeX
@article{cui2018mobile,
  author = {Shaohua Cui and Hui Zhao and Hui Chen and Cuiping Zhang},
  title = {{The Mobile Charging Vehicle Routing Problem with Time Windows and Recharging Services}},
  journal = {Comput. Intell. Neurosci.},
  year = {2018},
  doi = {10.1155/2018/5075916},
}
Figure