基于最小費用最大流算法的沖突車流分配

李　運，潘應(yīng)久，侯禮興(長安大學(xué)公路學(xué)院，陜西西安　710064)

?

基于最小費用最大流算法的沖突車流分配

李運，潘應(yīng)久，侯禮興
(長安大學(xué)公路學(xué)院，陜西西安710064)

摘要:從最短路徑角度研究交通分配問題，利用Dijkstra算法求解最短路徑，根據(jù)道路容量和運行時間的限制，得出非沖突車流的優(yōu)化路徑，在此基礎(chǔ)上假設(shè)沖突發(fā)生，采用設(shè)置優(yōu)先通行規(guī)則與最小費用最大流算法相結(jié)合，實現(xiàn)有交通沖突情況下的交通流分配。

關(guān)鍵詞:沖突車流;交通分配;最小費用最大流算法; Matlab

交通分配是把各種出行方式的空間O-D( Origin-Destination)分配到具體交通網(wǎng)絡(luò)上。對于交通分配，國內(nèi)外均有較多的研究，數(shù)學(xué)規(guī)劃法、圖論法及計算機(jī)技術(shù)的發(fā)展，為交通分配模型的研制及應(yīng)用提供了堅實的基礎(chǔ)［1］。國際上通常采用平衡和非平衡兩大類方法對交通分配進(jìn)行劃分［2］。在交通規(guī)劃方法相對成熟之后，業(yè)內(nèi)開始把注意力更多的轉(zhuǎn)向交通控制與誘導(dǎo)，由此動態(tài)交通分配( Dynamic Traffic Assignment)誕生［3］。

動態(tài)交通流分配理論從提出至今經(jīng)過了20多年的發(fā)展，在理論研究和方法應(yīng)用上都有一定的進(jìn)步與突破［4］，但仍處于發(fā)展階段，究其根本原因是考慮時間變量因素，建立合適的數(shù)學(xué)模型并設(shè)計相應(yīng)的算法非常困難［5］。沖突車流分配研究同步于動態(tài)分配研究，目前要找到一種解決沖突車流的合適方法仍然是比較困難的。

本文先用Dijkstra算法研究非沖突車流的最短路徑，再根據(jù)最小費用最大流算法得出非沖突車流的分配并考慮多種情況，最后利用設(shè)置優(yōu)先通行規(guī)則與最小費用最大流算法相結(jié)合的方法獲得沖突車流的分配。

1最小費用最大流算法

最小費用最大流問題是經(jīng)濟(jì)學(xué)和管理學(xué)中的一類典型的基本問題［6］。在一個網(wǎng)絡(luò)中每條路徑都存在“容量”和“費用”兩個限制條件，此類問題是想尋找出:車流從A地到B地，選擇合適的路徑及考慮分配路徑的流量，使其能夠在流量最大的前提下，達(dá)到所用的費用最小的要求。假設(shè)n輛卡車要從A地到B地運送物品，由于每條路段都存在不同的收費情況，每條路能容納的車的數(shù)量也有一定限制，最小費用最大流問題指如何分配卡車的出發(fā)路徑可以使費用降到最低，物品又能準(zhǔn)確全部的送達(dá)［7］。物流成本最小問題稱為最小費用流問題，在現(xiàn)實生活中有很多的應(yīng)用，一般把其歸為一類網(wǎng)絡(luò)優(yōu)化問題［8］?？梢园讶萘孔鳛榱?，費用作為時間代價，來研究交通運輸問題。

最小費用最大流算法包含很多經(jīng)典的算法和流程，本文主要采用其中的最大流算法和最小費用最大流對偶算法。

1．1最大流算法流程

1)對網(wǎng)絡(luò)G=［V，E，C，W］，給出流值為零的初始流，其中G［V，E］為具有n個頂點、m條弧的有向圖，V為n個頂點的非空有限集合，E為m條弧的非空有限集合，C為弧容量，W為弧間的費用函數(shù)。

2)作伴隨初始流的增流網(wǎng)絡(luò)G'=［V'，E'，W'］。G'的頂點同G，V' =V(頂點相同)，G'［V'，E'］為增流網(wǎng)絡(luò)的n個頂點、r條弧的有向圖，W'為增流網(wǎng)絡(luò)間的費用函數(shù)。

若G中f( u，ν)＜c( u，ν)，則G'中建邊( u，ν)，w'( u，ν) = w( u，ν)。其中: ( u，ν)為頂點，w( u，ν)、w'(ν，u)分別為對應(yīng)鏈的費用邊權(quán)值，f( u，ν)、c( u，ν)分別為可行流的邊權(quán)值和容量的邊權(quán)值。

若G中f( u，ν)＞0，則G'中建邊(ν，u)，w'(ν，u) =－w( u，ν)。

3)若G'不存在x至y的路徑，則G的流即為最小費用最大流，停止計算;否則用標(biāo)號法( Dijkstra算法)找出x至y的最短路徑P。

4)對P的每條邊( u，ν)，若G存在( u，ν)，則( u，ν)增流;若G存在(ν，u)，則(ν，u)減流。增(減)流后，應(yīng)保證對任一邊有c( e)≥f( e)≥0。其中: c( e)、f( e)分別為該弧的弧容量和弧流量。

5)根據(jù)計算最短路徑時的各頂點的標(biāo)號值L(ν)，修改G所有邊的權(quán)數(shù)w( e)，有L(ν) +w( e)→w( e)。6)將新流視為初始流，轉(zhuǎn)到步驟2)。

1．2最大流最小費用對偶算法流程

1)任意νi∈V，令πi=0;任意(νi，νj)∈E，令fij=0。νi、νj為頂點V集合里的第i和第j個頂點，πi為在i點處構(gòu)造的弧，fij為ij間的可行流。

2)如果ν0=ν( f)，則f是最小費用流，否則轉(zhuǎn)3)。其中:ν0為最大流的流值，ν( f)為可行流的流值。

3)構(gòu)造網(wǎng)絡(luò)G( f，π)，對任意νi∈V，求出G( f，π)中關(guān)于wπ的最短且由νs到νi的權(quán)d( i)，令πi+di= πi。G( f，π)為以f為頂點、π為弧的有向圖，wπ為該鏈的費用，νs、νt為發(fā)點和收點，di為i點對應(yīng)的距離函數(shù)。

4)由新的位勢，修改G( f，π)中的費用wπ，再求出G'( f，π)中的最大流。如果最大流的流值為0，則G'( f，π)中不存在由νs到νt的路，停止，且G中不存在流值為ν0的可行流;否則轉(zhuǎn)入步驟5)。

5)沿著最大流確定的由νs到νt的路對f進(jìn)行增廣，且增廣后的流值不超過ν0，轉(zhuǎn)入步驟2)［9］。

本文研究交通沖突下路徑分配模型，需先研究簡單節(jié)點路網(wǎng)，由于Dijkstra算法具有計算簡單、使用方便等諸多優(yōu)點，且本文主要研究的路網(wǎng)節(jié)點不是很多，所以先采用Dijkstra算法做基本路徑;然后考慮節(jié)點容量和運行時間對路徑的影響，由于最小費用最大流算法能夠?qū)τ腥萘肯拗频穆肪W(wǎng)求解［10］，故選用該算法作為動態(tài)路網(wǎng)優(yōu)化的基本方法。

2非沖突基本路徑分配

2．1 Dijkstra算法下最短路徑

在非沖突情況下，路段上車流可以按照既定的目標(biāo)函數(shù)找到最短的路徑。一般情況下目標(biāo)函數(shù)為實現(xiàn)最短距離、最短時間的函數(shù)。圖1是一個簡單的節(jié)點網(wǎng)，各節(jié)點的權(quán)值為各節(jié)點間的距離。求A到F的最短路徑，可以用Dijkstra算法計算，其中各節(jié)點的權(quán)值作為各節(jié)點的阻抗。經(jīng)過計算得出A→F的最短路徑為: A →C→D→F。如果為其他目標(biāo)函數(shù)，可以根據(jù)各自的目標(biāo)函數(shù)調(diào)整節(jié)點間的權(quán)值，即調(diào)整各節(jié)點阻抗表，然后進(jìn)行計算。

2．2考慮路網(wǎng)間運行時間初始流的路徑分配

實際情況下路網(wǎng)有容量限制，而且也存在費用的問題，采用最小費用最大流算法進(jìn)行路徑分配。解決最小費用最大流問題，一般有兩種方法:

1)先用最大流算法算出最大流，然后根據(jù)邊費用，檢查是否有可能在流量平衡的前提下，通過調(diào)整邊流量，使總費用得以減少［11］。調(diào)整后，得到一個新的最大流，在這個新流的基礎(chǔ)上繼續(xù)檢查，調(diào)整［12］。這樣迭代下去，直至得到最小費用的最大流［13］。這一思路的特點是保持問題的可行性(始終保持最大流)，向最優(yōu)解推進(jìn)。

圖1簡單節(jié)點圖

