基于多Agent的物流車輛調度系統構建及協作機理

孟　聰，初良勇，2

（1.集美大學　航海學院，福建　廈門　361021；2.集美大學　現代物流研究中心，福建　廈門　361021）

?

基于多Agent的物流車輛調度系統構建及協作機理

孟聰1，初良勇1，2

（1.集美大學航海學院，福建廈門361021；2.集美大學現代物流研究中心，福建廈門361021）

在傳統物流車輛調度過程的基礎上，結合Agent在物流車輛調度和物資調度方面的應用，設計了基于多Agent協作的車輛調度系統模型的框架，進一步分析了各Agent之間共同協作完成任務的過程。同時建立了基于黑板系統的通信機制，深入分析Agent之間的協作機理。

多Agent；物流車輛；車輛調度；協作機理；通信機制

1　引言

隨著市場經濟的發展，物流成為企業最重要的競爭領域之一，未來一段時間，企業之間的競爭一定程度上取決于其物流能力的發展。眼下我國物流行業的總體水平仍落后于發達國家，最顯著的問題是物流成本較高和物流運作手段落后。作為物流最重要的環節之一，配送的費用在整個物流運作中占據了很大比重，因為目前相當一部分物流企業還是通過人工經驗來判斷和進行配送，如配送車輛的調度以及路徑選擇。在歐美、日本等一些國家，在20世紀80年代末就已然出現了專供物流調度所使用的計算機軟件，擺脫了陳舊的人工經驗調度的方法，開啟了車輛調度操作智能化、自動化的新時代，這些技術中智能Agent技術越來越引起人們的關注。

智能體（Agent）是一個具有自主性、主動性、持續性、交互性和自適應性的智能實體，可以在沒有外界直接操縱的情況下，通過自身的傳感器感知外部環境的變化，并通過效應器自主地對環境做出反應。而由多個智能體組成的多智能體系統（Multi-AgentSystem，MAS）具有敏捷、靈活、實時的優點，采用分布式體系結構，其每個智能體皆有一定的獨立功能，且智能體之間的結構關系是動態可調整的，不同功能Agent組成緊耦合的運輸調度管理體系結構，具有適應性、自組織和良好的協調性能，可以通過協調方式完成繁雜的整體運作［1］。因此，多智能體技術非常適用于解決物流配送中的車輛調度問題。

近年來，國內外的學者對基于Agent的復雜系統建模問題進行了研究，如許多學者開展了基于MAS的故障診斷系統理論和模型研究，提出了基于MAS的智能故障診斷原型系統的基本框架［2-3］。隨著研究的深入，有學者設計了一套基于合同網機制、擁有混合多Agent系統架構的裁判模型，將其應用于生產調度以及再調度的相關領域［4］。Tamagawa等將多智能體系統應用到城市商業運輸模擬中，構建了兩個模型，分別是學習模型和帶時間窗的車輛路線規劃和運輸調度問題的模型。另外，還有學者將多Agent技術拓展應用于解決機場的應急資源動態調度和軍用物資的車輛調度方面［5］。

本文針對傳統配送車輛調度過程中存在的問題，提出了一種基于多Agent的配送車輛調度系統模型，通過將傳統配送模式下的過程分解成幾個模塊，每個模塊用一個智能Agent來代替，各Agent之間通過特定的通信語言進行協調合作，以實現整個配送過程的合理化、智能化。

2　基于多Agent的配送車輛調度系統模型設計

2.1系統模型中各Agent的設定及分析

傳統電子商務下的配送是指客戶填寫訂單，配送中心接受訂單并組織車輛進行配送的整個過程。該過程主要由人工操作，信息溝通不夠及時，造成效率低下，同時，在組織車輛進行配送時，通常由人工經驗進行車輛調度，存在很大的不合理性。為了克服傳統人工經驗可能帶來的不合理性，物流車輛智能調度系統將配送過程分解成幾個模塊，即訂單的處理過程、車輛調度的求解過程、車場的調度過程以及車輛執行任務的過程，每個模塊利用一個智能Agent代替，即訂單處理Agent、車輛調度Agent、車場Agent、車輛Agent，同時需要倉庫管理Agent和路網信息Agent的配合，并增加一個協調控制Agent來解決一些全局性問題。本文將這些Agent模塊分為四種類型，即管理型、任務型、計算型和資源型［6］。

（1）任務型：訂單Agent。任務型Agent會選擇合適的資源完成對自己的處理，是動態生成的，同時要監控任務的順利執行。在實際物流配送系統中，映射為訂單Agent。訂單Agent負責接收和處理客戶訂單，包括手動輸入、文件導入等方式，并對訂單進行分析，形成任務。并向客戶反饋和監控訂單的處理狀態。同時，它可以提取客戶相關信息，用來分析該網點的客戶類型和客戶群。

（2）管理型：協調控制Agent。管理型Agent協調處理和監控一些全局性信息。映射為智能車輛調度系統中的協調控制Agent，負責整個系統的管理、監督與控制，尤其當系統出現緊急或者突發狀況，如出現緊急訂單，協調控制Agent會根據計劃編制知識庫中的規則，給緊急訂單一個較高的優先級。

