軒 華

(鄭州大學(xué)管理工程學(xué)院,鄭州450001)

基于FCFS策略的帶時(shí)間窗車隊(duì)調(diào)度問題研究

軒 華*

(鄭州大學(xué)管理工程學(xué)院,鄭州450001)

對貨運(yùn)車輛和運(yùn)輸任務(wù)進(jìn)行科學(xué)有效調(diào)度,有助于提高資源利用率,實(shí)現(xiàn)貨物運(yùn)輸科學(xué)化.對一類帶時(shí)間窗的車隊(duì)調(diào)度問題進(jìn)行分析,建立其數(shù)學(xué)規(guī)劃模型.由于傳統(tǒng)算法求解該類模型較為困難,為此,設(shè)計(jì)一類啟發(fā)式算法.該算法利用FCFS規(guī)則進(jìn)行運(yùn)輸任務(wù)和車輛的分配,并為車輛設(shè)計(jì)一組簡單的編號來標(biāo)記車輛所處的位置和到達(dá)節(jié)點(diǎn)的時(shí)間,通過不斷更新車輛標(biāo)號生成一條條車輛任務(wù)發(fā)送鏈,最后形成一整套車隊(duì)調(diào)度方案.實(shí)例分析驗(yàn)證了該算法的可行性.

綜合交通運(yùn)輸;車隊(duì)調(diào)度;啟發(fā)式算法;先到先服務(wù);時(shí)間窗

1 引 言

運(yùn)輸企業(yè)為了最大限度地滿足運(yùn)輸網(wǎng)絡(luò)中不同時(shí)段不同地域上所產(chǎn)生的運(yùn)輸任務(wù)需求,以達(dá)到最少的資源投入獲得最優(yōu)經(jīng)濟(jì)效益的目的,需要對所掌握的車隊(duì)資源進(jìn)行有效管理.考慮影響實(shí)際車隊(duì)調(diào)度工作執(zhí)行的諸多制約因素,從而制定出合理的車隊(duì)調(diào)度計(jì)劃是整車和零擔(dān)貨物運(yùn)輸公司、各大物流企業(yè)在實(shí)際工作中直接面對且亟待解決的難題.

本文研究的帶時(shí)間窗車隊(duì)調(diào)度優(yōu)化問題,來源于貨物運(yùn)輸行業(yè)和物流企業(yè)的貨物運(yùn)輸組織工作.通過對貨運(yùn)車輛和運(yùn)輸任務(wù)的科學(xué)有效調(diào)度,可以大大提高資源利用率,實(shí)現(xiàn)貨物運(yùn)輸科學(xué)化.同時(shí),對車隊(duì)調(diào)度問題進(jìn)行研究也是構(gòu)建高效貨物運(yùn)輸組織體系、建立現(xiàn)代調(diào)度指揮系統(tǒng)、實(shí)現(xiàn)物流集約化和科學(xué)化、發(fā)展智能交通運(yùn)輸系統(tǒng)的基礎(chǔ)與關(guān)鍵.

2 問題的描述

帶時(shí)間窗的車隊(duì)調(diào)度問題可描述為:運(yùn)輸網(wǎng)絡(luò)N中各節(jié)點(diǎn)處的運(yùn)輸任務(wù)分布情況已知,即運(yùn)輸任務(wù)l的產(chǎn)生地i∈N,目的地j∈N和服務(wù)時(shí)間窗均為已知.如果任務(wù)l在時(shí)間窗內(nèi)沒有分配到車輛,則該任務(wù)自動消失[1-6].現(xiàn)有一個(gè)車隊(duì)承擔(dān)該運(yùn)輸網(wǎng)絡(luò)上的運(yùn)輸任務(wù),要求制定出該車隊(duì)的調(diào)度方案,使得調(diào)用最少的車輛數(shù)完成最多的運(yùn)輸任務(wù)[1].

