秦維洋

（中國(guó)電信股份有限公司上海研究院 上海 200122）

1 車(chē)輛調(diào)度網(wǎng)絡(luò)的現(xiàn)狀

在現(xiàn)實(shí)世界，車(chē)輛調(diào)度是解決突發(fā)事件、應(yīng)急事件等問(wèn)題的重要研究課題，在智能交通領(lǐng)域更是研究的熱點(diǎn)。目前，國(guó)內(nèi)外諸多專(zhuān)家學(xué)者紛紛對(duì)車(chē)輛調(diào)度問(wèn)題進(jìn)行研究。

王旭[1]等人通過(guò)分析調(diào)度問(wèn)題的需求信息提出順序，將動(dòng)態(tài)調(diào)度問(wèn)題等效為不同時(shí)刻的靜態(tài)調(diào)度，并建立了基于時(shí)間軸的動(dòng)態(tài)調(diào)度模型，設(shè)計(jì)了“初始優(yōu)化階段+實(shí)時(shí)優(yōu)化階段”的分段求解策略；唐偉勤[2]等人通過(guò)對(duì)應(yīng)急車(chē)輛調(diào)度路徑的研究，以調(diào)度所花費(fèi)時(shí)間的均衡性為目標(biāo)建立了調(diào)度模型，并結(jié)合實(shí)例改進(jìn)了最近搜索法；王曉博[3]等人建立了多車(chē)型、多車(chē)場(chǎng)的混合車(chē)輛導(dǎo)讀模型，運(yùn)用混合遺傳啟發(fā)式算法對(duì)車(chē)輛調(diào)度問(wèn)題進(jìn)行求解；張景玲[4]等人考慮了物流配送中需求的動(dòng)態(tài)變化、車(chē)型、路線(xiàn)等，建立了數(shù)學(xué)規(guī)劃調(diào)度模型，制定了預(yù)優(yōu)化路徑調(diào)度和實(shí)時(shí)調(diào)度策略，提出了2-OPT優(yōu)化方法，提高了算法的收斂速度；劉芹[5]等人基于實(shí)際交通狀況提出了改進(jìn)的車(chē)輛調(diào)度模型，并運(yùn)用粒子群算法和模擬退火算法混合求解了調(diào)度問(wèn)題；何正文[6]等人基于禁止時(shí)間窗的應(yīng)急物資調(diào)度問(wèn)題，通過(guò)整數(shù)規(guī)劃優(yōu)化了調(diào)度模型，并定義了相關(guān)決策變量，對(duì)路徑的節(jié)點(diǎn)和支線(xiàn)進(jìn)行選擇；王文蕊[7]等人從實(shí)際配送中變化的訂貨量出發(fā)，提出了變動(dòng)成本概念，引入預(yù)優(yōu)化策略，建立了能夠根據(jù)訂貨量變化實(shí)時(shí)調(diào)整的兩階段數(shù)學(xué)模型，并采用粒子群算法求解調(diào)度模型，驗(yàn)證了兩階段模型的有效性；何建敏[8]等人基于調(diào)度問(wèn)題中的時(shí)間緊迫性與車(chē)輛出發(fā)地?cái)?shù)目相互矛盾的目標(biāo)，運(yùn)用模糊優(yōu)化方法研究了限制期下的多出救點(diǎn)組合模型；趙燕偉[9]等人通過(guò)建立基于模糊滿(mǎn)意度的多目標(biāo)數(shù)學(xué)規(guī)劃模型來(lái)優(yōu)化車(chē)輛調(diào)度問(wèn)題，提出利用分段優(yōu)化的方法求解Pareto解，并為保持Pareto解的分散性，提出了一種自適應(yīng)網(wǎng)格算子；安一帆[10]結(jié)合道路交通情況，建立了包含時(shí)間影響因素的結(jié)構(gòu)模型，從而實(shí)現(xiàn)調(diào)度時(shí)間的優(yōu)化。