2)將零流作為初始流，這個流的費用為零，當(dāng)然是最小費用。然后尋找一條源點至匯點的增廣鏈，但要求這條增廣鏈必須是全部增廣鏈中費用最小的1條［14］。如果能找出增廣鏈，則在增廣鏈基礎(chǔ)上增流，得出新流，將這個流看作初始流，繼續(xù)尋找增廣鏈增流。這樣迭代下去，直至迭代完成，找不到增廣鏈時，這時的流即為最小費用最大流。這一算法的特點是保持解的最優(yōu)性(每次得到的新流都是費用最小的流)，而逐漸向可行解接近(可行解是最終得到的最大流)。

本文采用第二種方法，先找到不考慮路網(wǎng)間運行時間的初始流，即采用最大流算法找到最優(yōu)路徑，然后根據(jù)各節(jié)點運行時間來調(diào)整這個最大流，從而實現(xiàn)考慮運行時間時的路徑分配。

3沖突路徑優(yōu)化分配

交通沖突是在道路可觀測條件下，2個或2個以上道路使用者在同一時間、空間上相互接近，如果其中一方采取非常規(guī)交通行為，如轉(zhuǎn)換方向、改變車速、突然停車等，除非另一方也相應(yīng)采取避險行為，否則會發(fā)生碰撞［15］，這一現(xiàn)象就是交通沖突。

在交通實際路網(wǎng)中存在很多交通沖突的情況，如何解決這些交通沖突，具有現(xiàn)實意義。在之前的交通流研究中，只是考慮節(jié)點容量及運行時間，對于交通沖突沒有考慮。根據(jù)交通流知識，在產(chǎn)生交通沖突時，應(yīng)變固定沖突點為隨機(jī)沖突點，減少沖突次數(shù)。制定交通規(guī)則時主要考慮整個系統(tǒng)的優(yōu)化。

1)進(jìn)入沖突點前，平均速度較大的車流優(yōu)先通過，道路容量有剩余時其他車流再通過。速度相同時，優(yōu)先考慮車流大者通行。

2)路途遠(yuǎn)的車流優(yōu)先通過，能使其他車流迅速通過，可以減少延誤，實現(xiàn)整個系統(tǒng)的優(yōu)化。

4　算例

4．1路網(wǎng)簡介

以浙江大學(xué)玉泉校區(qū)到紫金港校區(qū)的交通路網(wǎng)為例進(jìn)行研究，該路網(wǎng)包含了擁擠路段、限制路段、暢行路段，在一定程度上代表一個小型路網(wǎng)系統(tǒng)，該路網(wǎng)有21條包含重要交通點的路段，如圖2所示。把圖2中的21條路段簡化為12個節(jié)點的路段。節(jié)點間的路段長度如圖3所示。

4．2 Dijkstra算法下最短路徑分配結(jié)果

求解圖2中節(jié)點1→12的非沖突情況下最短路徑和最短時間的優(yōu)化路徑。找到最短路徑的節(jié)點，計算節(jié)點1→12的最短路徑。

為了簡便及具有實際效果，采用Matlab編程模擬Dijkstra算法的過程。根據(jù)路段長度，通過Matlab仿真得到節(jié)點1→12的最短路徑為: 1→2→3→5→8→10→11→12。根據(jù)路段長度、路段速度及信號配時，求得節(jié)點間的運行時間，得到最短時間的優(yōu)化路徑為1→2→4→7→8→10→12。根據(jù)調(diào)查數(shù)據(jù)及Matlab仿真，計算結(jié)果如圖4所示。

圖2簡化路段、節(jié)點圖

圖3節(jié)點路段長度圖

圖4基本分配路徑

4．3初始流路徑分配

在實際情況下需要考慮通行能力、道路情況、交通配時及突發(fā)事件應(yīng)急能力等因素，故引進(jìn)路段容量參數(shù)。路段容量就是路段斷面的流量，根據(jù)最大通行能力及路段實際情況得到，表1列出了部分路段的容量參數(shù)。表1中:ρmax為假設(shè)單位密度，pcu/km; q為根據(jù)平均速度vp得到的容量，pcu/h，q=ρmaxvp。

表1部分路段容量參數(shù)

本文假設(shè)車輛到達(dá)是“瞬時、全部”的，例如:節(jié)點A→B有100 pcu/h的車流，那么這100 pcu/h的車流只存在A地或B地，而沒有處于A地與B地之間的路段上。