國內(nèi)對貨物運(yùn)輸系統(tǒng)優(yōu)化方面的研究主要集中在車輛路線問題(Vehicle Routing Problem, VRP),而非本文所研究的車隊(duì)調(diào)度問題(Fleet Scheduling Problem).文獻(xiàn)[7-11]分別設(shè)計(jì)了遺傳算法、改進(jìn)遺傳算法、禁忌搜索算法、節(jié)約里程法和線性規(guī)劃技術(shù)等方法解決不同類型的車輛路線安排問題.

國外對車隊(duì)調(diào)度問題的相關(guān)研究多是基于傳統(tǒng)數(shù)學(xué)規(guī)劃技術(shù)(包括線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃等).文獻(xiàn)[12]和[13]針對油罐車調(diào)度問題分別建立了線性整數(shù)規(guī)劃模型和集劃分模型.文獻(xiàn)[14]在對動態(tài)車隊(duì)調(diào)度問題進(jìn)行分析的過程中同時(shí)考慮了載貨車輛和空車,并設(shè)計(jì)了動態(tài)規(guī)劃模型描述確定性動態(tài)車輛調(diào)度問題.為了迎合數(shù)學(xué)規(guī)劃常規(guī)求解算法的需要,通常都對問題進(jìn)行了簡化處理.這種處理方式雖然便于問題的解決,卻偏離了車隊(duì)調(diào)度工作的實(shí)際情況,從而使得研究成果無法應(yīng)用于實(shí)際工作.而且,基于數(shù)學(xué)規(guī)劃理論所建立的模型與設(shè)計(jì)的求解算法大多不適合大規(guī)模問題求解,當(dāng)車隊(duì)規(guī)模增加時(shí),算法的計(jì)算時(shí)間將呈指數(shù)增加.

鑒于帶時(shí)間窗車隊(duì)調(diào)度問題的數(shù)學(xué)模型利用傳統(tǒng)數(shù)學(xué)規(guī)劃方法難以求解,本文設(shè)計(jì)出一套基于FCFS策略的啟發(fā)式算法,該算法利用一套FCFS規(guī)則進(jìn)行運(yùn)輸任務(wù)和車輛的分配,同時(shí)為車輛設(shè)計(jì)一組簡單的編號來標(biāo)記車輛所處位置和到達(dá)節(jié)點(diǎn)時(shí)間,并通過不斷更新車輛標(biāo)號生成一條條車輛任務(wù)發(fā)送鏈,最后形成一整套車隊(duì)調(diào)度方案,從而使問題得到有效解決.

3 變量表示

為了便于問題的討論,對問題中所涉及的變量做出如下說明.

3.1 運(yùn)輸網(wǎng)絡(luò)的表示

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

tij:運(yùn)輸網(wǎng)絡(luò)中車輛從節(jié)點(diǎn)i裝貨出發(fā),運(yùn)行到節(jié)點(diǎn)j并完成卸貨的總時(shí)間,i,j∈N.

3.2 運(yùn)輸任務(wù)的表示

Li:運(yùn)輸網(wǎng)絡(luò)中節(jié)點(diǎn)i處產(chǎn)生的運(yùn)輸任務(wù)集合.

l[i,j,t1,t2]:運(yùn)輸網(wǎng)絡(luò)中節(jié)點(diǎn)i處產(chǎn)生的目的地為j的運(yùn)輸任務(wù),其服務(wù)時(shí)間窗為[t1,t2].顯然Li和l[i,j,t1,t2]二者之間存在關(guān)系Li=∪j∈Nl[i,j, t1,t2].

3.3 運(yùn)輸車輛的表示

Vi:節(jié)點(diǎn)i處的可調(diào)配車輛集合.

v[i,t]:在時(shí)刻t到達(dá)節(jié)點(diǎn)i并完成卸貨的車輛.顯然Vi和vi[t]二者之間存在關(guān)系Vi=∪vi[t].

3.4 車輛和運(yùn)輸任務(wù)的匹配

