基于參數誘導的隨機動態車隊調度求解策略

李 冰，李 靜，軒 華

（1.鄭州大學管理工程學院，河南鄭州450001；2.鄭州大學人事處，河南鄭州450001）

基于參數誘導的隨機動態車隊調度求解策略

李 冰1，李 靜2，軒 華1

（1.鄭州大學管理工程學院，河南鄭州450001；2.鄭州大學人事處，河南鄭州450001）

基于運輸任務產生的隨機特性，進行運輸任務分布生成機制設計，并給出路網上運輸任務分布函數的確定方法，進而研究車輛分布更新過程.在對兩大狀態變量的更新環節進行設計的基礎上，引入車輛增量收益參數，并給出車輛增量收益參數的確定方法及動態更新過程，進而將該參數引入問題模型中的未來時段期望收益函數部分，實現問題模型的可分解形式改造.給出隨機動態問題的完整求解算法流程.最后演示獨立節點處收益函數擬合過程，并對控制參數對問題求解質量的影響進行數值分析，從而驗證方法的有效性.

隨機動態車隊調度；車輛增量收益參數；逐段分解；控制變量

1 引 言

開展貨物運輸作業的優化組織工作是降低運輸成本、提高運輸效率的重要手段和關鍵.貨運車輛作為貨物運輸的直接載體，同時也是貨物運輸作業過程中最重要的可支配資源.運用所掌握的車隊資源合理安排組織運輸任務，消除對流、迂回、重復等不合理現象，實現車隊資源的優化組合和配置，并達到以最少的資源投入獲得最優經濟效益的目的，是整個貨物運輸優化組織工作的核心內容.

對貨物運輸系統優化問題的研究主要集中在車輛路線安排問題.文獻［1］研究基于協作的帶時間窗的車輛調度問題，設計了一種求解車輛路線優化問題的兩階段算法.文獻［2］建立考慮車載率和油耗的綜合費用為優化目標的車輛路線優化模型，并設計了改進遺傳算法對車輛路線進行實時再優化.文獻［3］引用集劃分方法研究了機場接送車輛的路線優化問題.文獻［4］研究了一類求解單車型路徑優化問題的禁忌搜索算法.文獻［5］研究了一類帶時間窗的車輛路徑優化問題，并設計了分支定界算法對問題進行求解.文獻［6］研究解決多車場車輛路線優化問題，首先運用聚類分析進行客戶聚類，進而利用遺傳算法進行路線優化，最后進行基于粒子群算法的優化調整.

針對確定性動態車隊調度計劃安排問題，文獻［7］研究了一類面向公眾服務的機隊調度優化問題，構建了一個機隊分配優化模型，并設計了粒子群優化算法.文獻［8］研究了維修服務車隊調度問題，提出了一個新的和改進的Lipschitz優化算法.文獻［9］研究了機場擁擠情況下的飛行調度計劃制定和機隊分配問題，構建了一個混合整數線性規劃模型.文獻［10］研究了用于存儲補給的運輸車隊調度問題，構建了一個基于運輸成本最小化的整數規劃模型，并設計了列生成方法對模型進行求解.

對于隨機車隊調度優化問題可分為未來需求可預先獲取的隨機動態車隊調度問題和未來需求無法預先獲取的隨機動態車隊調度問題.對于未來需求可預先獲取的隨機車隊調度問題，文獻［11］從多目標規劃和隨機規劃的角度構建了應急物資配送的多目標隨機規劃模型.模型設定當受災情景發生時，某一可觀測信息發生的概率已知，其值可以通過歷史統計得出.文獻［12］研究了一類隨機旅行時間的區域公交車輛調度問題.因突發事件而引起的車輛延時完成某班次的時間事先難以預料，將其看作隨機變量，假設延時時間服從正態分布，從而將該模型轉化為一類確定性數學模型.文獻［13］研究了一類基于隨機運行時間的車隊調度方法用于租車公司的日常車輛管理.車輛運行時間雖然是一隨機變量但可以根據歷史數據進行預測，從而將問題轉化為一個確定性的多商品網絡流問題進行求解，并設計了基于仿真的評價方法.