Sangheon HAN[11]等人考慮到利用遺傳算法計(jì)算車(chē)輛調(diào)度問(wèn)題的收斂速度，提出了一種結(jié)合遺傳算法與其他啟發(fā)式算法的混合算法來(lái)解決車(chē)輛調(diào)度問(wèn)題；William Ho[12]等人為解決多車(chē)場(chǎng)多路徑的調(diào)度問(wèn)題，提出了一種混合遺傳算法，并驗(yàn)證了算法的有效性；Ombuki B[13]等人用遺傳算法求解多目標(biāo)調(diào)度問(wèn)題，考慮了車(chē)輛數(shù)量和距離成本，從兩個(gè)維度驗(yàn)證了算法的可靠性；Jin M Z[14]等人提出了一種時(shí)延最小的數(shù)學(xué)規(guī)劃模型，并通過(guò)線(xiàn)性規(guī)劃提高了模型的性能指標(biāo)。

上述研究?jī)?nèi)容包含大量車(chē)輛調(diào)度問(wèn)題的研究成果及應(yīng)用，為多路徑車(chē)輛調(diào)度問(wèn)題的動(dòng)態(tài)描述和求解提供了很好的思路，對(duì)建立和完善多路徑車(chē)輛調(diào)度模型有很好的借鑒意義。

2 多路徑調(diào)度網(wǎng)絡(luò)建模

2.1 多路徑調(diào)度網(wǎng)絡(luò)的定義

在智能交通領(lǐng)域，多路徑的車(chē)輛調(diào)度網(wǎng)絡(luò)是一個(gè)由車(chē)輛出發(fā)地（S）、目的地（D）和連接路徑（P）組成的網(wǎng)絡(luò)。在復(fù)雜的多路徑調(diào)度網(wǎng)中，調(diào)度目的地是構(gòu)建車(chē)輛調(diào)度網(wǎng)絡(luò)的誘因，也是車(chē)輛調(diào)度系統(tǒng)建模的首要元素，在調(diào)度過(guò)程中提出調(diào)度需求的類(lèi)型、數(shù)量、時(shí)間等；車(chē)輛出發(fā)地是構(gòu)建車(chē)輛調(diào)度網(wǎng)絡(luò)的必備條件，是建模的重要元素，必須具備一定數(shù)量相同類(lèi)型或不同類(lèi)型的車(chē)輛，能夠?yàn)檐?chē)輛調(diào)度提供一定類(lèi)型、數(shù)量的有效車(chē)輛；連接路徑是網(wǎng)絡(luò)中車(chē)輛進(jìn)行有效調(diào)度的激活條件，是車(chē)輛出發(fā)地和目的地之間建立聯(lián)系的必要元素，只有兩者存在有效連接，車(chē)輛的調(diào)度需求才能得到滿(mǎn)足。

在實(shí)際的調(diào)度網(wǎng)絡(luò)中，車(chē)輛調(diào)度是一個(gè)實(shí)時(shí)的動(dòng)態(tài)過(guò)程，調(diào)度目標(biāo)有可能會(huì)發(fā)生改變，導(dǎo)致車(chē)輛數(shù)量增減、調(diào)度目的地變更等。如在調(diào)度中，由于天氣、人為等因素的影響，調(diào)度策略需要做出修改和調(diào)整，可能出現(xiàn)已經(jīng)出發(fā)的車(chē)輛雖然未到達(dá)目的地，但需要執(zhí)行新的調(diào)度方案，原來(lái)未建立有效連接路徑的兩點(diǎn)間可以直接連接或通過(guò)間接路徑連接。此時(shí)，原有模型中的節(jié)點(diǎn)、連接路徑不能很好地體現(xiàn)此時(shí)調(diào)度網(wǎng)絡(luò)的實(shí)際特征和性質(zhì)。因此，模型中還應(yīng)包含表征多路徑、多類(lèi)型車(chē)輛、多目的地以及動(dòng)態(tài)因素的建模元素。

