基于ＤＣＯＭ的動態運輸調度多智能體系統研究
2009-01-01 00:00:00徐麗群李斌
計算機應用研究 2009年3期
（上海交通大學 安泰經濟與管理學院， 上海 200052）
摘 要：針對物流運輸調度中的客戶需求動態性和隨機性問題的解決，設計了一種基于DCOM的動態運輸調度多智能體系統。在多智能體系統中，設計了包括預規劃智能體、實時監控智能體、決策智能體和車輛智能體四類智能體。智能體以DCOM式組件形式實現，智能體之間的通信和協調由決策智能體集中執行。通過一個實例驗證了系統算法的有效性，同時也為動態運輸調度問題的解決提供了一個可參考的思路。
關鍵詞：動態運輸調度； 多智能體系統； 物流
中圖分類號：TP18 文獻標志碼：A
文章編號：10013695(2009)03094904
Research on multiagent system of dynamic transportation
scheduling based on DCOM
XU Liqun， LI Bin
(Antai College of Economics Management， Shanghai Jiaotong University， Shanghai 200052， China)
Abstract:Aiming at solving the problems of the dynamic and random customers’ demand， this paper designed a multiagent system of dynamic transportation scheduling based on DCOM. This system contained planning agent， realtime surveillance agent， decisionmaking agent and vehicle agent， operated the communication and cooperation among the agents by decisionmaking agent. Used a case to prove the validity of this system and algorithm， as well as the result indicates that this system can be used to solve the problems of the dynamic transportation scheduling.
Key words：dynamic transportation scheduling; multiagent system; logistics
國外將物流配送中的運輸調度問題歸結為vehicle scheduling problem，最早由Dantzig和Ramser于1959年首次提出，很快引起運籌學、應用數學、組合數學、圖論和網絡分析、物流科學、計算機應用等學科的專家、運輸計劃制訂者和管理者的極大重視，成為運籌學與組合優化領域的前沿和研究熱點問題。按照組織的行車路線的輸出是不是一條預先規劃好的路線，并且會不會被重新優化，運輸調度問題可以分為靜態和動態兩類。
動態運輸調度（DTS）問題是基于靜態運輸調度問題提出的，Psaraftis[1]對運輸調度問題是這樣定義的：如果一個運輸調度問題的輸出是一條預先規劃好的路線，并且這條線路不會被重新優化，而是根據事先知道的輸入進行優化計算得出來的，那么這個問題就是靜態的；反之，如果一個運輸調度問題的輸出不是一條預先規劃好的路線，這個問題就是動態的。DTS問題更適合于描述在現代物流運輸中的實際運輸調度情況。
人工智能現在廣泛應用于自主規劃和調度、博弈、自主控制、診斷、機器人技術、語言理解和問題求解。一般地，人工智能被定義為對從環境中接收感知信息并執行行動的agent的研究[2]。多智能體系統(multiagent system， MAS)是分布式人工智能研究的一個子領域，它是由多個智能體組成，每一個智能體都是一個自治或半自治系統。它們既可以各自完成局部問題求解，而且還能協作地求解單個目標問題或多個目標問題[2]。本文基于DCOM技術，建立了DTS多智能體系統，對系統模型框架、思想和算法等進行了研究。最后的實例分析表明，面向DTS的多智能體系統能很好地解決DTS問題，提高物流運輸系統效率。
1 DTS多智能體系統框架
1.1 系統特點
針對DTS問題的解決，建立的多智能體系統應具備下列功能：
a）實時了解顧客的動態需求。因為顧客請求可能通過網絡、電話、傳真等各種方式傳遞過來，所以智能化系統應包括需求信息收集模塊。
b）實時了解服務區域內的交通流狀況。這要求智能化系統要有與智能交通系統 (intelligent transportation systems， ITS)的信息接口，負責與ITS的溝通協調。
c）熟悉服務區域的交通網絡，以便實時對路線規劃作出重新安排。
d）存儲大量歷史數據，作為發現DTS問題周期的基礎。
e）有一定的求解最優解的能力。
f）較強的與人交互的能力，以便獲取專家知識，以及專家重新設定目標，對運輸調度進行人工干預。
為了實現上述功能，需要解決的問題是：
a）需要的數據分散，所求解的問題都是NP難題，要求的反應速度很快。
b）應用的協商、協調和信息共享之間的相互關系復雜。
c）問題的解決是不可能事先從頭到尾對問題進行預知，因此問題的解決者應該能夠對變化及時地進行響應。
由此可以看出，最好的解決方法是根據目標功能的不同集合建立起相應的智能體，最后組成一個多智能體系統，通過他們的相互協作，在及時了解動態信息的基礎上按一定的目標優化整個運輸調度。在這個意義下，智能體可以被看做封裝了的具有下列屬性的問題解決實體。
1）自治性 智能體在完成其主要任務時不需要人或其他智能體干涉，它能完全控制自身的行為和內部狀態。
2）社會性 智能體與人或其他智能體相互作用，以完成自身或其他智能體的活動，這需要智能體具有最起碼的通信能力和內部機制，以決定通信的時間和內容。
3）反應力 智能體應該能夠感受環境，并對環境的變化產生反應。
4）主動性 智能體不僅僅能夠被動地對環境產生反應，還應該在目標驅使下具有主動采取行動的能力。
1.2 DTS多智能體系統框架
根據企業DTS問題背景和要實現的功能，本文建立的DTS多智能體系統模型框架如圖1所示。
圖1所示的DTS多智能體系統模型框架包含四類智能體：
a）預規劃智能體。它主要負責利用動態運輸調度問題的周期性預規劃出一條最優的車輛運輸路徑。為此，該智能體需要維護一個龐大的歷史運輸調度路徑數據庫作為知識庫，在計算出對應時期的周期和重復度的基礎上，利用Apriori方法進行路線優化，輸出的結果是一條預規劃的車輛運輸路徑。
b）實時監控智能體。它主要負責實時監控交通流，該智能體與ITS系統通信，收集本服務區的交通網絡現狀，在發生擁堵或決策智能體請求等情況下，提供替換路徑給決策智能體。為此，該智能體需要維護一個本區域交通網絡的地圖數據庫或GIS。根據ITS將來的發展前景與ITS協商，從而確定合適的交通運輸路徑也將可能是該智能體的主要功能。
c）決策智能體。它是核心智能體，負責動態發布調度命令。該智能體以運輸調度專家知識作為知識庫，在一定目標的指引下，以預規劃的車輛運輸路徑為藍圖，在動態的訂單處理系統、實時監控智能體信息的刺激下，動態調整車輛運輸路徑。當然，該智能體還需要一個人機交互界面，使專家能在合適的時候對運輸調度加以干預。由于決策智能體要與其他各智能體進行頻繁、大量的通信，在決策智能體中應建立一個黑板（多智能體系統的公用數據庫），用來傳遞大量的數據，進行計算等。
d）車輛智能體。它是動態運輸調度的執行智能體，該智能體負責通過GPS向決策智能體報告實時地理位置，同時接收決策智能體的動態信息，遇到突發事件（如交通事故、車輛故障等），還可以向決策智能體發送處理請求。
每一個智能體可以執行一個或多個服務，一個服務相當于一個問題解決的活動單元。最簡單的服務表示為任務，代表問題解決的元單元，這些元單元加上順序控制和條件約束就可以組合成為復雜的服務。這些嵌套在一起的服務單元可以組成非常復雜的服務邏輯，在最頂層，整個DTS可視為一個服務。
1.3 DTS多智能體系統實現
圖1所示的DTS多智能體系統中，agent在地理分布上具有一定的分散性，因此考慮用DCOM（distributed component object model）式智能體來實現[3]。DCOM是指分布式組件，就是將COM組件發布到遠程機器上，從而實現遠程控制和并行計算。智能體組件[4]是Richard等人提出的實現智能體的一種新方法，它的最大特點是將組件和智能體兩者的優點結合起來（圖2）。
DCOM式智能體并不需要專門的網絡通信代碼，通過對接口和連接點的調用[5]，智能體之間就可以實現通信（圖3）。
其中：1為調用接口；2為調用連接點。在圖3中，除決策智能體外，其他智能體都以DCOM式組件形式實現。決策智能體作為多智能體系統的中樞，將其他智能體發布到合適的遠程機器上。這樣，由決策智能體發起的通信通過調用相應智能體的接口來實現；由其他智能體發起的通信通過其他智能體與決策智能體的連接來實現；其他智能體之間的通信和協調由決策智能體集中實現。
2 DTS多智能體系統運行
通常情況下，DTS多智能體系統的基本運行模型如圖4所示。決策智能體一般的目標總是維持原規劃車輛運輸路徑能得到不變的執行，但當受到交通流情況變化、顧客動態請求的干擾后，將采用使行駛里程最小等目標策略局部修改原預規劃路徑。
2.1 預規劃智能體
預規劃智能體通過對DTS大量歷史數據的分析，掌握其周期性，并利用周期性作出預規劃的車輛運輸路徑。它的一般描述如下：
〈agent〉::=〈AID〉〈目標〉〈感知器〉〈通信機制〉〈效應器〉〈信息處理器〉
〈AID〉::=〈預規劃智能體〉
〈目標〉::=〈輸出預規劃車輛運輸路徑〉
〈感知器〉::=〈周期發生明顯改變〉〈過去一段時間的運輸調度信息〉
〈通信機制〉::=〈通信源語〉〈通信內容〉
〈通信源語〉::=〈Command〉|〈Require〉|〈Reject〉|〈Inform〉|〈Cancel〉
〈通信內容〉::=〈發送者〉〈接收者〉〈時間〉〈信息源〉
〈效應器〉::={
〈系統初始預規劃輸出〉〈系統初始預規劃輸出描述〉
〈重新預規劃輸出〉〈重新預規劃輸出描述〉}
〈系統初始預規劃輸出描述〉::=begin
{確定系統日期；
查找周期及重復度；
利用周期找出顧客將來的動態需求；
將顧客靜態需求與動態需求合在一起用Apriori方法求解；
輸出預規劃車輛運輸路徑； }
end
〈重新預規劃輸出描述〉::=begin
{
根據車輛運行現狀修改預測的動態需求；
將本時點的顧客靜態需求與修改過的動態需求合在一起用Apriori方法求解；
輸出新的預規劃車輛運輸路徑； }
end
〈信息處理器〉::=〈內部執行機制〉〈知識庫〉
〈內部執行機制〉::={
〈計算周期〉
〈計算重復度〉 }
〈計算周期〉::=begin
{ 確定選取的歷史數據時間范圍；
確定可接受的基準；
計算相應重復度；
確定周期； }
end
〈計算重復度〉::=begin
{ 確定選取周期；
計算相應重復度；
以平均值作為重復度； }
end
〈知識庫〉::={〈領域知識〉}
〈領域知識〉::={{動態運輸調度的歷史數據庫}}
預規劃智能體中最重要的算法是求解預規劃車輛運輸路徑的算法，系統采用Apriori方法進行線路規劃。
2.2 決策智能體
決策智能體以預規劃的車輛運輸線路為藍圖，基于專家知識，對交通流的變化和顧客的動態需求作出反應，對車輛智能體發布動態調度命令，不斷調整車輛運輸路徑。其描述如下：
〈agent〉::=〈AID〉〈目標〉〈感知器〉〈通信機制〉〈效應器〉〈信息處理器〉
〈AID〉::=〈決策智能體〉
〈目標〉::=〈動態發布調度命令〉
〈感知器〉::=〈其他智能體或人工干預的請求〉〈實時從其他智能體或人機交互接收的信息〉
〈通信機制〉::=〈通信源語〉〈通信內容〉
〈通信源語〉::=〈Command〉|〈Require〉|〈Reject〉|〈Inform〉|〈Cancel〉
〈通信內容〉::=〈發送者〉〈接收者〉〈時間〉〈信息源〉
〈效應器〉::={
〈專家決策〉〈專家決策描述〉 }
〈專家決策描述〉::=begin
{ 查找感知器接收的請求；
對應請求搜索相應的專家知識規則；
if 匹配
then 執行相應的規則；
else 發送不能處理信息，要求提供更多信息；
}
end
〈信息處理器〉::=〈類比匹配機制〉〈知識庫〉
〈類比匹配機制〉::=〈映射機制〉〈匹配度計算方法〉
〈知識庫〉::={〈領域知識〉〈控制知識〉}
〈領域知識〉::={
{顧客，地理位置，需求量}
{交通流，位置，行駛速度}
{車輛，位置，事件代碼}
{人工干預，性質，干預事件代碼}
}
〈控制知識〉::={〈產生式規則〉}
決策智能體最關鍵的部分就是利用專家知識實時地對交通流、人工干預、車輛問題、顧客動態請求作出反應，通過對人類專家處理問題過程建模，在計算機上用程序仿制一個與人類專家相同處理能力的專家程序，從而解決一些復雜的問題[6]。在DTS智能化系統中，決策智能體要處理的就是這類復雜問題。一方面一個預規劃車輛運輸路線需要執行；另一方面顧客需求、交通流又在發生變化。如何在復雜的環境下執行好運輸調度就是決策智能體的主要任務。
2.3 實時監控智能體
實時監控智能體是與ITS協商的智能體，它的功能是隨著ITS的發展而發展的[7~9]。其一般描述如下：
〈agent〉::=〈AID〉〈目標〉〈感知器〉〈通信機制〉〈效應器〉〈信息處理器〉
〈AID〉::=〈實時監控智能體〉
〈目標〉::=〈輸出替換路徑〉
〈感知器〉::=〈某條線路出現交通堵塞〉〈從ITS傳來的實時交通流信息〉
〈通信機制〉::=〈通信源語〉〈通信內容〉
〈通信源語〉::=〈Command〉|〈Require〉|〈Reject〉|〈Inform〉|〈Cancel〉
〈通信內容〉::=〈發送者〉〈接收者〉〈時間〉〈信息源〉
〈效應器〉::={
〈替換路徑輸出〉〈替換路徑輸出描述〉 }
〈替換路徑輸出描述〉::=begin
{ 詢問決策智能體相關限制條件；
向ITS請求解決方案；
綜合評價；
輸出替換路徑； }
end
〈信息處理器〉::=〈類比匹配機制〉〈知識庫〉
〈類比匹配機制〉::=〈映射機制〉〈匹配度計算方法〉
〈知識庫〉::={〈領域知識〉}
〈領域知識〉::={
{地理數據庫}
〈替換路徑初始待選方案集合〉 }
2.4 車輛智能體
車輛智能體負責執行運輸路徑規劃，它可以是布置在車輛上的智能控制部件，也可以是向實際發布命令的消息發布中心。其一般描述如下：
〈agent〉::=〈AID〉〈目標〉〈感知器〉〈通信機制〉〈效應器〉
〈AID〉::=〈××車輛智能體〉
〈目標〉::=〈運輸路徑輸出〉
〈感知器〉::=〈車輛發生問題〉〈車輛的實時運行狀況〉
〈通信機制〉::=〈通信源語〉〈通信內容〉
〈通信源語〉::=〈Command〉|〈Require〉|〈Reject〉|〈Inform〉|〈Cancel〉
〈通信內容〉::=〈發送者〉〈接收者〉〈時間〉〈信息源〉
〈效應器〉::={
〈接收決策智能體的調度命令〉〈接收決策智能體的調度命令描述〉
〈發送車輛問題請求〉〈發送車輛問題請求描述〉
}
〈接收決策智能體的調度命令描述〉::=begin
{將預規劃車輛運輸路徑寫入本地數據庫；
接收動態調度命令；
輸出當前的運輸路徑；}
end
〈發送車輛問題請求描述〉::=begin
{確定問題類型、后果；
發送給決策智能體，請求處理；}
end
3 實例分析
以快遞業務中收集顧客郵件的過程為基本研究背景。車輛位于中心車場位置[0，0]，其服務區域為[100，100]內所有的顧客，基本假設有：a）車輛的容量是無限的；b）車輛經過一個回路，最后回到中心車場[0，0]；c）顧客的數目為49，顧客的需求是動態的，可能需要服務，可能不需要，其動態度為50％，重復度為80％，周期為1；d）運輸調度的目標是在必須滿足所有顧客需求的基礎上，盡可能地減少車輛行駛里程。
實例分析所用的顧客地理位置數據用Access數據庫存儲，方便了顧客地理位置數據的修改。顧客地理位置數據可以來自仿真軟件的隨機生成，也可以是來自現實生產中的實際數據。本實例分析的數據源自仿真軟件隨機生成（表1）。本實例的顧客位置數據存放于數據庫Data.mdb中，實例分析程序采用VC++6.0編寫。
程序運行分為三個部分：a）載入數據；b）按周期為1、動態度50％、重復度80％的顧客動態需求，模擬DTS過程；c）在每次作業終了后，以全部顧客需求為基礎，用靜態運輸調度問題方法重新計算車輛運輸路徑。本實例分析共運行了三個周期，其模擬結果如表2所示。
表2所列數據是設計的系統運行結果和DTS終了后，用靜態運輸調度方法重新計算的結果，兩種方法計算的線路長度的差異為
（1 315.8－1 240.03）/1 240.03＝6.1％
（1 406.5－1 389.62）/1 389.62＝1.2％
（1 280.56－1 122.55）/1 122.55＝14％
在三個周期中都沒有超過20％，說明DTS智能化系統運行結果接近于優化的解，用DTS多智能體系統解決動態運輸調度問題是有效的。
4 結束語
隨著信息技術的發展和物流設備設施的改進，解決DTS問題已成為可能。本文設計的基于多智能體技術的DTS智能化系統，使每一個智能體可以執行一個或多個服務。一個服務相當于一個問題解決的活動單元，這些嵌套在一起的服務單元可以組成非常復雜的服務邏輯，完成DTS的線路設計。DTS智能化系統本身具有開放性，可以依據需要增加相應的智能體，使決策依據更加全面，如可以增加以庫存控制為目標智能體，使庫存與運輸調度決策聯合起來考慮。隨著ITS的進一步發展，DTS智能化系統最終將整合到ITS中去，作為ITS在企業中的一個分支，從而實現在全社會層面上對運輸調度進行合理優化。
參考文獻：
［1］PSARAFTIS H N. Dynamic vehicle routing problems[M]//Vehicle routing: methods and studies. Amsterdam: NorthHolland， 1988:223248.
[2]徐麗群. 基于多智能體技術的出行誘導管理系統研究[J].東南大學學報:自然科學版，2004，34(6):814818.
[3]李斌，徐麗群.基于DCOM式智能體的交通控制系統模型[J].交通與計算機，2005，23(2)：1417.
[4]KRUTISCH R， MEIER P， WIRSING M. The agent component approach， combing agents， and components[C]//Proc of MATES’03. 2003:112.
[5]ROGERSON D. COM技術內幕——微軟組件對象模型[M].北京：清華大學出版社，1999：1126.
[6]張金壽，周建峰.專家系統建造原理和方法[M].北京： 中國鐵道出版社，1992：1165.
[7]HANI S.Dynamic network traffic assignment and simulation methodology for advanced system management application[J]. Networks and Spatial Economics， 2001，1(3):267292.
[8]WEYMANN J， FARGES J L， HENRY J. Dynamic route guidance， congestion and disobedience to route advice[J]. Control Eng Practice， 1995， 3(4):525533.
[9]WAHLE J， ANNEN O， SCHUSTER C， et al. A dynamic route guidance system based on real traffic data[J]. European Journal of Operation Research， 2001，131（2）:302308.
