Hybrid Memetic Search for Electric Vehicle Routing With Time Windows, Simultaneous Pickup-Delivery, and Partial Recharges

Zubin Zheng, Shengcai Liu, Yew-Soon Ong

TL;DR

This paper introduces a novel hybrid memetic algorithm (HMA) to tackle the complex Electric Vehicle Routing Problem with Time Windows, Simultaneous Pickup-Delivery, and Partial Recharges (EVRP-TW-SPD). HMA achieves state-of-the-art performance by combining innovative parallel-sequential station insertion and cross-domain neighborhood search techniques, and is validated on a new, large-scale benchmark derived from real-world logistics data.

What Problem Does This Paper Address?

The increasing adoption of electric vehicles (EVs) for logistics presents a unique set of challenges compared to traditional vehicles. These include limited battery range, the need for recharging, and the time required for charging. The Electric Vehicle Routing Problem (EVRP) aims to optimize routes for these vehicles, but real-world scenarios are far more complex. This paper focuses on a particularly challenging variant: EVRP-TW-SPD. This problem incorporates:

  • Time Windows: Customers have specific timeframes for deliveries and pickups.
  • Simultaneous Pickup-Delivery: Vehicles must handle both picking up items and delivering them within the same route.
  • Partial Recharges: EVs don't necessarily need to fully recharge at stations, allowing for quicker stops and better adherence to tight schedules.

Existing research on EVRP-TW-SPD is limited, and current benchmarks are often too small to reflect the scale of real-world logistics operations. This gap hinders the development of robust algorithms capable of handling the complexities of modern EV fleet management.

Methods

The core of this paper is the proposed Hybrid Memetic Algorithm (HMA), which combines individual-based large neighborhood search (LNS) with population-based memetic search (MS). HMA introduces two key novel components:

  • Parallel-Sequential Station Insertion (PSSI): This procedure addresses the need for partial recharges. It combines two strategies:
  • Parallel Station Insertion (PSI): A genetic algorithm explores multiple station insertion possibilities simultaneously between customer pairs, aiming to avoid local optima.
  • Sequential Station Insertion (SSI): A more traditional approach that inserts stations one by one along the route. PSSI selects the better outcome from PSI and SSI, offering a more comprehensive route exploration.

  • Cross-Domain Neighborhood Search (CDNS): This local search module explores two solution spaces concurrently:

  • The EVRP-TW-SPD solution space (considering all constraints).
  • The VRP-TW-SPD solution space (ignoring the electricity constraint). This dual-domain approach allows HMA to leverage existing efficient local search techniques for the non-electric VRP and potentially discover better solutions that might be missed by single-domain searches. CDNS has two sub-procedures: Aggressive Local Search (ALS) for the VRP-TW-SPD space and Conservative Local Search (CLS) for the EVRP-TW-SPD space.

The HMA framework also includes an initialization step using the RCRS heuristic and a destroy-repair operator for large-step perturbations. For very large instances, a decomposition strategy (Barycenter Clustering Decomposition - BCD) is employed to break down the problem into smaller subproblems.

Datasets

The paper uses two sets of datasets for evaluation:

  • Existing Benchmark (akb set): This set is derived from existing EVRP-TW instances and consists of small (5-15 customers) and medium (100 customers) scale problems. These instances are synthetic and assume Euclidean distances.
  • New Large-Scale Benchmark (jd set): Introduced by the authors, this benchmark is derived from real-world JD Logistics data from Beijing. It features significantly larger instances, with up to 1000 customers and 100 charging stations. Crucially, these instances use real-world geographic coordinates (longitude/latitude) and may not satisfy the triangle inequality for distances, making them more representative of practical scenarios.

