A column generation approach to the heterogeneous fleet vehicle routing problem

A column generation approach to the heterogeneous fleet vehicle routing problem

0.00 Avg rating0 Votes
Article ID: iaor20082528
Country: United Kingdom
Volume: 34
Issue: 7
Start Page Number: 2080
End Page Number: 2095
Publication Date: Jul 2007
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: integer, programming: dynamic
Abstract:

We consider a vehicle routing problem with a heterogeneous fleet of vehicles having various capacities, fixed costs and variable costs. An approach based on column generation (CG) is applied for its solution, hitherto successful only in the vehicle routing problem with time windows. A tight integer programming model is presented, the linear programming relaxation of which is solved by the CG technique. A couple of dynamic programming schemes developed for the classical vehicle routing problem are emulated with some modifications to efficiently generate feasible columns. With the tight lower bounds thereby obtained, the branch-and-bound procedure is activated to obtain an integer solution. Computational experience with the benchmark test instances confirms that our approach outperforms all the existing algorithms both in terms of the quality of solutions generated and the solution time.

Reviews

Required fields are marked *. Your email address will not be published.