一种稳定匹配的任务分配策略研究  

Research on matching stability for assignment allocation strategy

作　　者：高欣 周绍峰 柳絮 孙茂圣 GAO Xin;ZHOU Shaofeng;LIU Xu;SUN Maosheng(College of Information Engineering,Yangzhou University,Yangzhou 225127,China;Office of Informationization Construction and Administration,Yangzhou University,Yangzhou 225127,China;School of Information Engineering,Jiangsu College of Tourism,Yangzhou 225131,China)

机构地区：[1]扬州大学信息工程学院,扬州222512 [2]扬州大学信息化建设与管理处,扬州222512 [3]江苏旅游职业学院信息工程学院,扬州225131

出　　处：《江苏科技大学学报（自然科学版）》2022年第3期85-92,共8页Journal of Jiangsu University of Science and Technology:Natural Science Edition

基　　金：国家自然科学基金资助项目(61872313);江苏省教育信息化研究重点课题(20180012);扬州市科技计划项目(YZ2019133,YZ2020174);江苏省应急管理厅科技项目(YJGL-YF-2021-3,YJGL-YF-2020-17)。

摘　　要：网约车订单任务分配策略的核心目标在于提高司机和乘客利益,但提高利益并不能保证利益相关方的每个个体均获得更高的利益,故会出现利益分配不均的情况.针对上述问题,通过建立非共享出行和共享出行的订单任务分配模型,使用稳定匹配算法获得订单任务的稳定匹配结果.在非共享出行模型中提出了基于延迟接受的迭代算法,以获得最优稳定匹配结果.同时,为进一步优化稳定匹配结果,还提出了一种通过打破现有稳定匹配对的算法以获取全部稳定匹配.在共享出行模型中,将稳定匹配算法分为最大集合打包问题和匹配问题两个步骤进行求解,利用近似算法解决最大集合打包问题,用稳定匹配算法解决稳定匹配问题.最后,在纽约市出租车数据集TCL上通过模拟实验,与其他主流算法从匹配延迟时间、乘客利益、司机利益等评估指标进行了比较与分析,验证文中所提模型的有效性和可行性.The main goal of the online car-hailing order assignment allocation strategy is to improve the interests of drivers and passengers,however,the improvement of interests does not guarantee that each individual of the stakeholders will get higher benefits,so the uneven distribution of benefits will occur.In order to solve the above issues,the order tasks allocation models of non-shared travel mode and shared travel mode are established,and the stable matching algorithm is used to obtain the stable matching results of order tasks.An iterative algorithm based on delayed acceptance is proposed in the non-shared travel model to obtain the optimal stable matching result of the active party,meanwhile,in order to further optimize the stable matching results,an algorithm is proposed to obtain all stable matching pairs by breaking existing stable matching pairs.In the shared travel model,solving the stable matching is divided into two steps:maximum set packing problem and stable matching problem,the approximate algorithm is used to solve the maximum set packing problem,and the stable matching algorithm is used to solve the stable matching problem.Finally,through simulation experiments and test on the taxi data set of New York city TCL,the proposed model is compared and analyzed with other mainstream algorithms in terms of matching delay time,passenger benefits,driver benefits and other evaluation indexes,which verifies the effectiveness and feasibility of the proposed model.

关 键 词：网约车 订单任务分配策略 稳定匹配 

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