基于E-CARGO模型的共乘出行匹配建模与优化方法

doi:10.11772/j.issn.1001-9081.2021060983

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (3): 778-782.DOI: 10.11772/j.issn.1001-9081.2021060983

• 2021年中国计算机学会人工智能会议(CCFAI 2021) • 上一篇

基于E-CARGO模型的共乘出行匹配建模与优化方法

李晓会¹^,², 董红斌¹()

^1.哈尔滨工程大学计算机科学与技术学院，哈尔滨 150001
^2.哈尔滨职业技术学院电子与信息工程学院，哈尔滨 150081

收稿日期:2021-06-09 修回日期:2021-07-04 接受日期:2021-07-15 发布日期:2022-04-09 出版日期:2022-03-10
通讯作者: 董红斌
作者简介:李晓会（1983—），女，黑龙江双城人，副教授，博士研究生，主要研究方向：机器学习、智能信息处理；
基金资助:
黑龙江省教育科学规划重点项目(ZJB1421113)

Modeling and optimization method of ride-sharing matching based on E-CARGO model

Xiaohui LI¹^,², Hongbin DONG¹()

^1.College of Computer Science and Technology，Harbin Engineering University，Harbin Heilongjiang 150001，China
^2.School of Electronic and Information Engineering，Harbin Vocational and Technical College，Harbin Heilongjiang 150081，China

Received:2021-06-09 Revised:2021-07-04 Accepted:2021-07-15 Online:2022-04-09 Published:2022-03-10
Contact: Hongbin DONG
About author:LI Xiaohui， born in 1983， Ph. D. candidate， associate professor. Her research interests include machine learning， intelligent information processing.
Supported by:
Key Program of Educational Science Plan of Heilongjiang Province(ZJB1421113)

摘要/Abstract

摘要：

共乘出行应用系统通过提高汽车可用座位容量利用率来减少交通拥堵、缓解停车位紧张，提高社会效益和环境效益。司机和乘客的实时匹配和优化技术是共乘系统的核心内容。基于角色的协同（RBC）是一种用于促进组织结构、提供有序系统行为和协调系统内活动的新方法。为了减少乘客和司机的动态实时匹配时间、提高匹配效率，提出结合RBC和环境-类、代理、角色、群组和对象（E-CARGO）模型形式化共乘问题的方法。在资源容量约束和利润收入给定的情况下，对共乘匹配问题进行建模和仿真实验，提高可用座位容量利用率，实现平台收益最大化，资源匹配合理化。实验结果表明，基于E-CARGO模型的形式化方法可以应用于共乘出行匹配问题建模，最优匹配矩阵和时间可以采用Kuhn-Munkres（K-M）算法和Java中的优化软件包（ILOG）解决方案获得。与ILOG软件包算法相比，K-M算法所用平均时间至少减少了21%；当代理规模大于一定数值（大于600）时，算法时间开销急剧增大。

关键词: 共乘, 匹配算法, Kuhn-Munkres算法, 基于角色的协同, ILOG软件包算法, E-CARGO模型

Abstract:

Ride-sharing application systems can reduce traffic congestion and alleviate parking space tension by increasing the utilization rate of car available seat capacity， thus improving social and environmental benefits. The effective real-time matching and optimization technology of drivers and passengers is one of the core components for a successful ride-sharing system. Role-Based Collaboration （RBC） is an emerging methodology to facilitate an organizational structure， provide orderly system behavior， and coordinate the activities within the system. In order to reduce the dynamic real-time matching time of passengers and drivers， and improve the matching efficiency， a method combining RBC and Environment-Class， Agent， Role， Group and Object （E-CARGO） model was proposed to formalize ride sharing problem. To improve the utilization rate of available seat capacity， maximize platform revenue， and rationalize resource allocation with constraints of entire resource capacity and given profit， the modeling and simulation experiments for ride-sharing matching method were conducted. The experimental results show that the proposed formal method based on E-CARGO model can be applied to the modeling of ride-sharing matching problem， and the optimal matching matrix and time can be obtained by Kuhn-Munkres （K-M） algorithm and ILOG software package in Java. The simulation results show that the average time of K-M algorithm is reduced by 21% at least compared to ILOG software package algorithm. When the agent size is larger than a certain value （more than 600）， the time consumption of the proposed algorithm increases sharply.

