基于客户分级及换乘的多车辆合乘问题算法研究

计算机科学 ›› 2013, Vol. 40 ›› Issue (9): 237-242.

基于客户分级及换乘的多车辆合乘问题算法研究

孟春华,王洪国,邵增珍,于洪玲,丁艳辉

山东师范大学管理科学与工程学院济南250014;山东师范大学信息科学与工程学院济南250014;山东师范大学信息科学与工程学院济南250014;山东师范大学管理科学与工程学院济南250014;山东师范大学信息科学与工程学院济南250014

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受山东省自然科学基金项目(ZR2011FQ029,ZR2011FL026),山东省科技发展计划项目(2011YD01099,2011YD01100),山东省高等学校科技计划项目(J11LG32)资助

Algorithm Research on Multi-vehicle Ride Matching Problem Based on Passengers Classification and Transfers

MENG Chun-hua,WANG Hong-guo,SHAO Zeng-zhen,YU Hong-ling and DING Yan-hui

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 多车辆合乘匹配问题(MRMP)是物流领域和交通领域的一个重要问题,现有的多车辆合乘匹配算法是以解决基本的多车辆合乘问题为主。为了提高客户的搭乘率,提出了客户分等级并且带有换乘的多车辆合乘匹配算法。该算法以蚁群优化算法为核心,分为3步:寻找起点终点集合；蚁群寻优,并在单向蚁群的基础上提出双向蚁群算法；车辆路径微调。实验仿真显示该算法获得80%以上的搭乘率,同时双向蚁群比单向蚁群具有更强的寻优能力。所得结果表明,该算法可以有效地获得带有换乘的匹配路线。

关键词: 多车辆合乘匹配问题,蚁群算法,换乘,客户分级中图法分类号TP18文献标识码A

Abstract: Multi-vehicle ride matching problem(MRMP)is an important problem in the field of logistics and transportation.The existing MRMP algorithms mainly solve the basic MRMP.To improve the riding rate,an algorithm for the MRMP with transfers and passengers classifing was proposed.The algorithm with ant colony optimization algorithm as the core is divided into three steps:finding the sets of start-point and end-point；ant colony optimizes the routes,and two-way ant colony is proposed based on one-way ant colony,triming the vehicle routes．Simulation experiment shows that the algorithm can achieve riding rate of 80%.And the two-way ant colony shows stronger optimization ability than one-way ant colony.The results show clealy that the algorithm can find the matching routes effectively.

Key words: Multi-vehicle ride matching problem,Ant algorithm,Transfers,Passengers classifing

孟春华,王洪国,邵增珍,于洪玲,丁艳辉. 基于客户分级及换乘的多车辆合乘问题算法研究[J]. 计算机科学, 2013, 40(9): 237-242. https://doi.org/

MENG Chun-hua,WANG Hong-guo,SHAO Zeng-zhen,YU Hong-ling and DING Yan-hui. Algorithm Research on Multi-vehicle Ride Matching Problem Based on Passengers Classification and Transfers[J]. Computer Science, 2013, 40(9): 237-242. https://doi.org/

参考文献

[1] 李玲,谷寒雨,陈坚.复杂PDPTW问题的插入启发式算法[J].计算机工程,2003,6(2):65-69
[2] 贾永基,谷寒雨,席裕庚.求解PDPTW问题的一种快速禁忌搜索算法[J].控制与决策,2004(01)
[3] Cristián E,Cortés．The pickup and delivery problem with transfers Formulation and a branch-and-cut solution method[J].European Journal of Operational Research,2010,200(3):711-724
[4] Parragh S N．Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem [J]．Transportation Research Part C-emerging Technologies,2011,9(5):912-930
[5] Hme 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
[6] Herbawi W,Weber M．Comparison of multiobjective evolutionary algorithms for solving the multiobjective route planning in dynamic multi-hop ridesharing[A]∥IEEE CEC[C]．New Or-leans,June 2011
[7] 李文勇,王炜,陈学武.公交出行路径蚂蚁算法[J].交通运输工程学报,2004(04)
[8] 柯良军,章鹤,尚可,等.一类求解带时间窗的团队定向问题的改进蚁群算法[J].计算机科学,2012,9(4):214-216
[9] Balseiro S R.An ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows[J].Computers & Operations Research,2011,38(6):954-965
[10] 邵增珍,王洪国,刘弘,等．多车辆合乘问题的两阶段聚类启发式优化算法[J].计算机研究与发展,2013

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed