孟　聰，初良勇，2

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

?

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

孟聰1，初良勇1，2

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

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

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

1　引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2Agent之間的通信機(jī)制

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

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

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

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

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

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

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

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

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

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

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

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

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

4　結(jié)論

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

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

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

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

［8］朱欣娟，薛惠鋒.基于本體的MAS黑板模型研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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

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

孟聰（1992-），女，碩士生，研究方向：交通運(yùn)輸規(guī)劃與管理。