An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem. (November 2016)

• Record Type: Journal Article
• Authors: Dayarian, Iman; Crainic, Teodor Gabriel; Gendreau, Michel; Rei, Walter
• Is Part Of: Transportation research. Volume 95(2016)
• Page Start: 95
• Page End: 123
• Publication Date: 2016-11
• Subjects: Multi-period vehicle routing problem with seasonal fluctuations -- Tactical planning -- Seasonal variation -- Adaptive large neighborhood search; Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2016.09.004
• Languages: English
• ISSNs: 1366-5545

Abstract

Highlights: We design an ALNS based metaheuristic for the MPVRPSF. Our ALNS includes a set of novel algorithmic features and new operators. We compute a series of lower/upper bounds to evaluate the quality of the solution. We analyze the method in terms of computational time and solution quality. We study the contribution of different algorithmic components of our approach. Abstract: This problem involves optimizing product collection and redistribution from production locations to a set of processing plants over a planning horizon. This horizon consists of several days, and the collection-redistribution is performed on a repeating daily basis. A single routing plan must be prepared for the whole horizon, taking into account the seasonal variations in the supply. We model the problem using a sequence of periods, each corresponding to a season. We propose an adaptive large-neighborhood search with several specifically designed operators and features. The results show the excellent performance of the algorithm in terms of solution quality and computational efficiency.