v[i,t]{l[i,j,t1,t2]}:時(shí)刻t到達(dá)節(jié)點(diǎn)i處的車輛分配到了一項(xiàng)運(yùn)輸任務(wù)l,該運(yùn)輸任務(wù)l的時(shí)間窗為[t1,t2],目的地為節(jié)點(diǎn)j.顯然,車輛到達(dá)節(jié)點(diǎn)i的時(shí)刻t要位于運(yùn)輸任務(wù)l的時(shí)間窗允許范圍內(nèi)[t1, t2],否則該車輛不能承擔(dān)運(yùn)輸任務(wù)l.

3.5 參數(shù)

rl:車輛發(fā)送運(yùn)輸任務(wù)l所能創(chuàng)造的純利潤.

3.6 決策變量

xl′,l:0-1變量,如果車輛裝載運(yùn)輸任務(wù)l′到達(dá)目的地后,在目的節(jié)點(diǎn)又裝載運(yùn)輸任務(wù)l運(yùn)出,則xl′,l=1；如果車輛裝載運(yùn)輸任務(wù)l′到達(dá)目的地后,在目的節(jié)點(diǎn)沒有再裝載運(yùn)輸任務(wù),則xl′,l=0.

yl:0-1變量,如果車輛裝載了運(yùn)輸任務(wù)l,到達(dá)目的地后沒有再裝載其他運(yùn)輸任務(wù),則yl=1；如果車輛裝載了運(yùn)輸任務(wù)l,到達(dá)目的地后又裝載其他運(yùn)輸任務(wù),則yl=0.

3.7 車輛任務(wù)發(fā)送鏈

{l1,l2,…,ls}:表示車輛先后承擔(dān)了運(yùn)輸任務(wù)l1、l2、…、ls-1和ls,共s個(gè)運(yùn)輸任務(wù)[1,15,16].

顯然如果車輛任務(wù)發(fā)送鏈為{l1,l2,…,ls},則其所對應(yīng)的變量值為

yl1=0,xl1,l2=1,xl2,l3=1,…,xls-1,ls=1,yls=1

4 問題的模型

根據(jù)上述對車輛調(diào)度問題的描述,建立數(shù)學(xué)模型如下:

問題的目標(biāo)函數(shù)式(1)是為了使車隊(duì)調(diào)度方案所創(chuàng)造的總收益達(dá)到最大化.約束條件(2)確保車輛到達(dá)節(jié)點(diǎn)后或者被安排另一項(xiàng)運(yùn)輸任務(wù)或者沒有被安排任何運(yùn)輸任務(wù)；約束條件(3)確定了初始車輛分配方案,確保每輛車在剛開始至少分配了一項(xiàng)運(yùn)輸任務(wù)；約束(4)和(5)保證在同一時(shí)刻每項(xiàng)運(yùn)輸任務(wù)至多被一輛車運(yùn)輸,一輛車至多只能承擔(dān)一項(xiàng)運(yùn)輸任務(wù)；約束條件(6)確保決策變量xl′,l和yl為0-1變量；約束條件(7)保證車輛任務(wù)發(fā)送鏈中的任務(wù)數(shù)s多于2個(gè)時(shí),決策變量xl′,l=1的個(gè)數(shù)為s-1個(gè).

很明顯,上述所建立的問題模型是一個(gè)0-1規(guī)劃模型.對上述模型進(jìn)行分析可以發(fā)現(xiàn),除了初始各節(jié)點(diǎn)運(yùn)輸任務(wù)分布情況(Li,i∈N)已知之外,完成這些運(yùn)輸任務(wù)所需的車輛數(shù)和車輛分布情況(Vi,i∈N)均為未知.而且各運(yùn)輸任務(wù)又有不同的時(shí)間窗約束l[t1,t2],從而集合Li需要進(jìn)行及時(shí)更新,這也就導(dǎo)致了在解決實(shí)際問題時(shí),上述數(shù)學(xué)模型利用傳統(tǒng)數(shù)學(xué)規(guī)劃算法很難處理.

5 基于FCFS的啟發(fā)式算法設(shè)計(jì)

