A column generation approach to the heterogeneous fleet vehicle routing problem

Cited 105 time in webofscience Cited 0 time in scopus
  • Hit : 711
  • Download : 14
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. (c) 2005 Elsevier Ltd. All rights reserved.
Publisher
PERGAMON-ELSEVIER SCIENCE LTD
Issue Date
2007-07
Language
English
Article Type
Article
Keywords

BRANCH-AND-PRICE; TIME WINDOWS; SIZE; ALGORITHM

Citation

COMPUTERS & OPERATIONS RESEARCH, v.34, no.7, pp.2080 - 2095

ISSN
0305-0548
DOI
10.1016/j.cor.2005.08.002
URI
http://hdl.handle.net/10203/4248
Appears in Collection
MT-Journal Papers(저널논문)
Files in This Item
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 105 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0