解決最大流問題時通常需要一個可行流，選擇單車情況下的最短時間路徑。假設(shè)初始流量為60 pcu/h，因最小時間路徑為1→2→4→7→8→10→12，可以發(fā)現(xiàn)節(jié)點2不能滿足道路容量條件，根據(jù)最大流算法對初始流進(jìn)行重新調(diào)整，用Matlab編程來實現(xiàn)對偶算法，計算結(jié)果如圖5所示。由圖5可以看出車流在節(jié)點2分流，在節(jié)點10聚集，能夠使車流達(dá)到最大，基本與非沖突基本路徑中以最短時間為目標(biāo)函數(shù)的路徑重合。

4．4考慮路網(wǎng)間運行時間初始流的路徑分配

圖5初始流分配結(jié)果

實際進(jìn)行初始流路徑分配時還要考慮運行時間因素。采用最大流最小費用算法，其中的費用相當(dāng)于時間代價?？紤]路段時間和容量，對于原始的初始流用最大流最小費用算法，采用對偶法找到最大流最小時間。結(jié)果表明，60 pcu/h車流在考慮時間和容量的情況下，優(yōu)化路徑和非沖突情況下的最短路徑相似，屬于非沖突情況下最短時間和最短路徑的路徑結(jié)合，如圖6所示。

4．5交通沖突下的車流分配

在實際交通路網(wǎng)中存在很多交通沖突的情況，本文作出一種假設(shè)的沖突情況，即由節(jié)點1→12的60 pcu/h車流，與從節(jié)點3→8的80 pcu/h車流沖突，對兩車流的路徑進(jìn)行優(yōu)化。由于圖6的路網(wǎng)是單向圖，從節(jié)點3→8只有一條唯一路徑(可以直觀看出節(jié)點3→8的最優(yōu)路徑是節(jié)點3→5→8)，為了使運算結(jié)果準(zhǔn)確，須增加節(jié)點3→8的路徑選擇且排除明顯會導(dǎo)致運行時間增加的路徑，如9以后的節(jié)點路段，所以把節(jié)點5、6間和8、9間改成雙向圖。各節(jié)點容量如圖7所示。

根據(jù)速度、容量及在發(fā)生沖突下的優(yōu)先權(quán)規(guī)則，通過MATLAB編程，得到兩種路徑及車流分配情況如圖8所示。圖8中實線代表節(jié)點1→12路徑，虛線代表節(jié)點3→8路徑。

圖6考慮各路網(wǎng)間運行時間分配結(jié)果

由圖8可知，節(jié)點1→12和3→8的最優(yōu)路徑在節(jié)點3產(chǎn)生了沖突，由于節(jié)點2→3的平均速度大于節(jié)點3→5的平均速度，優(yōu)先通過節(jié)點1→12的10 pcu/h車流量，于是節(jié)點3→5只能走65 pcu/h，剩下的15 pcu/h流量只能走節(jié)點3→6。到了節(jié)點5，節(jié)點4→5有50 pcu/h流量，而節(jié)點3→5有75 pcu/h流量，所以優(yōu)先保證75 pcu/h的流量，50 pcu/h流量不進(jìn)入節(jié)點5，所以節(jié)點1→12的50 pcu/h車流走節(jié)點4→7。對于混合車流節(jié)點3→5的75 pcu/h，到了節(jié)點5必須分流，因為節(jié)點5→8只有60 pcu/h容量，優(yōu)先保證路途遠(yuǎn)的流量，即優(yōu)先保證節(jié)點1→12的10 pcu/h車流量。節(jié)點3→8的15 pcu/h車流在節(jié)點5走節(jié)點5→6。節(jié)點1 →12的50 pcu/h車流在節(jié)點8與之前的10 pcu/h車流匯合，節(jié)點3→8的30 pcu/h( 15+15)車流在節(jié)點8與之前的50 pcu/h車流共同到達(dá)終點。

圖7交通沖突下的節(jié)點容量

圖8交通沖突下的車流分配結(jié)果

由圖6、8可以看出，節(jié)點1→12車流的路徑在有無沖突下的主要區(qū)別在于其中50 pcu/h這部分車流同另外10 pcu/h車流匯入點的不同，有沖突時避開沖突點(節(jié)點5)，選擇最近的道路(節(jié)點4→7)達(dá)到匯合點8，比較符合實際情況，整個車流運行時間變化不大。而相對于節(jié)點1→12的路徑改變，節(jié)點3→8的路徑變化就大很多了。為了實現(xiàn)整個路網(wǎng)優(yōu)化，增加了節(jié)點3→8間車流的運行時間，其中主要增加了節(jié)點6→9→8( 30 pcu/h)這部分車流的運行時間，但網(wǎng)絡(luò)優(yōu)化后車流的運行時間較優(yōu)化前減少了很多。

5　結(jié)語

