.png){kind=icon}
.png){kind=icon}
Return
A hybrid genetic search and dynamic programming-based split algorithm for the multi-trip time-dependent vehicle routing problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2024.04.011.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We design a hybrid algorithm for the multi -trip time -dependent vehicle routing problem (MT-TD-VRP). One of its components is the Time -Dependent SPlit Algorithm (TD -SPA), which is a dynamic programming -based algorithm specifically designed to handle both the multi -trip per vehicle and the time -dependent aspects of the problem. The hybrid algorithm combines the proposed TD -SPA, designed to efficiently split a giant tour into complete vehicle routes, with a genetic algorithm for generating these tours. We introduce a monotone queue optimization (MQO) technique to accelerate the TD -SPA. The effectiveness of MQO is evaluated by comparing computation times between the original split algorithm for the capacitated vehicle routing problem (CVRP) and its MQO-enhanced counterpart. Extensive numerical experiments with a real -world dataset from a Singapore food and beverage company are conducted to assess our algorithm's performance on various MTTD-VRP instances. The results indicate that our algorithm surpasses the performance of the commercial solver Gurobi, with an average improvement of 25.13% on the best solutions found within a prescribed duration. Our numerical simulations further reveal the algorithm's ability to efficiently solve both the capacitated vehicle routing problem (CVRP) and the multi -trip vehicle routing problem (MTVRP), consistently producing competitive solutions. Moreover, to highlight the importance of incorporating the time -dependent (TD) factor into our model and algorithm, we demonstrate a notable enhancement in performance-averaging at 7.47% for the best solutions under TD conditions for an MTVRP dataset.
Keywords:
Routing
Time-dependent travel time
Multi-trip
Split algorithm
Monotone queue optimization
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
View more organizations