基于近似動態(tài)規(guī)劃的動態(tài)車輛調(diào)度算法

李　雪　聶蘭順　齊文艷　戰(zhàn)德臣

哈爾濱工業(yè)大學(xué)，哈爾濱，150001

基于近似動態(tài)規(guī)劃的動態(tài)車輛調(diào)度算法

李雪聶蘭順齊文艷戰(zhàn)德臣

哈爾濱工業(yè)大學(xué)，哈爾濱，150001

針對物流配送服務(wù)業(yè)中，車輛調(diào)度問題日漸呈現(xiàn)任務(wù)規(guī)模大，車輛類型多、屬性多，調(diào)度實時性要求越來越高等特點，提出了基于近似動態(tài)規(guī)劃的動態(tài)車輛調(diào)度算法。根據(jù)當(dāng)前的任務(wù)需求與車輛狀態(tài)以及相應(yīng)的約束條件作出相應(yīng)的調(diào)度，并且對一些樣本進行訓(xùn)練，得到了一個近似價值函數(shù)。通過該價值函數(shù)，即可對任務(wù)迅速作出相應(yīng)的決策。仿真模擬實驗證明了該算法的有效性和優(yōu)越性。

服務(wù)資源；近似動態(tài)規(guī)劃；動態(tài)調(diào)度；價值函數(shù)

0　引言

針對車輛動態(tài)調(diào)度問題,國內(nèi)外專家學(xué)者開展了一系列研究。Gendreau等[1]著重研究了車輛動態(tài)調(diào)度問題中出現(xiàn)的各種不確定性信息的影響，指出在求解此問題時，對這些不確定性信息應(yīng)加以全面考慮；Powell[2]詳細(xì)分析了車輛動態(tài)調(diào)度問題中一類隨機車輛調(diào)度模型，采用改進的A-priori兩階段優(yōu)化方法求解了該問題；Minkoff[3]以馬爾可夫決策模型為基礎(chǔ)，完成了車輛動態(tài)調(diào)度問題基于馬爾可夫決策過程的建模求解，研究提出的算法在中小規(guī)模(10個需求)的車輛動態(tài)調(diào)度問題求解中可以得到比較滿意的解，但因其模型的局限性，算法對大規(guī)模的問題難以求解。針對動態(tài)車輛調(diào)度問題實時性強的特點，張景玲等[4]、王旭等[5]研究了車輛的動態(tài)調(diào)度問題，通過基于兩階段優(yōu)化的方法對該類問題進行了有效求解。袁建清[6]以解決車輛利用效率最大化為目標(biāo)，建立了幾類隨機數(shù)學(xué)模型，提出了相應(yīng)的智能算法，解決了車輛調(diào)度的不確定調(diào)度問題。文獻[7-9]針對車輛動態(tài)調(diào)度中的不同問題提出了相應(yīng)的解決方法。

本文以軍事行動中車輛動態(tài)調(diào)度問題為背景，提出了基于近似動態(tài)規(guī)劃的車輛動態(tài)調(diào)度算法。通過對車輛調(diào)度問題進行形式化描述，利用近似動態(tài)規(guī)劃方法對車輛動態(tài)調(diào)度問題進行建模，根據(jù)近似動態(tài)規(guī)劃的思想，設(shè)計實現(xiàn)求解大規(guī)模、多類型車輛調(diào)度的算法，并對算法進行了仿真性實驗，驗證了算法的有效性和優(yōu)越性。

1　動態(tài)車輛調(diào)度的問題

車輛調(diào)度問題對實時性有較高要求，即在盡可能短的時間內(nèi)，通過合理的運輸方式、運輸路徑、運輸工具組合來完成調(diào)度任務(wù)，是動態(tài)車輛調(diào)度問題領(lǐng)域關(guān)注的重點。對于動態(tài)車輛調(diào)度問題，本文以一個有關(guān)的軍事任務(wù)中的車輛調(diào)度情景予以描述，如圖1所示。

圖1　軍演中車輛調(diào)度情景圖

在某次軍事演習(xí)中，共涉及有1個車輛調(diào)度中心和N個駐防要點，車輛調(diào)度中心擁有載重車、乘坐車、牽引車和特種車四種類型的運力資源，共K輛運輸工具。每個駐防要點擁有兵員、物資、裝備等參演要素。演習(xí)中，需要在這N個駐防要點之間完成兵員、物資和裝備的調(diào)運服務(wù)。演習(xí)過程中無法預(yù)知哪個駐防要點具有運輸任務(wù)請求。根據(jù)描述情況，可對上述場景進行抽象，得到如表1所示的信息。

表1　大規(guī)模、多類型動態(tài)車輛調(diào)度問題范圍約束

將本文研究的問題看作一個系統(tǒng)，問題中每個時刻的調(diào)度場景就可看作是該系統(tǒng)的一個狀態(tài)，那么每個時刻的系統(tǒng)狀態(tài)與該時刻的調(diào)度決策是一一對應(yīng)的，不同的調(diào)度決策導(dǎo)致系統(tǒng)到達不同的狀態(tài)，因此，每個時刻不同的系統(tǒng)狀態(tài)價值，可以反映不同調(diào)度決策的優(yōu)劣。由此，文中系統(tǒng)狀態(tài)價值的含義可以描述為：每個時刻不同的調(diào)度決策會對系統(tǒng)的現(xiàn)狀和將來產(chǎn)生不同的貢獻，由此，每個時刻的系統(tǒng)狀態(tài)價值就是該時刻對應(yīng)調(diào)度決策對系統(tǒng)的貢獻值。

由此，我們用系統(tǒng)狀態(tài)價值來定義本文研究問題的優(yōu)化目標(biāo)：根據(jù)每個時刻不斷出現(xiàn)的運輸任務(wù)請求和不斷變化更新的車輛狀態(tài)，在一定條件下(如運輸任務(wù)類型、任務(wù)起止時間、車輛剩余載重、單次最大行駛里程等)，動態(tài)查詢所有車輛狀態(tài)，挑選合適的車輛，規(guī)劃合理的路線，盡可能地滿足任務(wù)點的運輸任務(wù)請求，使得每個時刻的系統(tǒng)狀態(tài)價值最大。

2　動態(tài)車輛調(diào)度問題模型

根據(jù)上述情景分析，對此調(diào)度場景建立相應(yīng)的模型，主要包括車輛資源、任務(wù)信息和調(diào)度決策等。

2.1車輛資源

車輛資源建模的基本思想是抽象出車輛資源的重要屬性，明確車輛資源的使用規(guī)則，從而約束車輛屬性向量的空間取值。車輛屬性主要包括靜態(tài)屬性和動態(tài)屬性：靜態(tài)屬性描述車輛資源的基本特點；動態(tài)屬性刻畫車輛資源的狀態(tài)。

通過以上對車輛資源的建模，可以得到:t時刻，可以調(diào)度的具有屬性a的車輛資源的數(shù)量為

t時刻，可以調(diào)度的車輛資源的數(shù)量為

Rt=(Rta)a∈A

2.2任務(wù)信息

任務(wù)請求信息也可以看作是系統(tǒng)資源，為了刻畫運輸任務(wù)的多方面屬性以及運輸任務(wù)的靜態(tài)屬性和動態(tài)屬性，筆者建立了調(diào)度決策模型。通過屬性向量來描述和刻畫運輸任務(wù)的狀態(tài)；通過明確運輸任務(wù)的使用規(guī)則，來約束其屬性向量的空間取值。

那么，t時刻需要被滿足的、具有屬性b的運輸任務(wù)請求的數(shù)量為

t時刻需要被滿足的任務(wù)數(shù)量為

Mt=(Mtb)b∈B

2.3調(diào)度決策

調(diào)度決策屬于動態(tài)系統(tǒng)的內(nèi)部信息，為了刻畫調(diào)度決策的內(nèi)容以及調(diào)度決策如何起效作用于車輛資源和運輸任務(wù)，對調(diào)度決策的建模要從對車輛資源和運輸任務(wù)的狀態(tài)影響出發(fā)，抽象其重要屬性，通過定義調(diào)度決策的策略集，來約束其屬性向量的空間取值。

d為調(diào)度決策的屬性向量，d=(d1(當(dāng)前派遣)，d2(暫不派遣)，d3(執(zhí)行車輛編號)，d4(執(zhí)行任務(wù)編號)，d5(預(yù)派遣時刻))；Da為可以作用于具有屬性a的車輛資源向量；Π為可行調(diào)度策略的集合。調(diào)度策略是指在給定系統(tǒng)狀態(tài)信息的前提下，決定一個調(diào)度決策的規(guī)則。在本文的研究中，調(diào)度策略由貢獻函數(shù)(反映當(dāng)前調(diào)度決策對系統(tǒng)當(dāng)前貢獻的影響)和近似價值函數(shù)(反映當(dāng)前調(diào)度決策對系統(tǒng)未來的影響)共同來反映。xtad為t時刻，具有屬性a的，被決策d作用的車輛的數(shù)量，則

(1)

xtad≥0,?a∈A,d∈Da

σtad為決策結(jié)果指示函數(shù)，用來捕獲決策的結(jié)果，且

那么t時刻，被派遣執(zhí)行運輸任務(wù)的、具有屬性a的車輛數(shù)量為σtadxtad；χt為t時刻，在給定有效信息下的可行調(diào)度策略的集合。

為了通過數(shù)學(xué)形式來反映決策結(jié)果，需要定義一個決策函數(shù)，一些調(diào)度策略，在每個取樣時刻，給定系統(tǒng)的狀態(tài)信息，返回調(diào)度決策。

(2)

本文在車輛調(diào)度決策過程中，考慮了兩種車輛調(diào)度方式：一是單車多任務(wù)，二是多車單任務(wù)。

此外，為了計算的方便，對時間采取離散時間模型，如圖2所示。在前述的對車輛資源、運輸任務(wù)、調(diào)度決策的符號中，右下角的時間角標(biāo)“t”，表示的是離散時間點t時刻或第t期，第t期指t=(t-1,t]。

圖2　取樣時刻模型

2.4目標(biāo)方程

把大規(guī)模、多類型車輛動態(tài)調(diào)度問題看作是一個“動態(tài)系統(tǒng)”，把每次作調(diào)度決策的場景看作是該系統(tǒng)在時間軸上的一個“狀態(tài)”St。St由車輛資源狀態(tài)Rt-1、運輸任務(wù)信息Mt和調(diào)度決策xt共同描述。St的價值是由貢獻函數(shù)和近似價值函數(shù)共同決定。貢獻函數(shù)捕獲調(diào)度決策xt對當(dāng)前系統(tǒng)狀態(tài)的影響；近似價值函數(shù)捕獲調(diào)度決策xt對未來系統(tǒng)狀態(tài)的影響。本文優(yōu)化目標(biāo)為：“每期決策，使得在盡可能完成運輸任務(wù)的前提下，動用的車輛數(shù)最少；長期目標(biāo)是在完成盡可能多的任務(wù)前提下，車輛動用率最低?！?，那么，大規(guī)模、多類型車輛動態(tài)調(diào)度問題的目標(biāo)方程可以形式化表達為

(3)

當(dāng)然，式(3)還要滿足一定的約束條件：①調(diào)度決策作用的車輛資源數(shù)量不能超過當(dāng)前已知的可調(diào)度車輛資源的數(shù)量；②每個時刻的調(diào)度決策滿足的任務(wù)請求數(shù)不能超過當(dāng)期已知的任務(wù)請求數(shù)；③調(diào)度決策作用的車輛資源數(shù)量、運輸任務(wù)數(shù)量都是正整數(shù)。

3　基于近似動態(tài)規(guī)劃的動態(tài)車輛調(diào)度方法

動態(tài)規(guī)劃是基于多階段決策過程尋優(yōu)問題提出的，廣泛應(yīng)用于工程學(xué)、運籌學(xué)、經(jīng)濟學(xué)等多個領(lǐng)域[10]。但是，經(jīng)典動態(tài)規(guī)劃所面臨的“維數(shù)災(zāi)難”使其只能解決小規(guī)模問題，限制了其應(yīng)用[11]。通過上面的建模，本文采用近似動態(tài)規(guī)劃(ADP)的思想設(shè)計動態(tài)車輛調(diào)度算法。

3.1基本思路和設(shè)計流程

基于ADP方法求解大規(guī)模、多類型的車輛動態(tài)調(diào)度問題需要劃分為兩個階段，第一階段是訓(xùn)練獲取近似價值函數(shù)的表達式，第二階段是應(yīng)用訓(xùn)練得到的近似價值函數(shù)的表達式指導(dǎo)車輛調(diào)度。ADP在訓(xùn)練數(shù)據(jù)階段是用本次系統(tǒng)產(chǎn)生的數(shù)據(jù)去更新上一次假設(shè)的數(shù)據(jù)，即將來對過去的影響，不斷地更新進而產(chǎn)生出近似價值函數(shù)；在應(yīng)用階段就是利用訓(xùn)練階段產(chǎn)生的近似價值函數(shù)來生成任務(wù)到來時的決策，即對未來的影響。

因此，第一階段算法的輸入是仿真得到的任務(wù)信息，輸出為訓(xùn)練周期中每期系統(tǒng)狀態(tài)價值的近似值。通過仿真任務(wù)信息來獲得、辨識和測量訓(xùn)練階段算法的各種參數(shù)，比如折扣因子、步長以及系統(tǒng)狀態(tài)初值等。在第二階段，應(yīng)用第一階段訓(xùn)練得到的近似價值函數(shù)表達式，根據(jù)當(dāng)前的運輸任務(wù)信息，求解決策函數(shù)(式(2))以得到優(yōu)化調(diào)度決策xt。因此，第二階段算法的輸入為當(dāng)前運輸任務(wù)信息，算法的輸出為優(yōu)化的調(diào)度決策xt。

3.2調(diào)度策略的啟發(fā)式規(guī)則

在求解大規(guī)模、多類型車輛動態(tài)調(diào)度問題中，本文中車輛調(diào)度策略的啟發(fā)式算法規(guī)則集如下：

(1)對于每期出現(xiàn)的新運輸任務(wù)，盡量從已經(jīng)派出在外執(zhí)行任務(wù)的車輛中挑選滿足新運輸任務(wù)要求的車輛，而盡量避免從調(diào)度中心增派車輛去滿足新任務(wù)，以此來減少每期的車輛動用數(shù)量。

(2)對于當(dāng)期出現(xiàn)的多個運輸任務(wù)，按照任務(wù)開始時間的緊急程度，優(yōu)先滿足任務(wù)開始時間早的任務(wù)。

(3)對于在當(dāng)期隨機出現(xiàn)的運輸任務(wù)請求，在任務(wù)開始時間和任務(wù)量滿足的前提下，優(yōu)先考慮與現(xiàn)有任務(wù)是否可以合并執(zhí)行，以減少車輛動用的數(shù)量。

(4)對于可以滿足某一運輸任務(wù)的多輛可調(diào)度車輛，先將這些車輛按照剩余載重的大小進行排序，然后依次挑選剩余載重大的車輛去執(zhí)行該運輸任務(wù)；對于剩余載重也相同的車輛，按照可以到達任務(wù)起始點的時間排序，依次選擇可以最早到達任務(wù)起始點的車輛執(zhí)行該運輸任務(wù)，這樣可以在多車單任務(wù)中，減少車輛動用的數(shù)量，從而降低車輛的動用率。

啟發(fā)式規(guī)則的輸入為當(dāng)前時刻的運輸任務(wù)信息，即需要被滿足、具有某屬性的多個運輸任務(wù)；輸出為可調(diào)度的車輛序列和已調(diào)度的車輛序列。算法具體步驟描述如下。

(1)查詢當(dāng)期任務(wù)信息Mt，按任務(wù)類型分類匯總得到每種類型任務(wù)數(shù)量Mt b2。

(2)對于當(dāng)期出現(xiàn)的每個任務(wù)Mt b,按當(dāng)期任務(wù)的開始時刻從小(早)到大(晚)排序。

(3)for當(dāng)期出現(xiàn)的、開始時間最早的任務(wù)：

do按任務(wù)類型要求、開始時間要求查詢是否有在外執(zhí)行任務(wù)的、可調(diào)度的相應(yīng)類型的車輛資源狀態(tài)。

if有在外執(zhí)行任務(wù)的、可調(diào)度的車輛，

do返回在外執(zhí)行任務(wù)的、可調(diào)度的車輛資源序列。

else查詢在調(diào)度中心的車輛資源，返回可調(diào)度的車輛資源序列：

Rt,a2=1,a3≠0Rt,a2=2,a3≠0Rt,a2=3,a3≠0Rt,a2=4,a3≠0

(4)將步驟(3)中得到的可調(diào)度車輛按剩余載重/員從大到小進行排序，得到每種類型可調(diào)度的車輛序列:

Rt,a2=1,a5Rt,a2=2,a5Rt,a2=3,a5Rt,a2=4,a5

(5)對步驟(4)中挑選出來的可調(diào)度車輛序列中，再對剩余載重相同的車輛按照起效時間從小(早)到大(晚)進行排序，得到每種類型可調(diào)度的車輛新序列如下：

Rt,a2=1,a5,a10Rt,a2=2,a5,a10Rt,a2=3,a5,a10Rt,a2=4,a5,a10

(6)計算單車是否可以滿足該任務(wù)。

if單車滿足，do轉(zhuǎn)至步驟(7)，else轉(zhuǎn)至步驟(8)。

(7)從步驟(5)中挑選第一輛車。

(8)從步驟(3)中依次挑選車輛，直到車輛組合剩余載重之和滿足任務(wù)量要求。

(9)按照貢獻函數(shù)的定義式計算不同調(diào)度決策的貢獻值，按當(dāng)前最大貢獻值對應(yīng)的調(diào)度決策調(diào)度車輛執(zhí)行任務(wù)。

(10)將當(dāng)期沒有車輛滿足的任務(wù)順延至下一期轉(zhuǎn)至步驟(1)。

3.3采用價值迭代和平滑策略訓(xùn)練近似價值函數(shù)的算法設(shè)計

大規(guī)模、多類型車輛調(diào)度問題訓(xùn)練階段的算法采用價值迭代和平滑策略來獲取系統(tǒng)狀態(tài)的真實值。具體算法步驟如下：

(1)初始化。

②設(shè)置n=1，N=100，n為取樣路徑標(biāo)記，N為總的取樣次數(shù)；

(3)對于訓(xùn)練階段的每一個取樣時刻，t=1,2,…,30。

②調(diào)用前述的啟發(fā)式規(guī)則算法，篩選得到最優(yōu)的執(zhí)行車輛；

③將執(zhí)行車輛中可以推遲派遣的，推遲一期派遣；

⑤更新價值函數(shù)：

(4)

⑥計算車輛資源狀態(tài)轉(zhuǎn)換函數(shù)，更新車輛資源狀態(tài)：

(4)n加1，如果n≤N，跳轉(zhuǎn)至步驟(2)。

接下來可計算近似價值函數(shù)的線性表達式：

其中，θ1、θ2和θ3為待定參數(shù)，根據(jù)上述ADP求解問題的算法步驟(5)達到穩(wěn)態(tài)的一組有效值，采用線性回歸的方法求解得到待定參數(shù)θ1、θ2和θ3，從而得到近似價值函數(shù)的線性表達式。

3.4應(yīng)用近似值函數(shù)進行大規(guī)模、多類型車輛調(diào)度算法設(shè)計

大規(guī)模、多類型車輛動態(tài)調(diào)度問題應(yīng)用階段算法是對訓(xùn)練階段獲得的近似價值函數(shù)進行調(diào)度應(yīng)用，具體算法步驟如下:

(1)初始化車輛資源的狀態(tài)R0。

(2)輸入當(dāng)前時刻的運輸任務(wù)信息Mt。

(3)調(diào)用前述的啟發(fā)式規(guī)則算法，求解決策函數(shù)：

(5)

其中，調(diào)度決策xt為式(5)的解。

(4)更新車輛資源狀態(tài)：

Rt=RM(Rt-1,ωt,xt)

4　實驗

4.1實驗場景以及訓(xùn)練結(jié)果

根據(jù)上文中算法的描述，進行了相應(yīng)的實驗。實驗過程中，假定有4種不同類型的車輛，每種類型的車輛有10輛，10個任務(wù)點，4種不同的任務(wù)。價值迭代算法需要為其設(shè)計合理的收斂準(zhǔn)則。實驗中，在取樣時間軸上，具有相同周期長度和固定期數(shù)的一組連續(xù)的系統(tǒng)狀態(tài)，本文嘗試分別取樣50次和取樣100次，觀察每條取樣路徑上某一相同時刻系統(tǒng)狀態(tài)價值的近似值是否趨于穩(wěn)態(tài)，用MATLAB分析，結(jié)果如圖3所示。

