求解物流配送路径优化问题的一种改进蚁群算法

• 论文 •

求解物流配送路径优化问题的一种改进蚁群算法

乐逸祥，周磊山，乐群星，孙琦

1.北京交通大学交通运输学院，北京 100044；2.北京航空航天大学经济管理学院，北京 100083

收稿日期:2005-05-18 修回日期:2005-08-02 出版日期:2006-06-15 发布日期:2006-06-25

Improved ant colony algorithm for logistics distribution routing problem

YUE Yi-xiang,ZHOU Lei-shan,YUE Qun-xing,SUN Qi

1.Sch. of Traffic & Transportation, Beijing Jiaotong Univ., Beijing 100044, China; 2.Sch. of Economics & Management, Beihang Univ., Beijing 100083, China

Received:2005-05-18 Revised:2005-08-02 Online:2006-06-15 Published:2006-06-25

摘要/Abstract

摘要： 物流配送路径优化是现代物流配送服务的关键环节之一，由于需求的小批量和动态变化等特点，需要设计一个快速有效的求解算法。为此，构建了物流配送路径优化问题的数学模型，设计了一个改进的蚁群算法来求解该问题，引进了选择算子、插点操作和动态改变算法参数等改进措施，开发和实现了一个试验软件包。仿真试验结果表明，该算法具有较好的全局寻优能力，收敛速度快，是解决物流配送路径优化问题的有效算法。

关键词: 物流, 物流配送, 蚁群算法, 车辆路径问题, 优化

Abstract: Vehicle Routing Problem (VRP) optimization is a very important problem in modern logistics service. Due to its small batch and dynamic changes of VRP, effective and fast algorithm to solve VRP was in great need. To deal with this need, a new mathematic model of logistics VRP was constructed and an improved Ant Colony Algorithm (ACA) for VRP with Time Window (VRPTW) was presented. To solve VRPTW with ACA, three improvements were introduced: interpolation operation, selection operator and dynamic change on algorithm parameters. An experimental program was developed and many computational studies were carried out. Simulation results showed that the improved ACA had better overall search ability and astringency. It was an effective solution to VRPTW.

Key words: logistics, physical distribution, ant colony algorithm, vehicle routing problem, optimization

中图分类号:

U116.2

乐逸祥，周磊山，乐群星，孙琦. 求解物流配送路径优化问题的一种改进蚁群算法[J]. .

YUE Yi-xiang,ZHOU Lei-shan,YUE Qun-xing,SUN Qi. Improved ant colony algorithm for logistics distribution routing problem[J]. .

参考文献

［1］ LENSTRA J K,RINNOOY K.Complexity of vehicle routing and scheduling problem［J］.Networks,1981,11(2):221-227.

[2] SAVELSBERG H M.Local search in routing problem with time window［J］.Operations Research,1985,33(4):285-305.

[3] SOLOMON M M.On the worst-case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints［J］.Networks,1986,16(2):161-174.

[4] DORIGO M,CARO G D.Ant algorithms for discrete optimization［J］.ArtificialLife,1999,5(2): 137-172.

[5] DORIGO M,VITTORIO M,ALBERTO C.The ant system: optimization by a colony of cooperating Agents［J］.IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1): 1-13.

[6] COSTA D,HERTZ A.Ants can color graphs［J］.Journal of the Operational Research Society,1997,48(3):295-305.

[7] AKON M M,GOSWAMI D,JYOTI A.Routing in telecommunication network with controlled ant population［A］.Proceedings of the First IEEE Consumer Communications and Networking Conference［C］.New York,NY,USA:Institute of Electrical and Electronics Engineers Inc.,2004.665-667.

[8] KASILINGAM R G.Logistics and transportation: design and planning［M］.Boston,MA,USA: Kluwer Academic Publishers,1998.29-33.

[9] LIU Zhishuo,SHEN Jinsheng.An adaptive ant colony algorithm for vehicle routing problem based on the evenness of solution［J］.Journal of System Simulation,2005,17(5): 1079-1083(in Chinese).［刘志硕，申金升.基于解均匀度的车辆路径问题的自适应蚁群算法［J］.系统仿真学报,2005,17(5): 1079-1083.］

[10] MURAO H,TOHMATA K,KONISHI M,et al.Pheromone based transportation scheduling system for the multi-vehicle routing problem［A］.IEEE International Conference on Systems,Man and Cybernetics［C］.Piscataway,NJ,USA:Institute of Electrical and Electronics Engineers Inc.,1999.

[11] KUO R J,CHIU C Y,LIN Y J.Integration of fuzzy theory and ant algorithm for vehicle routing problem with time window［A］.Annual Meeting of the North American Fuzzy Information Processing Society［C］.Piscataway,NJ,USA:Institute of Electrical and Electronics Engineers Inc.,2004.925-930.

[1]	陈年,金涛,王建民. 基于变异反馈的临床路径优化[J]. 计算机集成制造系统, 2021, 27(9): 2556-2564.
[2]	刘德田,王德玉,张光欣,赵剑慧. 电网企业以“承诺制”推进流程优化方法研究与实践[J]. 计算机集成制造系统, 2021, 27(9): 2729-2735.
[3]	秦旋,房子涵,张赵鑫. 考虑资源约束的预制构件多目标生产调度优化[J]. 计算机集成制造系统, 2021, 27(8): 2248-2259.
[4]	尚正阳,顾寄南,王建平. 求解带能力约束车辆路径优化问题的改进模拟退火算法[J]. 计算机集成制造系统, 2021, 27(8): 2260-2269.
[5]	李国明,李军华. 带软时间窗随机需求车辆路径问题的算法研究[J]. 计算机集成制造系统, 2021, 27(8): 2270-2281.
[6]	顾九春,姜天华,朱惠琦. 多目标离散灰狼优化算法求解作业车间节能调度问题[J]. 计算机集成制造系统, 2021, 27(8): 2295-2306.
[7]	刘晶,张喆语,董志红,季海鹏. 基于工业物联网的区块链多目标优化[J]. 计算机集成制造系统, 2021, 27(8): 2382-2392.
[8]	冯国奇,崔东亮,代学武,俞胜平. 数据视角下神经网络增量学习支持的涡轮盘多目标优化[J]. 计算机集成制造系统, 2021, 27(8): 2393-2404.
[9]	谭春桥,李波,周丽. 考虑企业社会责任的物流服务供应链定价决策[J]. 计算机集成制造系统, 2021, 27(8): 2461-2475.
[10]	汪逸晖,高亮. 乌鸦搜索算法的改进及其在工程约束优化问题中的应用[J]. 计算机集成制造系统, 2021, 27(7): 1871-1883.
[11]	刘景森,马义想,李煜. 改进鲸鱼算法求解工程设计优化问题[J]. 计算机集成制造系统, 2021, 27(7): 1884-1897.
[12]	张建侠,宋明顺,方兴华,邓钰佳. 基于Kriging模型的多目标代理优化算法及其收敛性评估[J]. 计算机集成制造系统, 2021, 27(7): 2035-2044.
[13]	王文中,张树生,余隋怀,陈登凯. 基于解构·重构思维的潜水器舱室布局优化[J]. 计算机集成制造系统, 2021, 27(7): 2045-2052.
[14]	张英英,夏一,杜纲. 产品族配置与考虑升级的再制造设计主从关联优化[J]. 计算机集成制造系统, 2021, 27(7): 2053-2064.
[15]	郭羽含,于俊宇,刘万军,张宇,张美琪. 制造业可持续供应链网络建模及求解[J]. 计算机集成制造系统, 2021, 27(7): 2112-2133.