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:
  • 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


  • English

Media Info

Subject/Index Terms

Filing Info

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