Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 205-215 |
Journal / Publication | Computers and Operations Research |
Volume | 38 |
Issue number | 1 |
Publication status | Published - Jan 2011 |
Link(s)
Abstract
In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances. © 2010 Elsevier Ltd. All rights reserved.
Research Area(s)
- Extend guided local search, Tabu search, Two-dimensional packing, Vehicle routing
Citation Format(s)
Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem. / Leung, Stephen C.H.; Zhou, Xiyue; Zhang, Defu et al.
In: Computers and Operations Research, Vol. 38, No. 1, 01.2011, p. 205-215.
In: Computers and Operations Research, Vol. 38, No. 1, 01.2011, p. 205-215.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review