基于參數(shù)誘導(dǎo)的隨機(jī)動(dòng)態(tài)車隊(duì)調(diào)度求解策略

李 冰，李 靜，軒 華

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

基于參數(shù)誘導(dǎo)的隨機(jī)動(dòng)態(tài)車隊(duì)調(diào)度求解策略

李 冰1，李 靜2，軒 華1

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

基于運(yùn)輸任務(wù)產(chǎn)生的隨機(jī)特性，進(jìn)行運(yùn)輸任務(wù)分布生成機(jī)制設(shè)計(jì)，并給出路網(wǎng)上運(yùn)輸任務(wù)分布函數(shù)的確定方法，進(jìn)而研究車輛分布更新過程.在對(duì)兩大狀態(tài)變量的更新環(huán)節(jié)進(jìn)行設(shè)計(jì)的基礎(chǔ)上，引入車輛增量收益參數(shù)，并給出車輛增量收益參數(shù)的確定方法及動(dòng)態(tài)更新過程，進(jìn)而將該參數(shù)引入問題模型中的未來時(shí)段期望收益函數(shù)部分，實(shí)現(xiàn)問題模型的可分解形式改造.給出隨機(jī)動(dòng)態(tài)問題的完整求解算法流程.最后演示獨(dú)立節(jié)點(diǎn)處收益函數(shù)擬合過程，并對(duì)控制參數(shù)對(duì)問題求解質(zhì)量的影響進(jìn)行數(shù)值分析，從而驗(yàn)證方法的有效性.

隨機(jī)動(dòng)態(tài)車隊(duì)調(diào)度；車輛增量收益參數(shù)；逐段分解；控制變量

1 引 言

開展貨物運(yùn)輸作業(yè)的優(yōu)化組織工作是降低運(yùn)輸成本、提高運(yùn)輸效率的重要手段和關(guān)鍵.貨運(yùn)車輛作為貨物運(yùn)輸?shù)闹苯虞d體，同時(shí)也是貨物運(yùn)輸作業(yè)過程中最重要的可支配資源.運(yùn)用所掌握的車隊(duì)資源合理安排組織運(yùn)輸任務(wù)，消除對(duì)流、迂回、重復(fù)等不合理現(xiàn)象，實(shí)現(xiàn)車隊(duì)資源的優(yōu)化組合和配置，并達(dá)到以最少的資源投入獲得最優(yōu)經(jīng)濟(jì)效益的目的，是整個(gè)貨物運(yùn)輸優(yōu)化組織工作的核心內(nèi)容.

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

針對(duì)確定性動(dòng)態(tài)車隊(duì)調(diào)度計(jì)劃安排問題，文獻(xiàn)［7］研究了一類面向公眾服務(wù)的機(jī)隊(duì)調(diào)度優(yōu)化問題，構(gòu)建了一個(gè)機(jī)隊(duì)分配優(yōu)化模型，并設(shè)計(jì)了粒子群優(yōu)化算法.文獻(xiàn)［8］研究了維修服務(wù)車隊(duì)調(diào)度問題，提出了一個(gè)新的和改進(jìn)的Lipschitz優(yōu)化算法.文獻(xiàn)［9］研究了機(jī)場擁擠情況下的飛行調(diào)度計(jì)劃制定和機(jī)隊(duì)分配問題，構(gòu)建了一個(gè)混合整數(shù)線性規(guī)劃模型.文獻(xiàn)［10］研究了用于存儲(chǔ)補(bǔ)給的運(yùn)輸車隊(duì)調(diào)度問題，構(gòu)建了一個(gè)基于運(yùn)輸成本最小化的整數(shù)規(guī)劃模型，并設(shè)計(jì)了列生成方法對(duì)模型進(jìn)行求解.

