The vehicle routing problem with arrival time diversification on a multigraph

Adria Soriano, Thibaut Vidal, Margaretha Gansterer and Karl Doerner

European Journal of Operational Research, 2020, vol. 286, issue 2, 564-575

Abstract: Efficiency and security are the two major concerns in cash-in-transit transportation planning. Whereas efficiency is generally achieved by finding short routes, security can be improved by generating dissimilar visit patterns. To achieve a good balance between these two objectives, the vehicle routing problem with arrival time diversification (VRPATD) aims to find optimized routing plans, over multiple periods, subject to a minimum difference between visit times at each customer. Since the customer visits are constrained by time windows and no waiting time is allowed en route, the number of feasible solutions is generally limited. To explore a larger set of feasible route options, we propose to consider alternative paths with different distances between visit locations. The resulting multigraph VRPATD better captures the characteristics of urban networks. Moreover, the extra flexibility achieved with the alternative paths helps finding better routing plans while meeting time constraints. To solve this complex problem, we introduce an adaptive large neighborhood search, which exploits piecewise-linear penalty functions for insertion evaluations, efficient local searches, and an adaptive destruction rate. This method produces remarkable results on classical instances for the simple-graph VRPATD. Moreover, our theoretical results and our experiments on real-life instances obtained from an application case in Vienna show that the multigraph problem extension leads to very significant distance savings subject to the same arrival-time diversification constraints.

Keywords: Routing; Optimization; Cash-in-transit; Arrival time diversification (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720302915
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:286:y:2020:i:2:p:564-575

DOI: 10.1016/j.ejor.2020.03.061

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