A hybrid algorithm for vehicle routing problem with time windows

作者：Yu, B.; Yang, Z. Z.^*; Yao, B. Z.

来源：Expert Systems with Applications, 2011, 38(1): 435-441.

DOI：10.1016/j.eswa.2010.06.082

• VRPTW
• Ant colony optimization
• Neighborhood search
• Tabu search

Vehicle routing problem with time windows (VRPTVV) is a well-known combinatorial problem. Many researches have presented meta-heuristics are effective approaches for VRPTW. This paper proposes a hybrid approach, which consists of ant colony optimization (ACO) and Tabu search, to solve the problem. To improve the performance of ACO, a neighborhood search is introduced. Furthermore, when ACO is close to the convergence Tabu search is used to maintain the diversity of ACO and explore new solutions. Computational experiments are reported for a set of the Solomon's 56 VRPTW and the approach is compared with some meta-heuristic published in literature. Results show that considering the tradeoff of quality and computation time, the hybrid algorithm is a competitive approach for VRPTVV.

• 出版日期2011-1
• 单位大连海事大学; 北京交通大学