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

朱丽华，龙海侠

(1.安阳工学院 计算机科学与信息工程学院，河南 安阳 455000；2.海南师范大学 信息科学技术学院，海南 海口 571158)

0 引 言

随着社会经济的发展和人们工作节奏步伐的加快，实时共享乘车(俗称拼车)正在迅速改变人们每天上下班往返或其它活动的交通出行方式。实时共享乘车最早起源于少数西方发达国家，然后迅速引进到国内。如美国著名的优步(Uber)和来福车(Lyft)，以及国内的滴滴、首约汽车和曹操出行等网约车公司。这种网约车公司的一个明显特征是要建立一个用户社区(或称共同体)，其中上下班往返的人(或称通勤者)可以对驾驶员/乘客进行评分，然后利用这些信息自动形成彼此了解/信任的通勤者群体，以降低相关的交通成本。本文将这个问题称为社会共享乘车(social sharing by car，SSC)问题。

本文将SSC问题转换为一个图约束联盟形成(graph constraint coalition formation，GCCF)问题，其中的通勤者(即乘客和司机)组成联盟(即加入一辆车)，以满足由社交网络施加的约束(即用户更愿意与他们的朋友一起加入一辆车)。具体来说，根据关于GCCF的相关文献[1,2]，只有当参与这个联盟的通勤者构成社交网络的一个连通子图时，认为一个联盟是可行的。

近年来，有一些文献针对SSC问题和GCCF问题进行研究；文献[3]将网约拼车匹配与路径优化问题考虑为静态车辆路径问题，构建了网约拼车匹配与路径优化模型；文献[4]提出了一种基于数据挖掘的城市上下班拼车线路优化拟合的方法；文献[5]研究了与拼车相关方面的计算，提出了一种模型来评价拼车计划；……