一种动态车辆路径问题解决策略仿真研究

系统仿真学报 ›› 2015, Vol. 27 ›› Issue (12): 2942-2947.

一种动态车辆路径问题解决策略仿真研究

宁涛^1,2, 郭晨², 陈荣², 金花¹

1.大连交通大学软件学院,大连 116045;
2.大连海事大学信息科学技术学院,大连 116026

收稿日期:2014-10-20 修回日期:2015-01-21 出版日期:2015-12-08 发布日期:2020-07-30
作者简介:宁涛(1979-),男,山东蓬莱,博士,副教授,硕导,研究方向为计算机集成制造、交通信息工程控制、交通调度系统研究。
基金资助:
国家自然科学基金(61374114); 中央高校基本科研业务费(3132014321)

Simulation Study on Scheduling Strategy of Dynamic Vehicle Routing Problem

Ning Tao^1,2, Guo Chen², Chen Rong², Jin Hua¹

1. Institute of Software, Dalian Jiaotong University, Dalian 116045, China;
2. School of Management, Dalian University of Technology, Dalian 116026, China

Received:2014-10-20 Revised:2015-01-21 Online:2015-12-08 Published:2020-07-30

摘要/Abstract

摘要： 配送过程中动态因素的变化会引起车辆配送的重调度问题,以最小化成本和最优化稳定性值为目标,建立了动态车辆路径问题的数学模型;提出了基于车辆链和货物链的双链量子编码方法和改进的多相量子粒子群算法;为能够在获取的一组非支配解中获取最优决策方案,引入了"层次分析法"(以下简称AHP)策略。把所提出的方法应用于动态仿真算例,并将结果与已经存在的算法进行比较,分析结果验证了所提出方法的有效性。

关键词: 动态车辆路径问题, 多相量子粒子群算法, 双链量子编码, AHP策略

Abstract: For the purpose of solving the rescheduling of dynamic vehicle routing problem, the simulation model was established to minimize the cost and optimize the stability. The method of double chains structure coding was proposed. An improved hybrid multi-phases quantum particle swarm algorithm was proposed. An AHP (Analytic hierarchy process strategy) was introduced to obtain the optimal strategy from the Pareto solution. A novel method was applied to a dynamic simulation and the result of comparing with other classical algorithms verifies its effectiveness.

Key words: dynamic vehicle routing problem, multi-phases quantum particle swarm algorithm, double chains coding, Analytic hierarchy process strategy

中图分类号:

TP391.9A

宁涛, 郭晨, 陈荣, 金花. 一种动态车辆路径问题解决策略仿真研究[J]. 系统仿真学报, 2015, 27(12): 2942-2947.

Ning Tao, Guo Chen, Chen Rong, Jin Hua. Simulation Study on Scheduling Strategy of Dynamic Vehicle Routing Problem[J]. Journal of System Simulation, 2015, 27(12): 2942-2947.

参考文献

[1] Angelelli E, Savelsbergh M, Grazia Speranza M.Competitive analysis of a dispatch policy for a dynamic multi-period routing problem[J]. Operations Research Letters (S0167-6377), 2007, 35(6): 713-721.
[2] Angelelli E, Bianchessi N, Mansini R, et al. Short term strategies for a dynamic multi-period routing problem[J]. Transportation Research Part C: Emerging Technologies (S 0968-090X), 2009, 17(2): 106-119.
[3] 王旭, 葛显龙, 代应. 基于两阶段求解算法的动态车辆调度问题研究[J]. 控制与决策, 2012, 27(2): 175-181.
[4] Smith S L, Pavone M, Bullo F, et al. Dynamic vehicle routing with priority classes of stochastic demands[J]. SIAM J on Control and Optimization (S0363-0129), 2010, 48(5): 3224-3245.
[5] Bent R, Van Hentenryck P.Waiting and relocation strategies in online stochastic vehicle routing[C]// Proc of the 20th Int Joint Conf on Artificial Intelligence. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc, 2007: 1816-1821.
[6] Potvin J Y, Xu Y, Benyahia I.Vehicle routing and scheduling with dynamic travel times[J]. Computers & Operations Research (S0305-0548), 2006, 33(4): 1129-1137.
[7] 宁涛. 混合量子算法在车辆路径问题中应用的研究 [D]. 大连: 大连海事大学, 2013.
[8] Ishibuchi H, Murata T.A Multi-Objective Genetic Local Search Algorithm and Its Application to Flow shop Scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews (S1083-4427), 1998, 28(3): 392-403.
[9] Fattahi P, Fallahi A.Dynamic Scheduling in Flexible Job Shop Systems by Considering Simultaneously Efficiency and Stability[J]. CIRP Journal of Manufacturing Science and Technology (S1755-5817), 2010, 2(2): 114-123.
[10] Jeong-Yun Do, Doo-Kie Kim.AHP-Based Evaluation Model for Optimal Selection Process of Patching Materials for Concrete Repair: Focused on Quantitative Requirements[J]. International Journal of Concrete Structures and Materials (S1976-0485), 2012, 6(2): 87-100.
[11] Bagheri A, Zandith M, Mahdavi I, et al. An Artificial Immune Algorithm for the Flexible Job-shop Scheduling Problem[J]. Fut Gen Comp Sys (S0036-1437), 2010, 26(4): 533-541.
[12] 汤健超. 基于混合进化算法的若干调度问题研究 [D].广州: 华南理工大学, 2012.
[13] 张利平. 作业车间预反应式动态调度理论与方法研究 [D]. 武汉: 华中科技大学, 2013.
[14] Seyed Habib A Rahmat, M Zandieh, M Yazdani. Developing Two Multi-objective Evolutionary Algorithms for the Multi-objective Flexible Job Shop Scheduling Problem[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2013, 64(5): 915-932.