對于未來需求無法預先獲取的隨機車隊調度問題，文獻［14］對隨機需求客戶構建了三維量子比特矩陣，通過產生隨機數的方法形成客戶服務的先后序列，從而形成二維0-1觀測矩陣.文獻［15］研究了具有不確定需求和客戶選擇服務水平的隨機動態車隊管理問題，因客戶需求量和車輛運輸時間均為隨機變量，且無法通過歷史數據分析其分布函數，設計了部分獨立的隨機弧來表述不確定客戶需求和車輛運輸時間.文獻［16］研究了不確定需求下越庫中心選址和車輛路線優化問題，引入基于預期區間和模糊數的期望值目標函數可行度，構建混合模糊概率隨機規劃模型，并設計了求解算法.

本文研究了一類未來需求無法預先獲取的多階段隨機動態車隊調度問題，設計了不同于已有研究工作中所采用的處理方法.基于運輸任務產生的隨機特性，設計運輸任務分布生成機制，進而引入車輛增量收益參數，并給出車輛增量收益參數的確定方法及動態更新過程，進而將該參數引入問題模型以實現可分解模型形式改造，最終形成逐段分解求解策略.

2 隨機動態車隊調度模型

2.1 符號說明

隨機動態車隊調度問題是指在計劃周期內制定合理的車隊調度方案，以滿足發生在各時段各節點處的運輸任務需求，從而達到總收益最大或成本最小的目標.因為服務周期內各時段各節點間的運輸任務數是不確定，需要通過歷史數據擬合出其概率分布函數，所以車隊調度問題具有隨機特性；又因為在進行某時段的車隊調度時不僅要考慮本時段的經濟效益，同時還要考慮到對未來時段車隊調度工作的影響，所以問題又具有動態特性.為便于問題描述，對問題中所涉及的變量介紹如下：

G（N,E）為運輸網絡，其中N，E分別表示G中的節點集合和弧集合.

T為計劃周期內的時段劃分集合，計劃周期由K個相同長度的時段組成，運輸任務分別在這K個時段產生，可表示為T=｛1，2，...，K｝.

lijt為時段t節點i處產生的目的地為j的運輸任務數，t=1，2，...，K.該變量為隨機變量，其概率空間可通過歷史數據統計得知，記為（?，F，Pr），其中?為樣本空間、F為分布函數、Pr為概率測度.

Vi1為計劃周期之初，各節點處的車輛數.該變量值為已知.

Vit為時段t節點i處的車輛數，t=2，3，...，K.

rij為發送運輸任務從節點i到節點j所能創造的純利潤，該參數為已知.

cij為當i≠j時，表示車輛從節點i空移到節點j的成本；當i=j時，表示車輛在節點i處原地駐留的成本，這里假設?i∈N，且cii=0.該參數為已知.

xijt為整數變量，表示時段t從節點i裝載任務發往節點j的車輛數，t=1，2，...，K.

yijt為整數變量，當i≠j時，表示時段t從節點i發往節點j的空車數；當i=j時，表示時段t在節點i處原地駐留到時段t+1的車數.

2.2 問題的隨機特性分析

運輸任務數lijt為一隨機變量，從而時段t路網上各節點間的任務數組合在一起就形成了一個任務數矩陣，該矩陣為一個n×n的隨機數方陣，該方陣中的每一個分量均為一個隨機數，表示由節點i到節點j的運輸任務數.計劃周期內各時段的運輸任務數lijt可簡記為｛L（t），t∈T｝，其概率空間為（?，F，Pr）.要全面了解此隨機變量，就要知道對于每個時段路網上運輸任務數隨機變量lijt的分布函數.獲得F（·）概率分布函數的方法如下：

1）選取某個計劃周期作為統計時間范圍；

2）選取計劃周期內路網上任意兩點間的運輸任務數lijt作為統計對象；

3）得到多個lijt的變化值，利用概率統計技術近似擬合出lijt的概率分布函數.

2.3 問題的描述