（3）計算型：車輛調度Agent。計算型Agent是指寫入具體算法，并擁有判斷能力的智能體。在物流配送智能車輛調度系統中，映射為車輛調度Agent，是整個系統的核心部分，即智能車輛調度的算法庫，如遺傳算法，模擬退火算法、神經網絡算法等，判斷自己是否有能力解決該訂單，并且基于一定的目標形成車輛調度方案。

（4）資源型：倉庫管理Agent、車場Agent，車輛Agent，路網信息Agent。資源型Agent即資源的一個功能單元或者管理資源的單元組合。映射為實際物流配送中，一般包括物資設備、運輸工具、操作人員等。

2.2系統模型的構建

本文設計的車輛調度系統模型由多個Agent共同協作完成配送任務（如圖1所示），任務完成過程中各Agent之間的配合如下：

（1）客戶首先通過Internet端輸入訂單信息，訂單Agent被激活，負責提取訂單的各方面信息，如配送地點、時間要求、貨物種類及數量等，形成具體的配送任務，任務消息將傳送給車輛調度Agent，訂單Agent轉為等待狀態。

圖1　基于多Agent的車輛調度系統框架

（2）讀取到任務的車輛調度Agent被激活，通過其他Agent的配合對任務進行求解，即需要激活車場Agent、倉庫管理Agent以及路網信息Agent，通過調取倉庫貨物信息、車場的車輛信息、道路狀態信息等，根據其內部封裝的調度算法以及自身的數據庫、知識庫、合作庫等對任務進行求解，形成的配送及車輛調度方案發送給車場Agent，同時將任務的處理進程反饋給訂單Agent，車輛調度Agent轉為空閑狀態。

（3）車場Agent在接收到調度方案后，激活各車輛Agent，尋找合適的車輛Agent并進行任務分派。

（4）各車輛Agent根據接收到的調度指令，完成配送任務。

此外，協調控制Agent在整個任務完成過程中起到統籌全局的作用，如全程跟蹤監控訂單的處理狀態，若出現緊急訂單，協調控制Agent將給該訂單一個優先級；當Agent之間合作或者通信出現問題，協調控制Agent將進行協調；或當任務的完成出現問題，協調控制Agent可以幫助追溯問題環節。

3　Agent之間的通信機制及協作機理

3.1Agent的物理結構

智能體（Agent）是一個可以在沒有外界直接操縱的情況下，通過自身的傳感器感知外部環境的變化，并通過效應器自主地對環境做出反應的智能實體。單個智能體的應用只能解決簡單的現實問題，即接收外部環境的問題，通過內部封裝的算法或程序對問題進行求解，再反饋給外部環境的簡單過程。

圖2　Agent的物理結構

如圖2，在多個Agent組成的系統中，Agent之間需要互相共享協作共同完成任務，一個通用的Agent一般具有用戶接口、通訊接口和自模型三部分。用戶接口用來與外部環境進行交互，即接收問題或者反饋求解結果。自模型是其核心部分，負責對問題進行求解，一般包括求解模塊和合作模塊，求解模塊內部有與該智能體對應的數據庫、知識庫及封裝的算法庫，推理機負責將問題進行分解并利用現有的知識進行推理求解；合作模塊內部有合作庫，負責該Agent與其他Agent之間的信息交互及交流協作，共同完成任務。

3.2Agent之間的通信機制

Agent之間的通信語言主要有三種［7］，第一種是知識查詢與操縱語言—KQML（Knowledge Query and Manipulation Language），它規定了消息的格式及傳送系統，為Agent之間的通信和協作提供了一種通用的框架，尤其提供了一組識別、連接建立和消息交換的協議；第二種是知識交換格式—KIF（Knowledge Interact Format），用來表達某一集域的性質以及集域中實體與實體之間關系的公共語言，嚴格基于一階謂語邏輯演算；第三種是FIPA定義的ACL語言，用于表示Agent的行為特征，其消息往往表示一個通信動作。

Agent之間的通信方式主要有兩種，一種是同步信息傳遞，即黑板系統，就是把消息放在可以廣泛存取的黑板上，每個Agent可以向黑板發送消息，也可以從黑板上讀取消息；另一種是異步消息傳遞，即點對點的方式，一個Agent可以向一個或多個Agent發送消息，這種通信方式需要Agent之間有更多了解，要求消息的發送者事先了解消息接收者的有關信息。

本文設計的智能車輛調度系統的通訊方式是黑板系統，通訊語言是美國ARPA知識共享項目提出的KQML語言定義協調規則，KQML包括以下要素：述行語、角色、語言、論域、內容等，一個KQML的例子如下［8］：

各Agent的狀態由協調規則進行定義，以訂單Agent為例，從訂單的開始狀態向獲得狀態轉移時的協調規則定義如下［9］：

3.3車輛調度系統中的協作機理

本文設計的黑板系統中包括兩個黑板，一個主要應用于車輛調度Agent對車輛調度方案進行求解的過程，另一個應用于車場Agent對于車輛Agent的管理過程，整個系統的信息傳遞如下：

