唐 蕾 孙 晨 段宗涛 陈 柘

(长安大学信息工程学院 陕西 西安 710064)

0 引 言

共乘是一种新兴的交通方式，既环保又可持续，因为它不仅能让乘客节省出行成本[1]，比如燃料、通行费和停车费，还能减少汽车的交通拥堵和交通拥堵。共乘，也就是所谓的拼车，将人们(代理)从特定起点到特定目的地的汽车共享。

现有多Agent系统交互系统主要考虑在无目标冲突的情况下各Agent的相互帮助,实现目标。这种研究并不适合于共乘出行下利益驱动的司乘人员协商过程。考虑到共乘出行系统中，司机和乘客具有智能、自治活动，且处于资源有限、动态演化的交通环境中，针对以上问题，本文提出了一种基于群Agent协同交互的共乘出行仿真模型。采用Agent技术模拟司机与乘客出行活动，并支持两者在出行利益不一致的情况下，通过交互机制，逐步实施协调，调整其与环境的关系，改变不同Agent之间的行为，以仿真完整的共乘出行。本文所做的贡献包括：(1) 基于多Agent技术和共乘过程，提出了一种群代理协同交互的仿真模型；(2) 提出了路径匹配模型和协商模型，并通过大量的实验数据说明该模型准确性和高效性。

1 相关工作

1.1 多Agent技术

智能协作信息技术也称基于Agent的技术[2]。在软件工程领域,Agent一般被描述为:一个处于特定环境中,能感知并灵活、自主地适应环境,可以代理实现一定任务的具有较高自治能力的计算机实体。Agent具有社会性、自主性、反应性、主动性。由于单Agent在解决大型复杂问题时,难以满足实际需求。多Agent系统的设计目标就是解决单Agent系统所不能解决的复杂问题，已经成为目前研究的热点。

作为人工智能的一项重要研究,多Agent技术主要研究一组自治的Agent在分布式开放的动态环境下,通过交互、合作、竞争、协商等智能行为完成复杂的控制或任务求解。由于它更能体现人类的社会智能,更加适合开放的,动态的社会环境,因而在共乘出行下，多Agent技术可通过交互、协商等行为完成复杂的出行计划制定以及动态乘客搭乘任务求解。

1.2 共乘出行

随着定位技术、移动网络的发展和智能终端的普及，终端设备、即时通信、社交网络每天都在产生海量数据，而这些数据量也会随着时间迅速增长。以江苏省为例，其交通轨迹数据已高达500多亿条、100多TB，每日新增数据量7 000万条、150多GB[3]。以海量个人的实时出行数据、交通信息数据、社交媒体数据等为代表的大数据背景为智能交通系统发展带来了新的机遇[4]。

近年来智能共乘平台逐步普及发展。国外已涌现出Avego[5]、zimride[6]、Carpooling、Blablacar[7]等共乘平台，Uber[8]、Lyft[9]用车平台也推出拼车服务。国内的共乘业务相对起步较晚，在杭州、北京等城市，相继出现了民间自发组织的拼车，如武汉的邻里合乘[10]项目，2008年北京因为奥运期间限行而自发组织的拼车等。近年随着滴滴[11]、神州专车等智能终端叫车业务的发展，国内用户也已经接受通过智能终端叫车的出行方式。共乘业务服务商也如雨后春笋般涌现，已有用车、滴滴顺风车等数十个拼车平台，并在上下班通勤中得到了大量应用。

共乘[12-13]也被称为“拼车”、“合乘”、“顺风车”，通过有效整合运力资源和减少道路上行驶车辆的数量，对缓解交通堵塞、降低出行成本、减轻环境污染都有重要意义。为了更好地提高共乘资源利用率，所以研究学者提出了动态共乘的概念[14]，并有大量研究工作，在提高匹配度[15-18]、降低行程开销、减少用户请求响应时间等方面展开了深入研究，其中许多研究是基于真实出行数据集进行了测试仿真。

共乘，就是把一辆车从一个人(代理)到一个特定的目的地共享。因此，为了研究共乘概念，我们应该考虑到在整个共乘过程中两个或多个代理的相互作用。共乘的过程包括若干步骤，即:(1) 创建共乘的动机；(2) 将此动机与其他代理沟通；(3) 与感兴趣的代理协商计划；(4) 执行商定的计划；(5) 向所有有关的代理提供反馈。创建一个动机意味着旅行者(代理)可以选择共乘，因为旅游资源、时间、货币和路线成本约束的可用性。此外，一些社会经济因素的变化，如燃料价格的增加、停车费用，或在新交通政策的实施中，可能会引发对合伙用车的倡议。

2 共乘模型框架

本文采用基于三层架构的JADE平台，包括MAS Architecture、JADE Platform与RIDESHARE System。其中，多代理系统架构提供共乘出行背景下的一些约束条件，通过这些约束条件产生共乘出行的动机模型、(路径)匹配模型和协商模型。比如，司机的(出发)位置信息、目的地、出发时间、到达时间、座位数、信誉度，乘客的(出发)位置信息、目的地、出发时间以及到达时间。

