State-Space Relaxation (SSR) is an approach often used to compute by dynamic programming (DP) effective bounds for many combinatorial optimization problems. Currently, the most effective exact approaches for solving many Vehicle Routing Problems (VRPs) are DP algorithms making use of SSR for computing their bounding components. In particular, most of these make use of the q-route and ng-route relaxations. The bounding procedures based on these relaxations provide good quality bounds but they are often time consuming to compute, even for moderate size instances. In this paper we investigate the use of GPU computing for solving q-route and ng-route relaxations. The results prove that the proposed GPU implementations are able to achieve remarkable computing time reductions, up to 40 times with respect to the sequential versions.

Route relaxations on GPU for vehicle routing problems

BOSCHETTI, MARCO ANTONIO;MANIEZZO, VITTORIO;STRAPPAVECCIA, FRANCESCO
2017

Abstract

State-Space Relaxation (SSR) is an approach often used to compute by dynamic programming (DP) effective bounds for many combinatorial optimization problems. Currently, the most effective exact approaches for solving many Vehicle Routing Problems (VRPs) are DP algorithms making use of SSR for computing their bounding components. In particular, most of these make use of the q-route and ng-route relaxations. The bounding procedures based on these relaxations provide good quality bounds but they are often time consuming to compute, even for moderate size instances. In this paper we investigate the use of GPU computing for solving q-route and ng-route relaxations. The results prove that the proposed GPU implementations are able to achieve remarkable computing time reductions, up to 40 times with respect to the sequential versions.
2017
Boschetti, Marco Antonio; Maniezzo, Vittorio; Strappaveccia, Francesco
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/583903
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact