【文章內(nèi)容簡介】 用在于協(xié)助管理Agent和執(zhí)行Agent保證程序的順利進行，：（1）初始化步驟（Initialization），在本階段系統(tǒng)中所有的Agent都將自身的位置、狀態(tài)、能力等信息報告給管理Agent，為管理的Agent的調(diào)度決策提供基本信息[22]。（2）任務發(fā)布步驟（WorkAnnouncement），管理Agent在接收到任務后，立即對任務進行判斷，并下發(fā)到執(zhí)行Agent。（3）投標步驟（Bidding），執(zhí)行Agent在接收到任務后，將根據(jù)決策策略對任務進行評估，如果評價結(jié)果“滿意”，(也就是說優(yōu)選出最適合自己的任務)，開始向管理Agent返回“bid”消息，標識自己使用該任務。（4）確認步驟（Awarding），管理Agent根據(jù)各個執(zhí)行Agent的投標數(shù)據(jù)，開始優(yōu)選最佳的執(zhí)行者，當確認找出最佳的執(zhí)行者，管理Agent開始向下發(fā)布信息，如果是最佳結(jié)果發(fā)送“award”消息，其他執(zhí)行Agent發(fā)送“fail”消息。（5）任務執(zhí)行步驟（Executing），在這個階段，任何一個優(yōu)選出來的執(zhí)行Agent在接收到管理Agent發(fā)送過來的“award”消息后，開始執(zhí)行執(zhí)行任務，其他的Agent將什么都不做。國外車輛優(yōu)化調(diào)度研究已廣泛用于生產(chǎn)、生活的各個方面，如快遞郵件投遞、物流配送、車輛載貨、郵遞員線路設計、集配中心的選址優(yōu)化、物流超市的送貨線路優(yōu)化等等。在過去的幾年里車輛優(yōu)化調(diào)度取得不少成果，成果除在物流行業(yè)應用外，在工業(yè)管理、計算機應用等領域也廣泛的應用，還用于各種行業(yè)計劃安排、物流配送現(xiàn)了優(yōu)化、發(fā)貨單的計劃與控制等各個領域[23]。1）啟發(fā)式算法啟發(fā)式算法是計算機算法分析與設計中一種常用算法，主要用來計算最優(yōu)值或者尋找出最佳方案，我們將這種算法運用于物流調(diào)度的多Agent系統(tǒng)中，主要是用來尋找出在車輛調(diào)度中的最佳運輸路線方案。由于物流車輛調(diào)度系統(tǒng)影響車輛調(diào)度有大量參數(shù)需要考慮，如果將這些參數(shù)在系統(tǒng)建模時候就開始考慮，會使得系統(tǒng)便得非常復雜，甚至無從下手，所以我們需要利用啟發(fā)式算法簡化系統(tǒng)模型，因此在本文中我們將選用啟發(fā)式算法來設計物流車輛調(diào)度模型。啟發(fā)式（heuristics），意為借助于某種試探和迭代演化的方法，通過歸納推理歷史經(jīng)驗以及實驗分析來解決問題的方法。啟發(fā)式算法要求分析人員利用自己在經(jīng)驗在各種模型計算法中找出其內(nèi)在聯(lián)系，從中得到啟發(fā)，找出該問題的解決思路和途徑。由于物流車輛調(diào)度系統(tǒng)影響車輛調(diào)度有大量參數(shù)需要考慮，如果將這些參數(shù)在系統(tǒng)建模時候就開始考慮，會使得系統(tǒng)便得非常復雜，甚至無從下手，所以我們需要利用啟發(fā)式算法簡化系統(tǒng)模型，如何利用啟發(fā)式算法找出簡單的建模方法，稱為目前研究的重點。在過去十幾年里，啟發(fā)式算法在各種不同的領域開始運用，并且取得非常不錯的成績，主要是因為它具有以下優(yōu)勢：（1）啟發(fā)式算法雖然具有簡單、解決問題速度快、容易理解，但是它的應用具有大量的經(jīng)驗成分。（2）某些組合優(yōu)化問題目前還沒用可行的算法，或者找出最優(yōu)算法非常困難，即使能夠找出最優(yōu)算法，其付出的時間代價也是很難接受的。（3）在數(shù)學模型的構為了降低難度，容易忽略一些因素；同時容易出現(xiàn)參數(shù)估算不準確；數(shù)據(jù)采集具有不精確，這些都容易造成誤差。當然，啟發(fā)式算法也有一些頗受爭議的不足之處：（1）計算結(jié)果可能會出現(xiàn)不穩(wěn)定的情況，由于用啟發(fā)式算法在建模選用不同的參數(shù)，因此在實際運用中效果會完全不一樣，有時候會取得非常不錯的成績，但是有時候運算結(jié)果可能會強差人意，在實驗室中這樣會允許這樣的誤差，但是在實際的工程應用中，這樣的不穩(wěn)定性成為啟發(fā)式算法最大的軟肋。（2）算法設計取決于設計者對模型的把握和個人經(jīng)驗，但是這些問題很難找出特定的規(guī)律，這種完全憑借設計者的經(jīng)驗的方法，也使得沒有標準的評審方法，能夠讓不同的算法在同一起點上進行比較。由于沒有這種比較，設計者往往得到運算結(jié)果，無法進行比較，也無法知道運算結(jié)果是否就是最佳的結(jié)果，很多時候決策者根據(jù)經(jīng)驗來認可是否可靠，造成決策者不去追求最優(yōu)性和探求最優(yōu)解。其主要形成原因是：（1）很多問題很難找出最優(yōu)解，最優(yōu)解本來就很難發(fā)現(xiàn)，我們只能依靠決策組的經(jīng)驗來判斷結(jié)果是否最優(yōu)。（2）有些問題，找出最優(yōu)解付出的代價太大。（3）在實際決策中，太高的精度沒有很大的實際意義。啟發(fā)式方法主要應用于解決NP難題。啟發(fā)式方法求解問題，主要是通過反復的計算，通過計算結(jié)果也就是通過運算求解過程，找出最佳的結(jié)果值，也就是說通過一定的搜索和評估規(guī)則找出算法的滿意解，為了能夠順利的尋找出最佳的求解，算法會進行自主學習，通過學習已經(jīng)運用的求解知識，推演出新知識，找出新的搜索規(guī)則，能夠利用失敗信息逐步縮小搜索范圍。具體的啟發(fā)式算法的搜索求解過程如圖21所示：分析問題，建立模型研究模型結(jié)構設計搜索規(guī)則應用規(guī)則得到的解可接受嗎？可獲得有助于搜索的新信息嗎？修正搜索規(guī)則得不到解有時間和能力重新考慮問題嗎？N得到解YNNYY 圖21 啟發(fā)式算法的一般求解過程用啟發(fā)式方法求解在不同的環(huán)境和算法下，需要選用不同的策略。下文將列出幾個常用的策略，開發(fā)者可以根據(jù)啟發(fā)算法應用環(huán)境的的性質(zhì)和要求進行選用。（1）改進解策略，從初始解開始，通過一定的算法來進行結(jié)果分解和合并，通過不斷的遞歸分解和合并，來修正運算出來的解，通過修正使得解被決策組接受。（2）分解策略，主要是利用各個擊破的策略，將大問題分解成小問題，然后分別解決小問題來降低問題的求解難度。（3）逐步構造解策略，通過逐步增加條件，逐漸提高解的難度，從而逐步求出解結(jié)果。（4）數(shù)學規(guī)劃策略，通過一些數(shù)學公式的推演，利用一些數(shù)學運算的知識來提升算法的效能，通過數(shù)學的推演來提升算法的性能，對算法進行評估，使得算法能夠更快的找出高效的啟發(fā)式算法。（5）可行解空間的限制策略，將算法限定在某些情況下，從而降低問題解決的難度，然后再求解問題。（6）搜索學習策略，通過迭代來實現(xiàn)求解，這樣需要制定出一套解的搜索規(guī)則。為獲取算法的滿意解，在整個求解過程中要求算法能夠不斷學習，利用吸收的新的信息建立新的搜索規(guī)則，能夠利用失敗信息逐步縮小搜索范圍。在實際應用時我們通常采用某一種策略或者多種策略，根據(jù)具體問題具體分析，因地制宜，靈活運用。對于物流系統(tǒng)運輸優(yōu)化問題，對問題產(chǎn)生影響的參數(shù)非常多，通過在搭建模型的時候我們可能會添加許多限定條件，這些是為了減少建模難度，通過逐步深入的方法，開始逐步加入問題的因素，從少量參數(shù)開始逐步加入復雜的參數(shù)，不斷提升系統(tǒng)效率，優(yōu)化運算結(jié)果直到找出可行解[24]。2）CW算法由于啟發(fā)算法本身有很多分支，所以對物流車輛調(diào)度中線路優(yōu)化問題的求解，我們選用節(jié)約法（Saving Method）。CW算法是節(jié)約法的一種，也是一種非常常見的啟發(fā)式算法，本身利用前人的經(jīng)驗來提升模型的精確度。利用學習的方法來利用前人處理處理復雜問題的方法，通過跟蹤校正過程逐步找出滿意解。[25]算法開始先設計由一個配送中心和N個零售商組成數(shù)學模型中，配送車輛的路線安排變得非常困難，這個數(shù)學模型適合采用啟發(fā)式算法。節(jié)約量公式描述為：首先將配送中心用數(shù)學模型表示為，N個零售商用數(shù)學模型表示為，已知任意節(jié)點PI和Pi的距離我們表示為公式，我們假設外對任意零售商Pi和Pj的分別取合并送貨和分離送貨兩種方式，前者比后者節(jié)約的運輸距離為：j。根據(jù)三點的位置關系可以計算出節(jié)約量。本文將節(jié)約法優(yōu)化線路算法描述為，首先假定所有零售商線路都是直接往返進行第一次計算安排。然后分別計算任意兩者之間的節(jié)約量，對節(jié)約量進行降序排列，利用排列結(jié)果調(diào)整初始安排。如果兩者之間所在線路的貨運量之少于車輛的載重限制，算法允許兩者直接連接；如果所在線路的貨運量之和超過車輛的載重限制，算法設定兩者不連接，算法判斷節(jié)約量稍小兩者之間能否連接。循環(huán)迭代，直到所有零售商完成連接，該結(jié)果就是滿意解[26]。CW算法主要由Clarke和Wright提出，算法具有的特點是簡單易用并且應用非常廣泛有大量的案例可以參考，本文通過改進的CW算法來求解車輛調(diào)度問題，其具體的算法流程如下：① 首先我們計算車輛調(diào)度節(jié)約值，代表調(diào)度系統(tǒng)的任意兩點i和j之間線路的費用，并按照降序?qū)M行排序，其中:s。② 如果的計算結(jié)果為空，算法停止迭代，否則考察第一個是否滿足下列條件之一，如滿足進入下一步，如果都不滿足算法跳轉(zhuǎn)到步驟⑥。216。 假設點i和j之間沒有構成線路；216。 假設點i和j之間構成線路,但不與車場相連；216。 假設點i和j之間構成線路，均不與車場相連，可以得之I,j兩點分別是起點和終點。③ 計算兩點連接后之間的總貨運量Q，若，則轉(zhuǎn)下步，否則轉(zhuǎn)⑥。④ 計算兩點線路后，計算出車輛到達j點的時間比原計劃的變化量為：。若，轉(zhuǎn)⑤；⑤ 連接點i和點j，計算車輛到達各任務點的新時間。⑥ 令，轉(zhuǎn)②。以上算法主要針對對單車場的進行逐步優(yōu)化遞歸求解，現(xiàn)實當中的真實環(huán)境可能是多車場，對于這樣的問題我們一般采用轉(zhuǎn)化為單車場問題來處理，將復雜問題分解成簡單問題，我們首先計算出單車場完成的任務，然后再開始遞歸求解。同時我們發(fā)現(xiàn)節(jié)約法在物流車輛調(diào)度上的應用存在缺陷，它不支持訂貨量分割。本算法的核心在于，我們限定一些變量，然后逐步建立連接線，然后限制連接后的線路訂貨量和車輛載重，然后利用線路來進行優(yōu)選，當然這樣的也容易發(fā)生部分車輛沒有滿載的情況，造成其他線路出現(xiàn)超載，這樣使得系統(tǒng)沒有辦法建立線路，使得線路安排失敗。如果允許分割零售商的貨運量，可以減少車輛數(shù)目，縮短運輸距離和運輸成本。 一般運輸調(diào)度問題的數(shù)學模型車輛優(yōu)化調(diào)度問題的數(shù)學模型我們將做以下定義為：在物流調(diào)度模型中，我們隨即設計一連串裝貨點和卸貨點，然后在滿足貨物需求量、貨物的發(fā)送量、客戶要求交發(fā)貨時間、車輛載重、車輛行駛里程限制、送貨時間等約束條件，對各點之間構建行車線路，使車輛根據(jù)調(diào)度策略通過這些裝卸點，完成既定目標（如降低費用等）[27]。物流調(diào)度的核心問題就是車輛與運輸調(diào)度問題，運輸調(diào)度問題描述為是，假設某種貨物有m個產(chǎn)地。其中各個產(chǎn)地的貨物產(chǎn)量值分別是，再假設貨物有n個銷地，銷地的銷量分別是。假定從產(chǎn)地向銷地運輸貨物單位物品的運價是F，那么我們建模的目的就是考慮在達到運輸?shù)囊蟮耐瑫r使得整個系統(tǒng)的總運費最少。 小結(jié)本章主要介紹了智能Agent及多Agent系統(tǒng)的理論知識、啟發(fā)式算法的理論知識，以及啟發(fā)算法的主要策略和優(yōu)缺點，然后介紹CW算法理論的歷史以及在物流調(diào)度系統(tǒng)的運用、介紹如何搭建運輸問題的數(shù)學模型等理論知識。為智能Agent和多Agent理論在物流調(diào)度系統(tǒng)應用研究提供理論基礎；啟發(fā)式算法主要用來如果在物流調(diào)度系統(tǒng)模型中簡化復雜度的問題；CW算法解決了運輸線路優(yōu)化問題。3物流車輛調(diào)度策略與優(yōu)化算法設計物流調(diào)度策略的設計主要是在限定一些條件下開始系統(tǒng)建模，然后利用一些較好的算法來實施物流車輛調(diào)度設計，因為建模方式和選定的限定條件的不同，會得到完全不同的調(diào)度效果，同時會付出完全不同的調(diào)度代價。綜上述可見，選取合適的調(diào)度算法或者策略對優(yōu)化物流車輛調(diào)度有非常重要的作用 [29]。如果選取車輛的運輸任務作為限定參數(shù)進行系統(tǒng)建模，然后進行車輛線路優(yōu)化，這樣一種建模和調(diào)度方式比較適合于車輛幾種在停車場，任務非常多的情況下。而對于另外一種情況，車輛處于動態(tài)調(diào)度，環(huán)境非常復雜，條件非常多的情況下，由于車輛在外的行使過程中其環(huán)境參數(shù)比較復雜想進行任務優(yōu)化調(diào)度就比較困難了。本文的算法設計主要立足這種復雜情況，建立一種基于多Agent技術的，車輛競標和合作協(xié)同完成任務的調(diào)度優(yōu)化算法。根據(jù)前面的理論介紹，由于選擇的條件比較復雜，我們的整個系統(tǒng)由許多Agent來構建系統(tǒng)，這些Agent被區(qū)分為調(diào)度控制Agentheels車輛Agent。本論文利用車輛調(diào)度的已有的算法研究成果，以及Agent的在其他領域的應用成果，在兼顧平衡系統(tǒng)調(diào)度代價和目標優(yōu)化等多種因素后提出一種混合調(diào)度策略。其核心思想在于，調(diào)度控制Agent統(tǒng)一安排大批量任務，車輛Agent自主決定執(zhí)行小批量任務。這樣，能夠進一步提高調(diào)度系統(tǒng)效能 [30]。我們構建的物流車輛調(diào)度算法主要分為三個步驟，這三個步驟是確定運輸任務優(yōu)化類型；運輸任務優(yōu)化；運輸任務分派。車輛調(diào)度時候?qū)⒏鶕?jù)以三個基本步驟進行。具體步驟說明如圖31所示。確定運輸任務優(yōu)化類型運輸任務優(yōu)化運輸任務分派圖31調(diào)度策略的實施步驟步驟1：確定運輸任務優(yōu)化類型，本步驟首先確定任務是屬于何種運輸優(yōu)化類型，然后根據(jù)系統(tǒng)所確定運輸優(yōu)化類型，來選擇不同的優(yōu)化算法。本文將運輸優(yōu)化類型區(qū)分為調(diào)整型和規(guī)劃型兩大類型。調(diào)整型優(yōu)化這類任務的任務量比較少，大部分的車輛都處于停車場，這種類型結(jié)構比較簡單。優(yōu)化型優(yōu)化主要是車輛都處于動態(tài)狀態(tài)，貨物數(shù)量非常多，而且車輛要少于貨物數(shù)量，或者是車輛甚至會出現(xiàn)沒有任務的情況。步驟2：優(yōu)化車輛運輸任務本步驟是根據(jù)系統(tǒng)所確定的優(yōu)化類型選擇不同的優(yōu)化算法，由于優(yōu)化類型有調(diào)整型和規(guī)劃型兩種不同類型，我們將對兩類任務分別論述其優(yōu)化方式：（1）調(diào)整型的任務優(yōu)化方式，從名字可以看出主要是進行調(diào)整，也就是說系統(tǒng)調(diào)度Agent先將任務分別傳送給車輛Agent，車輛Agent在接收任務以后評估任務的信息，并且將評估的情況在回傳給系統(tǒng)調(diào)度Agent,系統(tǒng)調(diào)度Agent將根據(jù)反饋情況再分配任務。（2）規(guī)劃型的任務優(yōu)化，從名字來看主要是進行系統(tǒng)整體的規(guī)劃，這種算法的執(zhí)行情況是首先利用發(fā)貨單信息、庫存信息、車輛各種信息開始初始化系統(tǒng)模型，然后利用啟發(fā)式算法來反復迭代，進行不同優(yōu)化選取，最后求解出最優(yōu)的車輛線路。步驟3：運輸任務分派本步驟是調(diào)度控制Agent獲取優(yōu)化結(jié)果后，調(diào)度控制Agent的任務下發(fā)，由于其優(yōu)化任務方法的不同，其任務指派給車輛Agent的策略算法也會略有不同，根據(jù)不同的任務類型選擇不同的分派策略，下面我們將介紹兩種分配策略：（1）調(diào)整型的任務分派策略，調(diào)度控制Agent在獲取車輛Agent的反饋信息后，將反饋信息進行統(tǒng)一的評估選擇最優(yōu)的車輛Agent,如果發(fā)現(xiàn)某個車輛是最好的選擇，就