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