A New Two-Stage Heuristic For Vehicle Routing Problem with Time Windows
The vehicle routing problem with time windows is a famous combinatorial optimization problem. The m-VRPTW is a variant of the VRPTW in which only a limited number of vehicles are available, whose feasible solution may include some un-served customers due to the limited vehicles. The primary objective of m-VRPTW is to maximize the number of customers served, while the second is to minimize the total travel distance. We present a new two-stage heuristic to solve m-VRPTW, we firstly introduced adaptive k-means to create initial solutions, with an Ejection Pool (EP) to hold temporarily un-served customers and an Adaptive Memory to keep good solutions. Whats more, we proposed a new operator called Transfer to improve our initial solutions.Then, we minimized the total distance using an improved AMP algorithm(IAMP). The experimental results show consistently good performance of our algorithm when compared with other methods.
m-VRPTW k-means ejection pool adaptive memory
Weimin Liu Zhifeng Hao Ming Chen
School of Mathematical Science, South China University of Technology, Guangzhou, 510641, China School of Mathematical Science, South China University of Technology, Guangzhou, 510641, China;Natio Nation Mobile Communications Research Laboratory, Southeast University, Nanjing,210096,China
国际会议
杭州
英文
898-903
2006-10-12（万方平台首次上网日期，不代表论文的发表时间）