多约束条件的车辆装卸算法.pdf.pdf

第31卷第11期 2003年11月 同济大学学报 JOURNAL OF丁ONGTI UNIVERSITY Vol. 31 N- N.. 1 2003 多约束条件的车辆装卸算法陈继山,须鼎兴,刘大杰(同济大学恻量与国土信息工程系,上海200092) 摘要:多约束条件的有时间窗装卸货间$$(PDPTW),由于它具有非确定型的多项式算法(NP)特性,“虚拟车辆”,以缩短线路的总时间成本为准,讨论了在复杂约束条件下车辆的多轮次分派问题, -Wright(C-W)节约启发式算法为基础的混合算法,求取近似解,最后根据算法的特征提出了改进程序运行速度的方法关镇词:物流;C-W节约启发式算法;有时间窗装卸货中图分类号:U 111 文献标识码:A 文章编号:0253一374X(2003) 11一1304一05 Algorithm in Vehicle Pickup and Delivery Problem CHEN五-shan, X U Ding-zing, LIU Da币(DePsrtrnent of Surveying and Oaoinfotmaties,Tongji University, Shanghai 200092,Chine) Abstract: It is very difficult to get the precise result of complex pickup and delivery problem with time window problem for the property of hard NP in the logistics management. This paper discusses the multi- dispatching problem under the complex restrictions and design a kind of algorithm based on the C-W saving heuristic algorithm to seek for an approximate result and dispatch more goods by introducing "virtual vehicles". This paper also gives some advice to improve the pgram's performance according to the property of the algorithm Key words: logistics; C-W saving heuristic algorithm; pickup and delivery with time window 订单配送是将订单从物流结点(集货中心)送达到收货人的过程,配送直接影响物流系统的运作效益. 在配送管理中,需要经常决策的一个问题是如何寻找一组费用最小的车辆线路组合,以得到最