本文引入虛擬節(jié)點(diǎn)和虛擬路徑的概念對(duì)調(diào)度過(guò)程中的動(dòng)態(tài)特征進(jìn)行描述，并給出多路徑車(chē)輛調(diào)度網(wǎng)的形式化定義。多路徑車(chē)輛調(diào)度網(wǎng)是一個(gè)滿(mǎn)足如下條件的六元組N=(S,Sv,D,P,Pv,M)：

·S={s1,s2,…}是一個(gè)有限的車(chē)輛出發(fā)地集合，其中S≠；

·Sv={sv1,sv2,…}是一個(gè)有限的車(chē)輛出發(fā)地集合，其中Sv可以為空；

·Dv={dv1,dv2,…}是一個(gè)有限的目的地集合，其中Dv可以為空；

·P={p1,p2,…}是一個(gè)有限的連接路徑集合，其中P≠且P是((S∪Sv)∪D)×((S∪Sv)∪D)的多重子集；

·Pv={pv1,pv2,…}是一個(gè)有限的連接路徑集合，其中Pv可以為空；

·M:P∪Pv→{(a,b)|a∈(S∪Sv)∪D,b∈(S∪Sv)∪D,a≠b}是連接路徑P∪Pv到無(wú)序積((S∪Sv)∪D)&((S∪Sv)∪D)的映射，表示車(chē)輛出發(fā)地與目的地之間的連接關(guān)系；

· 存在M(pi)=(a,b)，M(pj)=(a,b)，其中a∈((S∪Sv)∪D),b∈((S∪Sv)∪D)，且a≠b，表示網(wǎng)絡(luò)中兩點(diǎn)間存在多條路徑；

·dom(P)∪cod(P)=(S∪Sv)∪D，其中dom(P)={a|堝b:(a,b)∈P}，cod(P)={b|堝a:(a,b)∈P}。

上述定義中S和D分別代表車(chē)輛出發(fā)地、目的地，是網(wǎng)絡(luò)的基本元素。其中S≠ 、D≠ 表示在調(diào)度網(wǎng)絡(luò)中至少存在一個(gè)車(chē)輛出發(fā)地和一個(gè)目的地，同時(shí)P≠ 是((S∪Sv)∪D)×((S∪Sv)∪D)的子集，表示網(wǎng)絡(luò)中不存在獨(dú)立的出發(fā)地或目 的地，M(p)=(a,b)，a∈(S∪D)，b∈(S∪D)，a≠b,p∈P，表示網(wǎng)絡(luò)中沒(méi)有無(wú)意義的自環(huán)。M是網(wǎng)絡(luò)中任意兩點(diǎn)間的映射，對(duì)于M(pi)=(a,b)，M(pj)=(a,b)，若M(pi)≠M(fèi)(pj)，表示網(wǎng)絡(luò)中兩點(diǎn)間存在的多條路徑中，包含的映射函數(shù)是不同的；若M(pi)=M(pj)，表示網(wǎng)絡(luò)中兩點(diǎn)間存在的多條路徑，包含的映射函數(shù)是相同的。若Sv≠ ，Dv≠ ，則調(diào)度網(wǎng)絡(luò)表示最基本的車(chē)輛調(diào)度網(wǎng)絡(luò)。

2.2 多路徑調(diào)度網(wǎng)絡(luò)結(jié)構(gòu)

節(jié)點(diǎn)和路徑是多路徑調(diào)度網(wǎng)絡(luò)中重要的組成元素，而網(wǎng)絡(luò)中很多結(jié)構(gòu)特性也是通過(guò)節(jié)點(diǎn)、路徑的種類(lèi)和連接關(guān)系來(lái)反映的。下面從節(jié)點(diǎn)和路徑兩個(gè)角度分析多路徑調(diào)度網(wǎng)絡(luò)結(jié)構(gòu)特征。

（1）路徑角度

路徑表示節(jié)點(diǎn)間復(fù)雜的關(guān)聯(lián)關(guān)系，在不同的網(wǎng)絡(luò)中，路徑也會(huì)根據(jù)連接關(guān)系、限制條件等因素劃分為不同的類(lèi)型，如多路徑調(diào)度網(wǎng)絡(luò)中的路徑可以分為公路、鐵路、水路、航空線(xiàn)路等類(lèi)型。