計劃周期T被等分為K個時段，運輸網絡G（N,E）中各節點處分別在這K個時段產生新的運輸任務l.時段t在節點i處產生且目的地為節點j的運輸任務數為一隨機變量lijt，但該隨機變量的概率分布函數可以通過歷史數據利用概率統計技術得知.現有Q輛貨運車輛，且這Q輛車在計劃周期開始時在各節點處的分配數Vi1已知.現在要分別制定計劃周期內各時段t各節點i處的車隊調度方案，使得整個計劃周期內所能創造的總收益最大.

2.4 模型的建立

基于問題的描述，建立問題的數學模型P1如下

問題的目標函數（1）是為了使車隊調度方案在整個計劃周期內所創造的總收益值達到最大化；約束（2）表示載貨車輛數不能超過運輸任務數，運輸任務數為一隨機變量，概率空間為（?，F，Pr），α為給定的置信水平，表示約束條件（2）成立的概率；約束（3）表示節點處的載貨車輛數、空移車數和原地駐留車數之和等于該節點處的可調配車輛總數；約束（4）表示本時段各節點發往某節點的載貨車輛數、空移車數和該節點的原地駐留車數共同構成下一時段該節點可調配車輛總數.

因為模型的約束條件中含有隨機變量lijt，且應在觀察到隨機變量的實現之前作出決策，所以模型屬于隨機規劃中的機會約束規劃（Chance Constrained Programming）.當問題涉及的運輸網絡節點比較多、時段比較多時，所建立的問題模型為一個大規模多階段隨機規劃模型，求解非常困難.

2.5 模型的可分解形式改造

1）決策變量

模型的決策變量由兩個分量組成，分別為重車數變量和空車數變量.

以xt表示計劃周期內時段t各節點處滿載移動的車輛數量，即xt=｛xijt|?i,j∈N,?t∈T｝.

以yt表示計劃周期內時段t各節點處空車移動和原地駐留的車輛數量，即yt=｛yijt|?i,j∈N,?t∈T｝.

2）狀態變量

模型的狀態變量是決策變量求解的基礎，它由兩個分量組成，分別為車輛數變量和任務數變量，記為S（t）=（Vt,Lt）.模型的狀態變量S（t）每階段需要不斷更新，狀態變量S（t）的更新過程設計是問題求解的關鍵之一.

以Vt表示計劃周期內時段t各節點處的車輛數，即Vt=｛Vit|?i∈N，?t∈N｝.車輛數變量Vt是一個不斷更新的過程，第一時段車輛數變量V1是已知的，以后其他各時段車輛數變量Vt的確定需要利用決策變量（xt，yt）來進行求解.

以Lt表示計劃周期內時段t節點之間的運輸任務數，即Lt=｛lijt|?i,j∈N，?t∈N｝.對于由n個節點組成的運輸網絡，Lt可用一個n×n的隨機矩陣表述，該矩陣中的每一個分量均為一個隨機量，表示由節點i到節點j的運輸任務數，顯然該隨機矩陣對角線的分量均為0，因為路網上不會產生始點和終點一致的運輸任務.

利用決策變量和狀態變量，引入車隊調度方案對未來時段所造成的期望收益E［Rt（Vt，Lt）］，對模型進行可分解改造，將其表述為可分解形式P2（由P2-1和P2-2組成），即

問題的模型P1為一個大規模隨機規劃模型，直接求解非常困難.對模型進行可分解形式改造，P2形式的模型轉變為一個K階段隨機規劃模型，可采取分階段處理的辦法進行逐一求解.

3 關鍵環節處理

要解決模型P2的求解問題，需要破解兩大關鍵環節的處理難題，即

1）關鍵環節之一：兩大狀態變量的更新環節設計.即任務分布生成過程設計和車輛分布更新過程設計.

2）關鍵環節之二：目標函數中未來時段期望收益函數的處理問題.模型P2中目標函數的第二部分E［Rt（Vt，Lt）］是模型是否能夠成功分解的關鍵所在，其含義是本階段車隊調度方案對未來時段所造成的預期收益的數學期望值.