對(duì)于隨機(jī)車隊(duì)調(diào)度優(yōu)化問題可分為未來需求可預(yù)先獲取的隨機(jī)動(dòng)態(tài)車隊(duì)調(diào)度問題和未來需求無法預(yù)先獲取的隨機(jī)動(dòng)態(tài)車隊(duì)調(diào)度問題.對(duì)于未來需求可預(yù)先獲取的隨機(jī)車隊(duì)調(diào)度問題，文獻(xiàn)［11］從多目標(biāo)規(guī)劃和隨機(jī)規(guī)劃的角度構(gòu)建了應(yīng)急物資配送的多目標(biāo)隨機(jī)規(guī)劃模型.模型設(shè)定當(dāng)受災(zāi)情景發(fā)生時(shí)，某一可觀測信息發(fā)生的概率已知，其值可以通過歷史統(tǒng)計(jì)得出.文獻(xiàn)［12］研究了一類隨機(jī)旅行時(shí)間的區(qū)域公交車輛調(diào)度問題.因突發(fā)事件而引起的車輛延時(shí)完成某班次的時(shí)間事先難以預(yù)料，將其看作隨機(jī)變量，假設(shè)延時(shí)時(shí)間服從正態(tài)分布，從而將該模型轉(zhuǎn)化為一類確定性數(shù)學(xué)模型.文獻(xiàn)［13］研究了一類基于隨機(jī)運(yùn)行時(shí)間的車隊(duì)調(diào)度方法用于租車公司的日常車輛管理.車輛運(yùn)行時(shí)間雖然是一隨機(jī)變量但可以根據(jù)歷史數(shù)據(jù)進(jìn)行預(yù)測，從而將問題轉(zhuǎn)化為一個(gè)確定性的多商品網(wǎng)絡(luò)流問題進(jìn)行求解，并設(shè)計(jì)了基于仿真的評(píng)價(jià)方法.

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

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

2 隨機(jī)動(dòng)態(tài)車隊(duì)調(diào)度模型

2.1 符號(hào)說明

隨機(jī)動(dòng)態(tài)車隊(duì)調(diào)度問題是指在計(jì)劃周期內(nèi)制定合理的車隊(duì)調(diào)度方案，以滿足發(fā)生在各時(shí)段各節(jié)點(diǎn)處的運(yùn)輸任務(wù)需求，從而達(dá)到總收益最大或成本最小的目標(biāo).因?yàn)榉?wù)周期內(nèi)各時(shí)段各節(jié)點(diǎn)間的運(yùn)輸任務(wù)數(shù)是不確定，需要通過歷史數(shù)據(jù)擬合出其概率分布函數(shù)，所以車隊(duì)調(diào)度問題具有隨機(jī)特性；又因?yàn)樵谶M(jìn)行某時(shí)段的車隊(duì)調(diào)度時(shí)不僅要考慮本時(shí)段的經(jīng)濟(jì)效益，同時(shí)還要考慮到對(duì)未來時(shí)段車隊(duì)調(diào)度工作的影響，所以問題又具有動(dòng)態(tài)特性.為便于問題描述，對(duì)問題中所涉及的變量介紹如下：

G（N,E）為運(yùn)輸網(wǎng)絡(luò)，其中N，E分別表示G中的節(jié)點(diǎn)集合和弧集合.

T為計(jì)劃周期內(nèi)的時(shí)段劃分集合，計(jì)劃周期由K個(gè)相同長度的時(shí)段組成，運(yùn)輸任務(wù)分別在這K個(gè)時(shí)段產(chǎn)生，可表示為T=｛1，2，...，K｝.

lijt為時(shí)段t節(jié)點(diǎn)i處產(chǎn)生的目的地為j的運(yùn)輸任務(wù)數(shù)，t=1，2，...，K.該變量為隨機(jī)變量，其概率空間可通過歷史數(shù)據(jù)統(tǒng)計(jì)得知，記為（?，F(xiàn)，Pr），其中?為樣本空間、F為分布函數(shù)、Pr為概率測度.

Vi1為計(jì)劃周期之初，各節(jié)點(diǎn)處的車輛數(shù).該變量值為已知.

Vit為時(shí)段t節(jié)點(diǎn)i處的車輛數(shù)，t=2，3，...，K.

rij為發(fā)送運(yùn)輸任務(wù)從節(jié)點(diǎn)i到節(jié)點(diǎn)j所能創(chuàng)造的純利潤，該參數(shù)為已知.

