Model and Algorithm for Vehicle Routing Problem with Backhauls and Time Windows
-
摘要: 在分析具有回送运输和时间窗的车辆路径问题特点的基础上,建立了该问题的优化数学模型,并通过设置与发货点距离为零的虚拟集货点使问题简化.在此基础上,构造了求解问题的改进遗传算法.在算法中,结合问题的特点设计了确保个体编码有效性的OX交叉算子,并采用基于Metropolis判别准则的复制算子,确保个体多样性和避免算法过早收敛.算例表明算法有效可行.Abstract: The characteristic of vehicle routing problem with backhauls and time windows was analyzed.An optimization model was proposed.The problem was simplified by setting a virtual collecting depot,from which the distance to the consignment depot is zero.To solve the model,an improved genetic algorithm was presented.An OX-crossover operator was designed to keep individual codes valid,and the reproduction operator based on Metropolis criteria was used to guarantee the diversity of individuals and to avoid premature convergence.Experimental computation indicates that the algorithm is valid and feasible.
-
Key words:
- genetic algorithm /
- vehicle routing problem /
- backhaul /
- time window /
- model
-
SAVELSBERGH M,DESROSIER J.Time constrained routing and scheduling problems[J]. Transportation Reserch,1985,22(1):1-11.[2] TANGIAH S,NYGARD K,JUELL P.A genetic algorithm system for vehicle routing with time windows[C] ∥ Proceedings of the Seventh Conference on Intelligence Applications.Miami,1991:322-325.[3] PRINS C.A simple and effective evolutionary algorithm for the vehicle routing problem[J]. Computers Operations Research,2004,31:1 985-2 002.[4] BAKER B,AYECHEW M.A genetic algorithm for the vehicle routing problem[J]. Computers Operations Research,2003,31:1 985-2 002.[5] 宾松,符卓.求解软时间窗的车辆路径问题的改进遗传算法[J]. 系统工程,2003,21(6):12-15.BIN Song,FU Zhuo.An improved genetic algorithm for vehicle routing problem with soft time windows[J]. Systems Engineering,2003,21(6):12-15.[6] 李大卫,王莉,王梦光.遗传算法在有时间窗车辆路径优化问题上的应用[J]. 系统工程理论与实践,1999,8:65-69.LI Dawei,WANG Li,WANG Mengguang.Genetic algorithm for vehicle routing problem with time windows[J]. Systems Engineering Theory Practice,1999,8:65-69.[7] 李军.有时间窗的车辆路径安排问题的启发式算法[J]. 系统工程,1996,5:45-50.LI Jun.A heuristic for vehicle routing with time windows[J]. Systems Engineering,1996,5:45-50.[8] 谢秉磊,李军,郭耀煌.有时间窗的车辆调度问题的遗传算法[J]. 系统工程学报,2000,15(3):290-294.XIE Binglei,LI Jun,GUO Yaohuang.Genetic algorithm for vehicle scheduling problem of non-full loads with time windows[J]. Journal of Systems Engineering,2000,15(3):290-294.[9] 郎茂祥,胡思继.用混合遗传算法物流配送路径优化研究[J]. 中国管理科学,2002,10(5):51-56.LANG Maoxiang,HU Siji.Study on the optimization of physical distribution routing problem by using hybrid genetic algorithm[J]. Chinese Journal Management Science,2002,10(5):51-56.[10] 康立山,谢云等.非数值并行算法(Ⅱ)——遗传算法[M]. 北京:科学出版社,1998:63-75.[11] 卜雷,尹传忠,蒲云.零担货物序贯装箱优化问题的遗传模拟退火算法[J]. 西南交通大学学报,2002,37(5):531-535.BU Lei,YIN Chuanzhong,PU Yun.Genetic and simulated annealing algorithm fo r optimal sequential casing of less-than-carload freights[J]. Journal of Southwest Jiaotong University,2002,37(5):531-535.[12] KOHL N,DESROSIEERS J,MADSEN O,et al.2-path cuts for the vehicle routing problem with time windows[J]. Transportation Science,1999,33(1):101-113[13] THANGIAH S R,POTVIN J Y,SUN T.Heuristic approaches to vehicles routing with backhauls and time windows[J]. Computers Operations Research,1996,23(11):1 043-105 7.[14] HASAMA T,KOKUBUGATA H,KAWASHIMA H.A heuristic approach based on the string model to solve vehicle routing problem with backhauls[C] ∥ The 5th World Congress on Intelligent Transport Systems.Korea,1998:25-32.[15] MINGOZZI A,GIORGI S,BALDACCI R.An exact method for the vehicle routing problem with backhauls[J]. Transportation Science,1999(3):315-329.[16] 王宏刚,曾建潮.基于Metropolis判别准则的遗传算法[J]. 控制与决策,1998,13(2):181-184.WANG Honggang,ZENG Jianchao.Genetic algorithm based on the metropolis criteria[J]. Control And Decision,1998,13(2):181-184.[17] 叶怀珍.现代物流学[M]. 北京:高等教育出版社,2003:306-316.
点击查看大图
计量
- 文章访问数: 1604
- HTML全文浏览量: 76
- PDF下载量: 410
- 被引次数: 0