下面分別就這兩大關鍵環節的處理問題進行詳細探討.

3.1 狀態變量的處理

1）任務分布生成

運輸任務分布的表述形式：運輸網絡中節點i和節點j間形成一條固定的運輸線路，該運輸線路上的運輸任務數lij為一隨機變量.對于由n個節點組成的運輸網絡，共形成n×n條運輸線路，每條運輸線路上的運輸任務數lij均為一隨機數，從而時段t運輸網絡中各條線路上的運輸任務數分布Lt可由一個n×n的方陣表示，稱時段t路網上的運輸任務分布矩陣，記為Lt.運輸任務分布矩陣Lt可以清楚的描述時段t路網上的運輸任務分布情況.

路網上運輸任務分布函數的確定：從歷史數據中抽取時段t路網中節點i處發往節點j的運輸任務數lij作為樣本數據，并分析頻數統計，進而擬合密度函數，從而得到lij的經驗分布.具體步驟為：對運輸任務數lij進行數據抽樣；計算各抽樣數據的頻數；根據抽樣數據頻數，計算運輸任務數lij各樣本數據的出現概率，從而繪制平滑密度函數曲線；確定經驗分布函數曲線；利用擬合優度檢驗，確定最合理的運輸任務數lij的分布函數F（Lt）.

路網上運輸任務分布矩陣的形成：利用擬合出的時段t路網上的運輸任務分布函數F（Lt），生成時段t路網上的運輸任務分布矩陣Lt，將其作為模型求解的狀態向變量.

2）車輛分布更新

因為下一時段某節點處的車輛數由上一時段各節點發往該節點的載貨車輛、空移車輛和該節點的原地駐留車輛共同構成，故利用求得的時段t的車隊調度方案，即解變量（xijt，yijt），?i,j∈N，確定時段t+1各節點處的車輛分布數.車輛數的更新過程為

3.2 期望收益函數的處理

模型P2的目標函數Rt（Vt，Lt）表示在時段t采取車隊調度方案（xijt，yijt）所能創造的收益值.因為時段t的車隊調度方案（xijt，yijt）會對時段t以后各時段的車隊調度方案制定產生影響，所以Rt（Vt，Lt）不僅包括車隊調度方案（xijt，yijt）在時段t所創造的收益而且包括其對以后各時段的影響.在本文中，設計了未來時段期望收益函數E［Rt+1（Vt+1，Lt+1）］來表述本時段車隊調度方案對以后時段的影響.

期望收益函數E［Rt+1（Vt+1，Lt+1）］的處理是模型能夠成功分解的關鍵所在.時段t+1節點j處所創造的期望收益值E［Rj,t+1（Vj,t+1，Lj,t+1）］等于該處各車輛所創造的期望收益值之和，其取值同該處的車輛數Vj,t+1直接相關.設節點j處增加一輛車所引起的期望收益值增加量為λj,t+1，則

將上式代入式（16）可知

從而可知

將上式代入模型P2的目標函數，替代模型P2的目標函數中的期望預期收益函數部分，可得模型P3.

模型P3的約束條件同模型P2.由此可見，車輛增量收益參數λj,t+1控制著模型P3的求解過程中，故又稱其為控制變量.下面針對隨機問題自身的特點，設計車輛增量收益參數λj,t+1的確定方法.

4 參數動態更新設計

控制變量λj,t+1表示節點j處增加一輛車所引起的期望收益值增加量，稱之為車輛增量收益參數，其值為

4.1 獨立節點處收益函數的確定

獨立節點收益函數Rit（Vit，Lit）表示獨立節點i處時段t所創造的收益值.根據時段t節點i處的運輸任務量lit，對該節點處車輛Vit進行合理調配，從而得到該處的車隊調度方案（xijt，yijt），代入函數Rit（Vit，Lit）可求得收益值.由此可以看出，車輛供給量變量Vit和任務數Lit兩因素共同影響著函數Rit（Vit，Lit）的取值，所以可以將函數Rit（Vit，Lit）看作車輛供給量變量Vit和Lit的函數，故又將其簡記為Rit（Vit，Lit），其確定過程如下：