Key words: ride-sharing, matching algorithm, Kuhn-Munkres (K-M) algorithm, Role-Based Collaboration (RBC), ILOG software package algorithm, E-CARG (Environment-Class, Agent, Role, Group, Object) model

中图分类号:

TP391

李晓会, 董红斌. 基于E-CARGO模型的共乘出行匹配建模与优化方法[J]. 计算机应用, 2022, 42(3): 778-782.

Xiaohui LI, Hongbin DONG. Modeling and optimization method of ride-sharing matching based on E-CARGO model[J]. Journal of Computer Applications, 2022, 42(3): 778-782.

图/表 5

表1 出行乘客与司机之间的关系

Tab. 1 Relationship between passengers and drivers

司机

数量

司机和乘客之间

一对一的匹配

根据乘客路线与时间，司机与

乘客之间一对多匹配

多个

乘客根据出行路线

换乘不同司机

根据乘客和司机的路线与

时间，各自分别进行多次匹配

图1 共乘中乘客时刻信息

Fig. 1 Time information of passenger in ride-sharing

表2 不同Agent数量下匹配算法时间 (ms)

Tab. 2 Matching algorithm time with different number of Agents

m	最大时间	最小时间	平均时间
10	3.192 6	1.652 7	2.274 4
20	3.328 8	1.736 7	2.580 8
30	3.340 2	1.873 2	2.392 1
40	4.646 5	1.976 8	2.848 1
50	3.341 7	2.044 7	2.645 2
60	4.279 7	1.941 3	3.069 2
70	4.409 1	1.999 4	2.785 4
80	3.971 6	2.025 8	2.689 1
90	3.402 7	2.201 8	2.805 6
100	3.946 1	2.034 7	2.541 1

图2 不同Agent规模下ILOG软件包算法和K-M算法时间性能

Fig. 2 Time performance of ILOG software package algorithm and K-M algorithm with different number of Agents

图3 不同Agent规模下三种算法时间性能比较

Fig. 3 Time performance comparison of three algorithms with different number of Agents

参考文献 28

