Multi-Depot Joint Distribution Vehicle Routing Problem Considering Energy Consumption with Time-Dependent Networks

Dengkai Hou, Houming Fan, Xiaoxue RenSymmetry 2021 · DOI

TL;DR

This paper tackles the complex challenge of optimizing multi-depot vehicle routing by accounting for real-world factors like time-varying road speeds and fuel consumption linked to vehicle load. They introduce a novel hybrid genetic algorithm with variable neighborhood search (HGAVNS) to solve this problem, demonstrating its effectiveness on benchmark datasets and custom instances.

What Problem Does This Paper Address?

Logistics companies often operate with multiple distribution centers (depots) and need to efficiently deliver goods to numerous customers. Traditional vehicle routing problems (VRPs) often simplify these scenarios by assuming constant travel times and neglecting factors like varying traffic conditions or how a vehicle's load affects its fuel efficiency. This paper addresses the Multi-Depot Joint Distribution Vehicle Routing Problem with Time-Dependent Networks (MDJDVRP-TDN). The core challenge is to minimize total distribution costs, which include fixed vehicle costs, fuel expenses, and penalties for late deliveries, while considering:

  • Multiple Depots: Vehicles can start from and return to any of several depots.
  • Time-Dependent Networks: Road travel times are not constant but change dynamically throughout the day due to traffic congestion. This is modeled using continuous trigonometric functions, a more realistic approach than piecewise constant speeds.
  • Vehicle Load and Fuel Consumption: Fuel consumption is directly related to the vehicle's load, meaning heavier loads consume more fuel.
  • Time Windows: Customers have specific time intervals during which they can receive deliveries.

By incorporating these realistic elements, the problem becomes significantly more complex, moving from symmetric to asymmetric graph representations and requiring sophisticated solution methods.

Methods

The authors propose a Hybrid Genetic Algorithm with Variable Neighborhood Search (HGAVNS) to solve the MDJDVRP-TDN. The key components of their approach are:

  • Initial Population Generation:
    • Nearest Neighbor Insertion: A greedy method to create initial routes by selecting the closest available customer.
  • Logistic Mapping Equation: Utilizes a chaotic system to introduce randomness and diversity into the initial population, preventing premature convergence.
  • Fitness Function: The fitness of a solution is the reciprocal of its objective function value (total cost), meaning lower costs result in higher fitness.
  • Selection Operation: A combination of elite reservation (preserving the best solutions) and roulette wheel selection (probabilistically selecting solutions based on fitness) to balance solution quality and population diversity.
  • Variable Neighborhood Search (VNS): This is the core of the algorithm's improvement phase. It systematically explores different "neighborhoods" of a solution to find better ones. The paper defines five neighborhood structures:
  • Insertion: Moving a customer to a different position in a route.
  • Swap: Exchanging the positions of two customers within a route.
  • 2-Insertion: Inserting two customers at a new location.
  • 2-opt: Reversing a segment of a route between two customers.
  • Or-opt: Moving a sequence of customers to a different location.
  • Adaptive Neighborhood Search Times: The number of times the VNS explores each neighborhood is adjusted dynamically based on the current iteration number. This allows for broader exploration early on and deeper local search later in the optimization process.

Datasets

The paper utilizes the following datasets:

  • MDVRP Standard Instances: Publicly available instances (e.g., from neo.lcc.uma.es/vrp/vrp-instances/) were adapted to test the algorithm's performance on multi-depot routing problems.
  • TDVRPTW Standard Instances: Publicly available instances were used to evaluate the algorithm's capability in handling time-dependent networks and time windows.
  • Newly Generated MDJDVRP-TDN Instances: Since standard MDJDVRP-TDN instances were not available, the authors generated their own by modifying an MDVRP instance (p04) and incorporating time-dependent speed functions and load-dependent fuel consumption.

Key Insights and Ideas

  • Realism in Routing: The paper highlights the significant impact of time-dependent road speeds and load-dependent fuel consumption on distribution costs. Ignoring these factors can lead to suboptimal and less realistic routing plans.
  • Continuous Speed Variation: Modeling vehicle speed using continuous trigonometric functions is a more accurate representation of real-world traffic dynamics compared to discrete piecewise functions.
  • Hybrid Algorithm Synergy: The combination of Genetic Algorithm (for global exploration and diversity) and Variable Neighborhood Search (for deep local exploitation) proves effective in finding high-quality solutions for this complex problem.
  • Adaptive Search Strategy: The adaptive mechanism for VNS search times is crucial for balancing exploration and exploitation, leading to better convergence and solution quality.
  • Depot Return Strategy: Allowing vehicles to return to the closest depot after serving their last customer, rather than strictly the originating depot, can significantly reduce travel distance and overall cost.

Key Results

  • MDVRP Performance: HGAVNS outperformed other algorithms (GA, ILS, AMAVNS) on standard MDVRP instances, finding optimal solutions for several instances and achieving very small deviations (less than 2%) on others.
  • TDVRPTW Performance: HGAVNS demonstrated stable and superior performance compared to IRCI and p-SA on TDVRPTW instances, often finding better optimal solutions.
  • MDJDVRP-TDN Performance: On the newly generated MDJDVRP-TDN instances, HGAVNS achieved solutions with deviations within 5% of the best found solution over 10 runs, with the best solution being found twice. The algorithm showed high solving efficiency, converging within 200 seconds.
  • Sensitivity Analysis:
    • Vehicle Speed: Changes in vehicle speed significantly impact time window penalty costs and fuel consumption. Increasing speed by 6 km/h led to a 1.77% decrease in total cost, while other changes resulted in increases.
  • Load on Fuel Consumption: Considering the impact of vehicle load on fuel consumption leads to more realistic total distribution costs, with deviations up to -24.98% when load is ignored.

Limitations and Future Work

  • Real-time Traffic Information: The paper acknowledges that real-time traffic information and handling unexpected emergencies are not incorporated. Future work could focus on dynamic route planning that adapts to live traffic updates.
  • Stochasticity: While time-dependent speeds are considered, other stochastic elements like uncertain travel times or customer demands are not explicitly modeled.
  • Scalability: While tested on various scales, further investigation into the algorithm's performance on extremely large-scale problems might be beneficial.
  • Other VNS Structures: Exploring additional or different neighborhood structures within the VNS framework could potentially yield further improvements.

Summary updated

BibTeX
@article{hou2021multi,
  author = {Dengkai Hou and Houming Fan and Xiaoxue Ren},
  title = {{Multi-Depot Joint Distribution Vehicle Routing Problem Considering Energy Consumption with Time-Dependent Networks}},
  journal = {Symmetry},
  year = {2021},
  doi = {10.3390/sym13112082},
}
Figure