1）初始化數據采樣

確定第1時段各節點處的初始車輛分布Vi1；生成第1時段各節點間的任務數分布情況Lij1（i,j∈N），使得各節點間的任務數符合指定分布；按靜態問題處理方法，求解時段1的車隊調度方案（xij1，yij1）；記錄第1時段各節點處的車輛數Vi1、任務數Li1、收益值Ri1數據.

2）中間時段數據采樣

3）各節點收益函數的確定

各節點收益函數Ri（Vi，Li）的確定（i∈N）過程為：取出從第1時段到第K時段關于節點i處的車輛數Vit、任務數Lit、收益值Rit數；利用數據擬合技術確定節點i處收益值Ri和車輛數Vi、運輸任務數Li之間的函數關系表達式Ri（Vi，Li）.

4）各節點收益函數梯度的確定

利用二元數據擬合技術得出的各節點收益函數表達式Ri（Vi，Li），求出該函數關于Vi、Li的梯度?Ri（Vi,Li）.

4.2 獨立節點處收益函數特性分析

設時段t節點i處的車輛供給量為Vit，對車輛進行編號，令為第k輛車所創造的總收益值，顯然編號靠前的車輛會選擇能夠創造更大收益值的運輸任務，故

又Rit和之間存在關系，令Rit（Vit）在Vit處的邊際收益記為ξit（Vit），則ξit（Vit）=Rit（Vit+1）-Rit（Vit）=

令函數Rit（Vit）在Vit處的斜率記為αit（Vit），因為（i，t）處車輛供給量Vit相對較大，故邊際收益ξit（Vit）可用函數Rit（Vit）在Vit處的斜率αit（Vit）來近似表示，即

圖1 獨立節點處收益函數變化趨勢示意圖Fig.1 Diagrammatic sketch of revenue function at single point

由圖1中可以看出，獨立節點處車輛總供給Vit≤Lit時，隨Vit增加，Rit呈遞增趨勢，但增量收益αit呈遞減趨勢；當Vit＞Lit時，Rit呈遞減趨勢.

4.3 車輛增量收益參數的動態更新設計

1）初始化時段處理

按靜態問題處理方法求解時段1的車隊調度方案（xij1，yij1）；利用公式確定Vj2的值；生成第2時段各節點間的任務數分布情況Lij2（i,j∈N），使得各節點間的任務數符合指定分布；利用公式計算節點i處的運輸任務數；將Vi2和Li2值代入梯度?Ri（Vi,Li），求出?Ri值，即為時段2節點i處增加一輛車的期望收益值，記為λi2=｛?Ri2|V=Vi2,L=Li2｝；將車輛增量收益λi2代入模型P3；利用線性規劃算法進行求解，得到新的解變量；利用公式重新確定的值，并作為下一時段的狀態變量.

2）中間時段處理

3）終止時段處理

因為問題共考慮K個時段的動態調度，故第K+1時段各節點處的車輛增加為各節點所帶來的增量收益為0，即最后一時段模型中使用的車輛期望收益參數λi,K+1均按0處理.從而建立時段K的車隊調度模型，得到K時段問題的解（xijK，yijK）.

5 算法步驟

基于參數誘導的隨機動態車隊管理問題的逐段分解求解算法流程如下.

階段1 運輸任務分布確定過程

步驟1從歷史數據中抽取時段t路網中節點i處發往節點j的運輸任務數lij作為樣本數據；

步驟2計算各抽樣數據lij的頻數；

步驟3根據抽樣數據頻數，計算運輸任務數lij各樣本數據的出現概率，從而繪制平滑密度函數曲線；

步驟4確定經驗分布函數曲線；

步驟5利用擬合優度檢驗，確定時段t最合理的運輸任務數lij的分布函數F（Lt），并做記錄；

步驟6如果沒有到最后一時段K，即t＜K，則轉步驟1；

步驟7如果為最后一時段K，即t=K，則得到從時段1到時段K路網上的運輸任務分布序列，｛F（Lt）|t=1，2，...，K｝記為，并轉階段2.

