Loading...
Please wait, while we are loading the content...
Similar Documents
New refinements for the solution of vehicle routing problems with branch and price (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Feillet, Dominique Gendreau, Michel Rousseau, Louis-Martin |
| Abstract | Column generation is a well-known mathematical programming technique based on two compo-nents: a master problem, which selects optimal columns (variables) in a restricted pool of columns, and a subproblem that feeds this pool with potentially good columns until an optimality criterion is met. Embedded in Branch and Price algorithms, this solution approach proved to be very efficient in the context of numerous vehicle routing problems, where columns represent feasible vehicle routes. The subproblem is then usually expressed as a shortest path problem with resource constraints, which can be solved using dynamic programming methods that are generally very effective in practice. In this paper, we propose some new refinements to improve the capabilities of column generation approaches in this context, with a focus on the subproblem phase. For the sake of simplicity, we restrict our study to the case of the Vehicle Routing Problem with Time Windows. We first introduce the notion of Limited Discrepancy Search, which is well known in the field of Constraint Programming, and we show how LDS can be applied to dynamic programming. We also discuss how the state graph of dynamic programming can be manipulated in order to simulate local search during label extension. Finally, we present some lower bounds that allow removing a substantial number of labels during the search. Com-putational results demonstrate the considerable impact of these refinements in terms of computing time. |
| File Format | |
| Language | English |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | New Refinement Optimal Column State Graph Solution Approach Restricted Pool Shortest Path Problem Column Generation Numerous Vehicle Well-known Mathematical Programming Technique Limited Discrepancy Search Label Extension Resource Constraint Substantial Number Local Search Optimality Criterion Vehicle Routing Problem Column Generation Approach Time Window Column Represent Feasible Vehicle Route Dynamic Programming Good Column Master Problem Dynamic Programming Method Subproblem Phase Constraint Programming Com-putational Result Considerable Impact |
| Content Type | Text |
| Resource Type | Technical Report |