(a)每條取樣路徑上 t1時刻的系統(tǒng)狀態(tài)近似值(50次)

(b)每條取樣路徑上 t1時刻的系統(tǒng)狀態(tài)近似值(100次)圖3　算法迭代50次和100次后系統(tǒng)近似值變化圖

由圖3觀察比較可以發(fā)現(xiàn)：算法在迭代50次后系統(tǒng)狀態(tài)近似值依然呈現(xiàn)出穩(wěn)步上升趨勢，說明值迭代策略還未逼近到系統(tǒng)狀態(tài)的真實值；在迭代100次后，觀察發(fā)現(xiàn)系統(tǒng)狀態(tài)近似值已經(jīng)趨于穩(wěn)態(tài)，說明值迭代策略已經(jīng)逼近到系統(tǒng)狀態(tài)的真實值，算法已經(jīng)收斂，所以算法可以終止。

取第100次迭代的最后一組系統(tǒng)狀態(tài)近似值進行擬合求解，求得近似價值函數(shù)的線性表達式，如表2所示。

表2　選取第100次取樣的系統(tǒng)狀態(tài)的

由此得到近似價值函數(shù)的線性表達式如下：

(6)

這里采用粒度比較大的線性擬合方式，擬合前這組系統(tǒng)狀態(tài)近似值的空間表現(xiàn)形式和擬合后近似價值函數(shù)的空間展現(xiàn)形式分別如圖4和圖5所示，由于線性函數(shù)存在的誤差較大，因此本文用盡可能多的離散值，用非線性的表達方式來得出這個函數(shù)。

圖4　擬合前達到穩(wěn)態(tài)的系統(tǒng)狀態(tài)近似值空間分布

圖5　擬合后近似價值函數(shù)的空間形式

圖4、圖5中，z軸為當(dāng)期系統(tǒng)系統(tǒng)狀態(tài)近似值，x軸為當(dāng)期車輛動用數(shù)量，y軸為當(dāng)期任務(wù)滿足數(shù)量，由圖可見近似價值函數(shù)的線性表達式能夠比較好地匹配解空間的值。

4.2算法正確性驗證

得到了近似價值函數(shù)的表達式之后，我們首先進行算法正確性的驗證。利用單期決策(忽略一期以后的影響)的滿意度“D”來反映算法的正確性，決策滿意度的計算如下：

D≈N1/N2

(7)

其中，N1表示當(dāng)期應(yīng)該被滿足的運輸請求任務(wù)數(shù)，N2表示應(yīng)用近似價值函數(shù)計算后得到的當(dāng)期實際被滿足的任務(wù)數(shù)。決策滿意度越高，說明算法越正確。

通過近似價值函數(shù)的表達式(式(6))求解決策函數(shù)(式(1))，得到的調(diào)度決策結(jié)果為x1ad=5，x2ad=1，即1時刻的任務(wù)全部派遣車輛執(zhí)行，2時刻的任務(wù)執(zhí)行任務(wù)6。

算法正確性分析：最優(yōu)的調(diào)度決策為1時刻和2時刻的7個任務(wù)應(yīng)該全部執(zhí)行，即N1=7，而近似價值函數(shù)求解決策函數(shù)給出的調(diào)度決策是實際執(zhí)行6個任務(wù)，即N2=6。如果下一時刻還能滿足條件的話，會延期調(diào)度剩余的任務(wù)。

決策滿意度由式(7)計算為85.71%，即正確性為85.71%?？梢?，算法能夠在較短時間內(nèi)，得到正確性較高的近似滿意解。

4.3算法優(yōu)越性驗證

為了進行算法的優(yōu)越性驗證，首先從算法的策略角度進行分析?；贏DP的大規(guī)模、多類型車輛動態(tài)調(diào)度算法的優(yōu)越性，主要體現(xiàn)在算法在每期的調(diào)度決策中不但都考慮了當(dāng)期決策對當(dāng)期系統(tǒng)狀態(tài)的影響，還考慮了當(dāng)期決策對系統(tǒng)未來各期的影響。由此，如果我們僅以基于ADP算法中的啟發(fā)式規(guī)則集為基礎(chǔ)，只考慮當(dāng)期決策對當(dāng)前系統(tǒng)貢獻值的影響而不考慮對將來各期的影響，設(shè)計一個大規(guī)模、多類型車輛動態(tài)調(diào)度的貪心算法，貪心算法實現(xiàn)就是任務(wù)到達只要有車輛滿足條件就立即調(diào)度，這樣就可以比較出兩種調(diào)度策略的差異，從而判斷哪種調(diào)度策略更為優(yōu)越。