階段2 數據記錄過程

步驟8從運輸任務分布序列｛F（Lt）|t=1，2，...，K｝中提取第t時段的分布函數F（Lt），并按此分布生成時段t路網上的運輸任務分布矩陣Lt，作為模型求解的狀態變量；

步驟9計算時段t單節點處運輸任務數Lit；

步驟10計算時段t單節處的車輛數Vit；

步驟11按靜態問題求解時段t車隊調度問題，得到解（xijt，yijt），并計算時段t單節點處創造的收益值Rit；

步驟12記錄數據Vit、Lit、Rit；

步驟13如果沒有到最后一時段K，即t＜K，則轉步驟8；

步驟14如果為最后一時段K，即t=K，則得到從時段1到時段K路網上的數據全序列，記為｛（Vit,Lit,Rit）, i∈N|t=1，2，...，K｝，并轉階段3.

階段3 收益函數梯度求解過程

步驟15取出從第1時段到第K時段關于節點i處的車輛數Vit、任務數Lit、收益值Rit數據；

步驟16利用曲線擬合工具確定節點i處收益值Ri和車輛數Vi、運輸任務數Li之間的函數關系表達式；

步驟17求解函數Ri（Vi,Li）關于Vi、Li的梯度?Ri（Vi,Li），并轉階段4.

階段4 控制參數與解變量更新過程

步驟19計算下時段各節點處的車輛數Vi,t+1的值；

步驟20計算下一時段各節點處的運輸任務數Li,t+1；

步驟21將Vi,t+1和Li,t+1值代入梯度?Ri（Vi,Li），求出?Ri值，取其中的關于車輛數的偏導分量作為模型控制參數，記為λi,t+1；

步驟22將控制參數λi,t+1代入靜態模型P3重新求解，可得時段t新的解

步驟24如果沒有到最后一時段K，即t＜K，則轉步驟18；

步驟25如果為最后一時段K，即t=K，則得到從時段1到時段K問題解序列，記為,i,j∈ N|t=1，2，...，K｝.

6 數值分析

設計由35個節點組成的運輸網絡，任意兩點之間的距離可以直接計算得出，可用35×35的方陣表示.車輛載貨運輸的單位運輸收益為20元/km，車輛空車運輸的單位成本為3元/km.車隊調度的計劃周期T分為50個時間段，記為T=｛1，2，...，50｝.

任意抽取一時段路網中產生的1 225項（設計路網為35個節點，每時段均會產生35×35項運輸任務）運輸任務進行數據擬合，并利用擬合優度檢驗，確定最合理的運輸任務數lij的分布函數F（Lt）.利用Matlab中的Difittool工具對任務數利用正態分布進行擬合，其數學期望值為79.859 6，方差為8.856 6，進行擬合優度檢驗，對數似然性為-449.62，利用Matlab中的jbtest函數進行擬合優度檢驗，分布為正態分布的概率為0.8.

1）求解質量對比分析

利用傳統馬氏求解算法分別求解50個時段的車隊調度問題，得到每個時段的車隊調度方案，并確定各時段創造的收益值；進而引入控制參數λ并對模型進行分解形式改造，利用文中設計的參數誘導求解算法對問題進行求解，得到每時段的車隊調度方案，并確定各時段創造的收益值.從而繪制求解質量對比分析圖如圖2所示.由圖2可知，在模型中引入控制參數λ并對模型進行分解形式改造之后求出的解質量要高于傳統馬氏決策方法進行分段求解的質量.

圖2 求解質量對比Fig.2 Result comparison of the two algorithm

2）獨立節點處收益函數擬合演進過程

抽取第1時段到第50時段25號節點的車輛數Vi、任務數Li、收益值Rt數據，利用數據擬合技術確定節點i處收益值Ri和車輛數Vi、運輸任務數Li之間的函數關系.圖3表示獨立節點處收益函數擬合過程.

圖3 獨立節點處收益函數擬合過程Fig.3 Revenue function fitting process at single point

3）車輛增量收益控制參數動態變動情況