如圖1所示，多路徑調(diào)度網(wǎng)絡(luò)的連接路徑包含兩種情況。

· 如圖1（a）所示，網(wǎng)絡(luò)中只有一種類(lèi)型的路徑，即網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)的連接路徑只有單一類(lèi)型，包含出發(fā)地之間和目的地之間，是車(chē)輛調(diào)度網(wǎng)絡(luò)中一種基本的結(jié)構(gòu)類(lèi)型。

· 如果1（b）所示，網(wǎng)絡(luò)中存在多種類(lèi)型的連接路徑。對(duì)于網(wǎng)絡(luò)中任意兩個(gè)關(guān)聯(lián)節(jié)點(diǎn)可能包含兩種情況：兩節(jié)點(diǎn)間有多重連接路徑，但每?jī)蓚€(gè)節(jié)點(diǎn)間的路徑只有一種類(lèi)型；兩節(jié)點(diǎn)間有多重連接路徑，兩節(jié)點(diǎn)間連接路徑的類(lèi)型也不相同。

圖1 多路徑調(diào)度網(wǎng)絡(luò)的連接路徑

（2）節(jié)點(diǎn)角度

多路徑調(diào)度網(wǎng)絡(luò)中節(jié)點(diǎn)的度表示與該節(jié)點(diǎn)連接的連接路徑數(shù)量，也是網(wǎng)絡(luò)結(jié)構(gòu)特征的基本參數(shù)。如圖2所示，當(dāng)節(jié)點(diǎn)入度為0、出度不為0時(shí)，表示該節(jié)點(diǎn)在網(wǎng)絡(luò)中僅作為車(chē)輛出發(fā)地，如節(jié)點(diǎn)s3；當(dāng)節(jié)點(diǎn)入度不為0、出度為0時(shí)，表示該節(jié)點(diǎn)在網(wǎng)絡(luò)中僅作為目的地，如節(jié)點(diǎn)d4；當(dāng)節(jié)點(diǎn)入度和出度均不為0時(shí)，表示該節(jié)點(diǎn)有可能同時(shí)作為車(chē)輛出發(fā)地和目的地，如節(jié)點(diǎn)d5。

圖2 調(diào)度網(wǎng)絡(luò)中節(jié)點(diǎn)的度

在實(shí)際的多路徑調(diào)度網(wǎng)絡(luò)中，連接路徑通常無(wú)指定方向，以節(jié)點(diǎn)的度作為參考對(duì)象，可將連接路徑看成一條雙向的連接路徑，如路徑p6。

3 分層調(diào)度網(wǎng)絡(luò)建模

在多路徑車(chē)輛調(diào)度問(wèn)題中，由于調(diào)度優(yōu)先級(jí)等原因，網(wǎng)絡(luò)結(jié)構(gòu)會(huì)呈現(xiàn)出一定的層次性，不同層次的網(wǎng)絡(luò)結(jié)構(gòu)體現(xiàn)了節(jié)點(diǎn)、連接路徑及網(wǎng)絡(luò)結(jié)構(gòu)的層次性。分層調(diào)度網(wǎng)絡(luò)是一個(gè)滿(mǎn)足如下條件的六元組N=（SD，PD，SH，PH，F(xiàn)PD，F(xiàn)PH）：

·SD是一個(gè)有限的多層次節(jié)點(diǎn)的集合，SD={S1,S2,…}，其中，Si={si1,si2,…}，i=1,2,…，表示第i層內(nèi)的節(jié)點(diǎn)(|SD|≥2，Si≠ ，i=1,2,…)；

·PD是一個(gè)有限的連接同層節(jié)點(diǎn)的連接路徑集合，PD={P1,P2,…}，其中，Pi={pi1,pi2,…}，i=1,2,…，表示第i層內(nèi)連接節(jié)點(diǎn)的連接路徑(|PD|≥2，Pi≠ ，i=1,2,… )；

·SH是一個(gè)有限的分層網(wǎng)絡(luò)間節(jié)點(diǎn)的集合；

