长期车辆合乘问题的复合变邻域搜索算法

doi:10.11772/j.issn.1001-9081.2018020343

计算机应用 ›› 2018, Vol. 38 ›› Issue (10): 3036-3041.DOI: 10.11772/j.issn.1001-9081.2018020343

• 应用前沿、交叉与综合 • 上一篇下一篇

长期车辆合乘问题的复合变邻域搜索算法

郭羽含, 伊鹏

辽宁工程技术大学软件学院, 辽宁葫芦岛 125100

收稿日期:2018-02-07 修回日期:2018-03-03 出版日期:2018-10-10 发布日期:2018-10-13
通讯作者: 郭羽含
作者简介:郭羽含(1983-),男,黑龙江哈尔滨人,副教授,博士,主要研究方向:智能搜索算法、车辆调度问题、供应链优化问题;伊鹏(1993-),男,河北承德人,硕士研究生,主要研究方向:车辆调度问题。
基金资助:
辽宁省教育厅科学技术研究一般项目（LJYL051）。

Hybrid variable neighborhood search algorithm for long-term carpooling problem

GUO Yuhan, YI Peng

School of Software, Liaoning Technical University, Huludao Liaoning 125100, China

Received:2018-02-07 Revised:2018-03-03 Online:2018-10-10 Published:2018-10-13
Supported by:
This work is partially supported by the General Project of Science and Technology Research of Liaoning Committee of Education (LJYL051).

摘要/Abstract

摘要： 针对于长期车辆合乘问题（LTCPP），提出一种复合变邻域搜索算法（HVNSA），将具有相同目的地的用户进行合乘匹配从而减少车辆出行数量。首先，构建一个全面准确的长期车辆合乘问题的数学模型，将所有用户按复合距离优先算法分配到合乘小组中，对时间窗口和车容量约束验证，得到初始合乘方案；然后利用变邻域搜索算法对初始合乘方案进行优化迭代，得到最终的优化合乘方案。实验结果表明，该算法在处理100人和200人的规模问题上可以在1 s内得到高质量的优化合乘方案，对于400人和1000人的较大规模问题，该算法仍然可以在2~4 s内得到较高质量的优化合乘方案。

关键词: 长期车辆合乘问题, 邻域结构, 变邻域搜索, 合乘匹配, 车辆调度问题

Abstract: A Hybrid Variable Neighborhood Search Algorithm (HVNSA) was proposed for solving Long-Term CarPooling Problem (LTCPP), which reduced the number of vehicle trips by matching the users with the same destination. Firstly, a comprehensive and accurate mathematical model of LTCPP was built. Then all users were assigned to the car pools by the composite distance preference algorithm, the time window and vehicle capacity constraint were verified to obtain the initial carpooling scheme. Secondly, the initial carpooling scheme was optimized by using variable neighborhood search algorithm to obtain the optimal long-term carpooling scheme. The experimental results show that HVNSA can obtain high quality of optimal carpooling scheme within 1 second for 100 people and 200 people instances; at the same time, the algorithm can obtain higher quality of optimal carpooling scheme within 2-4 seconds for the larger-scale instances such as 400 people and 1000 people.

Key words: Long-Term CarPooling Problem (LTCPP), neighborhood structure, variable neighborhood search, carpool matching, vehicle scheduling problem

中图分类号:

TP18
TP399

郭羽含, 伊鹏. 长期车辆合乘问题的复合变邻域搜索算法[J]. 计算机应用, 2018, 38(10): 3036-3041.

GUO Yuhan, YI Peng. Hybrid variable neighborhood search algorithm for long-term carpooling problem[J]. Journal of Computer Applications, 2018, 38(10): 3036-3041.

参考文献