各時段各節點處的車輛單位增量收益控制參數λ的動態波動情況如圖4所示.

圖4 各時段各節點處車輛增量收益控制參數動態波動情況Fig.4 Control parameters transformation for each terminal at each time period

4）求解質量與計劃周期長度、路網規模之間的關系

將計劃周期設定為10個周期、20個周期、30個周期、40個周期、50個周期等不同的時間長度，分別用不引入控制參數的方法和引入控制參數的方法進行求解，并對其求解質量進行比較分析，發現隨著計劃周期數的增加，解的差別性程線性擴大趨勢，即計劃周期越長，控制參數的效果越明顯，如圖5所示.

將路網設定為10個節點、20個節點、30個節點、40個節點等不同規模，分別用不引入控制參數的方法和引入控制參數的方法進行求解，并對其求解質量進行比較分析，發現隨著路網規模的擴大，解的差別性也呈擴大趨勢，即路網規模越大，控制參數的效果越明顯，如圖6所示.

圖5 解質量與計劃周期長度的關系Fig.5 Relationship between solution performance and planning horizon

圖6 求解質量與路網規模之間的關系Fig.6 Relationship between solution performance and network scale

7 結束語

系統研究了隨機動態車隊問題.基于運輸任務產生的隨機特性，進行了運輸任務分布生成過程設計，并給出了路網上運輸任務分布函數的確定方法，進而研究了車輛分布更新過程.在對兩大狀態變量的更新環節進行設計的基礎上，引入了車輛增量收益參數，并給出了車輛增量收益參數的確定方法及動態更新過程，進而將該參數引入問題模型中的未來時段期望收益函數部分，實現問題模型的可分解形式改造.給出隨機動態問題的完整求解算法流程，最后通過數值分析，演示運輸任務分布函數的擬合過程，并對未引入控制參數和引入控制參數對問題求解質量的影響進行了系統分析，驗證了控制參數引入對求解質量的改善有較大幫助，且隨著計劃周期長度的增加和路網規模的擴大，這種優勢呈現擴大的趨勢.

［1］許爭爭，唐加福.基于交匯點協作的車輛調度問題的兩階段算法.系統工程學報，2013，28（5）：573—580. Xu Z Z，Tang J F.Two-stage algorithm to vehicle scheduling problem based on intersection coordination.Journal of Systems Engineering，2013，28（5）：573—580.（in Chinese）

［2］葛顯龍，王 旭，邢樂斌.動態需求的多車型車輛調度問題及云遺傳算法.系統工程學報，2012，27（6）：823—832. Ge X L，Wang X，Xing L B.Multi-vehicle scheduling problems and cloud GA based on the dynamic needs.Journal of Systems Engineering，2012，27（6）：823—832.（in Chinese）

［3］曹夏夏，唐加福，劉黎黎.基于集劃分的精確算法求解機場接送車輛調度問題.系統工程理論與實踐，2013，33（7）：1682—1689. Cao X X，Tang J F，Liu L L.Exact algorithm based on set partition for vehicle scheduling in picking up and delivering customers to air port service.Systems Engineering：Theory and Practice，2013，33（7）：1682—1689.（in Chinese）

［4］Vogt L，Poojari C A，Beasley J B.A tabu search algorithm for the single vehicle routing allocation problem.Journal of the Operational Research Society，2007，58（4）：467—480.

［5］Dabia S，Ropke S，Van W T.Branch and price for the time-dependent vehicle routing problem with time windows.Transportation Science，2013，47（3）：380—396.

［6］Geetha S，Vanathi P T，Poonthalir G.Metaheuristic approach for the multi-depot vehicle routing problem.Applied Artificial Intelligence，2012，26（10）：878—901.

［7］Pita J P，Adler N，Antunes A P.Socially-oriented flight scheduling and fleet assignment model with an application to Norway. Transportation Research，Part B：Methodological，2014，61（3）：17—32.

［8］Yao Mingjong，Huang Jiayen.Scheduling of transportation fleet maintenance service by an improved Lipschitz optimization algorithm.Optimization Methods and Software，2014，29（3）：592—609.