在前面分析的基礎(chǔ)上設(shè)計(jì)車隊(duì)調(diào)度問題的啟發(fā)式算法如圖1所示.

圖1 算法流程圖Fig.1 The algorithm flow chart

5.1 初始車輛分布的確定過程

Step 1產(chǎn)生車輛和運(yùn)輸任務(wù)的初始匹配.

根據(jù)運(yùn)輸任務(wù)在路網(wǎng)上的分布情況Li,為每一項(xiàng)運(yùn)輸任務(wù)分配一輛車v{l[i,j,t1,t2]}.

Step 2確定初始車輛分布方案.

將車輛標(biāo)號由v{l[i,j,t1,t2]}形式更新為v[i,t]形式,更新方法如式(8)所示:

從而生成初始車輛分布方案Vj=∪v[j,t].

5.2 運(yùn)輸任務(wù)和車輛匹配的更新過程

Step1基于FCFS的運(yùn)輸任務(wù)和車輛匹配.

Step 1.1單節(jié)點(diǎn)處的任務(wù)和車輛分配.

對于單節(jié)點(diǎn)處的車輛分配問題,采取簡單的先到先服務(wù)(FCFS)策略,即先產(chǎn)生的運(yùn)輸任務(wù)優(yōu)先安排車輛:

(1)根據(jù)節(jié)點(diǎn)i處L個(gè)運(yùn)輸任務(wù)產(chǎn)生的時(shí)刻,按照從早到晚的順序排列；

(2)根據(jù)節(jié)點(diǎn)i處V個(gè)車輛到達(dá)的時(shí)刻,按照從早到晚的順序排列；

(3)從最早產(chǎn)生的運(yùn)輸任務(wù)開始,按照車輛到達(dá)時(shí)刻從早到晚的順序依次分配車輛,記為v[i, t]{l[i,j,t1,t2]},即時(shí)刻t到達(dá)節(jié)點(diǎn)i處的車輛分配到了一項(xiàng)時(shí)間窗為[t1,t2]的運(yùn)輸任務(wù)l,要求車輛到達(dá)節(jié)點(diǎn)i的時(shí)刻t必須要位于運(yùn)輸任務(wù)l的時(shí)間窗允許范圍內(nèi)[t1,t2],即t1≤t≤t2.

Step 1.2記錄車輛任務(wù)發(fā)送鏈.

(1)記錄車輛任務(wù)發(fā)送鏈{l1,l2,…,ln},表示車輛先后發(fā)送了運(yùn)輸任務(wù)l1、l2、…、ln-1、ln.

(2)確定車輛任務(wù)發(fā)送鏈所對應(yīng)的變量值:

①如果車輛承擔(dān)一項(xiàng)運(yùn)輸任務(wù),即車輛任務(wù)發(fā)送量為{l1},則所對應(yīng)的變量值為yl1=1.

②如果車輛僅承擔(dān)多項(xiàng)運(yùn)輸任務(wù),即車輛任務(wù)發(fā)送量為{l1,l2,…,ln},按式(9)確定車輛任務(wù)發(fā)送鏈所對應(yīng)的變量值為

Step 1.3記錄車輛運(yùn)輸任務(wù)集合.

將安排車輛的運(yùn)輸任務(wù)l記入已安排車輛的運(yùn)輸任務(wù)集合L^i.

Step 2更新車輛分布和未發(fā)送運(yùn)輸任務(wù)分布.

Step 2.1車輛分布的更新過程.

按照式(10)更新節(jié)點(diǎn)i處的車輛集合Vi:

式(10)表示根據(jù)運(yùn)輸任務(wù)和其分配的車輛,比較車輛的到達(dá)時(shí)刻t和運(yùn)輸任務(wù)l時(shí)間窗的起始時(shí)間t1,確定車輛的發(fā)送時(shí)刻為t和t1中較晚的時(shí)刻,從而確定車輛到到目的節(jié)點(diǎn)j的時(shí)刻為min(t, t1)+tij,最終得到下一階段的車輛分布情況.