cij為當(dāng)i≠j時(shí)，表示車輛從節(jié)點(diǎn)i空移到節(jié)點(diǎn)j的成本；當(dāng)i=j時(shí)，表示車輛在節(jié)點(diǎn)i處原地駐留的成本，這里假設(shè)?i∈N，且cii=0.該參數(shù)為已知.

xijt為整數(shù)變量，表示時(shí)段t從節(jié)點(diǎn)i裝載任務(wù)發(fā)往節(jié)點(diǎn)j的車輛數(shù)，t=1，2，...，K.

yijt為整數(shù)變量，當(dāng)i≠j時(shí)，表示時(shí)段t從節(jié)點(diǎn)i發(fā)往節(jié)點(diǎn)j的空車數(shù)；當(dāng)i=j時(shí)，表示時(shí)段t在節(jié)點(diǎn)i處原地駐留到時(shí)段t+1的車數(shù).

2.2 問題的隨機(jī)特性分析

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

1）選取某個(gè)計(jì)劃周期作為統(tǒng)計(jì)時(shí)間范圍；

2）選取計(jì)劃周期內(nèi)路網(wǎng)上任意兩點(diǎn)間的運(yùn)輸任務(wù)數(shù)lijt作為統(tǒng)計(jì)對(duì)象；

3）得到多個(gè)lijt的變化值，利用概率統(tǒng)計(jì)技術(shù)近似擬合出lijt的概率分布函數(shù).

2.3 問題的描述

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

2.4 模型的建立

基于問題的描述，建立問題的數(shù)學(xué)模型P1如下

問題的目標(biāo)函數(shù)（1）是為了使車隊(duì)調(diào)度方案在整個(gè)計(jì)劃周期內(nèi)所創(chuàng)造的總收益值達(dá)到最大化；約束（2）表示載貨車輛數(shù)不能超過運(yùn)輸任務(wù)數(shù)，運(yùn)輸任務(wù)數(shù)為一隨機(jī)變量，概率空間為（?，F(xiàn)，Pr），α為給定的置信水平，表示約束條件（2）成立的概率；約束（3）表示節(jié)點(diǎn)處的載貨車輛數(shù)、空移車數(shù)和原地駐留車數(shù)之和等于該節(jié)點(diǎn)處的可調(diào)配車輛總數(shù)；約束（4）表示本時(shí)段各節(jié)點(diǎn)發(fā)往某節(jié)點(diǎn)的載貨車輛數(shù)、空移車數(shù)和該節(jié)點(diǎn)的原地駐留車數(shù)共同構(gòu)成下一時(shí)段該節(jié)點(diǎn)可調(diào)配車輛總數(shù).

因?yàn)槟Ｐ偷募s束條件中含有隨機(jī)變量lijt，且應(yīng)在觀察到隨機(jī)變量的實(shí)現(xiàn)之前作出決策，所以模型屬于隨機(jī)規(guī)劃中的機(jī)會(huì)約束規(guī)劃（Chance Constrained Programming）.當(dāng)問題涉及的運(yùn)輸網(wǎng)絡(luò)節(jié)點(diǎn)比較多、時(shí)段比較多時(shí)，所建立的問題模型為一個(gè)大規(guī)模多階段隨機(jī)規(guī)劃模型，求解非常困難.

2.5 模型的可分解形式改造

1）決策變量

模型的決策變量由兩個(gè)分量組成，分別為重車數(shù)變量和空車數(shù)變量.

以xt表示計(jì)劃周期內(nèi)時(shí)段t各節(jié)點(diǎn)處滿載移動(dòng)的車輛數(shù)量，即xt=｛xijt|?i,j∈N,?t∈T｝.

以yt表示計(jì)劃周期內(nèi)時(shí)段t各節(jié)點(diǎn)處空車移動(dòng)和原地駐留的車輛數(shù)量，即yt=｛yijt|?i,j∈N,?t∈T｝.

2）狀態(tài)變量

模型的狀態(tài)變量是決策變量求解的基礎(chǔ)，它由兩個(gè)分量組成，分別為車輛數(shù)變量和任務(wù)數(shù)變量，記為S（t）=（Vt,Lt）.模型的狀態(tài)變量S（t）每階段需要不斷更新，狀態(tài)變量S（t）的更新過程設(shè)計(jì)是問題求解的關(guān)鍵之一.

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