Key Insights and Ideas

  • The Power of Hybridization: Combining population-based memetic search with individual-based large neighborhood search proves highly effective for complex optimization problems like EVRP-TW-SPD.
  • PSSI's Advantage: The parallel-sequential approach to handling partial recharges is more effective than purely sequential methods at avoiding local optima and finding higher-quality routes, even with a slight increase in computation time.
  • Cross-Domain Search for Broader Exploration: Exploring both the electric and non-electric VRP solution spaces simultaneously (CDNS) allows the algorithm to leverage existing VRP research and discover better solutions.
  • Real-World Data is Crucial: The new, large-scale benchmark derived from JD Logistics data is essential for bridging the gap between academic research and practical applications, highlighting the limitations of smaller, synthetic datasets.
  • Decomposition for Scalability: For very large problems, breaking them down into smaller, manageable subproblems using BCD significantly improves computational efficiency and solution quality.

Key Results

  • State-of-the-Art Performance: HMA consistently outperforms existing state-of-the-art algorithms (Adapt-CMSA-STD and Adapt-CMSA-SETCOV) on both small/medium and large-scale instances.
  • Significant Improvement on Large Instances: On the new, large-scale jd dataset, HMA demonstrates a substantial performance advantage, achieving better solutions and more stable results (lower standard deviation) compared to existing methods, especially as problem size increases.
  • BCD's Impact: The BCD decomposition strategy significantly enhances HMA's performance on large-scale instances, particularly for problems with 600 or more customers.
  • Robustness: Statistical tests (CD plots) confirm HMA's robust performance across various problem scales, customer distributions, and constraint characteristics.
  • Efficiency: HMA achieves its superior results with competitive or even reduced computation times compared to other algorithms, especially on larger instances. For example, it uses about 60% of the time consumed by other algorithms on medium-scale instances.

Limitations and Future Work

  • PSSI Refinement: The paper suggests that PSSI could be further improved by using learned functions (e.g., neural networks) to evaluate insertions, potentially leading to even better routes with less computational effort.
  • Decomposition Strategy: While BCD is effective, the paper acknowledges that designing ideal decomposition strategies is challenging. Future work could explore learning-based methods or pre-trained models to automatically design more effective decomposition strategies tailored to specific problem characteristics.
  • Triangle Inequality: While the paper notes that real-world distances might not satisfy the triangle inequality and suggests a preprocessing step (Floyd-Warshall), this aspect could be further investigated for its impact on algorithm performance.

Summary updated

Abstract

With growing environmental concerns, electric vehicles for logistics have gained significant attention within the computational intelligence community in recent years. This work addresses an emerging and significant extension of the electric vehicle routing problem (EVRP), namely EVRP with time windows, simultaneous pickup-delivery, and partial recharges (EVRP-TW-SPD), which has widespread real-world applications. We propose a hybrid memetic algorithm (HMA) for solving EVRP-TW-SPD. HMA incorporates two novel components: a parallel-sequential station insertion (PSSI) procedure for handling partial recharges that can better avoid local optima compared to purely sequential insertion, and a cross-domain neighborhood search (CDNS) that explores solution spaces of both electric and non-electric problem domains simultaneously. These components can also be easily applied to various EVRP variants. To bridge the gap between existing benchmarks and real-world scenarios, we introduce a new, large-scale EVRP-TW-SPD benchmark set derived from real-world applications, containing instances with many more customers and charging stations than existing benchmark instances. Extensive experiments demonstrate the significant performance advantages of HMA over existing algorithms across a wide range of problem instances. Both the benchmark set and HMA are to be made open-source to facilitate further research in this area.
BibTeX
@article{zheng2025hybrid,
  author = {Zubin Zheng and Shengcai Liu and Yew-Soon Ong},
  title = {{Hybrid Memetic Search for Electric Vehicle Routing With Time Windows, Simultaneous Pickup-Delivery, and Partial Recharges}},
  journal = {IEEE Trans. Emerg. Top. Comput. Intell.},
  year = {2025},
  url = {https://openreview.net/forum?id=lHm7VEoCNb},
}
Figure