An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows

Olli Bräysy (), Wout Dullaert (), Geir Hasle (), David Mester () and Michel Gendreau ()
Additional contact information
Olli Bräysy: Agora Innoroad Laboratory, Agora Center, FI-40014 University of Jyväskylä, Jyväskylä, Finland
Wout Dullaert: Institute of Transport and Maritime Management Antwerp, University of Antwerp, and Antwerp Maritime Academy, B-2000 Antwerp, Belgium
Geir Hasle: SINTEF ICT, Department of Applied Mathematics, NO-0314 Oslo, Norway
David Mester: Institute of Evolution, Mathematical and Population Genetics Laboratory, University of Haifa, 31905 Haifa, Israel
Michel Gendreau: Département d'informatique et de recherche opérationnelle and Centre de recherche sur les transports, Université de Montréal, Montréal, Québec H3C 3J7, Canada

Transportation Science, 2008, vol. 42, issue 3, 371-386

Abstract: This paper presents a new deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows. The objective is to service, at minimal total cost, a set of customers within their time windows by a heterogeneous capacitated vehicle fleet. First, we motivate and define the problem. We then give a mathematical formulation of the most studied variant in the literature in the form of a mixed-integer linear program. We also suggest an industrially relevant, alternative definition that leads to a linear mixed-integer formulation. The suggested metaheuristic solution method solves both problem variants and comprises three phases. In Phase 1, high-quality initial solutions are generated by means of a savings-based heuristic that combines diversification strategies with learning mechanisms. In Phase 2, an attempt is made to reduce the number of routes in the initial solution with a new local search procedure. In Phase 3, the solution from Phase 2 is further improved by a set of four local search operators that are embedded in a deterministic annealing framework to guide the improvement process. Some new implementation strategies are also suggested for efficient time window feasibility checks. Extensive computational experiments on the 168 benchmark instances have shown that the suggested method outperforms the previously published results and found 167 best-known solutions. Experimental results are also given for the new problem variant.

Keywords: vehicle routing; time windows; heterogeneous fleet; fleet dimensioning; neighborhood search (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1070.0217 (application/pdf)

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:inm:ortrsc:v:42:y:2008:i:3:p:371-386

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().