Dynamic ng-Path Relaxation for the Delivery Man Problem

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.