Step 2.2未發(fā)送運(yùn)輸任務(wù)分布的更新過程.

按照式(11)更新未發(fā)送運(yùn)輸任務(wù)集合Li:

5.3 算法的終止條件設(shè)計(jì)

Step 1如果未發(fā)送運(yùn)輸任務(wù)集合Li非空,轉(zhuǎn)5.2節(jié)；

Step 2如果未發(fā)送運(yùn)輸任務(wù)集合Li為空集,則算法停止,記錄每輛車的任務(wù)發(fā)送鏈,從而得到車隊(duì)調(diào)度方案.

6 實(shí)證分析

6.1 實(shí)例設(shè)計(jì)

運(yùn)輸網(wǎng)絡(luò)由5個(gè)節(jié)點(diǎn)組成,各節(jié)點(diǎn)之間的運(yùn)行時(shí)間為圖中邊上的權(quán)值,如圖2所示.

圖2 運(yùn)輸網(wǎng)絡(luò)Fig.2 The transportation network

在運(yùn)輸網(wǎng)絡(luò)中隨機(jī)產(chǎn)生了14項(xiàng)運(yùn)輸任務(wù),其中節(jié)點(diǎn)1處4項(xiàng),節(jié)點(diǎn)2處3項(xiàng),節(jié)點(diǎn)3處3項(xiàng),節(jié)點(diǎn)4處2項(xiàng),節(jié)點(diǎn)5處2項(xiàng),運(yùn)輸任務(wù)必須在規(guī)定的時(shí)間窗口內(nèi)完成,否則運(yùn)輸任務(wù)消失.運(yùn)輸任務(wù)的具體分布情況如表1所示.

表1 運(yùn)輸任務(wù)的分布Table 1 The distribution of transportation task

6.2 算法運(yùn)行過程

Step 1產(chǎn)生車輛和運(yùn)輸任務(wù)的初始匹配.

按照為每一項(xiàng)運(yùn)輸任務(wù)分配一個(gè)車輛的方法產(chǎn)生初始車輛和運(yùn)輸任務(wù)的匹配關(guān)系,如表2所示.

Step 2確定初始車輛分布方案.

按式(8)更新節(jié)點(diǎn)1-5處的車輛標(biāo)號,從而得到初始車輛分布方案,如表3所示.

Step 3第一次基于FCFS的運(yùn)輸任務(wù)和車輛匹配,如表4所示.

生成車輛的任務(wù)發(fā)送鏈={車輛1:l[1,2, 6:00-12:00]；車輛2:l[1,5,9:00-16:00]；車輛3:l[2,1,9:00-12:00]；車輛4:l[2,4,10:00-16:00]；車輛5:l[2,5,12:00-18:00]；車輛6: l[3,5,10:00-18:00]；車輛7:l[3,2,12:00-23:00]；車輛8:l[4,5,9:00-17:00]；車輛9: l[4,3,10:00-15:00]；車輛10:l[5,2,14:00-19:00]；車輛11:l[5,4,15:00-20:00]}.

Step 4第一次更新車輛和未發(fā)送運(yùn)輸任務(wù)分布.

按式(10)和式(11)更新車輛分布集合Vi和運(yùn)輸任務(wù)集合Li,如表5和表6所示.

表2 初始車輛和運(yùn)輸任務(wù)的匹配Table 2 The initial matching relation on the vehicle and task

表3 初始車輛分布方案Table 3 The initial distribution of the vehicle

表4 車輛和運(yùn)輸任務(wù)的匹配Table 4 The matching on the vehicle and task

表5 當(dāng)前車輛分布Table 5 The current distribution of the vehicle

表6 未發(fā)送的運(yùn)輸任務(wù)的分布Table 6 The distribution of the unallocated transportation task

Step 5第二次基于FCFS的運(yùn)輸任務(wù)和車輛匹配.

根據(jù)車輛分布集合Vi和未發(fā)送運(yùn)輸任務(wù)集合Li,為運(yùn)輸任務(wù)分配車輛如表7所示.

