一種基于群代理協同交互的共乘出行仿真模型

唐 蕾 孫 晨 段宗濤 陳 柘

(長安大學信息工程學院 陜西 西安 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數據源和出租車營運軌跡數據對匹配模型和協商模型進行了具體的仿真實驗。實驗表明了路徑匹配模型和協商模型的高效性和準確性。在未來的工作中，本文將分析共乘過程中反饋因素、以及社交網絡、代理偏好等多重約束因素，進而提高司機和乘客共乘的匹配效率。