Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

92 Scopus Citations
View graph of relations

Author(s)

  • Stephen C.H. Leung
  • Xiyue Zhou
  • Defu Zhang
  • Jiemin Zheng

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)205-215
Journal / PublicationComputers and Operations Research
Volume38
Issue number1
Publication statusPublished - Jan 2011

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.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review