為了評判兩種調(diào)度策略的優(yōu)劣，我們根據(jù)問題的目標(biāo)函數(shù)定義如下評判指標(biāo)：

(8)

其中，R為目標(biāo)值，N(t)為每期被滿足的任務(wù)數(shù)，N(v)為每期調(diào)度動用的車輛數(shù)。對于本文的問題，我們的優(yōu)化目標(biāo)是：對于每期調(diào)度決策，在盡可能完成任務(wù)的前提下，動用車輛數(shù)最少。那么，式(8)中的目標(biāo)值越大，則表明每期執(zhí)行相同任務(wù)數(shù)的前提下，車輛動用的數(shù)量越少。

對兩種算法給定同一組算例參數(shù)：取樣次數(shù)N為100，訓(xùn)練周期T為30，每期任務(wù)數(shù)為1～15的隨機數(shù)。

經(jīng)過運行后，兩種算法的各期目標(biāo)值的平均值的整體圖和局部圖分別如圖6和圖7所示。

(a)基于啟發(fā)式的ADP算法

(b)基于啟發(fā)式的貪心算法圖6　兩種算法的目標(biāo)值比較(整體圖)

(a)圖6a放大圖(b)圖6b放大圖圖7　兩種算法的目標(biāo)比較(局部放大圖)

由圖6和圖7可見，基于ADP的算法策略目標(biāo)值的平均值在1.4左右，而貪心算法目標(biāo)值的平均值在1.2左右，這表明，按照ADP算法策略進行車輛調(diào)度，任務(wù)完成數(shù)量與車輛動用數(shù)量比值的平均值要比按照貪心算法策略高16.7%，即對于同樣的任務(wù)，按ADP的調(diào)度策略進行車輛調(diào)度比按照貪心策略調(diào)度進行車輛調(diào)度，平均每期的車輛動用數(shù)量要少16.7%。這說明，既考慮每期調(diào)度決策的當(dāng)期貢獻值，又考慮對未來各期影響的ADP策略，要比只考慮當(dāng)期貢獻值的貪心策略優(yōu)越，從而驗證了算法的優(yōu)越性。

5　結(jié)語

車輛調(diào)度問題因其規(guī)模大、類型多、不確定性強等特征需要動態(tài)的調(diào)度模型與調(diào)度優(yōu)化算法。針對大規(guī)模、多類型車輛動態(tài)調(diào)度問題，基于近似動態(tài)規(guī)劃的思想建立了系統(tǒng)狀態(tài)模型和調(diào)度決策模型，提出了車輛動態(tài)調(diào)度的一系列啟發(fā)式規(guī)則，在此基礎(chǔ)上，提出了基于ADP的車輛動態(tài)調(diào)度訓(xùn)練算法和應(yīng)用算法。基于訓(xùn)練算法所獲得的仿真數(shù)據(jù)和屬性聚集獲得了系統(tǒng)的近似價值函數(shù)，基于該近似價值函數(shù)在應(yīng)用階段能夠在線快速生成調(diào)度決策，為實際決策提供依據(jù)。實驗結(jié)果表明，近似價值函數(shù)能夠形成對狀態(tài)價值的有效近似，算法(在缺少未來信息的前提下)所生成的調(diào)度能夠兼顧當(dāng)前和未來，顯著好于貪心算法。因此，所提出模型和方法是解決大規(guī)模、多類型、不確定車輛動態(tài)調(diào)度問題的有效思路。實際應(yīng)用過程中，其效果受模型的質(zhì)量、參數(shù)的辨識準(zhǔn)確性、訓(xùn)練數(shù)據(jù)的可獲得性及準(zhǔn)確性、對系統(tǒng)狀態(tài)演化的實時跟蹤能力等影響，需要針對真實系統(tǒng)進行適應(yīng)性的調(diào)整、仿真和近似。