表7 車輛和運(yùn)輸任務(wù)的匹配Table 7 The match on the vehicle and task

更新車輛的任務(wù)發(fā)送鏈:

車輛3:l[2,1,9:00-12:00]-l[1,3,6:00 -13:00],即x{l[2,1,9:00-12:00],l[1,3,6:00 -13:00]}=1.

車輛9:l[4,3,10:00-15:00]-l[3,1,13:00 -21:00],即x{l[4,3,10:00-15:00],l[3,1,13: 00-21:00]}=1.

Step 6第二次更新車輛和未發(fā)送運(yùn)輸任務(wù)分布.

更新車輛分布集合Vi和運(yùn)輸任務(wù)集合Li如表8和表9所示.

表8 當(dāng)前車輛分布Table 8 The current distribution of the vehicle

表9 未發(fā)送的運(yùn)輸任務(wù)的分布Table 9 The distribution of the unallocated transportation task

Step 7第三次基于FCFS的運(yùn)輸任務(wù)和車輛匹配.

根據(jù)車輛分布集合Vi和運(yùn)輸任務(wù)集合Li,為運(yùn)輸任務(wù)分配車輛如表10所示.

表10 車輛和運(yùn)輸任務(wù)的匹配Table 10 The matching relation on the vehicle and task

更新生成車輛的任務(wù)發(fā)送鏈:

車輛9:l[4,3,10:00-15:00]-l[3,1, 13:00-21:00]-l[1,4,10:00-18:00],即

x{l[3,1,13:00-21:00], l[1,4,10:00-18:00]}=1

Step 8第三次更新車輛分布和未發(fā)送運(yùn)輸任務(wù)分布.

未發(fā)送運(yùn)輸任務(wù)分布Li為空集.

Step 9算法終止.

因?yàn)槲窗l(fā)送運(yùn)輸任務(wù)分布Li為空集,算法停止,得到車隊(duì)調(diào)度方案如下:

車輛1:l[1,2,6:00-12:00]；車輛2:l[1,5, 9:00-16:00]；車輛3:l[2,1,9:00-12:00]——l[1,3,6:00-13:00]；車輛4:l[2,4,10:00-16:00]；車輛5:l[2,5,12:00-18:00]；車輛6:l [3,5,10:00-18:00]；車輛7:l[3,2,12:00-23:00]；車輛8:l[4,5,9:00-17:00]；車輛9: l[4,3,10:00-15:00]——l[3,1,13:00-21:00]——l[1,4,10:00-18:00]；車輛10:l[5,2,14:00 -19:00]；車輛11:l[5,4,15:00-20:00].

該車隊(duì)調(diào)度方案由11條車輛任務(wù)發(fā)送鏈組成,該方案共使用了11輛車.將該方案轉(zhuǎn)變?yōu)閱栴}解的形式:

y{l[1,2,6:00-12:00]}=1；y{l[1,5,9:00-16:00]}=1；

y{l[2,1,9:00-12:00]}=0,x{l[2,1,9:00-12:00],l[1,3,6:00-13:00]}=1,y{l[1,3,6:00 -13:00]}=1；

y{l[2,4,10:00-16:00]}=1；y{l[2,5,12:00 -18:00]}=1；y{l[3,5,10:00-18:00]}=1；y{l[3,2,12:00-23:00]}=1；

y{l[4,5,9:00-17:00]}=1；y{l[4,3,10:00 -15:00]}=0,x{l[4,3,10:00-15:00],l[3,1,13:00-21:00]}=1,x{l[3,1,13:00-21:00], l[1,4,10:00-18:00]}=1,

y{l[1,4,10:00-18:00]}=0；y{l[5,2,14:00 -19:00]}=1；y{l[5,4,15:00-20:00]}=1.

6.3 算法的有效性分析