1)對于簡單的、負(fù)荷不是很大的交通路網(wǎng)，采用Dijkstra算法進(jìn)行分配得到基本路徑，進(jìn)而考慮節(jié)點運行時間和道路容量進(jìn)行路徑的優(yōu)化。交通沖突情況下，在最小費用最大流算法基礎(chǔ)上，利用計算機(jī)編程以及制定通行規(guī)則實現(xiàn)算法的優(yōu)化，從而更好地處理交通流間的沖突。

2)在實際問題中交通沖突情況涉及到的因素很多，具有隨機(jī)性和復(fù)雜性，本文在建模過程中假設(shè)沖突車流的到達(dá)是“同時、全部”的，但在實際中交通流往往是分時、分段的到達(dá)，在接下來的研究中有待于對所建模型進(jìn)一步完善，以期能更好地提高沖突車流分配結(jié)果的準(zhǔn)確性。

參考文獻(xiàn):

［1］張維全，張寶玉．公路網(wǎng)規(guī)劃中多路徑交通分配模型的計算機(jī)實現(xiàn)［J］．山東交通科技，2005( 4) : 9－13．

［2］黃崇超，劉炳全．非平衡交通分配的幾種新的有效分配算法［C］．武漢: 2005—2006年大城市交通高層學(xué)術(shù)論壇，2006．

［3］楊清華．交通誘導(dǎo)系統(tǒng)的研究［D］．天津:天津大學(xué)，2000．

［4］張曉峰，陳鴻杰，王軍利．淺析交通分配理論［J］．中國人民公安大學(xué)學(xué)報(自然科學(xué)版)，2007，13( 1) : 91－93．

［5］朱軍功．高速公路路網(wǎng)事件的信息發(fā)布及救援策略研究［D］．南京:東南大學(xué)，2006．

［6］田西，壽建敏，施雄彪．我國貨運鐵路擴(kuò)容對煤炭港口吞吐量的影響［J］．中國港口，2011( 5) : 41－44．

［7］沈鑫宇．移動自組網(wǎng)中基于能量的路由協(xié)議研究［D］．杭州:浙江工業(yè)大學(xué)，2011．

［8］張新敬，李剛，邱學(xué)紹，等．最小費用最大流算法實現(xiàn)［J］．鄭州輕工業(yè)學(xué)院學(xué)報(自然科學(xué)版)，2005，20( 3) : 132－134．

［9］白睿．最大流及最小費用研究［D］．南京:南京郵電大學(xué)，2012．

［10］吳群妹．受容量限制的多品種物質(zhì)運輸問題的最小費用最大流算法［J］．常州工學(xué)院學(xué)報，2012，25( 3) : 73－77．

［11］盛鑫芽．ForCES體系結(jié)構(gòu)中流量矩陣建模及其應(yīng)用的研究［D］．杭州:浙江工商大學(xué)，2011．

［12］王勤波．最小費用流問題及其擴(kuò)展［D］．青島:青島大學(xué)，2009．

［13］曹志剛．基于網(wǎng)絡(luò)編碼的無線傳輸優(yōu)化算法［D］．武漢:華中科技大學(xué)，2011．

［14］孟利民，沈鑫宇，周凱，等．基于最小費用最大流的MANET網(wǎng)絡(luò)路由能量控制模型［J］．傳感技術(shù)學(xué)報，2010，23( 4) : 582－586．

［15］黃娟．信號交叉口通行能力分析及軟件設(shè)計［D］．南京:東南大學(xué)，2006．

(責(zé)任編輯:楊秀紅)

Research of Conflict-Flow Distribution Based on Minimum-Cost Maximum-Flow Algorithm

LI Yun，PAN Yingjiu，HOU Lixing
( School of Highway，Changan University，Xi'an 710064，China)

Abstract:This article studies the traffic distribution from the angle of the shortest path selection．Firstly，the minimal path can be found out by using the Dijkstra algorithm．Then the non-conflict traffic optimization path is obtained on the basis of road capacity and the limitation of operation．Finally，under the condition of this conflict assumption，it concludes that the goal of the trip distribution in traffic conflict situations can be achieved by setting priority rules and minimum cost maximum flow algorithm．

Key words:conflict-flow; traffic distribution; minimum-cost maximum-flow algorithm; Matlab

作者簡介:李運( 1990—)，男，內(nèi)蒙古包頭人，碩士研究生，主要研究方向為交通規(guī)劃及交通政策．

收稿日期:2015－03－31

DOI:10．3969/j．issn．1672－0032．2015．02．005

文章編號:1672－0032( 2015) 02－0025－06

文獻(xiàn)標(biāo)志碼:A

中圖分類號:U491．2