基于近似動態規劃的動態車輛調度算法

李　雪　聶蘭順　齊文艷　戰德臣

哈爾濱工業大學，哈爾濱，150001

基于近似動態規劃的動態車輛調度算法

李雪聶蘭順齊文艷戰德臣

哈爾濱工業大學，哈爾濱，150001

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

服務資源；近似動態規劃；動態調度；價值函數

0　引言

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

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

1　動態車輛調度的問題

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

圖1　軍演中車輛調度情景圖

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

表1　大規模、多類型動態車輛調度問題范圍約束

將本文研究的問題看作一個系統，問題中每個時刻的調度場景就可看作是該系統的一個狀態，那么每個時刻的系統狀態與該時刻的調度決策是一一對應的，不同的調度決策導致系統到達不同的狀態，因此，每個時刻不同的系統狀態價值，可以反映不同調度決策的優劣。由此，文中系統狀態價值的含義可以描述為：每個時刻不同的調度決策會對系統的現狀和將來產生不同的貢獻，由此，每個時刻的系統狀態價值就是該時刻對應調度決策對系統的貢獻值。

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

2　動態車輛調度問題模型

根據上述情景分析，對此調度場景建立相應的模型，主要包括車輛資源、任務信息和調度決策等。

2.1車輛資源

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

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

t時刻，可以調度的車輛資源的數量為

Rt=(Rta)a∈A

2.2任務信息

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

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

t時刻需要被滿足的任務數量為

Mt=(Mtb)b∈B

2.3調度決策

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

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

(1)

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

σtad為決策結果指示函數，用來捕獲決策的結果，且

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

為了通過數學形式來反映決策結果，需要定義一個決策函數，一些調度策略，在每個取樣時刻，給定系統的狀態信息，返回調度決策。

(2)

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

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

圖2　取樣時刻模型

2.4目標方程

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

(3)

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

3　基于近似動態規劃的動態車輛調度方法

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

3.1基本思路和設計流程

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

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

3.2調度策略的啟發式規則

在求解大規模、多類型車輛動態調度問題中，本文中車輛調度策略的啟發式算法規則集如下：

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

(2)對于當期出現的多個運輸任務，按照任務開始時間的緊急程度，優先滿足任務開始時間早的任務。

(3)對于在當期隨機出現的運輸任務請求，在任務開始時間和任務量滿足的前提下，優先考慮與現有任務是否可以合并執行，以減少車輛動用的數量。

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

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

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

(2)對于當期出現的每個任務Mt b,按當期任務的開始時刻從小(早)到大(晚)排序。

(3)for當期出現的、開始時間最早的任務：

do按任務類型要求、開始時間要求查詢是否有在外執行任務的、可調度的相應類型的車輛資源狀態。

if有在外執行任務的、可調度的車輛，

do返回在外執行任務的、可調度的車輛資源序列。

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

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

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

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

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

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

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

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

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

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

(9)按照貢獻函數的定義式計算不同調度決策的貢獻值，按當前最大貢獻值對應的調度決策調度車輛執行任務。

(10)將當期沒有車輛滿足的任務順延至下一期轉至步驟(1)。

3.3采用價值迭代和平滑策略訓練近似價值函數的算法設計

大規模、多類型車輛調度問題訓練階段的算法采用價值迭代和平滑策略來獲取系統狀態的真實值。具體算法步驟如下：

(1)初始化。

②設置n=1，N=100，n為取樣路徑標記，N為總的取樣次數；

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

②調用前述的啟發式規則算法，篩選得到最優的執行車輛；

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

⑤更新價值函數：

(4)

⑥計算車輛資源狀態轉換函數，更新車輛資源狀態：

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

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

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

3.4應用近似值函數進行大規模、多類型車輛調度算法設計

大規模、多類型車輛動態調度問題應用階段算法是對訓練階段獲得的近似價值函數進行調度應用，具體算法步驟如下:

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

(2)輸入當前時刻的運輸任務信息Mt。

(3)調用前述的啟發式規則算法，求解決策函數：

(5)

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

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

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

4　實驗

4.1實驗場景以及訓練結果

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

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

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

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

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

表2　選取第100次取樣的系統狀態的

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

(6)

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

圖4　擬合前達到穩態的系統狀態近似值空間分布

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

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

4.2算法正確性驗證

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

D≈N1/N2

(7)

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

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

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

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

4.3算法優越性驗證

為了進行算法的優越性驗證，首先從算法的策略角度進行分析。基于ADP的大規模、多類型車輛動態調度算法的優越性，主要體現在算法在每期的調度決策中不但都考慮了當期決策對當期系統狀態的影響，還考慮了當期決策對系統未來各期的影響。由此，如果我們僅以基于ADP算法中的啟發式規則集為基礎，只考慮當期決策對當前系統貢獻值的影響而不考慮對將來各期的影響，設計一個大規模、多類型車輛動態調度的貪心算法，貪心算法實現就是任務到達只要有車輛滿足條件就立即調度，這樣就可以比較出兩種調度策略的差異，從而判斷哪種調度策略更為優越。

為了評判兩種調度策略的優劣，我們根據問題的目標函數定義如下評判指標：

(8)

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

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

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

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

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

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

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

5　結語

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

[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]張景玲，趙燕偉，王海燕，等. 多車型動態需求車輛路徑問題建模及優化[J].計算機集成制造系統，2010,16(3):544-550.

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

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

WangXu,GeXianlong,DaiYing,ResearchonDynamicVehicleRoutingProblemBasedonTwo-phasedAlgorithm[J].ControlandDecision, 2012，27(2)：175-181.[6]袁建清.基于TS的動態車輛調度問題的混合算法研究[J].計算機現代化，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

國家自然科學基金資助項目(61273038)；國家科技支撐計劃資助項目(2013BAH17F03)；國家重點基礎研究發展計劃(973計劃)資助項目(2010CB328004)；山東省自主創新成果轉化重大專項(2012ZH1A0411)

TP311.52< class="emphasis_italic">DOI

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

李雪，女，1989年生。哈爾濱工業大學計算機科學與技術學院碩士研究生。主要研究方向為信息物理系統、資源動態調度。聶蘭順，男，1979年生。哈爾濱工業大學計算機科學與技術學院副教授。齊文艷，女，1987年生。哈爾濱工業大學計算機科學與技術學院碩士研究生。戰德臣，男，1965年生。哈爾濱工業大學計算機科學與技術學院教授、博士研究生導師。