Intelligent Iterated Local Search Methods for Solving Vehicle Routing Problem with Different Fleets  

作　　者：李妍峰 李军 赵达 

机构地区：[1]School of Economics and Management, Southwest Jiaotong University [2]Caotang School, Sichuan Normal University, Chengdu 610072, China

出　　处：《Journal of Southwest Jiaotong University(English Edition)》2007年第4期344-352,共9页西南交通大学学报（英文版）

基　　金：The National Natural Science Founda-tion of China ( No.70471039);the National Social Science Foundation of China (No.07BJY038);the Program for New Century Excellent Talents in University (No.NCET-04-0886)

摘　　要：To solve vehicle routing problem with different fleets, two methodologies are developed. The first methodology adopts twophase strategy. In the first phase, the improved savings method is used to assign customers to appropriate vehicles. In the second phase, the iterated dynasearch algorithm is adopted to route each selected vehicle with the assigned customers. The iterated dynasearch algorithm combines dynasearch algorithm with iterated local search algorithm based on random kicks. The second methodplogy adopts the idea of cyclic transfer which is performed by using dynamic programming algorithm, and the iterated dynasearch algorithm is also embedded in it. The test results show that both methodologies generate better solutions than the traditional method, and the second methodology is superior to the first one.To solve vehicle routing problem with different fleets, two methodologies are developed. The first methodology adopts twophase strategy. In the first phase, the improved savings method is used to assign customers to appropriate vehicles. In the second phase, the iterated dynasearch algorithm is adopted to route each selected vehicle with the assigned customers. The iterated dynasearch algorithm combines dynasearch algorithm with iterated local search algorithm based on random kicks. The second methodplogy adopts the idea of cyclic transfer which is performed by using dynamic programming algorithm, and the iterated dynasearch algorithm is also embedded in it. The test results show that both methodologies generate better solutions than the traditional method, and the second methodology is superior to the first one.

关 键 词：Vehicle routing problem Savings method Iterated dynasearch algorithm Dynamic programming Iterated local search Random kick Cyclic transfer 

分 类 号：U116.2[交通运输工程]