算法針對運(yùn)輸網(wǎng)絡(luò)中單節(jié)點(diǎn)處運(yùn)輸任務(wù)和車輛分配問題設(shè)計(jì)了先到先服務(wù)原則,從而確保了各運(yùn)輸任務(wù)都能夠最大限度地在其時(shí)間窗約束要求范圍內(nèi),分配到所需的車輛.同時(shí),算法通過對每輛車設(shè)計(jì)一條車輛任務(wù)發(fā)送鏈,使得每輛車都能夠盡可能地承擔(dān)多項(xiàng)運(yùn)輸任務(wù),使得車輛的利用率達(dá)到最大.

綜上所述,本文所設(shè)計(jì)的基于FCFS策略的求解算法能夠有效地解決車隊(duì)調(diào)度問題,不但可以減少車隊(duì)中車輛的數(shù)量,而且可以給出每輛車的具體行車路線、具體安排的運(yùn)輸任務(wù)和到達(dá)各節(jié)點(diǎn)的時(shí)間.

7 研究結(jié)論

本文對一類帶時(shí)間窗的車隊(duì)調(diào)度問題進(jìn)行了分析,建立了其數(shù)學(xué)規(guī)劃模型.鑒于數(shù)學(xué)規(guī)劃模型利用傳統(tǒng)數(shù)學(xué)規(guī)劃算法難于求解,設(shè)計(jì)了一類啟發(fā)式算法.該算法設(shè)計(jì)了一套FCFS規(guī)則進(jìn)行運(yùn)輸任務(wù)和車輛的分配,同時(shí)算法為車輛設(shè)計(jì)了一組簡單的編號來標(biāo)記車輛所處的位置和到達(dá)節(jié)點(diǎn)的時(shí)間,并通過不斷更新車輛標(biāo)號生成一條條車輛任務(wù)發(fā)送鏈,最后形成一整套車輛調(diào)度方案.本文最后通過實(shí)例驗(yàn)證了算法的可行性.

[1] 軒華,李冰.動態(tài)車輛調(diào)配問題中的車輛供給變動分析[J].中原工學(xué)院學(xué)報(bào),2007,18(3):59-63. [XUAN H,LI B.Vehicle supply change analysis of the dynamic vehicle allocation problem[J].Journal of Zhongyuan University of Technology,2007,18(3): 59-63.]

[2] 李冰.動態(tài)車隊(duì)調(diào)度問題的模型及優(yōu)化控制方法研究[M].北京:機(jī)械工業(yè)出版社,2011.[LI B. Study on the model and optimal control method of the dynamic vehicle allocation problem[M].Beijing: Mechanical Industry Press,2011.]

[3] 李冰.多車型動態(tài)車隊(duì)調(diào)度問題的算法設(shè)計(jì)及求解[J].系統(tǒng)管理學(xué)報(bào),2011,20(4):503-509.[LI B. Algorithm for dynamic fleet scheduling with multiple vehicle types[J].Journal of Systems&Management, 2011,20(4):503-509.]

[4] 李冰.隨機(jī)動態(tài)車隊(duì)管理問題研究[J].系統(tǒng)工程, 2005,23(1):96-101.[LI B.The stochastic dynamic fleet management[J].Systems Engineering,2005,23 (1):96-101.]

[5] 李冰.單車型確定性動態(tài)車輛調(diào)配問題[J].系統(tǒng)管理學(xué)報(bào),2008(3):353-360.[LI B.Research on the deterministic dynamic vehicle allocation problem with homogeneous vehicle type[J].Journal of Systems &Management,2008(3):353-360.]

[6] 李冰,郝越,軒華.基于排隊(duì)網(wǎng)絡(luò)的運(yùn)輸排隊(duì)過程研究[J].重慶交通大學(xué)學(xué)報(bào),2012,31(4):293-298 [LI B,HAO Y,XUAN H.Transportation queuing processes research based on queuing network[J]. Journal of Chongqing Jiaotong University,2012,31 (4):293-298.]