［9］Pita J P，Barnhart C，Antunes P.Integrated flight scheduling and fleet assignment under airport congestion.Transportation Science，2013，47（4）：477—492.

［10］Ai-Yakoob S M，Sherali H D.A column generation approach for determining optimal fleet mix，schedules，and transshipment facility locations for a vessel transportation problem.Applied Mathematical Modelling，2013，37（4）：2374—2387.

［11］詹沙磊，劉 南.基于災情信息更新的應急物資配送多目標隨機規劃模型.系統工程理論與實踐，2013，33（1）：159—166. Zhan S L，Liu N.Multi-objective stochastic programming model for relief allocation based on disaster scenario information updates. Systems Engineering：Theory and Practice，2013，33（1）：159—166.（in Chinese）

［12］魏 明，靳文舟，孫 博.隨機旅行時間的區域公交車調度模型及算法.公路交通科技，2011，28（10）：124—129 Wei M，Jin W Z，Sun B.Model and algorithm for regional bus scheduling with stochastic travel time.Journal of Highway and Transportation Research and Development，2011，28（10）：124—129.（in Chinese）

［13］Yan Shaoyang，Chen Chunying，Chang Shengchieh.A car pooling model and solution method with stochastic vehicle travel times. IEEE Transactions on Intelligent Transportation Systems，2014，15（1）：47—61.

［14］葛顯龍，王 旭，代 應.基于混合量子遺傳算法的隨機需求車輛調度問題.系統工程，2011，29（3）：54—59. Ge X L，Wang X，Dai Y.The vehicle routing problem in the case of stochastic demand based on hybrid quantum genetic algorithm. Systems Engineering，2011，29（3）：54—59.（in Chinese）

［15］Shi Ning，Song Haiqing，Powell W B.The dynamic fleet management problem with uncertain demand and customer chosen service level.International Journal of Production Economics，2014，148（2）：110—121.

［16］Mousavi S M，Vahdani B，Tavakkoli-Moghaddam R，et al.Location of cross-docking centers and vehicle routing scheduling under uncertainty：A fuzzy possibilistic-stochastic programming model.Applied Mathematical Modelling，2014，38（7）：2249—2264.

Solving strategies for the stochastic dynamic fleet scheduling problem based on leading of parameters

Li Bing1，Li Jing2，Xuan Hua1
（1.School of Management Engineering，Zhengzhou University，Zhengzhou 450001，China；2.Personnel Department，Zhengzhou University，Zhengzhou 450001，China）

The number of the transportation tasks between all regions is treated as being random.The generating mechanism on the distribution of transportation task is devised；the formulation of transportation task distribution function is presented；then the transformation mechanism on number of vehicles of a region at a time period to be dispatched is discussed.After the two state variables are updated to improve the solution，the control variable depicting the marginal cost of having one more vehicle in a region is drawn.The calculation and development of the control variable are expressed.Then，using the control variable to approximate the expected function in the model，the dissolution model is formulated.The algorithm is given.At last，the revenue function's fitting process at a single point is simulated.The effect of the control variable in improving the solution quality is numerically analyzed.It is verified that the control variable is very helpful to enhance the solution quality.

dynamic stochastic fleet scheduling；incremental revenue of vehicle；piecewise decomposition；control variable

N945；TP11；F530

A

1000-5781（2016）04-0545-12

10.13383/j.cnki.jse.2016.04.012

李 冰（1976—），男，河南開封人，博士，教授，研究方向：運輸組織優化，物流優化與控制，Email：lbing@zzu.edu.cn；

李 靜（1980—），女，河南開封人，博士生，講師，研究方向：物流優化與控制，Email：ljing@zzu.edu.cn；

軒 華（1979—），女，河南睢縣人，博士，教授，研究方向：物流優化與控制，智能優化算法，Email：hxuan@zzu.edu.cn.

2014-03-14；

2014-12-18.

教育部人文社會科學研究項目（15YJC630148）；國家自然科學基金資助項目（71001091；71001090）；鄭州大學優秀青年教師發展基金項目（1421326092）.