Designing granular solution methods for routing problems with time windows

Michael Schneider, Fabian Schwahn and Daniele Vigo

European Journal of Operational Research, 2017, vol. 263, issue 2, 493-509

Abstract: The use of granular neighborhoods is one way to improve the run-time of local-search-based metaheuristics for combinatorial optimization problems without compromising solution quality. So-called sparsification methods are applied to restrict the neighborhoods to include only elements which are likely to be part of high-quality solutions. The goal of this work is to provide insights about the design of effective and efficient granular solution methods for routing problems with time windows. In extensive numerical experiments with a granular tabu search (GTS) for the vehicle-routing problem with time windows (VRPTW), we find that sparsification methods using reduced-cost values based on the solution of a linear relaxation of the original problem outperform standard sparsification methods. Furthermore, including additional depot arcs into the restricted arc set (beyond those selected by the sparsification method) improves solution quality. The same is true for dynamically inserting into the restricted arc set (i) the arcs involved in the best move selected in each iteration, and (ii) the arcs of the current best-known solution. Moreover, for small restricted arc sets, guaranteeing a minimum number of incoming and outgoing arcs per vertex is beneficial. Finally, dynamically altering the size of the restricted arc set can be used to successfully diversify and intensify the search, which has a significant positive effect on solution quality. The usefulness of the gained insights about the design of granular solution methods is demonstrated by the performance of the final configuration of our GTS for VRPTW, which obtains state-of-the-art results and reaches an outstanding computational efficiency.

Keywords: Metaheuristics; Granular neighborhoods; Vehicle routing; Time windows; Local search (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171730406X
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:263:y:2017:i:2:p:493-509

DOI: 10.1016/j.ejor.2017.04.059

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