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