·PH是一個(gè)有限的分層網(wǎng)絡(luò)間的連接路徑集合；

·:PD→{(x,y)|x,y∈Si,x≠y,Si哿SD}，表示同層連接路徑PD到無(wú)序積SD&SD（不包含自環(huán)）的映射；

·:PH→{(x,y)|x∈Si,y∈Sj,x≠y,i≠j,Si哿SD,Sj哿SD}，表示跨層連接路徑PH到無(wú)序積SD&SD（不包含自環(huán)）的映射。

在分層網(wǎng)中，節(jié)點(diǎn)分為多個(gè)層次，連接路徑也相應(yīng)地分為同層連接和層間連接，同層節(jié)點(diǎn)之間按照同層連接規(guī)則由同層連接路徑進(jìn)行連接，跨層節(jié)點(diǎn)之間的連接關(guān)系則由層間連接規(guī)則確定。

分層調(diào)度網(wǎng)絡(luò)也具有一定的結(jié)構(gòu)特征，本文定義變量如下：

·HS(S)={hs1,hs2,…}，表示分層網(wǎng)絡(luò)中節(jié)點(diǎn)所屬的層次集，HS≥1；

·fhs:S→HS(S)，表示節(jié)點(diǎn)到節(jié)點(diǎn)所屬層次的劃分函數(shù)；

· ω(si)=fhs(si)，表示節(jié)點(diǎn)所屬的層次，ω(si)∈HS；

·HP(P)={hp1,hp2,…}，表示分層網(wǎng)絡(luò)中連接路徑所屬的層次集，HP≥1；

·fhp:P→HP(P)，表示連接路徑到連接路徑所屬層次的劃分函數(shù)；

· ω(pi)=fhp(pi)，表示連接路徑所屬的層次，ω(pi)∈HP。

在分層調(diào)度網(wǎng)絡(luò)中，任意兩個(gè)節(jié)點(diǎn)間存在層次差，用DHS(si,sj)=ω(si)-ω(sj)表示。若DHS(si,sj)>0，即 ω(si)>ω(sj)，則表示節(jié)點(diǎn)si所屬的層次大于節(jié)點(diǎn)sj所屬的層次；若DHS(si,sj)<0，即ω(si)<ω(sj)，則表示節(jié)點(diǎn)si所屬的層次小于節(jié)點(diǎn)sj所屬的層次；若DHS(si,sj)=0，即 ω(si)=ω(sj)，則表示節(jié)點(diǎn)si與節(jié)點(diǎn)sj屬同一層次；若DHS(si,sj)=1，表示兩節(jié)點(diǎn)是鄰層節(jié)點(diǎn)；若DHS(si,sj)>1，表示兩節(jié)點(diǎn)是跨層節(jié)點(diǎn)。

同理，分層調(diào)度網(wǎng)絡(luò)中的連接路徑也存在上述情況，用DES(pi,pj)=ω(pi)-ω(pj)表示連接路徑的層次差。若DES(pi,pj)>0，即ω(pi)>ω(pj)，則表示連接路徑pi所屬的層次大于連接路徑pj所屬的層次；若DES(pi,pj)<0，即 ω(pi)<ω(pj)，則表示連接路徑pi所屬的層次小于連接路徑pj所屬的層次；若DES(pi,pj)=0，即 ω(pi)=ω(pj)，則表示連接路徑pi與連接路徑pj所屬的層次相同；若DES(pi,pj)=1，表示兩條連接路徑是鄰層連接路徑；若DES(pi,pj)>1，表示兩條連接路徑是跨層連接路徑。

定義Vad(si)={uj|uj∈S-si,(si,sj)∈F(P)}，表示節(jié)點(diǎn)si的鄰接節(jié)點(diǎn)集合；VadS(si)={uj|uj∈Vad(si),ω(uj)=ω(si)}，表示節(jié)點(diǎn)si的處于同層的鄰接節(jié)點(diǎn)集；VadD(si)={uj|uj∈Vad(si),ω(uj)≠ω(si)}，表示節(jié)點(diǎn)si的處于不同層的鄰接節(jié)點(diǎn)集。其中，Vad(si)=VadS(si)∪VadD(si)。

