The ng-path relaxation was introduced by Baldacci, Mingozzi, and Roberti [Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283] for computing tight lower bounds to vehicle routing problems by solving a relaxation of the set-partitioning formulation, where routes are not necessarily elementary and can contain predefined subtours. The strength of the achieved lower bounds depends on the subtours that routes can perform. In this paper, we introduce a new general bounding procedure called dynamic ng-path relaxation that enhances the one of Baldacci, Mingozzi, and Roberti (2011) by iteratively redefining the subtours that routes can perform. We apply the bounding procedure on the well-known delivery man problem, which is a generalization of the traveling salesman problem where costs for traversing arcs depend on their positions along the tour. The proposed bounding procedure is based on column generation and computes a sequence of nondecreasing lower bounds to the problem. The final lower bound is used to solve the problem to optimality with a simple dynamic programming recursion. An extensive computational analysis on benchmark instances from the TSPLIB shows that the new bounding procedure yields better lower bounds than those provided by the method of Baldacci, Mingozzi, and Roberti (2011). Furthermore, the proposed exact method outperforms other exact methods recently presented in the literature and is able to close five open instances with up to 150 vertices.

Dynamic ng-Path Relaxation for the Delivery Man Problem

MINGOZZI, ARISTIDE
2014

Abstract

The ng-path relaxation was introduced by Baldacci, Mingozzi, and Roberti [Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283] for computing tight lower bounds to vehicle routing problems by solving a relaxation of the set-partitioning formulation, where routes are not necessarily elementary and can contain predefined subtours. The strength of the achieved lower bounds depends on the subtours that routes can perform. In this paper, we introduce a new general bounding procedure called dynamic ng-path relaxation that enhances the one of Baldacci, Mingozzi, and Roberti (2011) by iteratively redefining the subtours that routes can perform. We apply the bounding procedure on the well-known delivery man problem, which is a generalization of the traveling salesman problem where costs for traversing arcs depend on their positions along the tour. The proposed bounding procedure is based on column generation and computes a sequence of nondecreasing lower bounds to the problem. The final lower bound is used to solve the problem to optimality with a simple dynamic programming recursion. An extensive computational analysis on benchmark instances from the TSPLIB shows that the new bounding procedure yields better lower bounds than those provided by the method of Baldacci, Mingozzi, and Roberti (2011). Furthermore, the proposed exact method outperforms other exact methods recently presented in the literature and is able to close five open instances with up to 150 vertices.
2014
Roberto Roberti;Aristide Mingozzi
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/261516
 Attenzione

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

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