JADE平台主要包括Agent Management System(AMS)和消息传输系统(Message Transport System，MTS)。

共乘系统支持在一组约束条件下，司机Agent和乘客Agent通过动机模型、(路径)匹配模型与协商模型等，达到共乘出行规划制定与执行。图1给出了群代理协同交互的共乘出行服务执行框架。

图1 群代理协同交互的共乘出行服务执行框架

首先通过对乘客代理和司机代理的POI签到数据进行预处理，生成一组出行约束条件，其中约束条件包括司机的出发位置信息、目的地、出发时间、到达时间、座位数以及信誉度，和乘客的出发位置信息、目的地、出发时间以及到达时间。在出行约束条件下，司机代理产生共乘动机，构造动机模型。动机模型的描述为Agent(出发时间、达到时间、目的地)。如，司机Agent(10:07，11:10，利民誉印服务社)乘客Agent(10:31，10:44，清华大学)。司机代理将共乘动机与多个乘客代理进行沟通协商，将协商结果形成路径匹配模型。该模型主要用于搜寻司机Agent和乘客Agent的相似路径。满足路径匹配模型的司机Agent和乘客Agent进行共乘协商，生成协商模型。协商的内容主要包括司机Agent和乘客Agent出发时间与到达时间。通过代理管理系统，从而得到司机代理和乘客代理的动机模型、路径匹配模型、协商模型。在JADE平台中，AMS通过动机模型、路径匹配模型与协商模型，生成司机Agent和乘客Agent之间的共乘系统。在整个仿真系统的运行当中，多代理之间的交互是通过消息传输系统(MTS)完成的。

3 模型的建立

3.1 路径匹配模型

设OA、OB分别表示司机和乘客的出发地点，DA、DB分别表示司机和乘客目的地。假定乘客行驶路线在司机的行驶路线上。表1是运用前期工作[19]得到的POI(Points of interest)数据实例。

表1 部分poi数据

根据欧式距离公式，确定两个位置之间的距离：

(1)

式中：WA、WB表示A、B两点的纬度，JA、JB表示A、B两点的经度，R表示地球半径，取值为6 378 137.0米。OA、OB分别表示顺如风单车和圆明园遗址公园，DA、DB分别表示利民誉印服务社和清华大学。

运用下式计算单位距离上所消耗的时间成本:

(2)

式中：d表示路程花费的时间，l表示距离长度。d(OA,DA)、d(OA,OB)、d(OB,DB)、d(DB,DA)分别表示OA到DA、OA到OB、OB到DB、DB到DA的路程所用的时间。

用下式计算司机Agent和乘客Agent的路径相似度：

(3)

式(3)表明，路径相似度越大，司机Agent和乘客Agent的相似度越高,共乘概率越高。路径匹配模型用于通过相似度搜寻司机Agent和乘客Agent的相似路径。

假定乘客的出发地点OB不在司机的行驶路线上，但乘客的目的地DB在司机行驶路线上。

Case1:假定OA、OB、DB、DA在一条直线上，如图2所示。

图2 B的出发点在A的行驶路线上

Case2:假定OB和OA、DB、DA不在一条直线上，如图3所示。

图3 B的出发点不在A的行驶路线上

随着垂直距离x的增加，可以计算出不同的pathSim值。在后续的实验中对于以上两种情形，我们采取部分POI数据集对路径相似度公式进行验证，结果表明随着垂直距离x的增加路径相似度在减小。

3.2 最短路径算法

算法1给出了改进的A*算法，该算法用于计算所有的最短路径。该算法使用最佳优先搜索，找到从给定的初始道路到一个目标段的最小成本路径。最佳优先搜索是一种启发式搜索算法，可以将它看作广度优先搜索算法的一种改进。启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用不同的估价可以有不同的效果。估价函数就是从当前节点移动到目标节点的预估费用，这个估计就是启发式的。当A*遍历道路图时，它遵循一条预期总成本或距离最低的路径，沿途保持备用路径段优先队列级的顺序。该算法使用两个基础函数：(1) 过去路径成本函数g(x)，表示从开始片段到当前片段x的距离；(2) 将来路径成本函数h(x),表示当前片段x到目的地距离的评估。h(x)一定是允许启发式的，也就是说，它不能高估目标的距离。因此，对于像路径选择的应用来说h(x)代表了到目的地的直线距离，因为这是物理意义上在任意两点或节点之间的最小可能距离。

算法1改进的A*算法

1 function ASTAR(start,goal)

2cset←φ

3oset←{start}

4came_from[start]←nil

5g[start]←0

6v[start]←g[start]+h(start,goal)

7 whileosetdo

8c←{s|∀(m,s)∈oset2,v[s]≤v[m]}

9 ifc=goal

10p←<>

11 whilegoaldo

12p←·p

13goal←came_from[goal]

14 end while

15 returnp

16 end if

17oset←oset-{c}

18cset←cset∪{c}

19 for alln∈neightbor(c) do

20ng←g[c]+distance(c,n)

21 ifn∉oset∨ng

22came_from[n]←c