（1）從鄰接節(jié)點(diǎn)數(shù)量分析

·當(dāng)存在|VadS(si)|=1時(shí)，表示節(jié)點(diǎn)si只與同層次中的一個(gè)節(jié)點(diǎn)連接。

·當(dāng)存在|VadS(si)|>1時(shí)，表示節(jié)點(diǎn)si與同層次中的多個(gè)節(jié)點(diǎn)連接。

·當(dāng)存在|VadD(si)|=1時(shí)，表示節(jié)點(diǎn)si只與其他層次中的一個(gè)節(jié)點(diǎn)連接。

·當(dāng)存在|VadD(si)|>1時(shí)，表示節(jié)點(diǎn)si與其他層次中的多個(gè)節(jié)點(diǎn)連接。

（2）從鄰接節(jié)點(diǎn)層次差分析

在同層鄰接節(jié)點(diǎn)集VadS(si)中，DHS(si,uj)=0。

在不同層鄰接節(jié)點(diǎn)集VadD(si)中，若DHS(si,uj)=1，表示在不同層鄰接節(jié)點(diǎn)集中存在與節(jié)點(diǎn)si連接的鄰層節(jié)點(diǎn)；若DHS(si,uj)>1，表示在不同層鄰接節(jié)點(diǎn)集中存在與節(jié)點(diǎn)si連接的跨層節(jié)點(diǎn)。

圖3為一個(gè)分層調(diào)度網(wǎng)絡(luò)結(jié)構(gòu)，該分層調(diào)度網(wǎng)N=（SD，PD，SH，PH，，）描述如下 ：SD={S1,S2,S3}，其中，S1={s1,d1,s2,d2,s3,d3}，S2={s4,d4,s5,d5}，S3={s6,s7,d6,d7}，PD={P1,P2,P3}，其 中 ，P1={p1,p2,p3,p4,p5,p6}，P2={p8,p11,p12}，P3={p24,p25},SH= ,PH={p7,p9,p10,p13,p14,p15,p16,p17,p18,p19,p20,p21,p22,p23}。

從圖3中可以看出，第一層網(wǎng)絡(luò)中存在兩種類(lèi)型的節(jié)點(diǎn)，單一類(lèi)型的連接路徑；第二層網(wǎng)絡(luò)中存在兩種類(lèi)型的節(jié)點(diǎn)，3種類(lèi)型的連接路徑；第三層分層網(wǎng)中存在兩種類(lèi)型的節(jié)點(diǎn)，單一類(lèi)型的連接路徑。

（1）從節(jié)點(diǎn)的角度分析

對(duì)于節(jié)點(diǎn)s1，其鄰接節(jié)點(diǎn)集為Vad(s1)={d1,d4,s6,d6}，同層的鄰接節(jié)點(diǎn)集VadS(s1)={d1}，不同層的鄰接節(jié)點(diǎn)集VadS(s1)={d4,s6,d6}。其中，DHS(s1,d1)=0，表示節(jié)點(diǎn)s1與節(jié)點(diǎn)d1為同層節(jié)點(diǎn)且兩節(jié)點(diǎn)為不同類(lèi)型；|VadS(s1)|=1，表示節(jié)點(diǎn)s1只與同層次中的一個(gè)節(jié)點(diǎn)連接。|VadD(s1)|=3，表示節(jié)點(diǎn)s1與其他層次中的多個(gè)節(jié)點(diǎn)連接。DHS(d4,s1)=0表示節(jié)點(diǎn)s1與節(jié)點(diǎn)d4為鄰層連接節(jié)點(diǎn)，且兩節(jié)點(diǎn)為不同類(lèi)型；DHS(s6,s1)=DHV(d6,s1)=2表示節(jié)點(diǎn)s1與節(jié)點(diǎn)s6、d6為跨層鄰接節(jié)點(diǎn)。

（2）從連接路徑的角度分析

