带服务优先级车辆路径问题的扫描禁忌搜索算法  

Sweep-Taboo Search Algorithm for Vehicle Routing Problem with Precedence Constraints

作　　者：黎金玲[1,2] 陈燕[3] 王德运[1] 郭海湘[1] 杨娟[1] 

机构地区：[1]中国地质大学(武汉)经济管理学院,湖北武汉430074 [2]中国地质大学江城学院,湖北武汉430200 [3]中国地质大学远程与继续教育学院,湖北武汉430074

出　　处：《数学的实践与认识》2014年第9期169-180,共12页Mathematics in Practice and Theory

基　　金：国家自然科学基金(71103163;71103164;71301153);教育部新世纪优秀人才支持计划(NCET13-1012);教育部人文社会科学研究青年基金(10YJC790071);中央高校基本科研业务费专项资金资助(CUG110411;CUG120111;G2012002A;CUG140604)

摘　　要：提出了一种带服务优先级车辆路径问题的模型(Vehicle Routing Problem with Precedence Constraints,VRPPC),和一种扫描—禁忌搜索算法(sweep-Taboo Search Algorithm,S-TSA).然后,运用S-TSA对郑煤物资供销有限公司的带有服务优先级的危险物资配送进行优化求解,并与扫描遗传算法(sweep-Genetic Algorithm,SGA),禁忌搜索算法(Taboo Search Algorithm,TSA),人工鱼群算法(Artificial Fish Algorithm,AFA)进行比较研究,研究结果显示:扫描禁忌搜索算法能在满足服务优先级的前提下,使配送费用最少.This paper presents a model for Vehicle Routing Problem with Precedence Con- straints and a Sweep-Taboo Search Algorithm（S-TSA） which can effectively solve the VRPPC problem. Secondly, the paper applies S-TSA to solve the distribution of dangerous materials of Zhengzhou Coal Electricity Group Company. It also compares S-TSA with Sweep-Genetic Algorithm （S-GA）, Taboo Search Algorithm （TSA） and Artificial Fish algorithms （AFA）. The results show that under the precondition of satisfied precedence constraints, S-TSA can get the least cost in overall distribution fees.

关 键 词：车辆路径问题 服务优先级 扫描法 禁忌搜索算法 

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