基于多Agent的物流車輛調(diào)度系統(tǒng)構(gòu)建及協(xié)作機理

孟　聰，初良勇，2

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

?

基于多Agent的物流車輛調(diào)度系統(tǒng)構(gòu)建及協(xié)作機理

孟聰1，初良勇1，2

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

在傳統(tǒng)物流車輛調(diào)度過程的基礎(chǔ)上，結(jié)合Agent在物流車輛調(diào)度和物資調(diào)度方面的應(yīng)用，設(shè)計了基于多Agent協(xié)作的車輛調(diào)度系統(tǒng)模型的框架，進一步分析了各Agent之間共同協(xié)作完成任務(wù)的過程。同時建立了基于黑板系統(tǒng)的通信機制，深入分析Agent之間的協(xié)作機理。

多Agent；物流車輛；車輛調(diào)度；協(xié)作機理；通信機制

1　引言

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

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

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

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

2　基于多Agent的配送車輛調(diào)度系統(tǒng)模型設(shè)計

2.1系統(tǒng)模型中各Agent的設(shè)定及分析

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

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

（2）管理型：協(xié)調(diào)控制Agent。管理型Agent協(xié)調(diào)處理和監(jiān)控一些全局性信息。映射為智能車輛調(diào)度系統(tǒng)中的協(xié)調(diào)控制Agent，負責整個系統(tǒng)的管理、監(jiān)督與控制，尤其當系統(tǒng)出現(xiàn)緊急或者突發(fā)狀況，如出現(xiàn)緊急訂單，協(xié)調(diào)控制Agent會根據(jù)計劃編制知識庫中的規(guī)則，給緊急訂單一個較高的優(yōu)先級。

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

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

2.2系統(tǒng)模型的構(gòu)建

本文設(shè)計的車輛調(diào)度系統(tǒng)模型由多個Agent共同協(xié)作完成配送任務(wù)（如圖1所示），任務(wù)完成過程中各Agent之間的配合如下：

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

圖1　基于多Agent的車輛調(diào)度系統(tǒng)框架

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

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

（4）各車輛Agent根據(jù)接收到的調(diào)度指令，完成配送任務(wù)。

此外，協(xié)調(diào)控制Agent在整個任務(wù)完成過程中起到統(tǒng)籌全局的作用，如全程跟蹤監(jiān)控訂單的處理狀態(tài)，若出現(xiàn)緊急訂單，協(xié)調(diào)控制Agent將給該訂單一個優(yōu)先級；當Agent之間合作或者通信出現(xiàn)問題，協(xié)調(diào)控制Agent將進行協(xié)調(diào)；或當任務(wù)的完成出現(xiàn)問題，協(xié)調(diào)控制Agent可以幫助追溯問題環(huán)節(jié)。

3　Agent之間的通信機制及協(xié)作機理

3.1Agent的物理結(jié)構(gòu)

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

圖2　Agent的物理結(jié)構(gòu)

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

3.2Agent之間的通信機制

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

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

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

各Agent的狀態(tài)由協(xié)調(diào)規(guī)則進行定義，以訂單Agent為例，從訂單的開始狀態(tài)向獲得狀態(tài)轉(zhuǎn)移時的協(xié)調(diào)規(guī)則定義如下［9］：

3.3車輛調(diào)度系統(tǒng)中的協(xié)作機理

本文設(shè)計的黑板系統(tǒng)中包括兩個黑板，一個主要應(yīng)用于車輛調(diào)度Agent對車輛調(diào)度方案進行求解的過程，另一個應(yīng)用于車場Agent對于車輛Agent的管理過程，整個系統(tǒng)的信息傳遞如下：

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

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

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

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

圖3　多Agent之間的協(xié)作機理

此外，如圖3協(xié)調(diào)控制Agent作為一個中心控制節(jié)點，可以從黑板系統(tǒng)中讀取到整個調(diào)度過程的各種信息，如訂單信息及其處理狀態(tài)、倉庫信息、路網(wǎng)信息等，當任務(wù)處理過程出現(xiàn)任何突發(fā)問題需要其協(xié)調(diào)解決時，只需將協(xié)調(diào)方法和機制寫入黑板1中，相應(yīng)的Agent會讀取到黑板1中的消息，并按照規(guī)定執(zhí)行。

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

4　結(jié)論

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

［1］席釕姿.基于Multi-Agent技術(shù)的物流企業(yè)運輸調(diào)度系統(tǒng)優(yōu)化研究［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］崔國山.機場應(yīng)急救援系統(tǒng)中資源動態(tài)調(diào)配研究［D］.南京：南京航空航天大學，2009.

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

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

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

［9］周宏，廖雪珍.基于Agent的網(wǎng)絡(luò)物流配送決策系統(tǒng)研究［J］.系統(tǒng)工程與電子技術(shù)，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-），女，碩士生，研究方向：交通運輸規(guī)劃與管理。