A New Two-phase Hybrid Metaheuristic for Vehicle Routing Problem with Time Windows

This paper proposes a new two-phase hybrid metaheuristic for vehicle routing problems with time windows (VRPTW). The first phase is to minimize the number of routes by means of variable neighborhood search algorithm, while the second phase is mainly aimed at minimizing the total travel distance using tabu search algorithm. Three neighborhood search operators (All-exchange, All-2-opt, All-) and two local search operators (All-relocate and ejection chain) are designed. To further lower the number of vehicles, the sum-of-squares route size is maximized in the first phase. A comparative test is implemented by our algorithm on the basis of 56 benchmark problems proposed by Solomon (1987), the mean number of vehicles and running time of this algorithm is very competitive compared to previous metaheuristics, showing that the new two-phase hybrid metaheuristic is effective and fast.

• Record URL:
  • https://doi.org/10.11175/easts.10.880
• Summary URL:
  • http://scholar.google.com/scholar_lookup?title=A+New+Two-phase+Hybrid+Metaheuristic+for+Vehicle+Routing+Problem+with+Time+Windows&author=M.+QI&author=Y.+ZHANG&author=J.+ZHANG&author=L.+MIAO&publication_year=2013
• Authors:
  • QI, Mingyao
  • ZHANG, Ying
  • ZHANG, Jinjin
  • MIAO, Lixin
• Publication Date: 2013

Language

• English
• Japanese

Media Info

• Media Type: Digital/other
• Features: Appendices; Figures; References; Tables;
• Pagination: pp 880-896
• Serial:
  • Journal of the Eastern Asia Society for Transportation Studies
  • Volume: 10
  • Issue Number: 0
  • Publisher: Eastern Asia Society for Transportation Studies
  • EISSN: 1881-1124
  • Serial URL: https://www.jstage.jst.go.jp/browse/easts/-char/en
• Publication flags:

  Open Access (libre)

Subject/Index Terms

• TRT Terms: Algorithms; Heuristic methods; Minimization; Routing; Tabu search; Time windows; Trip length; Vehicles
• Subject Areas: Freight Transportation; Highways; Operations and Traffic Management; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01517421
• Record Type: Publication
• Source Agency: Japan Science and Technology Agency (JST)
• Files: TRIS, JSTAGE
• Created Date: Mar 7 2014 8:24AM