1	CRAMER J， KRUEGER A B. Disruptive change in the taxi business： the case of uber ［J］. The American Economic Review， 2016， 106（5）： 177-182. 10.1257/aer.p20161002
2	CHEB M J， SHEN W R， TANG P Z， et al. Dispatching through pricing： modeling ride-sharing and designing dynamic prices［C］// Proceedings of the 28th International Joint Conference on Artificial Intelligence. Piscataway： IEEE， 2019：165-171. 10.24963/ijcai.2019/24
3	ZHU H B， ZHOU M C. M-M role-transfer problems and their solutions ［J］. IEEE Transactions on Systems， Man and Cybernetics - Part A： Systems and Humans， 2009， 39（2）： 448-459. 10.1109/tsmca.2008.2009924
4	ZHU H B， HOU M， WANG C， et al. An efficient outpatient scheduling approach ［J］. IEEE Transactions on Automation Science and Engineering， 2012， 9（4）： 701-709. 10.1109/tase.2012.2207453
5	ZHU H B. Role mechanism in collaborative systems ［J］. International Journal of Production Research， 2006， 44（1）： 181-193. 10.1080/00207540500247495
6	ZHU H B， ZHOU M C. Efficient role transfer based on Kuhn-Munkres algorithm ［J］. IEEE Transactions on Systems， Man and Cybernetics - Part A： Systems and Humans， 2012， 42（2）： 491-496. 10.1109/tsmca.2011.2159587
7	MUNKRES J. Algorithms for the assignment and transportation problems ［J］. Journal of the Society for Industrial and Applied Mathematics， 1957， 5（1）：32-38. 10.1137/0105003
8	KUHN H W， YAW B. The Hungarian method for the assignment problem ［J］. Naval Research Logistics， 1955， 52（1）：83-97.
9	DUTTA J， PAL S C. A note on Hungarian method for solving assignment problem ［J］. Journal of Information and Optimization Sciences， 2015， 36（5）：451-459. 10.1080/02522667.2014.926711
10	GHOSEIRI K， HAGHANI A， HAMEDI M. Real-time rideshare matching problem ［EB/OL］.［2021-06-22］. .
11	LOPEZ A， JIN W L. Security analysis for fixed-time traffic control systems ［J］. Transportation Research Part B： Methodological， 2020， 139：473-495. 10.1016/j.trb.2020.07.002
12	DAILEY D J， LOSEFF D， MEYERS D. Seattle smart traveler： dynamic ride matching on the world wide web ［J］. Transportation Research Part C： Emerging Technologies， 1999， 7（1）： 17-32. 10.1016/s0968-090x(99)00007-8
13	WANG X L， YANG H， ZHU D L. Driver-rider cost sharing strategies and equilibrium in a ridesharing program ［J］. Transportation Science， 2018， 52（4）： 739-1034. 10.1287/trsc.2017.0801
14	AGATZ N A H， ERERA A， SAVELSBERGH M W P， et al. Dynamic ride-sharing： a simulation study in metro atlanta ［J］. Transportation Research Part B： Methodological， 2011， 45（9）： 1450-1464. 10.1016/j.trb.2011.05.017
15	KLEINER A， NEBEL B， ZIPARO V. A mechanism for dynamic ride sharing based on parallel auctions ［C］// Proceedings of the 22th International Joint Conference on Artificial Intelligence. Piscataway： IEEE， 2011： 266-272.
16	SUN H， WANG H， WAN Z X. Model and analysis of labor supply for ride-sharing platforms in the presence of sample self-selection and endogeneity ［J］. Transportation Research Part B： Methodological， 2019， 125：76-93. 10.1016/j.trb.2019.04.004
17	CACHON G P， DANIELS K， LOBEL R. The role of surge pricing on a service platform with self-scheduling capacity ［J］. Social Science Research Network Electronic Journal，2015，19（3）：368-384.
18	ALONSO-MORA J， SAMARANAYAKE S， WALLAR A， et al. On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment ［J］. Proceedings of the National Academy of Sciences of the United States of America， 2017， 114（3）：462-467. 10.1073/pnas.1611675114
19	CALVO R W， FABIO D L， HAASTRUP P， et al. A distributed geographic information system for the daily car pooling problem ［J］. Computers & Operations Research， 2004， 31（13）： 2263-2278. 10.1016/s0305-0548(03)00186-2
20	刘冬宁，刘统武，宋静静，等. 面向基站代维人员分工协作优化的多重指派研究［J］. 广东工业大学学报， 2018， 35（6）： 69-76. 10.12052/gdutxb.180062
	LIU D N， LIU T W， SONG J J， et al. Multiple assignment in task allocation of communication base stations ［J］. Journal of Guangdong University of Technology， 2018， 35（6）： 69-76. 10.12052/gdutxb.180062
21	罗沛. 群组角色协同多对多推荐算法研究［D］. 广州：广东工业大学， 2019：15-23.（LUO P. M2M Recommendation via group multi-role assignment ［D］. Guangzhou： Guangdong University of Technology， 2019：15-23.）
22	刘冬宁，袁云钇，黄宝莹，等. 基于E-CARGO模型的志愿型偏好平衡性指派［J］. 工业工程， 2018， 21（2）： 68-74. 10.3969/j.issn.1007-7375.e16-1318
	LIU D N， YUAN Y Y， HUANG B Y， et al. Balanced assignment of voluntary type’s preference based on E-CARGO ［J］. Industrial Engineering Journal， 2018， 21（2）： 68-74. 10.3969/j.issn.1007-7375.e16-1318
23	滕少华，张如琪，刘冬宁，等. 基于角色协同的角色扮演逻辑机器代数模型［J］. 电子学报， 2017， 45（12）： 3012-3018.
	TENG S H， ZHANG R Q， LIU D N， et al. Role playing logic and its algebra model in role-based collaboration ［J］. Acta Electronica Sinica， 2017， 45（12）： 3012-3018.
