基于图约束联盟形成的社会共享乘车问题  

Social sharing by car problem based on graph constraint coalition formation

作　　者：朱丽华[1] 龙海侠[2] ZHU Li-hua;LONG Hai-xia(School of Computer Science and Information Engineering,Anyang Institute of Technology,Anyang 455000,China;School of Information Science Technology,Hainan Normal University,Haikou 571158,China)

机构地区：[1]安阳工学院计算机科学与信息工程学院,河南安阳455000 [2]海南师范大学信息科学技术学院,海南海口571158

出　　处：《计算机工程与设计》2021年第4期1089-1095,共7页Computer Engineering and Design

基　　金：国家自然科学基金项目(61762034);海南省自然科学基金项目(618MS057)。

摘　　要：对社会共享乘车问题进行研究。在对图约束联盟形成及其求解分析的基础上,将社会共享乘车问题转化为一个受社交网络约束的图约束联盟形成问题;建立起一个社会共享乘车问题模型,得到该问题模型的最佳联盟结构以及最优路径,采用一种改进的分支定界方法来求解这个社会共享乘车问题,使该系统的社会福利最大化。实验结果表明,提出算法模型能够改善社会福利,为中等规模的系统快速高效地获得最优解且为大规模的系统获得质量保证的近似解。A study of social sharing by car problem was carried out.On the basis of analysis for graph constraint coalition formation and its solving,a problem of social sharing by car was converted into a problem of graph constraint coalition formation mee-ting the constraints imposed by the social network.A model of social sharing by car problem was established,and the optimal coalition structure and the optimal path were obtained,and an improved branch and bound method was used to solve this social sharing by car problem,so as to maximize the social welfare of the system.Experimental results show that the proposed algorithm model can not only improve the social welfare,but obtain the optimal solution quickly and efficiently for the medium scale system and the approximate solution with quality assurance for the large scale system.

关 键 词：共享乘车 联盟结构生成 最优路径 代理 成本函数 福利改善 运行时间 

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