23g[n]←ng

24v[n]←g[n]+h[n,goal]

25oset←oset∪{n}

26 end if

27 end for

28 end while

29 return <>

30 end function

3.3 协商模型

为了共乘通勤，个体需要沟通、协商和协调，在大多数情况下，调整他们的日常时间表，使其达到合作。通过协商，代理可以反复地达成复杂协议。然而在本文中，我们专注于提出的谈判机制，有效地代表了实际人们基于若干影响因素的偏好行为。为了使协商机制更加精确，将一种方法引入到特定的个性化偏好函数中。所建议的偏好函数用于选择最优的出行时间，部分来自现有的出发时间，其研究基于许多因素：旅行因素、社会经济因素和时间压力因素。对于在共乘协商过程中出发时间的选择，现有的研究集中在可用的时间窗内的每个个体的恒定偏好。本文只去协商司机代理和乘客代理的出发时间。

TWUpper,ai=PSTTrip,ai+ΔT

我们认为协商结果与代理的时间间隔的交集长度有关。下式给出了协商后共乘出发时间的上下界；

TWLower,carpool=max(TWLower,ai)
TWUpper,carpool=min(TWUpper,ai)

下式给出了共乘可用的时间间隔：

TIntervals=min(TWUpper,ai)-max(TWLower,ai)

4 系统仿真实验与测试分析

4.1 系统实现

启动GUI管理器，然后在Main Container栏单击右键选择Start New Agent分别添加r1 com.sharing.CarMPReceiverAgent、a1 com.sharing.DriverSD Agent、a2 com.sharing.PassengerSDAgent三个代理如图4所示。

(a)

(b)图4 在GUI容器里添加代理

对以上的匹配模型和协商模型进行了编程实现。实验平台Eclipse、Java语言、JADE平台。图5显示了司机Agent和乘客Agent的共乘结果以及他们在出发前协商的结果，即Driver2(司机2)与乘1(乘客)、乘2、乘3、乘4、乘6共乘，剩余的座位数为1。以及共乘有效的时间间隔。在有效的时间间隔里，司机可以接受与乘客共乘，否则拒绝共乘。本系统通过司机和乘客的出发时间、到达时间、出发地点、到达地点，路径相似度、座位数等约束条件进行共乘匹配。系统功能完整且符合实际应用，系统性能较高，其中匹配算法时间复杂度为O(n2),鉴于现阶段高效CPU和较大内存空间，本系统运行时间为48 842毫秒。

图5 共乘界面显示

4.2 模型性能分析

实验数据是选取在西安市区域内15天的出租车营运轨迹数据，在不同时间窗口下对共乘进行了对比分析。

图6(a)显示了在15天里司机和乘客共乘组的数量，其中，从趋势线可以看出该共乘组的数量趋于40到50范围内。横轴代表时间，纵轴代表共乘组的数量。

图6(b)显示了在15天里5 min、10 min、15 min、20 min、25 min、30 min时间窗口下共乘数量。横轴代表时间，纵轴代表共乘组的数量。从图中可以看出，时间窗口越小，共乘数量越多。由于出租车本身本身的运营性质和经济效益因素，司机会在最短的时间里去寻找到需要共乘的乘客，从而产生经济效益。在同一时间窗口下的共乘数量基本稳定在一定区域范围内。

(a) 某一时间窗口下共乘组数差

(b) 不同时间窗口下共乘数量图6 15天内司机与乘客共乘组的数量

利用表1的POI数据结合Case1和Case2对相似度公式进行验证，分别令x0、x1、x2、x3、x4、x5为100、150、200、250、300、350时，路径相似度pathSim会随着垂直距离x的逐渐增大而减小。如图7所示，其中横轴代表垂直距离x，纵轴代表路径相似度。

图7 路径相似度渐变趋势

通过POI数据源对协商模型进仿真实验，得表2数据。

表2 poi仿真数据源 min

纵轴上分别表示代理d1、p1、p2、p3、p4、p5、p6，即表示司机1、乘客1到乘客6。

通过表2数据利用协商模型的公式可以得到该共乘出行活动的时间窗口的上下界：

TWUpper,carpool=min(TWUpper,ai)=34 min
TWLower,carpool=max(TWLower,ai)=10 min

从而可以得到共乘过程中有效的时间间隔为：

TIntervals=min(TWUpper,ai)-max(TWLower,ai)=24 min

通过该数据源，我们对协商模型公式进行了验证，可以得到有效的共乘时间间隔，同时验证了我们所提出的公式的有效性。

5 结 语

本文提出了一种基于群代理协同交互的共乘出行仿真模型框架，并对该模型框架的建立进行了详细的阐述。其中，对路径匹配模型和协商模型进行了公式建模，给出了最短路径算法，并且利用真实的POI数据源和出租车营运轨迹数据对匹配模型和协商模型进行了具体的仿真实验。实验表明了路径匹配模型和协商模型的高效性和准确性。在未来的工作中，本文将分析共乘过程中反馈因素、以及社交网络、代理偏好等多重约束因素，进而提高司机和乘客共乘的匹配效率。