Solving a Practical Pickup and Delivery Problem

Hang Xu (), Zhi-Long Chen (), Srinivas Rajagopal () and Sundar Arunapuram ()
Additional contact information
Hang Xu: Manugistics, Inc., 585 East Swedesford Road, Wayne, Pennsylvania 19087
Zhi-Long Chen: Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742-1815
Srinivas Rajagopal: Manugistics, Inc., 585 East Swedesford Road, Wayne, Pennsylvania 19087
Sundar Arunapuram: Manugistics, Inc., 585 East Swedesford Road, Wayne, Pennsylvania 19087

Transportation Science, 2003, vol. 37, issue 3, 347-364

Abstract: 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.

Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.37.3.347.16044 (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:37:y:2003:i:3:p:347-364

Access Statistics for this article

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