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

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

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

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

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

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

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

2.1車輛資源

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

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

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

Rt=(Rta)a∈A

2.2任務(wù)信息

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

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

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

Mt=(Mtb)b∈B

2.3調(diào)度決策

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

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

(1)

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

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

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

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

(2)

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

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

圖2　取樣時(shí)刻模型

2.4目標(biāo)方程

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

(3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

else查詢?cè)谡{(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)度車輛按剩余載重/員從大到小進(jìn)行排序，得到每種類型可調(diào)度的車輛序列:

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

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

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

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

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

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

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

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

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

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

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

(1)初始化。

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

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

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

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

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

(4)

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

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

接下來可計(jì)算近似價(jià)值函數(shù)的線性表達(dá)式：

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

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

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

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

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

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

(5)

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

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

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

4　實(shí)驗(yàn)

4.1實(shí)驗(yàn)場(chǎng)景以及訓(xùn)練結(jié)果

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

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

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

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

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

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

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

(6)

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

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

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

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

4.2算法正確性驗(yàn)證

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

D≈N1/N2

(7)

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

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

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

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

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

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

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

(8)

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

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

經(jīng)過運(yùn)行后，兩種算法的各期目標(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算法策略進(jìn)行車輛調(diào)度，任務(wù)完成數(shù)量與車輛動(dòng)用數(shù)量比值的平均值要比按照貪心算法策略高16.7%，即對(duì)于同樣的任務(wù)，按ADP的調(diào)度策略進(jìn)行車輛調(diào)度比按照貪心策略調(diào)度進(jìn)行車輛調(diào)度，平均每期的車輛動(dòng)用數(shù)量要少16.7%。這說明，既考慮每期調(diào)度決策的當(dāng)期貢獻(xiàn)值，又考慮對(duì)未來各期影響的ADP策略，要比只考慮當(dāng)期貢獻(xiàn)值的貪心策略優(yōu)越，從而驗(yàn)證了算法的優(yōu)越性。

5　結(jié)語

車輛調(diào)度問題因其規(guī)模大、類型多、不確定性強(qiáng)等特征需要?jiǎng)討B(tài)的調(diào)度模型與調(diào)度優(yōu)化算法。針對(duì)大規(guī)模、多類型車輛動(dòng)態(tài)調(diào)度問題，基于近似動(dòng)態(tài)規(guī)劃的思想建立了系統(tǒng)狀態(tài)模型和調(diào)度決策模型，提出了車輛動(dòng)態(tài)調(diào)度的一系列啟發(fā)式規(guī)則，在此基礎(chǔ)上，提出了基于ADP的車輛動(dòng)態(tài)調(diào)度訓(xùn)練算法和應(yīng)用算法?；谟?xùn)練算法所獲得的仿真數(shù)據(jù)和屬性聚集獲得了系統(tǒng)的近似價(jià)值函數(shù)，基于該近似價(jià)值函數(shù)在應(yīng)用階段能夠在線快速生成調(diào)度決策，為實(shí)際決策提供依據(jù)。實(shí)驗(yàn)結(jié)果表明，近似價(jià)值函數(shù)能夠形成對(duì)狀態(tài)價(jià)值的有效近似，算法(在缺少未來信息的前提下)所生成的調(diào)度能夠兼顧當(dāng)前和未來，顯著好于貪心算法。因此，所提出模型和方法是解決大規(guī)模、多類型、不確定車輛動(dòng)態(tài)調(diào)度問題的有效思路。實(shí)際應(yīng)用過程中，其效果受模型的質(zhì)量、參數(shù)的辨識(shí)準(zhǔn)確性、訓(xùn)練數(shù)據(jù)的可獲得性及準(zhǔn)確性、對(duì)系統(tǒng)狀態(tài)演化的實(shí)時(shí)跟蹤能力等影響，需要針對(duì)真實(shí)系統(tǒng)進(jìn)行適應(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]張景玲，趙燕偉，王海燕，等. 多車型動(dòng)態(tài)需求車輛路徑問題建模及優(yōu)化[J].計(jì)算機(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). 多車型動(dò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的動(dòng)態(tài)車輛調(diào)度問題的混合算法研究[J].計(jì)算機(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é)基金資助項(xiàng)目(61273038)；國家科技支撐計(jì)劃資助項(xiàng)目(2013BAH17F03)；國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃)資助項(xiàng)目(2010CB328004)；山東省自主創(chuàng)新成果轉(zhuǎn)化重大專項(xiàng)(2012ZH1A0411)

TP311.52< class="emphasis_italic">DOI

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

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