[1] 宋超超,王洪国,邵增珍,等. 一种求解多车辆合乘匹配问题的适应性算法[J].计算机科学,2013,40(2):222-228. (SONG C C, WANG H G, SHAO Z Z,et al. Adaptive algorithm for MRMP[J].Computer Science, 2013, 40(2):222-228.)
[2] 杨志家,王子,汪扬,等. 车辆合乘问题的两阶段分布式估计算法[J].交通运输系统工程与信息,2016,16(2):164-169.(YANG Z J, WANG Z, WANG Y, et al. Two-stage estimation of distribution algorithm to solve multi-vehicle carpooling problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(2):164-169.)
[3] BOUKHATER C M, DAKROUB O, LAHOUD F, et al. An intelligent and fair GA carpooling scheduler as a social solution for greener transportation[C]//Proceedings of the 2014 Mediterranean Electrotechnical Conference. Piscataway, NJ:IEEE, 2014:182-186.
[4] 李妍峰,高自友,李军. 基于实时交通信息的城市动态网络车辆路径优化问题[J].系统工程理论与实践,2013,33(7):1813-1819.(LI Y F, GAO Z Y, LI J. Vehicle routing problem in dynamic urban network with real-time traffic information[J]. Systems Engineering-Theory and Practice, 2013,33(7):1813-1819.)
[5] 张亦楠,魏志强,刘昊. 出租车多人合乘匹配问题的研究[J].信息通信,2014(3):70-71. (ZHANG Y N,WEI Z Q,LIU H. Research on the matching problem of taxi multi person carpooling[J]. Information & Communications,2014(3):70-71.)
[6] SOEANU A, RAY S, DEBBABI M, et al. A decentralized heuristic for multi-depot split-delivery vehicle routing problem[C]//Proceedings of the 2011 IEEE International Conference on Automation and Logistics. Piscataway, NJ:IEEE, 2011:70-75.
[7] 邵婷婷. 基于智能算法的车辆合乘研究与设计[D].南昌:东华理工大学,2014. (SHAO T T. Research and design of carpooling based on intelligent algorithm[D]. Nanchang:East China University of Technology, 2014.)
[8] 孟春华,王洪国,邵增珍,等. 基于客户分级及换乘的多车辆合乘问题算法研究[J]. 计算机科学,2013,40(9):237-242,261. (MENG C H,WANG H G,SHAO Z Z, et al. Algorithm research on multi-vehicle ride matching problem based on passengers classification and transfers[J].Computer Science, 2013,40(9):237-242, 261.)
[9] YAN S,CHEN C,LIN Y. A model with a heuristic algorithm for solving the long-term many-to-many car pooling problem[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(4):1362-1373.
[10] 于匡员. 基于预约模式的出租车合乘路径优化[D].哈尔滨:哈尔滨工业大学,2015.(YU K Y. Taxipooling routing optimization based on reserve pattern[D]. Harbin:Harbin Institute of Technology,2015.)
[11] CELSI L R, GIORGIO A D, GAMBUTI R, et al. On the many-to-many carpooling problem in the context of multi-modal trip planning[C]//Proceedings of the 201725th Mediterranean Conference on Control and Automation. Piscataway, NJ:IEEE, 2017:303-309.
[12] HAME L. An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows[J]. European Journal of Operational Research, 2011, 209(1):11-22.
[13] AGATZ N, ERERA A, SAVELSBERGH M, et al. The value of optimization in dynamic ride-sharing:a simulation study in metro atlanta[J]. Erim Report, 2010, 17(1):1450-1464.
[14] HERBAWI W M, WEBER M. A genetic and insertion heuristic algorithm for solving the dynamic ridematching problem with time windows[C]//Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation. New York:ACM, 2012:385-392.
[15] SANTOS D O, XAVIER E C. Taxi and ride sharing:a dynamic dial-a-ride problem with money as an incentive[J]. Expert Systems with Applications, 2015, 42(19):6728-6737.

长期车辆合乘问题的复合变邻域搜索算法

Hybrid variable neighborhood search algorithm for long-term carpooling problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[2]	李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.
[3]	陈林烽, 齐学梅, 陈俊文, 黄琤, 陈付龙. 批量流水调度问题的量子候鸟协同优化算法[J]. 计算机应用, 2019, 39(11): 3250-3256.
[4]	曹琦, 曹阳. 应急物资配送车辆调度模型与优化综述[J]. 计算机应用, 2018, 38(8): 2416-2422.
[5]	郭羽含, 张美琪, 周楠. 基于偏好矩阵遗传算法求解长期车辆合乘问题[J]. 计算机应用, 2017, 37(2): 602-607.
[6]	邵超万春红. 基于自组织映射的流形学习与可视化[J]. 计算机应用, 2013, 33(07): 1917-1921.
[7]	王超董兴业. 求解护士排班问题的变邻域搜索算法[J]. 计算机应用, 2013, 33(02): 338-352.
[8]	赵洋贺毅朝李晰. 具有自加速与变邻域搜索的差分演化算法[J]. 计算机应用, 2012, 32(10): 2911-2915.