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

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

作　　者：李晓会 董红斌[1] LI Xiaohui;DONG Hongbin(College of Computer Science and Technology,Harbin Engineering University,Harbin Heilongjiang 150001,China;School of Electronic and Information Engineering,Harbin Vocational and Technical College,Harbin Heilongjiang 150081,China)

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001 [2]哈尔滨职业技术学院电子与信息工程学院,哈尔滨150081

出　　处：《计算机应用》2022年第3期778-782,共5页journal of Computer Applications

基　　金：黑龙江省教育科学规划重点项目(ZJB1421113,GJB1421251)。

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]