以Lt表示計(jì)劃周期內(nèi)時(shí)段t節(jié)點(diǎn)之間的運(yùn)輸任務(wù)數(shù)，即Lt=｛lijt|?i,j∈N，?t∈N｝.對(duì)于由n個(gè)節(jié)點(diǎn)組成的運(yùn)輸網(wǎng)絡(luò)，Lt可用一個(gè)n×n的隨機(jī)矩陣表述，該矩陣中的每一個(gè)分量均為一個(gè)隨機(jī)量，表示由節(jié)點(diǎn)i到節(jié)點(diǎn)j的運(yùn)輸任務(wù)數(shù)，顯然該隨機(jī)矩陣對(duì)角線的分量均為0，因?yàn)槁肪W(wǎng)上不會(huì)產(chǎn)生始點(diǎn)和終點(diǎn)一致的運(yùn)輸任務(wù).

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

問題的模型P1為一個(gè)大規(guī)模隨機(jī)規(guī)劃模型，直接求解非常困難.對(duì)模型進(jìn)行可分解形式改造，P2形式的模型轉(zhuǎn)變?yōu)橐粋€(gè)K階段隨機(jī)規(guī)劃模型，可采取分階段處理的辦法進(jìn)行逐一求解.

3 關(guān)鍵環(huán)節(jié)處理

要解決模型P2的求解問題，需要破解兩大關(guān)鍵環(huán)節(jié)的處理難題，即

1）關(guān)鍵環(huán)節(jié)之一：兩大狀態(tài)變量的更新環(huán)節(jié)設(shè)計(jì).即任務(wù)分布生成過程設(shè)計(jì)和車輛分布更新過程設(shè)計(jì).

2）關(guān)鍵環(huán)節(jié)之二：目標(biāo)函數(shù)中未來時(shí)段期望收益函數(shù)的處理問題.模型P2中目標(biāo)函數(shù)的第二部分E［Rt（Vt，Lt）］是模型是否能夠成功分解的關(guān)鍵所在，其含義是本階段車隊(duì)調(diào)度方案對(duì)未來時(shí)段所造成的預(yù)期收益的數(shù)學(xué)期望值.

下面分別就這兩大關(guān)鍵環(huán)節(jié)的處理問題進(jìn)行詳細(xì)探討.

3.1 狀態(tài)變量的處理

1）任務(wù)分布生成

運(yùn)輸任務(wù)分布的表述形式：運(yùn)輸網(wǎng)絡(luò)中節(jié)點(diǎn)i和節(jié)點(diǎn)j間形成一條固定的運(yùn)輸線路，該運(yùn)輸線路上的運(yùn)輸任務(wù)數(shù)lij為一隨機(jī)變量.對(duì)于由n個(gè)節(jié)點(diǎn)組成的運(yùn)輸網(wǎng)絡(luò)，共形成n×n條運(yùn)輸線路，每條運(yùn)輸線路上的運(yùn)輸任務(wù)數(shù)lij均為一隨機(jī)數(shù)，從而時(shí)段t運(yùn)輸網(wǎng)絡(luò)中各條線路上的運(yùn)輸任務(wù)數(shù)分布Lt可由一個(gè)n×n的方陣表示，稱時(shí)段t路網(wǎng)上的運(yùn)輸任務(wù)分布矩陣，記為Lt.運(yùn)輸任務(wù)分布矩陣Lt可以清楚的描述時(shí)段t路網(wǎng)上的運(yùn)輸任務(wù)分布情況.