24	ZHU H B， ZHOU M C. Role-based collaboration and its kernel mechanisms ［J］. IEEE Transactions on Systems， Man and Cybernetics， Part C （Applications and Reviews）， 2006， 36（4）： 578-589. 10.1109/tsmcc.2006.875726
25	ZHU H B， ZHOU M C， ALKINS R. Group role assignment via a Kuhn-Munkres algorithm-based solution ［J］. IEEE Transactions on Systems， Man and Cybernetics - Part A： Systems and Humans， 2012， 42（3）： 739-750. 10.1109/tsmca.2011.2170414
26	ZHU H B， LIU D N， ZHANG S Q， et al. Solving the group multirole assignment problem by improving the ILOG approach［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2017， 47（12）：3418-3424. 10.1109/tsmc.2016.2566680
27	易欣，郭武士，赵丽.利用自适应选择算子结合遗传算法的机器人路径规划方法［J］. 计算机应用研究， 2020， 37（6）： 1745-1749. 10.19734/j.issn.1001-3695.2018.11.0874
	YI X， GUO W S， ZHAO L. Robot motion planning based on adaptive selection operator combined with genetic algorithm ［J］. Application Research of Computers， 2020， 37（6）： 1745-1749. 10.19734/j.issn.1001-3695.2018.11.0874
28	陈思语. 基于E-CARGO模型的再分配问题研究［D］. 长沙：湖南师范大学， 2018：18-20.
	CHEN S Y. Research on re-assignment problem based on E-CARGO model ［D］. Changsha： Hunan Normal University， 2018：18-20.

[1]	李炜, 吴群群, 张以文. 基于E-CARGO模型的开发者推荐方法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 557-564.
[2]	段宗涛, 龚学辉, 唐蕾, 陈柘. 共享交通的时空轨迹检索与群体发现[J]. 计算机应用, 2019, 39(1): 220-226.
[3]	张志强孙超. 自动气象站质量控制系统中覆盖软件的设计与实现[J]. 计算机应用, 2013, 33(04): 1169-1172.
[4]	石敏易清明. 一种有效的自适应运动估计搜索算法[J]. 计算机应用, 2008, 28(6): 1504-1506.
[5]	刘新刘任任. 一种基于逆向匹配算法的中文文本分类技术[J]. 计算机应用, 2008, 28(4): 945-947.
[6]	郭军文玉梅李平叶波李潇. 一种新的步态图像序列分割算法[J]. 计算机应用, 2007, 27(8): 2047-2050.
[7]	马建军唐进君曹凯. 一种新的智能地图匹配算法[J]. 计算机应用, 2007, (12): 3116-3118.
[8]	胡志刚胡周君 . 一种基于预测的资源匹配算法[J]. 计算机应用, 2007, 27(10): 2391-2394.
[9]	余志雄; 孙洪; 贺军. 基于低频子图的运动估计算法[J]. 计算机应用, 2006, 26(5): 1024-1026.
[10]	张培珍; 江华俊; 沈玉利. 自适应块匹配搜索算法研究[J]. 计算机应用, 2006, 26(4): 797-798.
[11]	员红娟叶飞跃李霞彭文滔 . 基于语义的Web服务发现核心技术研究[J]. 计算机应用, 2006, 26(11): 2661-2663.
[12]	卢达;浦炜;陈琦玮;谢铭培. 基于神经网络和模糊匹配算法的手写汉字预分类研究[J]. 计算机应用, 2005, 25(10): 2418-2421.
[13]	刘国翌，李华. 平板图案的跟踪及其在增强现实中的应用[J]. 计算机应用, 2005, 25(07): 1605-1607.
[14]	陈耀东，王挺. 基于有向图的双向匹配分词算法及实现[J]. 计算机应用, 2005, 25(06): 1442-1444.
[15]	唐辉，张国杰，黄建华，李祖鹏. 一种混合P2P网络模型研究与设计[J]. 计算机应用, 2005, 25(03): 521-524.

基于E-CARGO模型的共乘出行匹配建模与优化方法

Modeling and optimization method of ride-sharing matching based on E-CARGO model

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 28

相关文章 15

编辑推荐

Metrics