This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Xu, H. Articles by Arunapuram, S. Search for Related Content

Solving a Practical Pickup and Delivery Problem

Manugistics, Inc., 585 East Swedesford Road, Wayne, Pennsylvania 19087
Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742-1815
Manugistics, Inc., 585 East Swedesford Road, Wayne, Pennsylvania 19087
Manugistics, Inc., 585 East Swedesford Road, Wayne, Pennsylvania 19087
hhxu{at}manu.com
zchen{at}rhsmith.umd.edu
srajagop{at}manu.com
sarunapu{at}manu.com

We consider a pickup and delivery vehicle routing problem commonly encountered in real-world logistics operations. The problem involves a set of practical complications that have received little attention in the vehicle routing literature. In this problem, there are multiple carriers and multiple vehicle types available to cover a set of pickup and delivery orders, each of which has multiple pickup time windows and multiple delivery time windows. Orders and carrier/vehicle types must satisfy a set of compatibility constraints that specify which orders cannot be covered by which carrier/vehicle types and which orders cannot be shipped together. Order loading and unloading sequence must satisfy the nested precedence constraint that requires that an order cannot be unloaded until all the orders loaded into the truck later than this order are unloaded. Each vehicle trip must satisfy the driver's work rules prescribed by the Department of Transportation which specify legal working hours of a driver. The cost of a trip is determined by several factors including a fixed charge, total mileage, total waiting time, and total layover time of the driver. We propose column generation based solution approaches to this complex problem. The problem is formulated as a set partitioning type formulation containing an exponential number of columns. We apply the standard column generation procedure to solve the linear relaxation of this set partitioning type formulation in which the resulting master problem is a linear program and solved very efficiently by an LP solver, while the resulting subproblems are computationally intractable and solved by fast heuristics. An integer solution is obtained by using an IP solver to solve a restricted version of the original set partitioning type formulation that only contains the columns generated in solving the linear relaxation. The approaches are evaluated based on lower bounds obtained by solving the linear relaxation to optimality by using an exact dynamic programming algorithm to solve the subproblems exactly. It is shown that the approaches are capable of generating near-optimal solutions quickly for randomly generated instances with up to 200 orders. For larger randomly generated instances with up to 500 orders, it is shown that computational times required by these approaches are acceptable.

History: Received: January 2001; revised: March 2002; accepted: April 2002.

This article has been cited by other articles:

				M. Iori, J.-J. Salazar-Gonzalez, and D. Vigo An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints Transportation Science, May 1, 2007; 41(2): 253 - 264. [Abstract] [PDF]

				F. Carrabs, J.-F. Cordeau, and G. Laporte Variable Neighborhood Search for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading INFORMS Journal on Computing, January 1, 2007; 19(4): 618 - 632. [Abstract] [PDF]

				S. Ropke and D. Pisinger An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows Transportation Science, November 1, 2006; 40(4): 455 - 472. [Abstract] [PDF]

				M. Gendreau, M. Iori, G. Laporte, and S. Martello A Tabu Search Algorithm for a Routing and Container Loading Problem Transportation Science, August 1, 2006; 40(3): 342 - 350. [Abstract] [PDF]