路網(wǎng)上運(yùn)輸任務(wù)分布函數(shù)的確定：從歷史數(shù)據(jù)中抽取時(shí)段t路網(wǎng)中節(jié)點(diǎn)i處發(fā)往節(jié)點(diǎn)j的運(yùn)輸任務(wù)數(shù)lij作為樣本數(shù)據(jù)，并分析頻數(shù)統(tǒng)計(jì)，進(jìn)而擬合密度函數(shù)，從而得到lij的經(jīng)驗(yàn)分布.具體步驟為：對(duì)運(yùn)輸任務(wù)數(shù)lij進(jìn)行數(shù)據(jù)抽樣；計(jì)算各抽樣數(shù)據(jù)的頻數(shù)；根據(jù)抽樣數(shù)據(jù)頻數(shù)，計(jì)算運(yùn)輸任務(wù)數(shù)lij各樣本數(shù)據(jù)的出現(xiàn)概率，從而繪制平滑密度函數(shù)曲線；確定經(jīng)驗(yàn)分布函數(shù)曲線；利用擬合優(yōu)度檢驗(yàn)，確定最合理的運(yùn)輸任務(wù)數(shù)lij的分布函數(shù)F（Lt）.

路網(wǎng)上運(yùn)輸任務(wù)分布矩陣的形成：利用擬合出的時(shí)段t路網(wǎng)上的運(yùn)輸任務(wù)分布函數(shù)F（Lt），生成時(shí)段t路網(wǎng)上的運(yùn)輸任務(wù)分布矩陣Lt，將其作為模型求解的狀態(tài)向變量.

2）車輛分布更新

因?yàn)橄乱粫r(shí)段某節(jié)點(diǎn)處的車輛數(shù)由上一時(shí)段各節(jié)點(diǎn)發(fā)往該節(jié)點(diǎn)的載貨車輛、空移車輛和該節(jié)點(diǎn)的原地駐留車輛共同構(gòu)成，故利用求得的時(shí)段t的車隊(duì)調(diào)度方案，即解變量（xijt，yijt），?i,j∈N，確定時(shí)段t+1各節(jié)點(diǎn)處的車輛分布數(shù).車輛數(shù)的更新過程為

3.2 期望收益函數(shù)的處理

模型P2的目標(biāo)函數(shù)Rt（Vt，Lt）表示在時(shí)段t采取車隊(duì)調(diào)度方案（xijt，yijt）所能創(chuàng)造的收益值.因?yàn)闀r(shí)段t的車隊(duì)調(diào)度方案（xijt，yijt）會(huì)對(duì)時(shí)段t以后各時(shí)段的車隊(duì)調(diào)度方案制定產(chǎn)生影響，所以Rt（Vt，Lt）不僅包括車隊(duì)調(diào)度方案（xijt，yijt）在時(shí)段t所創(chuàng)造的收益而且包括其對(duì)以后各時(shí)段的影響.在本文中，設(shè)計(jì)了未來時(shí)段期望收益函數(shù)E［Rt+1（Vt+1，Lt+1）］來表述本時(shí)段車隊(duì)調(diào)度方案對(duì)以后時(shí)段的影響.

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

將上式代入式（16）可知

從而可知

將上式代入模型P2的目標(biāo)函數(shù)，替代模型P2的目標(biāo)函數(shù)中的期望預(yù)期收益函數(shù)部分，可得模型P3.

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

4 參數(shù)動(dòng)態(tài)更新設(shè)計(jì)

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

4.1 獨(dú)立節(jié)點(diǎn)處收益函數(shù)的確定

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

1）初始化數(shù)據(jù)采樣

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

2）中間時(shí)段數(shù)據(jù)采樣

3）各節(jié)點(diǎn)收益函數(shù)的確定

各節(jié)點(diǎn)收益函數(shù)Ri（Vi，Li）的確定（i∈N）過程為：取出從第1時(shí)段到第K時(shí)段關(guān)于節(jié)點(diǎn)i處的車輛數(shù)Vit、任務(wù)數(shù)Lit、收益值Rit數(shù)；利用數(shù)據(jù)擬合技術(shù)確定節(jié)點(diǎn)i處收益值Ri和車輛數(shù)Vi、運(yùn)輸任務(wù)數(shù)Li之間的函數(shù)關(guān)系表達(dá)式Ri（Vi，Li）.

4）各節(jié)點(diǎn)收益函數(shù)梯度的確定

利用二元數(shù)據(jù)擬合技術(shù)得出的各節(jié)點(diǎn)收益函數(shù)表達(dá)式Ri（Vi，Li），求出該函數(shù)關(guān)于Vi、Li的梯度?Ri（Vi,Li）.

