Title: A unified framework for routing problems with a fixed fleet size

Authors: Stefanie Kritzinger; Fabien Tricoire; Karl F. Doerner; Richard F. Hartl; Thomas Stützle

Addresses: Unit Logistics Informatics, RISC Software GmbH, Hagenberg, Austria ' Department of Business Administration, University of Vienna, Vienna, Austria ' Department of Business Administration, University of Vienna, Vienna, Austria ' Department of Business Administration, University of Vienna, Vienna, Austria ' IRIDIA, Université Libre de Bruxelles, Brussels, Belgium

Abstract: Vehicle routing problems constitute the core of many operations research efforts. Early studies introduced tailor-made solutions for each variant of a vehicle routing problem, but unified frameworks have emerged more recently. These approaches typically generalise across many vehicle routing problems and implement a method for tackling the generalised problem. In line with this, this research proposes a generic method for solving several fixed fleet vehicle routing problems - capacitated vehicle routing, open vehicle routing, vehicle routing with soft and hard time windows, open vehicle routing with soft and hard time windows, and time-dependent vehicle routing with soft and hard time windows - by transforming them into a time-dependent vehicle routing problem with soft time windows, solved by a variable neighbourhood search using a unique parameter setting, regardless of the original problem. Computational tests using standard benchmark instances from prior literature show that genericity does not come at the expense of solution quality. Moreover, the algorithm yields competitive results and some new best known solutions are obtained for the vehicle routing problem with soft time windows, the open vehicle routing problem with hard time windows, and time-dependent vehicle routing problem with hard time windows.

Keywords: metaheuristic framework; multiple attributes; variable neighbourhood search; vehicle routing problem.

DOI: 10.1504/IJMHEUR.2017.085124

International Journal of Metaheuristics, 2017 Vol.6 No.3, pp.160 - 209

Received: 12 Feb 2016
Accepted: 10 Oct 2016
Published online: 12 Jul 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article