万方数据资源系统

中国公路学报
CHINA JOURNAL OF HIGHWAY AND TRANSPORT
2006 Vol.19 No.4 P.118-122

数字化期刊

具有同时配送和回收需求的车辆路径问题的混合遗传算法

张建勇  李军 

摘 要:介绍了具有同时配送和回收需求的车辆路径问题(VRPSDP),并对其进行了描述,建立了该问题的数学规划模型.结合2-opt法和等级替换策略等设计了求解VRPSDP的一种混合遗传算法,给出了该算法初始种群的两种生成规则--随机生成和构造初始种群,设计了相应的交叉和变异算子,并详细阐述了违反约束条件的处理方法.通过随机模拟试验以及与其他方法的对比分析表明:该算法可有效缩短车辆行驶距离,而构造初始种群则在一定条件下可显著提高混合遗传算法的收敛速度并改善其运行结果.
关键词:物流;车辆路径问题;混合遗传算法;数学规划模型
分类号:U492.22 文献标识码:A

文章编号:1001-7372(2006)04-0118-05

Hybrid Genetic Algorithm to Vehicle Routing Problem with Simultaneous Delivery and Pick-up

ZHANG Jian-yong  LI Jun 

基金项目:国家自然科学基金项目(70071028)
作者简介:张建勇(1975-),男,山西和顺人,讲师,工学博士,E-mail:zhangjy94@nankai.edu.cn.
作者单位:张建勇(南开大学,商学院,天津,300071) 
     李军(天津职业大学,经济管理学院,天津,300402) 

参考文献:

[1]GOETSCHALCKX M,JACOBSBLECHA C.The Vehicle Routing Problem with Backhauls[J].European Journal of Operational Research,1989,42 (1):39-51.
[2]KIM N H,RIM S C,MIN B D.A Heuristic Algorithm for Vehicle Routing Problem with Backhauls[J].International Journal of Management Science,1997,3(1):1-14.
[3]DUMAS Y,DESROSIERS J,SOUMIS F.The Pickup and Delivery Problem with Time Windows[J].European Journal of Operational Research,1991,54(1):7-22.
[4]张波,叶家玮,胡郁葱.模拟退火算法在路径优化问题中的应用[J].中国公路学报,2004,17(1):79-81.ZHANG Bo,YE Jia-wei,HU Yu-cong.Application of Optimizing the Path by Simulated Annealing[J].China Journal of Highway and Transport,2004,17(1):79-81.
[5]MIN H.The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-up Points[J].Transportation Research,1989,23 (4):377-386.
[6]DETHLOFF J.Vehicle Routing and Reverse Logistics:the Vehicle Routing Problem with Simultaneous Delivery and Pick-up[J].OR Spektrum,2001,23(1):79-96.
[7]HOLLAND J H.Adaptation in Natural and Artificial Systems:an Introductory Analysis with Applications to Biology,Control,and Artificial Intelligence[M].Ann Arbor:University of Michigan Press,1975.
[8]GOLDBERG D E.Genetic Algorithms in Search,Optimization and Machine Learning[M].Boston:Addison-Wesley,1989.
[9]BEASLEY D,BULL D R,MARTIN R R.An Overview of Genetic Algorithms:Part I,Fundamentals[J].University Computing,1993,15 (1):58-69.
[10]BEASLEY D,BULL D R,MARTIN R R.An Overview of Genetic Algorithms:Part Ⅱ,Research Topics[J].University Computing,1993,15 (2):170-181.
[11]MITCHELL M.An Introduction to Genetic Algorithms[M].Cambridge:MIT Press,1996.
[12]GILLETT B E,MILLER L R.A Heuristic Algorithm for the Vehicle Dispatch Problem[J].Operations Research,1974,22 (4):340-349.
[13]BEASLEY J E,CHU P C.Constraint Handling in Genetic Algorithms:the Set Partitioning Problem[J].Journal of Heuristics,1998,4(4):323-357.

收稿日期:2005年11月20日

出版日期:2006年7月31日

请看PDF全文