[1]GendreauM,PotvinJY.DynamicVehicleRoutingandDispatching[J].FleetManagementandLogistics,1998:115-126.

[2]PowellWB.StochasticandDynamicNetworksandRouting[J].DepartmentofCivilEngineeringandOperationsResearch,PrograminStatistics&OperationsResearch, 1995,8:141-295.

[3]MinkoffAS.AMarkovDecisionModelandDecompositionHeuristicforDynamicVehicleDispatching[J].OperationsResearch, 1993,41:77-90.

[4]張景玲，趙燕偉，王海燕，等. 多車型動態(tài)需求車輛路徑問題建模及優(yōu)化[J].計算機集成制造系統(tǒng)，2010,16(3):544-550.

ZhangJingling,ZhaoYanwei,WangHaiyan,etal.ModelingandAlgorithmsforaDynamicMulti-vehicleRoutingProblemwithCustomers’DynamicRequests[J].ComputerIntegratedManufacturingSystems, 2010,16(3):544-550.

[5]王旭，葛顯龍，代應(yīng). 多車型動態(tài)需求車輛路徑問題建模及優(yōu)化[J].控制與決策，2012，27(2)：175-181.

WangXu,GeXianlong,DaiYing,ResearchonDynamicVehicleRoutingProblemBasedonTwo-phasedAlgorithm[J].ControlandDecision, 2012，27(2)：175-181.[6]袁建清.基于TS的動態(tài)車輛調(diào)度問題的混合算法研究[J].計算機現(xiàn)代化，2012(6):73-75.

Yuan Jianqing.Mixed Tabu Search Algorithm for Dynamic Vehivle Scheduling Problem[J].Jisuanji Yu Xiandaihua, 2012(6):73-75.

[7]Azi N, Gendreau M, Potvin J Y. A Dynamic Vehicle Routing Problem with Multiple Delivery Routes[J]. Annals of Operations Research, 2012, 199(1): 103-112.

[8]Warren B. Powell，Approximate Dynamic Programming for Operations Research[M]. Princeton:Department of Operations Research and Financial Engineering Princeton University, 2005.

[9]Clara Novoa,Robert Storer.An Approximate Dynamic Programming Approach for the Vehicle Routing Problem with Stochastic Demands[J]. European Journal of Operational Research,2009,196(2):509-515.

[10]Si J,Barot A G,Powell W B,et al.Handbook of Learning and Approximate Dynamic Programming: Sealing up to the Real World[M]. New York: IEEE Press and John Wiley & Sons,2004.

[11]Kirk D E. Optimal Control Theory: An Introduction[M]. Englewood Cliffs:Prentice_Hall,1970.

(編輯王艷麗)

An Algorithm of Dynamic Vehicle Scheduling Problem Based on Approximate Dynamic Programming

Li XueNie LanshunQi WenyanZhan Dechen

Harbin Institute of Technology,Harbin,150001

Vehicle scheduling in service industry of logistics distribution was presenting features including the tasks tended to be of large scale, vehicles were multi-type and had multiple attributes as well as high demands for real-time scheduling. To solve these problems, this paper proposed a dynamic vehicle scheduling algorithm based on the approximate dynamic programming. An approximate value function was obtained through training of some samples, and according to mission requirements, vehicle state and conditions, and quick scheduling decisions could be made with the value function. The simulation test has proved the correctness and effectiveness of the algorithm.

service resource; approximate dynamic programming; dynamic scheduling; value function

2013-04-23

國家自然科學(xué)基金資助項目(61273038)；國家科技支撐計劃資助項目(2013BAH17F03)；國家重點基礎(chǔ)研究發(fā)展計劃(973計劃)資助項目(2010CB328004)；山東省自主創(chuàng)新成果轉(zhuǎn)化重大專項(2012ZH1A0411)

TP311.52< class="emphasis_italic">DOI

：10.3969/j.issn.1004-132X.2015.05.020

李雪，女，1989年生。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院碩士研究生。主要研究方向為信息物理系統(tǒng)、資源動態(tài)調(diào)度。聶蘭順，男，1979年生。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院副教授。齊文艷，女，1987年生。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院碩士研究生。戰(zhàn)德臣，男，1965年生。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院教授、博士研究生導(dǎo)師。