4.2 獨(dú)立節(jié)點(diǎn)處收益函數(shù)特性分析

設(shè)時(shí)段t節(jié)點(diǎn)i處的車輛供給量為Vit，對(duì)車輛進(jìn)行編號(hào)，令為第k輛車所創(chuàng)造的總收益值，顯然編號(hào)靠前的車輛會(huì)選擇能夠創(chuàng)造更大收益值的運(yùn)輸任務(wù)，故

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

令函數(shù)Rit（Vit）在Vit處的斜率記為αit（Vit），因?yàn)椋╥，t）處車輛供給量Vit相對(duì)較大，故邊際收益ξit（Vit）可用函數(shù)Rit（Vit）在Vit處的斜率αit（Vit）來近似表示，即

圖1 獨(dú)立節(jié)點(diǎn)處收益函數(shù)變化趨勢示意圖Fig.1 Diagrammatic sketch of revenue function at single point

由圖1中可以看出，獨(dú)立節(jié)點(diǎn)處車輛總供給Vit≤Lit時(shí)，隨Vit增加，Rit呈遞增趨勢，但增量收益αit呈遞減趨勢；當(dāng)Vit＞Lit時(shí)，Rit呈遞減趨勢.

4.3 車輛增量收益參數(shù)的動(dòng)態(tài)更新設(shè)計(jì)

1）初始化時(shí)段處理

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

2）中間時(shí)段處理

3）終止時(shí)段處理

因?yàn)閱栴}共考慮K個(gè)時(shí)段的動(dòng)態(tài)調(diào)度，故第K+1時(shí)段各節(jié)點(diǎn)處的車輛增加為各節(jié)點(diǎn)所帶來的增量收益為0，即最后一時(shí)段模型中使用的車輛期望收益參數(shù)λi,K+1均按0處理.從而建立時(shí)段K的車隊(duì)調(diào)度模型，得到K時(shí)段問題的解（xijK，yijK）.

5 算法步驟

基于參數(shù)誘導(dǎo)的隨機(jī)動(dòng)態(tài)車隊(duì)管理問題的逐段分解求解算法流程如下.

階段1 運(yùn)輸任務(wù)分布確定過程

步驟1從歷史數(shù)據(jù)中抽取時(shí)段t路網(wǎng)中節(jié)點(diǎn)i處發(fā)往節(jié)點(diǎn)j的運(yùn)輸任務(wù)數(shù)lij作為樣本數(shù)據(jù)；

步驟2計(jì)算各抽樣數(shù)據(jù)lij的頻數(shù)；

步驟3根據(jù)抽樣數(shù)據(jù)頻數(shù)，計(jì)算運(yùn)輸任務(wù)數(shù)lij各樣本數(shù)據(jù)的出現(xiàn)概率，從而繪制平滑密度函數(shù)曲線；

步驟4確定經(jīng)驗(yàn)分布函數(shù)曲線；

步驟5利用擬合優(yōu)度檢驗(yàn)，確定時(shí)段t最合理的運(yùn)輸任務(wù)數(shù)lij的分布函數(shù)F（Lt），并做記錄；

步驟6如果沒有到最后一時(shí)段K，即t＜K，則轉(zhuǎn)步驟1；

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

階段2 數(shù)據(jù)記錄過程

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

步驟9計(jì)算時(shí)段t單節(jié)點(diǎn)處運(yùn)輸任務(wù)數(shù)Lit；

步驟10計(jì)算時(shí)段t單節(jié)處的車輛數(shù)Vit；

步驟11按靜態(tài)問題求解時(shí)段t車隊(duì)調(diào)度問題，得到解（xijt，yijt），并計(jì)算時(shí)段t單節(jié)點(diǎn)處創(chuàng)造的收益值Rit；

步驟12記錄數(shù)據(jù)Vit、Lit、Rit；

步驟13如果沒有到最后一時(shí)段K，即t＜K，則轉(zhuǎn)步驟8；

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

階段3 收益函數(shù)梯度求解過程

步驟15取出從第1時(shí)段到第K時(shí)段關(guān)于節(jié)點(diǎn)i處的車輛數(shù)Vit、任務(wù)數(shù)Lit、收益值Rit數(shù)據(jù)；

