面向智能交通的多路徑調度網絡模型解析
2014-12-31 12:50:12秦維洋
電信科學 2014年11期
秦維洋
（中國電信股份有限公司上海研究院 上海 200122）
1 車輛調度網絡的現狀
在現實世界，車輛調度是解決突發事件、應急事件等問題的重要研究課題，在智能交通領域更是研究的熱點。目前，國內外諸多專家學者紛紛對車輛調度問題進行研究。
王旭[1]等人通過分析調度問題的需求信息提出順序，將動態調度問題等效為不同時刻的靜態調度，并建立了基于時間軸的動態調度模型，設計了“初始優化階段+實時優化階段”的分段求解策略；唐偉勤[2]等人通過對應急車輛調度路徑的研究，以調度所花費時間的均衡性為目標建立了調度模型，并結合實例改進了最近搜索法；王曉博[3]等人建立了多車型、多車場的混合車輛導讀模型，運用混合遺傳啟發式算法對車輛調度問題進行求解；張景玲[4]等人考慮了物流配送中需求的動態變化、車型、路線等，建立了數學規劃調度模型，制定了預優化路徑調度和實時調度策略，提出了2-OPT優化方法，提高了算法的收斂速度；劉芹[5]等人基于實際交通狀況提出了改進的車輛調度模型，并運用粒子群算法和模擬退火算法混合求解了調度問題；何正文[6]等人基于禁止時間窗的應急物資調度問題，通過整數規劃優化了調度模型，并定義了相關決策變量，對路徑的節點和支線進行選擇；王文蕊[7]等人從實際配送中變化的訂貨量出發，提出了變動成本概念，引入預優化策略，建立了能夠根據訂貨量變化實時調整的兩階段數學模型，并采用粒子群算法求解調度模型，驗證了兩階段模型的有效性；何建敏[8]等人基于調度問題中的時間緊迫性與車輛出發地數目相互矛盾的目標，運用模糊優化方法研究了限制期下的多出救點組合模型；趙燕偉[9]等人通過建立基于模糊滿意度的多目標數學規劃模型來優化車輛調度問題，提出利用分段優化的方法求解Pareto解，并為保持Pareto解的分散性，提出了一種自適應網格算子；安一帆[10]結合道路交通情況，建立了包含時間影響因素的結構模型，從而實現調度時間的優化。
Sangheon HAN[11]等人考慮到利用遺傳算法計算車輛調度問題的收斂速度，提出了一種結合遺傳算法與其他啟發式算法的混合算法來解決車輛調度問題；William Ho[12]等人為解決多車場多路徑的調度問題，提出了一種混合遺傳算法，并驗證了算法的有效性；Ombuki B[13]等人用遺傳算法求解多目標調度問題，考慮了車輛數量和距離成本，從兩個維度驗證了算法的可靠性；Jin M Z[14]等人提出了一種時延最小的數學規劃模型，并通過線性規劃提高了模型的性能指標。
上述研究內容包含大量車輛調度問題的研究成果及應用，為多路徑車輛調度問題的動態描述和求解提供了很好的思路，對建立和完善多路徑車輛調度模型有很好的借鑒意義。
2 多路徑調度網絡建模
2.1 多路徑調度網絡的定義
在智能交通領域，多路徑的車輛調度網絡是一個由車輛出發地（S）、目的地（D）和連接路徑（P）組成的網絡。在復雜的多路徑調度網中，調度目的地是構建車輛調度網絡的誘因，也是車輛調度系統建模的首要元素，在調度過程中提出調度需求的類型、數量、時間等；車輛出發地是構建車輛調度網絡的必備條件，是建模的重要元素，必須具備一定數量相同類型或不同類型的車輛，能夠為車輛調度提供一定類型、數量的有效車輛；連接路徑是網絡中車輛進行有效調度的激活條件，是車輛出發地和目的地之間建立聯系的必要元素，只有兩者存在有效連接，車輛的調度需求才能得到滿足。
在實際的調度網絡中，車輛調度是一個實時的動態過程，調度目標有可能會發生改變，導致車輛數量增減、調度目的地變更等。如在調度中，由于天氣、人為等因素的影響，調度策略需要做出修改和調整，可能出現已經出發的車輛雖然未到達目的地，但需要執行新的調度方案，原來未建立有效連接路徑的兩點間可以直接連接或通過間接路徑連接。此時，原有模型中的節點、連接路徑不能很好地體現此時調度網絡的實際特征和性質。因此，模型中還應包含表征多路徑、多類型車輛、多目的地以及動態因素的建模元素。
本文引入虛擬節點和虛擬路徑的概念對調度過程中的動態特征進行描述，并給出多路徑車輛調度網的形式化定義。多路徑車輛調度網是一個滿足如下條件的六元組N=(S,Sv,D,P,Pv,M)：
·S={s1,s2,…}是一個有限的車輛出發地集合，其中S≠；
·Sv={sv1,sv2,…}是一個有限的車輛出發地集合，其中Sv可以為空；
·Dv={dv1,dv2,…}是一個有限的目的地集合，其中Dv可以為空；
·P={p1,p2,…}是一個有限的連接路徑集合，其中P≠且P是((S∪Sv)∪D)×((S∪Sv)∪D)的多重子集；
·Pv={pv1,pv2,…}是一個有限的連接路徑集合，其中Pv可以為空；
·M:P∪Pv→{(a,b)|a∈(S∪Sv)∪D,b∈(S∪Sv)∪D,a≠b}是連接路徑P∪Pv到無序積((S∪Sv)∪D)&((S∪Sv)∪D)的映射，表示車輛出發地與目的地之間的連接關系；
· 存在M(pi)=(a,b)，M(pj)=(a,b)，其中a∈((S∪Sv)∪D),b∈((S∪Sv)∪D)，且a≠b，表示網絡中兩點間存在多條路徑；
·dom(P)∪cod(P)=(S∪Sv)∪D，其中dom(P)={a|堝b:(a,b)∈P}，cod(P)={b|堝a:(a,b)∈P}。
上述定義中S和D分別代表車輛出發地、目的地，是網絡的基本元素。其中S≠ 、D≠ 表示在調度網絡中至少存在一個車輛出發地和一個目的地，同時P≠ 是((S∪Sv)∪D)×((S∪Sv)∪D)的子集，表示網絡中不存在獨立的出發地或目 的地，M(p)=(a,b)，a∈(S∪D)，b∈(S∪D)，a≠b,p∈P，表示網絡中沒有無意義的自環。M是網絡中任意兩點間的映射，對于M(pi)=(a,b)，M(pj)=(a,b)，若M(pi)≠M(pj)，表示網絡中兩點間存在的多條路徑中，包含的映射函數是不同的；若M(pi)=M(pj)，表示網絡中兩點間存在的多條路徑，包含的映射函數是相同的。若Sv≠ ，Dv≠ ，則調度網絡表示最基本的車輛調度網絡。
2.2 多路徑調度網絡結構
節點和路徑是多路徑調度網絡中重要的組成元素，而網絡中很多結構特性也是通過節點、路徑的種類和連接關系來反映的。下面從節點和路徑兩個角度分析多路徑調度網絡結構特征。
（1）路徑角度
路徑表示節點間復雜的關聯關系，在不同的網絡中，路徑也會根據連接關系、限制條件等因素劃分為不同的類型，如多路徑調度網絡中的路徑可以分為公路、鐵路、水路、航空線路等類型。
如圖1所示，多路徑調度網絡的連接路徑包含兩種情況。
· 如圖1（a）所示，網絡中只有一種類型的路徑，即網絡中任意兩個節點的連接路徑只有單一類型，包含出發地之間和目的地之間，是車輛調度網絡中一種基本的結構類型。
· 如果1（b）所示，網絡中存在多種類型的連接路徑。對于網絡中任意兩個關聯節點可能包含兩種情況：兩節點間有多重連接路徑，但每兩個節點間的路徑只有一種類型；兩節點間有多重連接路徑，兩節點間連接路徑的類型也不相同。
圖1 多路徑調度網絡的連接路徑
（2）節點角度
多路徑調度網絡中節點的度表示與該節點連接的連接路徑數量，也是網絡結構特征的基本參數。如圖2所示，當節點入度為0、出度不為0時，表示該節點在網絡中僅作為車輛出發地，如節點s3；當節點入度不為0、出度為0時，表示該節點在網絡中僅作為目的地，如節點d4；當節點入度和出度均不為0時，表示該節點有可能同時作為車輛出發地和目的地，如節點d5。
圖2 調度網絡中節點的度
在實際的多路徑調度網絡中，連接路徑通常無指定方向，以節點的度作為參考對象，可將連接路徑看成一條雙向的連接路徑，如路徑p6。
3 分層調度網絡建模
在多路徑車輛調度問題中，由于調度優先級等原因，網絡結構會呈現出一定的層次性，不同層次的網絡結構體現了節點、連接路徑及網絡結構的層次性。分層調度網絡是一個滿足如下條件的六元組N=（SD，PD，SH，PH，FPD，FPH）：
·SD是一個有限的多層次節點的集合，SD={S1,S2,…}，其中，Si={si1,si2,…}，i=1,2,…，表示第i層內的節點(|SD|≥2，Si≠ ，i=1,2,…)；
·PD是一個有限的連接同層節點的連接路徑集合，PD={P1,P2,…}，其中，Pi={pi1,pi2,…}，i=1,2,…，表示第i層內連接節點的連接路徑(|PD|≥2，Pi≠ ，i=1,2,… )；
·SH是一個有限的分層網絡間節點的集合；
·PH是一個有限的分層網絡間的連接路徑集合；
·:PD→{(x,y)|x,y∈Si,x≠y,Si哿SD}，表示同層連接路徑PD到無序積SD&SD（不包含自環）的映射；
·:PH→{(x,y)|x∈Si,y∈Sj,x≠y,i≠j,Si哿SD,Sj哿SD}，表示跨層連接路徑PH到無序積SD&SD（不包含自環）的映射。
在分層網中，節點分為多個層次，連接路徑也相應地分為同層連接和層間連接，同層節點之間按照同層連接規則由同層連接路徑進行連接，跨層節點之間的連接關系則由層間連接規則確定。
分層調度網絡也具有一定的結構特征，本文定義變量如下：
·HS(S)={hs1,hs2,…}，表示分層網絡中節點所屬的層次集，HS≥1；
·fhs:S→HS(S)，表示節點到節點所屬層次的劃分函數；
· ω(si)=fhs(si)，表示節點所屬的層次，ω(si)∈HS；
·HP(P)={hp1,hp2,…}，表示分層網絡中連接路徑所屬的層次集，HP≥1；
·fhp:P→HP(P)，表示連接路徑到連接路徑所屬層次的劃分函數；
· ω(pi)=fhp(pi)，表示連接路徑所屬的層次，ω(pi)∈HP。
在分層調度網絡中，任意兩個節點間存在層次差，用DHS(si,sj)=ω(si)-ω(sj)表示。若DHS(si,sj)>0，即 ω(si)>ω(sj)，則表示節點si所屬的層次大于節點sj所屬的層次；若DHS(si,sj)<0，即ω(si)<ω(sj)，則表示節點si所屬的層次小于節點sj所屬的層次；若DHS(si,sj)=0，即 ω(si)=ω(sj)，則表示節點si與節點sj屬同一層次；若DHS(si,sj)=1，表示兩節點是鄰層節點；若DHS(si,sj)>1，表示兩節點是跨層節點。
同理，分層調度網絡中的連接路徑也存在上述情況，用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)}，表示節點si的鄰接節點集合；VadS(si)={uj|uj∈Vad(si),ω(uj)=ω(si)}，表示節點si的處于同層的鄰接節點集；VadD(si)={uj|uj∈Vad(si),ω(uj)≠ω(si)}，表示節點si的處于不同層的鄰接節點集。其中，Vad(si)=VadS(si)∪VadD(si)。
（1）從鄰接節點數量分析
·當存在|VadS(si)|=1時，表示節點si只與同層次中的一個節點連接。
·當存在|VadS(si)|>1時，表示節點si與同層次中的多個節點連接。
·當存在|VadD(si)|=1時，表示節點si只與其他層次中的一個節點連接。
·當存在|VadD(si)|>1時，表示節點si與其他層次中的多個節點連接。
（2）從鄰接節點層次差分析
在同層鄰接節點集VadS(si)中，DHS(si,uj)=0。
在不同層鄰接節點集VadD(si)中，若DHS(si,uj)=1，表示在不同層鄰接節點集中存在與節點si連接的鄰層節點；若DHS(si,uj)>1，表示在不同層鄰接節點集中存在與節點si連接的跨層節點。
圖3為一個分層調度網絡結構，該分層調度網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中可以看出，第一層網絡中存在兩種類型的節點，單一類型的連接路徑；第二層網絡中存在兩種類型的節點，3種類型的連接路徑；第三層分層網中存在兩種類型的節點，單一類型的連接路徑。
（1）從節點的角度分析
對于節點s1，其鄰接節點集為Vad(s1)={d1,d4,s6,d6}，同層的鄰接節點集VadS(s1)={d1}，不同層的鄰接節點集VadS(s1)={d4,s6,d6}。其中，DHS(s1,d1)=0，表示節點s1與節點d1為同層節點且兩節點為不同類型；|VadS(s1)|=1，表示節點s1只與同層次中的一個節點連接。|VadD(s1)|=3，表示節點s1與其他層次中的多個節點連接。DHS(d4,s1)=0表示節點s1與節點d4為鄰層連接節點，且兩節點為不同類型；DHS(s6,s1)=DHV(d6,s1)=2表示節點s1與節點s6、d6為跨層鄰接節點。
（2）從連接路徑的角度分析
圖3中分層調度網絡存在不同類型的層間連接路徑。對于層間連接路徑p20，其兩個節點為不同類型的鄰層連接節點；對于層間連接路徑p18，其連接的兩個節點為不同類型的跨層連接節點。
4 多路徑調度網絡實例求解
圖4為某一多路徑車輛調度網絡。已知網絡中有3個車輛出發地，4個車輛目的地，按照實際調度情況及調度優先級對該調度網進行分層，包括第一層和第二層。出發地和目的地之間存在高速公路、一般公路、鐵路、水路4種連接路徑，對應的運輸工具包括大貨車、小貨車、火車、輪船4類。為了提高調度的響應效率，以調度時間最短為目標。由于在車輛調度過程中調度策略發生變化，引入了虛擬車輛出發地和虛擬連接路徑來完善該分層調度網絡。
圖3 分層調度網絡結構
圖4 多路徑車輛調度網絡示例
根據以上情況，對圖4所示分層調度網進行描述：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中，車輛出發地與目的地之間連接路徑P的鄰接矩陣為：
其中，矩陣中的任一元素pij表示車輛出發地si與目的地dj之間的連接路徑集合。
每一條連接路徑的路徑編號、連接節點、路徑類型及路徑長度等信息見表1。
上述分層調度實例具有多個結構對象，其在調度過程中的組織結構、元素對象等也會發生變化，在求解這類問題時希望能夠得到符合目標的最優結果。分層調度問題也可以看作求解最優調度策略問題。因此，采用遺傳算法對分層調度問題實例進行求解，通過對初始化種群的評價，擇優選擇較好的種群進行交叉編譯，產生新的種群，然后按照該順序重復計算，直至達到總體收斂條件，求解出最優方案。
表1 路徑信息
算法編碼采用(
其中，車輛出發地儲備的各類車輛數量與輸出的車輛數量情況見表2。
表2 車輛出發地車輛儲備數量與輸出數量對照
目的地對各類車輛的需求數量與實際接收到的各類車輛數量情況見表3。
表3 目的地對各類車輛需求數量與接收到的數量對照
從表2和表3可以看出，各出發地能夠有效地輸出自身儲備的車輛，且輸出量不大于自身儲備量。而目的地也能及時接收到其需求的各類車輛，需求被滿足。
通過上述實例，本文的多路徑車輛調度模型具有有效性，并能夠在原有基礎上通過引入虛擬節點、虛擬連接邊等建模元素進行擴展，同時能夠很好地應用于多層次調度等實際問題。
1 王旭,葛顯龍,代應.基于兩階段求解算法的動態車輛調度問題研究.控制與決策,2012,27(2):175～181
2 唐偉勤,張隱,張敏.大規模突發事件應急物資調度中的車輛路徑問題.物流技術,2008,27(12)
3 王曉博,李一軍.多車場多車型裝卸混合車輛路徑問題研究.控制與決策,2009,24(12)
4 張景玲,趙燕偉,王海燕.多車型動態需求車輛路徑問題建模及優化.計算機集成制造系統,2010,16(3)
5 劉芹,史忠科.混合粒子群算法求解交通路網中的車輛調度問題.控制與決策,2006,21(11)
6 何正文,賈濤,徐渝.基于禁止時間窗的應急物資調度車輛路徑問題.運籌與管理,2009,18(12)
7 王文蕊,吳耀華.考慮變動成本的車輛路徑問題建模及求解.計算機集成制造系統,2014,20(4)
8 何建敏,劉春林.限制期條件下應急車輛調度問題的模糊優化方法.控制與決策,2001,16(3)
9 趙燕偉,李川.一種新的求解多目標隨機需求車輛路徑問題的算法.計算機集成制造系統,2012,18(3)
10 安一帆.應急車輛調度中的最優路徑研究.技術應用,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
