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

Social sharing by car problem based on graph constraint coalition formation

对社会共享乘车问题进行研究。在对图约束联盟形成及其求解分析的基础上,将社会共享乘车问题转化为一个受社交网络约束的图约束联盟形成问题;建立起一个社会共享乘车问题模型,得到该问题模型的最佳联盟结构以及最优路径,采用一种改进的分支定界方法来求解这个社会共享乘车问题,使该系统的社会福利最大化。实验结果表明,提出算法模型能够改善社会福利,为中等规模的系统快速高效地获得最优解且为大规模的系统获得质量保证的近似解。

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.