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.

Schneider, M., Schwahn, F., Vigo, D. (2017). Designing granular solution methods for routing problems with time windows. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 263(2), 493-509 [10.1016/j.ejor.2017.04.059].

Designing granular solution methods for routing problems with time windows

Vigo, Daniele
2017

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.
2017
Schneider, M., Schwahn, F., Vigo, D. (2017). Designing granular solution methods for routing problems with time windows. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 263(2), 493-509 [10.1016/j.ejor.2017.04.059].
Schneider, Michael; Schwahn, Fabian; Vigo, Daniele*
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/622015
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 23
social impact