步驟16利用曲線擬合工具確定節(jié)點(diǎn)i處收益值Ri和車輛數(shù)Vi、運(yùn)輸任務(wù)數(shù)Li之間的函數(shù)關(guān)系表達(dá)式；

步驟17求解函數(shù)Ri（Vi,Li）關(guān)于Vi、Li的梯度?Ri（Vi,Li），并轉(zhuǎn)階段4.

階段4 控制參數(shù)與解變量更新過程

步驟19計(jì)算下時(shí)段各節(jié)點(diǎn)處的車輛數(shù)Vi,t+1的值；

步驟20計(jì)算下一時(shí)段各節(jié)點(diǎn)處的運(yùn)輸任務(wù)數(shù)Li,t+1；

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

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

步驟24如果沒有到最后一時(shí)段K，即t＜K，則轉(zhuǎn)步驟18；

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

6 數(shù)值分析

設(shè)計(jì)由35個(gè)節(jié)點(diǎn)組成的運(yùn)輸網(wǎng)絡(luò)，任意兩點(diǎn)之間的距離可以直接計(jì)算得出，可用35×35的方陣表示.車輛載貨運(yùn)輸?shù)膯挝贿\(yùn)輸收益為20元/km，車輛空車運(yùn)輸?shù)膯挝怀杀緸?元/km.車隊(duì)調(diào)度的計(jì)劃周期T分為50個(gè)時(shí)間段，記為T=｛1，2，...，50｝.

任意抽取一時(shí)段路網(wǎng)中產(chǎn)生的1 225項(xiàng)（設(shè)計(jì)路網(wǎng)為35個(gè)節(jié)點(diǎn)，每時(shí)段均會(huì)產(chǎn)生35×35項(xiàng)運(yùn)輸任務(wù)）運(yùn)輸任務(wù)進(jìn)行數(shù)據(jù)擬合，并利用擬合優(yōu)度檢驗(yàn)，確定最合理的運(yùn)輸任務(wù)數(shù)lij的分布函數(shù)F（Lt）.利用Matlab中的Difittool工具對(duì)任務(wù)數(shù)利用正態(tài)分布進(jìn)行擬合，其數(shù)學(xué)期望值為79.859 6，方差為8.856 6，進(jìn)行擬合優(yōu)度檢驗(yàn)，對(duì)數(shù)似然性為-449.62，利用Matlab中的jbtest函數(shù)進(jìn)行擬合優(yōu)度檢驗(yàn)，分布為正態(tài)分布的概率為0.8.

1）求解質(zhì)量對(duì)比分析

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

圖2 求解質(zhì)量對(duì)比Fig.2 Result comparison of the two algorithm

2）獨(dú)立節(jié)點(diǎn)處收益函數(shù)擬合演進(jìn)過程

抽取第1時(shí)段到第50時(shí)段25號(hào)節(jié)點(diǎn)的車輛數(shù)Vi、任務(wù)數(shù)Li、收益值Rt數(shù)據(jù)，利用數(shù)據(jù)擬合技術(shù)確定節(jié)點(diǎn)i處收益值Ri和車輛數(shù)Vi、運(yùn)輸任務(wù)數(shù)Li之間的函數(shù)關(guān)系.圖3表示獨(dú)立節(jié)點(diǎn)處收益函數(shù)擬合過程.

圖3 獨(dú)立節(jié)點(diǎn)處收益函數(shù)擬合過程Fig.3 Revenue function fitting process at single point

3）車輛增量收益控制參數(shù)動(dòng)態(tài)變動(dòng)情況

各時(shí)段各節(jié)點(diǎn)處的車輛單位增量收益控制參數(shù)λ的動(dòng)態(tài)波動(dòng)情況如圖4所示.

圖4 各時(shí)段各節(jié)點(diǎn)處車輛增量收益控制參數(shù)動(dòng)態(tài)波動(dòng)情況Fig.4 Control parameters transformation for each terminal at each time period

4）求解質(zhì)量與計(jì)劃周期長度、路網(wǎng)規(guī)模之間的關(guān)系

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