（1）用戶通過通訊接口將訂單信息輸入，訂單Agent將提取的訂單信息寫入黑板系統中。

（2）車場Agent、倉庫管理Agent以及路網信息Agent查看到黑板中的訂單信息后，將相應的車輛信息、倉庫貨物信息以及路網信息寫入黑板1中。其中，車輛信息需要黑板2進行配合，每個車輛Agent將該車輛的狀態信息寫入黑板2中，車場Agent根據黑板2中的信息將車輛信息匯總至黑板1中。

（3）車輛調度Agent讀取黑板中的信息后，激活內部封裝的算法庫，開始求解，并將形成的調度方案寫入黑板中。

（4）車場Agent讀取到黑板中的車輛調度方案后，將調度方案信息寫入黑板2中，尋求合適的車輛，完成配送任務。

圖3　多Agent之間的協作機理

此外，如圖3協調控制Agent作為一個中心控制節點，可以從黑板系統中讀取到整個調度過程的各種信息，如訂單信息及其處理狀態、倉庫信息、路網信息等，當任務處理過程出現任何突發問題需要其協調解決時，只需將協調方法和機制寫入黑板1中，相應的Agent會讀取到黑板1中的消息，并按照規定執行。

該系統模型將Agent的學習機制考慮進去，即群體學習機制。每個Agent通過記憶和遺忘來保存那些對共同任務求解有利的知識和經驗，如車輛調度Agent，每個訂單的調度方案形成之后，通過學習機對車輛調度方案的各個方面信息進行分析整合以及選擇性的遺忘和記憶，形成有利于完成共同任務的實際經驗的知識集合，記錄于車輛調度Agent的知識庫中，使知識庫不斷更新。協調控制Agent作為“負責人”的身份協調各Agent之間的通信和協作，除掌握各Agent的學習知識和經驗，還要通過對群體執行共同任務進行分析，記憶整個群體在執行任務過程中有利于共同任務求解的模式以及相對最優的求解結構和協作方法，為類似的任務解決奠定基礎。

4　結論

本文利用多智能體系統敏捷、靈活、實時的優點，結合目前Agent技術取得的研究成果，設計了基于多Agent的物流車輛智能調度的系統模型，并對其內部的協調運作過程和通信機制進行分析，以實現車輛調度過程的智能化、合理化。展望未來，物流配送的整個過程正在朝著更加智能化的方向發展，Agent技術在物流的配送決策、車輛的智能調度方面的應用更值得深入研究。

［1］席釕姿.基于Multi-Agent技術的物流企業運輸調度系統優化研究［D］.衡陽：南華大學，2014.

［2］Wooldridge M，Jennings N R.Intelligent Agents：Theory and Practice［J］.TheKnowledgeEngineeringReview，1995，10（2）：115-152.

［3］Willimason.Distributed Intelligent Agent［J］.IEEE Expert，1996，12（1）：36-45.

［4］Shen W，Norrie D H.An Agent-based Approach for Dynamic Manufacturing Scheduling［C］.Workshop Notes of the Agent-Based Manufacturing Workshop at Autonomous Agents'98［A］.1998.

［5］崔國山.機場應急救援系統中資源動態調配研究［D］.南京：南京航空航天大學，2009.

［6］李義華.基于多智能體的物流配送車輛調度決策方法研究［D］.長沙：中南大學，2012.

［7］賈利民，劉剛，秦勇.基于智能Agent的動態協作任務求解［M］.北京：科學出版社，2007.

［8］朱欣娟，薛惠鋒.基于本體的MAS黑板模型研究［J］.計算機工程與設計，2004，（1）：26-28，141.

［9］周宏，廖雪珍.基于Agent的網絡物流配送決策系統研究［J］.系統工程與電子技術，2004，（10）：1 421-1 425.

Establishment and Collaboration of Logistics Vehicle Dispatching System Based on Multi-agent System

Meng Cong1，Chu Liangyong1，2
（1. Navigation College， Jimei University， Xiamen 361021； 2. Modern Logistics Research Center， Jimei University， Xiamen 361021， China）

In this paper， on the basis of the traditional logistics vehicle dispatching process and in connection with the application of theAgent technology in logistics vehicle dispatching and material dispatching， we designed the framework of the vehicle dispatching systemmodel based on multi- agent collaboration and then further analyzed the collaborative process among the Agents. At the meantime， weestablished the blackboard-based telecommunication mechanism and analyzed in-depth the collaborative mechanism among the Agents.

multi-Agent； logistics vehicle； vehicle dispatching； collaborative mechanism； telecommunication mechanism

U116；F253.9

A

1005-152X（2016）08-0092-05

10.3969/j.issn.1005-152X.2016.08.024

2016-07-05

福建省自然科學基金（2012J01302）；廈門市科技項目（3502Z20143022）；福建省教育廳中青年教師教育科研項目（JA15288）

孟聰（1992-），女，碩士生，研究方向：交通運輸規劃與管理。