大规模同时集散货物路线问题的新禁忌搜索算法设计  

New Tabu Search Algorithm for Large-Scale Vehicle Routing Problem with Simultaneous Deliveries and Pickups

作　　者：李建[1] 鲁植雄[1] 高谋荣[2] 

机构地区：[1]南京农业大学工学院,江苏南京210031 [2]深圳职业技术学院汽车与交通学院,广东深圳518055

出　　处：《西南交通大学学报》2009年第5期787-793,共7页Journal of Southwest Jiaotong University

基　　金：国家自然科学基金资助项目(70772059);江苏省农机局基金资助项目(GXZ08002)

摘　　要：提出了一种新的禁忌搜索算法.该方法集成大量的邻域搜索方法,采用基于线路集合的分解策略,以及重起和扰动策略,将当前解分解成几个独立的路线子集合,用禁忌搜索法求解每个路线子集合,再将求得的子集合最好路线组成新的当前解.与记录更新法和传统禁忌搜索算法的最好目标值相比,在14组测试数据中,取得8个新的最好目标值,其余的误差值不超过2.41%,且有2组数据的车辆数减少了1辆.A new tabu search algorithm that integrates many neighborhood search methods, and adopts route set-based decomposition, restart and perturbation strategies, was proposed. The current solution is divided into several subsets of routes, each of which is solved by the tabu search algorithm and the best solutions of the subsets are then merged to form a new current solution. Computational results show that compared with record-to-record travel and traditional tabu search algorithm, the new tabu search algorithm can improve on 8 out of 14 of the best known solutions and reduce the number of vehicles by one in 2 cases, with error less than 2.41% for the others.

关 键 词：车辆路线问题 多邻域搜索 禁忌搜索 重起 扰动 

分 类 号：U492.22[交通运输工程—交通运输规划与管理]