多车型动态需求车辆路径问题建模及优化

• 论文 •

多车型动态需求车辆路径问题建模及优化

张景玲，赵燕伟，王海燕，介婧，王万良

1.浙江工业大学特种装备制造与先进加工技术教育部重点实验室，浙江杭州310012;2.浙江工业大学计算机科学与技术学院，浙江杭州310012

出版日期:2010-03-15 发布日期:2010-03-25

Modeling and algorithms for a dynamic multi-vehicle routing problem withCustomers'dynamic requests

ZHANG Jing-ling, ZHAO Yan-wei, WANG Hai-yan, JIE Jing, WANG Wan-liang

1.Key Laboratory of Special Equipment & Advanced Processing Technology Ministry of Education,Zhejiang University of Technology, Hangzhou 310012,China；2.College of Computer Science & Technology, Zhejiang University of Technology, Hangzhou 310012, China

Online:2010-03-15 Published:2010-03-25

摘要/Abstract

摘要： 针对现代物流配送系统中客户需求动态变化、配送中心车型多样化以及车辆行驶路线开放式的特点，建立了多车型开放式动态需求车辆路径问题的两阶段数学规划模型。制定了相应的“预优化路线调度”和“实时动态调度”的两阶段求解策略，提出了混合2-OPT量子进化算法的求解方法，设计了一种将常用的整数编码转换为量子比特的编码方法，每一个染色体都代表一种行车路线方案，对于量子进化算法求得的行车路线方案，引入2-OPT优化方法，对线路内的子路径进行局部调整，进一步提高了算法的收敛速度。最后通过实例测试及与其他算法的比较，验证了该方法的有效性。

关键词: 物流, 车辆路径, 动态需求, 多车型, 两阶段模型, 混合量子进化算法

Abstract: Aiming at the dynamic changes of customer requirements, vehicles'diversification and open routes in the dynamic vehicle routing problem (DVRP), a two-phase mathematic programming model was presented for the dynamic vehicle routing problem. Corresponding two-phase solutions of “Pre-optimization Route Scheduling” and “Real-time Dynamic Scheduling” were established. And a Hybrid 2-OPT Quantum-Inspired Evolutionary Algorithm (HQEA) for this dynamic problem was proposed. In the HQEA, an encoding method of converting Q-bit representation to integer representation was designed. Every chromosome represented a kind of route. The 2-OPT algorithm was introduced to optimize sub-routes for convergence acceleration. Finally, some examples were tested and were compared with other algorithms.The effectivness of this method was verified by case study and comparing with the other methods.

Key words: logistics, vehicle routing, dynamic requests, multi-vehicle, two-phase mathematic model, hybrid quantum evolutionary algorithm

中图分类号:

F224

张景玲，赵燕伟+，王海燕，介婧，王万良. 多车型动态需求车辆路径问题建模及优化[J]. .

ZHANG Jing-ling, ZHAO Yan-wei+, WANG Hai-yan, JIE Jing, WANG Wan-liang. Modeling and algorithms for a dynamic multi-vehicle routing problem withCustomers'dynamic requests[J]. .

[1]	尚正阳,顾寄南,王建平. 求解带能力约束车辆路径优化问题的改进模拟退火算法[J]. 计算机集成制造系统, 2021, 27(8): 2260-2269.
[2]	李国明,李军华. 带软时间窗随机需求车辆路径问题的算法研究[J]. 计算机集成制造系统, 2021, 27(8): 2270-2281.
[3]	谭春桥,李波,周丽. 考虑企业社会责任的物流服务供应链定价决策[J]. 计算机集成制造系统, 2021, 27(8): 2461-2475.
[4]	尚正阳,顾寄南,潘家保. 考虑LIFO约束的2L-CVRP优化[J]. 计算机集成制造系统, 2021, 27(7): 2134-2143.
[5]	刘利枚,龚尹励,曹文治,杨艺. 基于语言直觉模糊集的应急物流预案决策[J]. 计算机集成制造系统, 2021, 27(5): 1494-1505.
[6]	裴植,万明重,杜蕊,李英德,陈勇. 多充电桩下考虑运载机械释放时间的充电调度[J]. 计算机集成制造系统, 2021, 27(4): 1089-1098.
[7]	刘俊琦,张则强,王沙沙,曾艳清. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
[8]	夏扬坤,邓永东,庞燕,王忠伟,高亮. 带客户分级和需求可拆分的生鲜车辆路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1238-1248.
[9]	代应,马康宁,宋寒,周林. 第三方物流企业电商化转型与服务水平决策[J]. 计算机集成制造系统, 2021, 27(3): 899-911.
[10]	聂福海,李电生,肖婷婷. 考虑外源融资的资金约束供应链物流策略[J]. 计算机集成制造系统, 2021, 27(3): 924-932.
[11]	谭志龙,王征,薛桂琴,王新. 基于社会化库存的多回程物流配送问题的拉格朗日松弛算法[J]. 计算机集成制造系统, 2021, 27(3): 965-972.
[12]	邓建新,卫世丰,石先莲,陈星雨,韦婉冬. 基于数字孪生的配送管理系统研究[J]. 计算机集成制造系统, 2021, 27(2): 585-604.
[13]	向峰,钟雷,左颖,蒋国璋,段现银. 面向工业互联网平台的制造服务可信特征识别方法[J]. 计算机集成制造系统, 2021, 27(10): 2762-2773.
[14]	陈久梅,李英娟,胡婷,但斌,李俊. 开放式带时间窗车辆路径问题及变邻域搜索算法[J]. 计算机集成制造系统, 2021, 27(10): 3014-3025.
[15]	王万良,朱文成,赵燕伟. 基于全局边缘排序的超启发算法在绿色物流选址—路径优化问题中的应用[J]. 计算机集成制造系统, 2020, 26(第4): 1097-1107.