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

doi:10.3969/j.issn.0372-2112.2015.10.026

电子学报 ›› 2015, Vol. 43 ›› Issue (10): 2053-2061.DOI: 10.3969/j.issn.0372-2112.2015.10.026

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

易云飞^1,2,3, 蔡永乐¹, 董文永¹, 林晓东²

1. 武汉大学计算机学院, 湖北武汉 430079;
2. 河池学院计算机与信息工程学院, 广西宜州 546300;
3. 广西高校系统控制与信息处理重点实验室, 广西宜州 546300

收稿日期:2014-08-12 修回日期:2015-05-27 出版日期:2015-10-25 发布日期:2015-10-25
通讯作者: 董文永
作者简介:易云飞 男,1981年出生于广西资源,武汉大学计算机学院博士生,副教授,研究方向为智能计算,机器学习等.E-mail:gxyiyf@163.com;蔡永乐 男,1991年出生于河南平顶山,武汉大学计算机学院硕士研究生,研究方向为智能计算,机器学习.
基金资助:
国家自然科学基金(No.60873114,No.61170305);广西自然科学基金(No.2013GXNSFBA019282);广西高等学校科研项目(No.KY2015YB254);国家级大学生创新创业训练计划(No.201410605055,No.210510605024/25);广西混杂计算与集成电路设计分析重点实验室开放基金课题(No.HCIC201411)

Improved ITO Algorithm for Multiobjective Real-time Vehicle Routing Problem with Customers' Satisfaction

YI Yun-fei^1,2,3, CAI Yong-le¹, DONG Wen-yong¹, LIN Xiao-dong²

1. Computer School, Wuhan University.Wuhan, Hubei 430079, China;
2. College of Computer and Information Engineering, Hechi University.Yizhou, Guangxi 546300, China;
3. Guangxi Universities Key Laboratory Breeding Base of System Control and Information Processing.Yizhou, Guangxi 546300, China

Received:2014-08-12 Revised:2015-05-27 Online:2015-10-25 Published:2015-10-25

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP14

易云飞, 蔡永乐, 董文永, 林晓东. 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[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[J]. Acta Electronica Sinica, 2015, 43(10): 2053-2061.

参考文献

[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.

[1]	孙鑫威, 纪爱敏, 陈曦晖, 林新海, 许行. 强噪声背景下动车组轴承微弱故障信号检测[J]. 电子学报, 2021, 49(11): 2217-2224.
[2]	廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48(7): 1330-1342.
[3]	许凯波, 鲁海燕, 黄洋, 胡士娟. 基于双层蚁群算法和动态环境的机器人路径规划方法[J]. 电子学报, 2019, 47(10): 2166-2176.
[4]	李媛祯, 杨群, 赖尚琦, 李博涵. 一种Hadoop Yarn的资源调度方法研究[J]. 电子学报, 2016, 44(5): 1017-1024.
[5]	章刚, 陈庆奎. GCTA:一种群组命令传输算法[J]. 电子学报, 2016, 44(2): 413-419.
[6]	李琳, 应时, 赵翀, 董波. 基于蚁群算法的面向服务软件的部署优化方法[J]. 电子学报, 2016, 44(1): 123-129.
[7]	易云飞, 董文永, 林晓东, 蔡永乐. 求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J]. 电子学报, 2015, 43(4): 658-664.
[8]	邓广宏, 曹万华, 张剑, 冯力, 程雄. DTN网络环境下基于蚁群算法的数据编码分发[J]. 电子学报, 2014, 42(8): 1636-1641.
[9]	郑巧仙, 李明, 李元香, 唐秋华. 求解双边装配线平衡问题的改进蚁群算法[J]. 电子学报, 2014, 42(5): 841-845.
[10]	袁述, 袁东辉, 孙基洲, 刘永波, 李晶, 原琳. 蚁群-遗传算法在多传感器多目标跟踪技术中的应用[J]. 电子学报, 2013, 41(3): 609-614.
[11]	李静叶, 罗涛, 乐光新. 联合网络容量与认知用户满意度的资源分配优化方案[J]. 电子学报, 2012, 40(7): 1315-1322.
[12]	刘衍珩;张婧;王健. TrANTHOCNET:信任性蚁群自组织路由算法[J]. 电子学报, 2012, 40(2): 319-326.
[13]	郭蕴华, 袁成. 一种异步航迹关联的变异蚁群算法[J]. 电子学报, 2012, 40(11): 2200-2205.
[14]	易伟;王佳文;潘红兵;李丽. 基于蚁群混沌遗传算法的片上网络映射[J]. 电子学报, 2011, 39(8): 1832-1836.
[15]	柳长安;鄢小虎;刘春阳;吴华. 基于改进蚁群算法的移动机器人动态路径规划方法[J]. 电子学报, 2011, 39(5): 1220-1224.

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

Improved ITO Algorithm for Multiobjective Real-time Vehicle Routing Problem with Customers' Satisfaction

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics