Journal article
Dynamic ng-Path Relaxation for the Delivery Man Problem
Department of Electrical, Electronic and Information Engineering “Guglielmo Marconi” (DEI), University of Bologna, Bologna 40136, Italy1
Department of Mathematics, University of Bologna, Cesena 47521, Italy2
The ng-path relaxation was introduced by Baldacci, Mingozzi, and Roberti [Baldacci R, Mingozzi A, Roberti (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 sub tours.
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, 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 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.
Language: | English |
---|---|
Publisher: | Transportation Science & Logistic Society of the Institute for Operations Research and Management Sciences |
Year: | 2014 |
Pages: | 413-424 |
ISSN: | 15265447 and 00411655 |
Types: | Journal article |
DOI: | 10.1287/trsc.2013.0474 |