圖3中分層調(diào)度網(wǎng)絡(luò)存在不同類(lèi)型的層間連接路徑。對(duì)于層間連接路徑p20，其兩個(gè)節(jié)點(diǎn)為不同類(lèi)型的鄰層連接節(jié)點(diǎn)；對(duì)于層間連接路徑p18，其連接的兩個(gè)節(jié)點(diǎn)為不同類(lèi)型的跨層連接節(jié)點(diǎn)。

4 多路徑調(diào)度網(wǎng)絡(luò)實(shí)例求解

圖4為某一多路徑車(chē)輛調(diào)度網(wǎng)絡(luò)。已知網(wǎng)絡(luò)中有3個(gè)車(chē)輛出發(fā)地，4個(gè)車(chē)輛目的地，按照實(shí)際調(diào)度情況及調(diào)度優(yōu)先級(jí)對(duì)該調(diào)度網(wǎng)進(jìn)行分層，包括第一層和第二層。出發(fā)地和目的地之間存在高速公路、一般公路、鐵路、水路4種連接路徑，對(duì)應(yīng)的運(yùn)輸工具包括大貨車(chē)、小貨車(chē)、火車(chē)、輪船4類(lèi)。為了提高調(diào)度的響應(yīng)效率，以調(diào)度時(shí)間最短為目標(biāo)。由于在車(chē)輛調(diào)度過(guò)程中調(diào)度策略發(fā)生變化，引入了虛擬車(chē)輛出發(fā)地和虛擬連接路徑來(lái)完善該分層調(diào)度網(wǎng)絡(luò)。

圖3 分層調(diào)度網(wǎng)絡(luò)結(jié)構(gòu)

圖4 多路徑車(chē)輛調(diào)度網(wǎng)絡(luò)示例

根據(jù)以上情況，對(duì)圖4所示分層調(diào)度網(wǎng)進(jìn)行描述：SD={S1,S2}，其 中 ，S1={s1,sv1,d1,d2,d3}，S2={s2,s3,d4}，PD={P1,P2}其 中 ，P1={p1,p2,p3,p4,p6,p7}，P2={p13,p14,p15}，SH= ,PH={p5,p8,p9,p10,p11,p12,p16,pv1}。

圖4中，車(chē)輛出發(fā)地與目的地之間連接路徑P的鄰接矩陣為：

其中，矩陣中的任一元素pij表示車(chē)輛出發(fā)地si與目的地dj之間的連接路徑集合。

每一條連接路徑的路徑編號(hào)、連接節(jié)點(diǎn)、路徑類(lèi)型及路徑長(zhǎng)度等信息見(jiàn)表1。

上述分層調(diào)度實(shí)例具有多個(gè)結(jié)構(gòu)對(duì)象，其在調(diào)度過(guò)程中的組織結(jié)構(gòu)、元素對(duì)象等也會(huì)發(fā)生變化，在求解這類(lèi)問(wèn)題時(shí)希望能夠得到符合目標(biāo)的最優(yōu)結(jié)果。分層調(diào)度問(wèn)題也可以看作求解最優(yōu)調(diào)度策略問(wèn)題。因此，采用遺傳算法對(duì)分層調(diào)度問(wèn)題實(shí)例進(jìn)行求解，通過(guò)對(duì)初始化種群的評(píng)價(jià)，擇優(yōu)選擇較好的種群進(jìn)行交叉編譯，產(chǎn)生新的種群，然后按照該順序重復(fù)計(jì)算，直至達(dá)到總體收斂條件，求解出最優(yōu)方案。

表1 路徑信息

算法編碼采用(,pm,ts,te)的編碼方式，其中表示車(chē)輛出發(fā)地和目的地，pm為路徑編號(hào)，ts為調(diào)度開(kāi)始時(shí)間，te為調(diào)度結(jié)束時(shí)間；種群規(guī)模為10，以調(diào)度時(shí)間最短為調(diào)度目標(biāo)，因此將調(diào)度時(shí)間作為適應(yīng)度評(píng)價(jià)參數(shù)。設(shè)定基因交叉概率為1，變異概率為0.2，算法最大遺傳次數(shù)為500。

