Name
Abstract | ||
|---|---|---|
In the pickup and delivery problem with time windows vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and delivery location, under capacity, time window, and precedence constraints. This paper introduces a new branch-and-cut-and-price algorithm in which lower bounds are computed by solving through column generation the linear programming relaxation of a set partitioning formulation. Two pricing subproblems are considered in the column generation algorithm: an elementary and nonelementary shortest path problem. Valid inequalities are added dynamically to strengthen the relaxations. Some of the previously proposed inequalities for the pickup and delivery problem with time windows are also shown to be implied by the set partitioning formulation. Computational experiments indicate that the proposed algorithm outperforms a recent branch-and-cut algorithm. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1287/trsc.1090.0272 | Transportation Science |
Keywords | Field | DocType |
pickup and delivery,new branch-and-cut-and-price algorithm,time windows,proposed algorithm,valid inequalities.,delivery problem,column generation,column generation algorithm,time window,partitioning formulation,delivery location,branch-and-cut,branch-and-price,recent branch-and-cut algorithm,nonelementary shortest path problem,design,branch and cut,computer experiment,satisfiability,branch and price,linear programming relaxation,lower bound,vehicle routing,shortest path problem | Mathematical optimization,Column generation,Delivery location,Shortest path problem,Branch and price,Branch and cut,Algorithm,Linear programming relaxation,Pickup,Operations management,Mathematics | Journal |
Volume | Issue | ISSN |
43 | 3 | 0041-1655 |
Citations | PageRank | References |
99 | 3.18 | 29 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefan Ropke | 1 | 1347 | 55.90 |
| Jean-François Cordeau | 2 | 2604 | 127.77 |