將路網(wǎng)設(shè)定為10個(gè)節(jié)點(diǎn)、20個(gè)節(jié)點(diǎn)、30個(gè)節(jié)點(diǎn)、40個(gè)節(jié)點(diǎn)等不同規(guī)模，分別用不引入控制參數(shù)的方法和引入控制參數(shù)的方法進(jìn)行求解，并對(duì)其求解質(zhì)量進(jìn)行比較分析，發(fā)現(xiàn)隨著路網(wǎng)規(guī)模的擴(kuò)大，解的差別性也呈擴(kuò)大趨勢，即路網(wǎng)規(guī)模越大，控制參數(shù)的效果越明顯，如圖6所示.

圖5 解質(zhì)量與計(jì)劃周期長度的關(guān)系Fig.5 Relationship between solution performance and planning horizon

圖6 求解質(zhì)量與路網(wǎng)規(guī)模之間的關(guān)系Fig.6 Relationship between solution performance and network scale

7 結(jié)束語

系統(tǒng)研究了隨機(jī)動(dòng)態(tài)車隊(duì)問題.基于運(yùn)輸任務(wù)產(chǎn)生的隨機(jī)特性，進(jìn)行了運(yùn)輸任務(wù)分布生成過程設(shè)計(jì)，并給出了路網(wǎng)上運(yùn)輸任務(wù)分布函數(shù)的確定方法，進(jìn)而研究了車輛分布更新過程.在對(duì)兩大狀態(tài)變量的更新環(huán)節(jié)進(jìn)行設(shè)計(jì)的基礎(chǔ)上，引入了車輛增量收益參數(shù)，并給出了車輛增量收益參數(shù)的確定方法及動(dòng)態(tài)更新過程，進(jìn)而將該參數(shù)引入問題模型中的未來時(shí)段期望收益函數(shù)部分，實(shí)現(xiàn)問題模型的可分解形式改造.給出隨機(jī)動(dòng)態(tài)問題的完整求解算法流程，最后通過數(shù)值分析，演示運(yùn)輸任務(wù)分布函數(shù)的擬合過程，并對(duì)未引入控制參數(shù)和引入控制參數(shù)對(duì)問題求解質(zhì)量的影響進(jìn)行了系統(tǒng)分析，驗(yàn)證了控制參數(shù)引入對(duì)求解質(zhì)量的改善有較大幫助，且隨著計(jì)劃周期長度的增加和路網(wǎng)規(guī)模的擴(kuò)大，這種優(yōu)勢呈現(xiàn)擴(kuò)大的趨勢.

［1］許爭爭，唐加福.基于交匯點(diǎn)協(xié)作的車輛調(diào)度問題的兩階段算法.系統(tǒng)工程學(xué)報(bào)，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］葛顯龍，王 旭，邢樂斌.動(dòng)態(tài)需求的多車型車輛調(diào)度問題及云遺傳算法.系統(tǒng)工程學(xué)報(bào)，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］曹夏夏，唐加福，劉黎黎.基于集劃分的精確算法求解機(jī)場接送車輛調(diào)度問題.系統(tǒng)工程理論與實(shí)踐，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］詹沙磊，劉 南.基于災(zāi)情信息更新的應(yīng)急物資配送多目標(biāo)隨機(jī)規(guī)劃模型.系統(tǒng)工程理論與實(shí)踐，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］魏 明，靳文舟，孫 博.隨機(jī)旅行時(shí)間的區(qū)域公交車調(diào)度模型及算法.公路交通科技，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］葛顯龍，王 旭，代 應(yīng).基于混合量子遺傳算法的隨機(jī)需求車輛調(diào)度問題.系統(tǒng)工程，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—），男，河南開封人，博士，教授，研究方向：運(yùn)輸組織優(yōu)化，物流優(yōu)化與控制，Email：lbing@zzu.edu.cn；

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

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

2014-03-14；

2014-12-18.

教育部人文社會(huì)科學(xué)研究項(xiàng)目（15YJC630148）；國家自然科學(xué)基金資助項(xiàng)目（71001091；71001090）；鄭州大學(xué)優(yōu)秀青年教師發(fā)展基金項(xiàng)目（1421326092）.