A hybrid genetic search and dynamic programming-based split algorithm for the multi-trip time-dependent vehicle routing problem

Jingyi Zhao, Mark Poon, Vincent Y.F. Tan and Zhenzhen Zhang

European Journal of Operational Research, 2024, vol. 317, issue 3, 921-935

Abstract: 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 MT-TD-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 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724002923
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:317:y:2024:i:3:p:921-935

DOI: 10.1016/j.ejor.2024.04.011

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().