SOLVING A PRACTICAL PICKUP AND DELIVERY PROBLEM

This paper considers a complex pickup and delivery vehicle routing problem in which there are multiple carriers and multiple vehicle types available to cover a set of pickup and delivery orders, each of which has multiple pickup and delivery time windows. Orders and carrier/vehicle types must satisfy a set of compatibility constraints. Order loading and unloading sequence must satisfy a nested precedence constraint. Each vehicle trip also must satisfy Department of Transportation working hour rules for drivers. Column generation-based solution approaches are proposed to solve this problem. The problem is formulated as a set partitioning type formulation containing an exponential number of columns. The authors apply the standard column generation procedure to solve the linear relaxation of this set portioning type formulation in which the resulting master problem is a linear program (LP), and solved very efficiently by a LP solver, while the resulting subproblems are computationally intractable and solved by fast heuristics. An integer solution is obtained by using an integer program solver to solve a restricted version of the original set partitioning type formulation that 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. Results from randomly generated test problems demonstrate that the approaches developed here are capable of generating near-optimal solutions quickly for problems with up to 210 orders and can handle problems with up to 500 orders within acceptable computational time.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Corporate Authors:

  Institute for Operations Research and the Management Sciences (INFORMS)

  901 Elkridge Landing Road, Suite 400
  Linthicum, MD  United States  21090-2909
• Authors:
  • Xu, Hongli
  • Chen, Z-L
  • Rajagopal, S
  • Arunapuram, S
• Publication Date: 2003-8

Language

• English

Media Info

• Features: Figures; References; Tables;
• Pagination: p. 347-364
• Serial:
  • Transportation Science
  • Volume: 37
  • Issue Number: 3
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Constraints; Delivery vehicles; Dynamic programming; Heuristic methods; Integer programming; Linear programming; Pickup and delivery service; Routing; Sets; Time windows; Work rules
• Uncontrolled Terms: Column generation
• Subject Areas: Highways; Planning and Forecasting; Society; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 00961812
• Record Type: Publication
• Files: TRIS
• Created Date: Aug 11 2003 12:00AM