求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法

doi:10.3969/j.issn.0372-2112.2015.10.026

摘要
图/表
参考文献(0)
相关文章 (15)

全文: PDF (3348 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要

基于对标准车辆路径问题的分析,本文构建了一种包括交通因素、客户需求动态改变、用户满意度的多目标动态车辆路径问题模型.针对伊藤算法在求解离散组合优化问题时效率较低、收敛性较差等缺陷,本文以具有通用性的伊藤算法为框架,参考蚁群算法,设计了伊藤-蚂蚁优化算法,并采用正交实验的方法,分析了改进算法参数的设置问题.为了验证改进算法的有效性,文章对标准测试数据集中的数据进行了测试.最后,将标准测试数据改编成符合带用户满意度的多目标实时车辆路径问题模型的测试数据,并用改进算法进行求解.实验结果表明,本文提出的问题模型和改进算法是可行的、有效的.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	易云飞
	蔡永乐
	董文永
	林晓东

关键词 ：动态车辆路径问题, 伊藤算法, 蚁群算法, 用户满意度

Abstract：

Based on the analysis of the standard vehicle routing problem, we proposed a multiobjective real-time vehicle routing problem model, referred as MR-VRPCS.The MR-VRPCS considers the traffic factors, customer demand dynamic change and customers' satisfaction.As we know, the ITO algorithm has low efficiency and poor convergence performance on the discrete combinatorial optimization problems.Therefore, we apply the universal framework of ITO and introduce the Ant Colony Optimization algorithm, which has got depth studied in vehicle routing problem, to design the ITO-Ant Optimization algorithm.We analyze the IAO algorithm's parameter setting problem by the method of orthogonal experiment.Finally, we use the Solomon benchmark test data to prove the effectiveness of the IAO algorithm, and adjust the standard test data to the MR-VRPCS model's, and resolve it with IAO.The experimental results show the feasibility and effectiveness of the proposed model and algorithm.

Key words： dynamic vehicle routing problem ITO algorithm ant colony algorithm customers' satisfaction

收稿日期: 2014-08-12

ZTFLH:

TP14

基金资助:

国家自然科学基金(No.60873114,No.61170305);广西自然科学基金(No.2013GXNSFBA019282);广西高等学校科研项目(No.KY2015YB254);国家级大学生创新创业训练计划(No.201410605055,No.210510605024/25);广西混杂计算与集成电路设计分析重点实验室开放基金课题(No.HCIC201411)

通讯作者: 董文永 E-mail: dwy@whu.edu.cn

作者简介: 易云飞 男,1981年出生于广西资源,武汉大学计算机学院博士生,副教授,研究方向为智能计算,机器学习等.E-mail:gxyiyf@163.com;蔡永乐 男,1991年出生于河南平顶山,武汉大学计算机学院硕士研究生,研究方向为智能计算,机器学习.

引用本文:

易云飞, 蔡永乐, 董文永, 林晓东. 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J]. 电子学报, 2015, 43(10): 2053-2061. YI Yun-fei, CAI Yong-le, DONG Wen-yong, LIN Xiao-dong. Improved ITO Algorithm for Multiobjective Real-time Vehicle Routing Problem with Customers' Satisfaction. Chinese Journal of Electronics, 2015, 43(10): 2053-2061.

链接本文:

http://www.ejournal.org.cn/CN/10.3969/j.issn.0372-2112.2015.10.026 或 http://www.ejournal.org.cn/CN/Y2015/V43/I10/2053

[1] Dantzig G,Ramser J.The truck dispatching problem[J].Management Science,1959,6(1):80-91.
[2] Tang Guochun,Aibing Ning,et al.A practical split vehicle routing problem with simultaneous pickup and delivery[A].16th International Conference on Industrial Engineering and Engineering Management[C].Beijing:IEEE,2009.26-30.
[3] A LKok,E W Hans,J M J Schutten.Vehicle routing under time-dependent travel times:the impact of congestion avoidance[J].Computer & Operations Reasearch,2012,39(5):910-918.
[4] S Geetha,G Poonthalir,et al.A hybrid particle swarm optimization with genetic operators for vehicle routing problem[J].Journal of Advances in Information Technology,2010,1(4):181-188.
[5] Michalis Mavrovouniotis,Shengxiang Yang.Ant colony optimization with memory-based immigrants for the dynamic vehicle routing problem[A].2012 IEEE Congress on Evolutionary Computation[C].Brisbane:IEEE,2012.1-8.
[6] 易云飞,董文永,等.求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J].电子学报,2015,43(4):658-664. Yi Yunfei,Dong Wenyong,et al.The improved ITO algorithm to solve the vehicle routing problem with soft time windows and its convergence analysis[J].Acta Electronica Sinica,2015,43(4):658-664.(in Chinese)
[7] 董文永,张文生,于瑞国.求解组合优化问题伊藤算法的收敛性和期望收敛速度分析[J].计算机学报,2011,34(4):636-646. Dong Wenyong,Zhang Wensheng,et al.Convergence and runtime analysis of ITO algorithm for one class of combinatorial optimization[J].Chinese Journal of Computers.2011,34 (4):636-646.(in Chinese)
[8] 喻飞,李元香,等.透镜成像反学习策略在粒子群算法中的应用[J].电子学报,2014,42(2):230-235. Yu fei,Li Yuanxiang,et al.The applica-tion of a novel OBL based on lens imaging principle in PSO[J].Acta Electronica Sinica,2014,42(2):230-235.(in Chinese)
[9] S FGhannadpour,S Noori,R Tavakkoli Moghaddam.Multiobjective dynamic vehicle routing problem with fuzzy travel times and customers' satisfaction in supply chain management[J].IEEE Trans Eng Manage,2013,60(4):777-790.
[10] Quan XiongWen,Xu Ya.Dynamic pick-up and delivery vehicle routing problem with ready-time and deadline[A].32nd Chinese Control Conference[C].Xi'an:IEEE,2013.2515-2520.
[11] Barry van Veen,Michael Emmerich,et al.Ant colony algorithms for the dynamic vehicle routing problem with time windows[A].5th International Work Conference on the Interplay Between Natural and Artificial Computation (IWINAC 2013)[C].Mallorca:Springer Berlin Heidelberg,2013.1-10.