带软时间窗的集配货一体化VRP改进模拟退火算法优化研究.docx

第29卷第5期系统工程理论与实践、厂01．29．NO．52009年5月Systems Engineering—TheoryPracticeMay,2009文章编号：1000—6788(2009)05-0186—07带软时间窗的集配货一体化VRP改进模拟退火算法优化研究邓爱民，毛超，周彦霆(湖南大学工商管理学院交通运输与物流研究所，长沙410082)摘要建立了考虑软时间要求、配送车辆出行固定成本以及车辆出发满载系数等因素，更加符合 实际的集配货一体化车辆路径问题数学模型．求解时对传统的模拟退火算法进行了改进，结合线路 内交换和线路间交换产生新解，增加了记忆功能，采用了双终止准则．对一定规模的算例验算表明， 该算法求解更优，稳定性更好，计算效率也更高．关键词集配货车辆路径问题；优化模型；软时间窗；改进模拟退火算法；记忆功能 中图分类号Ul 16；TP301文献标志码AOptimizing research of an improved simulated annealing algorithm to softtime windows vehicle routing problem with pick—up and deliveryDENG Ai—min，MAO Chao，ZHOU Yan-ting(School of Business Administration，Institute of Transportation and Logistics，Hunan University,Changsha 410082，China)Abstract This paper establishes a more practical mathematical model of vehicle routing problem with pick—up and delivery,which considers the soft time request．vehicle fixed cost of vehicle and vehicle full-load coefficient．To solve the model，the paper improves the traditional simulation annealing algorithm，uni移ing the exchange in the lines and between the lines produces the new solution，through increasing the memoryfunction，using the double termination criterion．W色test the new algorithm through a certain scale example，the experimental results show that the new algorithm Can obtain better solution，better stabifity,and highcalculation efficiency．Keywords vehicle routing problem pick-up and delivery；optimal model；soft time windows improved simulated annealing algorithm；memory function1引言车辆路径问题(Vehicle routing problem，VRP)的研究大都是假设某个客户需求点存在单纯的配送业务 (Pure delivery)或者单纯的集货业务(Pure pick．up，即逆向物流)，即使允许配送车辆集货，也是假定在所有 的配送业务完成后再回程进行集货业务【1】．考虑某个客户需求点存在集货业务或者送货业务或者同时存在集货与送货业务(Pick-up and delivery)，允许在客户需求点同时进行集货作业和送货作业，即配送车辆只需 服务客户一次，就可以满足客户需求点的送货和集货需求，我们称之为集配货一体化车辆路径问题(Vehicle routing problem with pick-up and delivery,VRPPD)[21．集配货一体化的车辆路径问题最初可以追溯到20收稿日期：2007-12．27 资助项目：湖南省自然科学基金(02JJY3015)；重庆市市政府重点社科基金(2004ZD03) 作者简介：邓爱民(1964-)，女，湖南益阳人，湖南大学教授．万方数据第5期邓爱民，等：带软时间窗的集配货—体化VRP改进模拟退火算法优化研究 187世纪80年代逆向物流概念的