Dynamic ng-Path Relaxation for the Delivery Man Problem

Roberto Roberti () and Aristide Mingozzi ()
Additional contact information
Roberto Roberti: Department of Electrical, Electronic and Information Engineering “Guglielmo Marconi” (DEI), University of Bologna, Bologna 40136, Italy
Aristide Mingozzi: Department of Mathematics, University of Bologna, Cesena 47521, Italy

Transportation Science, 2014, vol. 48, issue 3, 413-424

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.

Keywords: column generation; state-space relaxation; traveling salesman problem (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2013.0474 (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:48:y:2014:i:3:p:413-424

Access Statistics for this article

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