[7] 宋偉剛,張宏霞,佟玲.有時(shí)間窗約束非滿載車輛調(diào)度問題的遺傳算法[J].系統(tǒng)仿真學(xué)報(bào),2005,17 (11):2593-2597.[SONG W G,ZHAGN H X, TONG L.Genetic algorithm for VRP of non-full loads with time windows[J].Acta Simulata Systematica Sinica,2005,17(11):2593-2597.]

[8] 黃瑞銘.配送時(shí)間窗約束下車輛調(diào)度遺傳算法研究[J].物流科技,2011,4:116-119.[HUANG R M. Research on the genetic algorithm for vehicle routing problem with delivery time windows[J].Logistics Sci-Tech,2011,4:116-119.]

[9] 鐘時(shí)泉,杜綱,賀國光.有顧客時(shí)間窗和發(fā)貨量變化的緊急車輛調(diào)度研究[J].管理工程學(xué)報(bào),2007, 21(4):114-118.[ZHONG S Q,DU G,HE G G. Study on urgency vehicle scheduling problem with the changes oftime windows and delivery weight of customers[J].Journal of Industrial Engineering and Engineering Management,2007,21(4):114-118.]

[10] 王雷.用節(jié)約法解帶有時(shí)間窗的車輛調(diào)度問題[J].黑龍江工程學(xué)院學(xué)報(bào)(自然科學(xué)學(xué)報(bào)),2011, 25(3):18-20.[WANG L.Saving algorithm for VRP of with time windows[J].Journal of Heilongjiang Institute of Technology,2011,25(3):18-20.]

[11] 霍佳震,張磊.用節(jié)約法解決帶有時(shí)間窗的滿載車輛調(diào)度問題[J].工業(yè)工程與管理,2006,4:39-49. [HUO J Z,ZHAGN L.Savings based algorithm for full truckload vehicle routing problem with time window [J].Industrial Engineering and Management,2006, 4:39-49.][12] Brown G,Graves G.Real-time dispatch of petroleum tank trucks[J].Management Science,1981,27: 19-32.

[13] Bell W,Delbert M,Fisher M,et al.Improving the distributionofindustrialgaseswithanonline computerized routing and scheduling optimizer[J]. Interfaces,1983,13:4-23.

[14] Powell W B,Carvalho T A,Godfrey G,et al. Dynamic fleet management as a logistics queueing network[J].Annal Operation Research,1998,61: 168-188.

[15] 李冰.多車型確定性動態(tài)車輛調(diào)配問題[J].管理工程學(xué)報(bào),2006,20(3):52-56.[LI B.The determinitic dynamic vehicle allocation problem with multiple vehicletype[J].JournalofIndustrial Engineering and Engineering Management,2006,20 (3):52-56.]

[16] Powell W B,Wayne Snow,Raymond K Cheung. Adaptivelabelingalgorithmsforthedynamic assignmentproblem[J].TransportationScience, 2000,34(1):50-66.

Fleet Scheduling Problem with Time Windows Based on FCFS Strategy

XUAN Hua
(School of Management Engineering,Zhengzhou University,Zhengzhou 450001,China)

It helps improve resource utilization and realize scientific transportation to schedule freight vehicle and transportation tasks effectively.A fleet scheduling problem with time windows is analyzed,and then formulated as a mathematical programming model.A heuristic algorithm is designed because of it is difficult to solve the model using traditional algorithms,where the vehicle is assigned to the transportation tasks using FCFS method.The vehicle label is devised to represent the location and the arrival time of the vehicle.A sub-tour is devised to contain a sequence of chained vehicle-task assignment.Finally,the fleet scheduling solution is proposed.A case validates the feasibility of this algorithm.

integrated transportation；fleet scheduling；heuristic algorithms；first come first served；time windows

U492.312；F542

A

U492.312；F542

A

1009-6744(2013)06-0140-08

2013-04-11

2013-06-10錄用日期:2013-06-20

國家自然科學(xué)基金(71001091,71001090)；中國博士后科學(xué)基金面上資助項(xiàng)目(2013M531683).

軒華(1979-),女,河南睢縣人,副教授,工學(xué)博士.

*通訊作者:hxuan@zzu.edu.cn