其中，車(chē)輛出發(fā)地儲(chǔ)備的各類(lèi)車(chē)輛數(shù)量與輸出的車(chē)輛數(shù)量情況見(jiàn)表2。

表2 車(chē)輛出發(fā)地車(chē)輛儲(chǔ)備數(shù)量與輸出數(shù)量對(duì)照

目的地對(duì)各類(lèi)車(chē)輛的需求數(shù)量與實(shí)際接收到的各類(lèi)車(chē)輛數(shù)量情況見(jiàn)表3。

表3 目的地對(duì)各類(lèi)車(chē)輛需求數(shù)量與接收到的數(shù)量對(duì)照

從表2和表3可以看出，各出發(fā)地能夠有效地輸出自身儲(chǔ)備的車(chē)輛，且輸出量不大于自身儲(chǔ)備量。而目的地也能及時(shí)接收到其需求的各類(lèi)車(chē)輛，需求被滿(mǎn)足。

通過(guò)上述實(shí)例，本文的多路徑車(chē)輛調(diào)度模型具有有效性，并能夠在原有基礎(chǔ)上通過(guò)引入虛擬節(jié)點(diǎn)、虛擬連接邊等建模元素進(jìn)行擴(kuò)展，同時(shí)能夠很好地應(yīng)用于多層次調(diào)度等實(shí)際問(wèn)題。

1 王旭,葛顯龍,代應(yīng).基于兩階段求解算法的動(dòng)態(tài)車(chē)輛調(diào)度問(wèn)題研究.控制與決策,2012,27(2):175～181

2 唐偉勤,張隱,張敏.大規(guī)模突發(fā)事件應(yīng)急物資調(diào)度中的車(chē)輛路徑問(wèn)題.物流技術(shù),2008,27(12)

3 王曉博,李一軍.多車(chē)場(chǎng)多車(chē)型裝卸混合車(chē)輛路徑問(wèn)題研究.控制與決策,2009,24(12)

4 張景玲,趙燕偉,王海燕.多車(chē)型動(dòng)態(tài)需求車(chē)輛路徑問(wèn)題建模及優(yōu)化.計(jì)算機(jī)集成制造系統(tǒng),2010,16(3)

5 劉芹,史忠科.混合粒子群算法求解交通路網(wǎng)中的車(chē)輛調(diào)度問(wèn)題.控制與決策,2006,21(11)

6 何正文,賈濤,徐渝.基于禁止時(shí)間窗的應(yīng)急物資調(diào)度車(chē)輛路徑問(wèn)題.運(yùn)籌與管理,2009,18(12)

7 王文蕊,吳耀華.考慮變動(dòng)成本的車(chē)輛路徑問(wèn)題建模及求解.計(jì)算機(jī)集成制造系統(tǒng),2014,20(4)

8 何建敏,劉春林.限制期條件下應(yīng)急車(chē)輛調(diào)度問(wèn)題的模糊優(yōu)化方法.控制與決策,2001,16(3)

9 趙燕偉,李川.一種新的求解多目標(biāo)隨機(jī)需求車(chē)輛路徑問(wèn)題的算法.計(jì)算機(jī)集成制造系統(tǒng),2012,18(3)

10 安一帆.應(yīng)急車(chē)輛調(diào)度中的最優(yōu)路徑研究.技術(shù)應(yīng)用,2013(2)

11 Sangheon HAN,Tabata Y.A hybrid genetic algorithm for the vehicle routing problem with controlling lethal gene.Asia Pacific Management Review,2002(7)

12 William Ho,George T S Ho.A hybrid genetic algorithm for the multi-depot vehicle routing problem.Engineering Applications of Artificial Intelligence,2008(2)

13 Ombuki B,Ross B J.Multi-objective genetic algorithms for vehicle routing problem with time windows.Applied Intelligence,2006(1)

14 Jin M Z.Optimal routing of vehicles with communication capabilities in disasters.Comput Manag Sci,2010(7):121～137