An accelerated benders decomposition algorithm for the solution of the multi-trip time-dependent vehicle routing problem with time windows

Antonios Fragkogios, Yuzhuo Qiu, Georgios K.D. Saharidis and Panos M. Pardalos

European Journal of Operational Research, 2024, vol. 317, issue 2, 500-514

Abstract: The logistics companies executing the last mile delivery of goods in urban areas deal every day with the problem of routing their vehicles, while taking into account multiple trips per vehicle, time-dependent travel time, customers’ time windows and loading time at the depot simultaneously. This paper addresses this problem, known as Multi-Trip Time-Dependent Vehicle Routing Problem with Time Windows, aiming at its exact solution, minimizing the total travelled distance of a company's fleet. Based on a literature model, a new reformulation with reduced size is suggested. This reformulation is decomposed by applying the Benders method in an effective way, resulting in a subproblem with no duality gap. By exploiting the special features of the problem and the particular structure of the decomposition made, several novel valid inequalities are introduced, in order to both tighten the non-decomposed formulations and warm start the relaxed master problem to achieve less infeasible solutions and higher lower bounds. For the solution of the problem, an innovative algorithm is proposed, including suboptimal master solutions and a multi-cut generation procedure, which is based on the careful observation of the values of the Benders dual subproblem variables. The impact of the valid inequalities as well as two variants of the suggested algorithm are tested on benchmark data and they are compared with the non-decomposed models and a heuristic introduced in the literature. The computational results indicate improved efficiency and stronger bounds for the proposed algorithm.

Keywords: Integer programming; Benders decomposition; Vehicle routing problem; Multi-Trip; Time-Dependent (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/S0377221724002947
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:2:p:500-514

DOI: 10.1016/j.ejor.2024.04.013

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 ().