一類點(diǎn)權(quán)網(wǎng)絡(luò)的最小費(fèi)用流問(wèn)題＊

高明霞 賀國(guó)光

（蘭州交通大學(xué)交通運(yùn)輸學(xué)院1） 蘭州 730070） （天津大學(xué)管理學(xué)院2） 天津 300072）

典型的最小費(fèi)用流問(wèn)題是指在一個(gè)給定的網(wǎng)絡(luò)中求一個(gè)從發(fā)點(diǎn)到收點(diǎn)的流值為某一給定常數(shù)的流，使其費(fèi)用最小［1］.在這個(gè)網(wǎng)絡(luò)中，流量除了滿足節(jié)點(diǎn)的守恒條件之外，其調(diào)整和增加只受邊上容量的限制，對(duì)應(yīng)費(fèi)用也是由各邊費(fèi)用得到，稱這類網(wǎng)絡(luò)為弧權(quán)網(wǎng)絡(luò)，平常所說(shuō)的網(wǎng)絡(luò)皆是指這類弧權(quán)網(wǎng)絡(luò).對(duì)弧權(quán)網(wǎng)絡(luò)中最小費(fèi)用流問(wèn)題的求解已經(jīng)有負(fù)回路算法、最小費(fèi)用路算法和原始對(duì)偶算法等有效算法［2］.

但有些情況下，網(wǎng)絡(luò)流量不但受邊上容量的限制，還取決于其所流經(jīng)的節(jié)點(diǎn)的容量，稱這類網(wǎng)絡(luò)為點(diǎn)權(quán)網(wǎng)絡(luò)［3］，城市道路網(wǎng)就是一類典型的點(diǎn)權(quán)網(wǎng)絡(luò).如果在城市道路網(wǎng)中進(jìn)行目標(biāo)為費(fèi)用最小的物資輸送或車輛調(diào)派，除路段通行能力之外，交叉口尤其是信號(hào)交叉口的通行能力也是限制物資或車輛流量的重要因素，交叉口處產(chǎn)生的費(fèi)用也不能忽略.以往考慮節(jié)點(diǎn)容量的最小費(fèi)用流算法如最小點(diǎn)截割法［3］、連續(xù)時(shí)間網(wǎng)絡(luò)的最小費(fèi)用流算法［4－5］等考慮的都是節(jié)點(diǎn)的總?cè)萘?，即一個(gè)節(jié)點(diǎn)只有一個(gè)容量權(quán)重.而城市道路網(wǎng)中由于信號(hào)配時(shí)等原因，即使是同一個(gè)交叉口，在不同走向（如左轉(zhuǎn)、直行、右轉(zhuǎn)）的通行能力并不相同，經(jīng)過(guò)交叉口j去往下一個(gè)交叉口k的車輛，在j處的延誤和通行能力限制如何，取決于該車是如何到達(dá)j的，上述算法不具有這樣的方向性.

本文將交叉口不同方向的延誤和通行能力作為節(jié)點(diǎn)權(quán)重，建立了包括節(jié)點(diǎn)分方向權(quán)重和弧權(quán)的點(diǎn)權(quán)網(wǎng)絡(luò)來(lái)表示城市道路網(wǎng)，并對(duì)普通網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題的最小費(fèi)用路算法做了改進(jìn)，給出了一個(gè)時(shí)間復(fù)雜性為O（nmf0）的最小費(fèi)用路算法.其中：n，m，f0分別為網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)，邊的條數(shù)和給定起點(diǎn)的流值.求解這類點(diǎn)權(quán)網(wǎng)絡(luò)中的最小費(fèi)用流問(wèn)題，其中費(fèi)用為時(shí)間.

1 算 法

1.1 相關(guān)符號(hào)和變量

用網(wǎng)絡(luò)中的節(jié)點(diǎn)代表交叉口和特定起終點(diǎn)，用弧代表相鄰交叉口之間的路段，將城市道路網(wǎng)表示為有向網(wǎng)絡(luò)G＝（V，A，D，C，T，U）.式中：V＝｛vi，i＝1，2，…，n｝為頂點(diǎn)集合，｜V｜＝n；D＝｛dijk，i，j，k＝1，2，…，n｝為點(diǎn)權(quán)集合，表示由節(jié)點(diǎn)i經(jīng)j至k時(shí)在j處產(chǎn)生的延誤；C＝｛cijk，i，j，k＝1，2，…，n｝為點(diǎn)權(quán)集合，表示由節(jié)點(diǎn)i經(jīng)j至k時(shí)在j處的通行能力；A＝｛（i，j），i，j＝1，2…，n｝為弧集合，｜A｜＝m；T＝｛tij，i，j＝1，2，…，n｝為弧權(quán)集合，表示路段（i，j）的走行時(shí)間；U＝｛uij，i，j＝1，2，…，n｝為弧權(quán)集合，表示路段（i，j）的通行能力；節(jié)點(diǎn)1和n分別為起點(diǎn)和終點(diǎn).

除上面的符號(hào)之外，定義以下符號(hào)和變量：fij為流經(jīng)路段（i，j）的流量；fijk為流經(jīng)節(jié)點(diǎn)j的流中來(lái)自i欲去往k的流量；f0為源點(diǎn)給定的待輸送流量；f，f＊為網(wǎng)絡(luò)當(dāng)前的流及其流量大??；P為流的增廣路或最小費(fèi)用路；p［i］為增廣路或最小費(fèi)用路中節(jié)點(diǎn)i的前一個(gè)節(jié)點(diǎn).

1.2 算法步驟

算法步驟如下.

步驟0 給網(wǎng)絡(luò)一個(gè)初始可行流f（如零流）.

步驟1 構(gòu)造與當(dāng)前流對(duì)應(yīng)的殘量網(wǎng)絡(luò)

步驟2 在殘量網(wǎng)絡(luò)中尋找源點(diǎn)至終點(diǎn)走行時(shí)間最短的路徑P，若不存在這樣的路線，則計(jì)算結(jié)束，網(wǎng)絡(luò)中不存在流值為f0的可行流，否則轉(zhuǎn)步驟3.

步驟3 沿路徑P增廣θ個(gè)單位的流量，其中θ＝min（θ1，θ2，f0－f＊），θ1＝min（uij－fij，cijk－fijk），if（i，j）∈P＋and （j，k）∈P＋，θ2＝min（fjk，fkji）；if（i，j）∈P－and（j，k）∈P－.式中：P＋，P－分別代表路徑P上前向弧和后向弧的集合.

其中步驟2中最短路徑的求解采用標(biāo)號(hào)修正算法逐步逼近最優(yōu)解，定義為第k次檢查標(biāo)號(hào)時(shí)起點(diǎn)1至節(jié)點(diǎn)i的最短走行時(shí)間，算法步驟如下：

1.3 算法時(shí)間復(fù)雜性分析

由以上步驟可知，算法的主要工作量在于連續(xù)地尋找最小費(fèi)用路并增廣，由于每次增廣使得流值至少增加一個(gè)單位，所以步驟1～步驟3最多循環(huán)f0次，所以整個(gè)算法的復(fù)雜性等于O（f0）乘以最短路算法的復(fù)雜性.步驟2中最短路算法的主要工作量在于步驟2.2中方程的循環(huán)迭代，在第k次循環(huán)中，計(jì)算每個(gè)只需檢查節(jié)點(diǎn)j的所有入弧，故步驟2.2的工作量為O（m），總共最多循環(huán)n－1次，所以最短路算法的復(fù)雜性為O（nm）；因此整個(gè)算法的復(fù)雜性為O（nmf0）.

2 算 例

在圖1所示的道路網(wǎng)中，節(jié)點(diǎn)1代表起點(diǎn)，節(jié)點(diǎn)14代表終點(diǎn)，其他節(jié)點(diǎn)代表城市道路網(wǎng)中的交叉口，假設(shè)所有交叉口皆為信號(hào)交叉口，所有路段皆為雙向通行.假設(shè)起點(diǎn)1處有一定數(shù)量的車流要派往終點(diǎn)14，要求車輛總走行時(shí)間最短，派送方案可以通過(guò)求解1至14的最小費(fèi)用流確定.為簡(jiǎn)便起見(jiàn)，算法中只考慮與節(jié)點(diǎn)1至節(jié)點(diǎn)14流量方向一致的走向，為避免殘量網(wǎng)絡(luò)中出現(xiàn)重復(fù)邊，對(duì)2個(gè)走向都與流量走行一致的路段，加入虛擬節(jié)點(diǎn)（圖2中15～20）代表該路段的中點(diǎn)，即路段兩端至虛擬節(jié)點(diǎn)的走行時(shí)間皆為路段走行時(shí)間的一半，則圖1表示的道路網(wǎng)絡(luò)圖簡(jiǎn)化為圖2所示的有向網(wǎng)絡(luò).節(jié)點(diǎn)分方向權(quán)重見(jiàn)表1，網(wǎng)絡(luò)中各弧權(quán)重見(jiàn)表2.

表1 交叉口分方向通行能力與延誤（以cijk和dijk表示）

表2 路段通行能力uij和走行時(shí)間tij

圖1 算例的道路網(wǎng)絡(luò)圖

圖2 由圖1簡(jiǎn)化的有向網(wǎng)絡(luò)

假定節(jié)點(diǎn)1處待調(diào)派的車流量為150pcu／h，運(yùn)用上述算法求解起終點(diǎn)間的最小費(fèi)用流，得到派送路線及相應(yīng)流量和走行時(shí)間如表3所列.

3 結(jié) 論

如果在城市道路網(wǎng)中進(jìn)行車輛調(diào)派或物資輸送，交叉口的通行能力是限制流量的重要因素，交叉口延誤占車輛整體走行時(shí)間的比重也很大，而且這兩項(xiàng)因素具有很強(qiáng)的方向性，以往的最小費(fèi)用流算法不具有這樣的方向性.本文將交叉口不同方向的通行能力和延誤作為節(jié)點(diǎn)權(quán)重建立點(diǎn)權(quán)網(wǎng)絡(luò)，并給出了一個(gè)在這類點(diǎn)權(quán)網(wǎng)絡(luò)中求解最小費(fèi)用流的最小費(fèi)用路算法，算法復(fù)雜性為O（nmf0）.其中：f0是參數(shù)，通常認(rèn)為f0可取到最大流流值，所以該算法不是多項(xiàng)式算法.不過(guò)在此基礎(chǔ)上通過(guò)一定的變尺度技術(shù)，可以得到該類問(wèn)題的多項(xiàng)式算法，具體的變尺度方法可參考文獻(xiàn)［6］.其中交叉口延誤可以利用流量數(shù)據(jù)根據(jù)Webster公式等計(jì)算［7］，交叉口不同方向的通行能力可以根據(jù)飽和流率等模型計(jì)算［8］.

表3 車輛調(diào)派路線及相應(yīng)的走行時(shí)間和流量

［1］謝金星，刑文訓(xùn).網(wǎng)絡(luò)優(yōu)化［M］.北京：清華大學(xué)出版社，2000.

［2］謝 政.網(wǎng)絡(luò)算法與復(fù)雜性理論［M］.長(zhǎng)沙：國(guó)防科技大學(xué)出版社，2003.

［3］吳文瀧.圖論基礎(chǔ)及應(yīng)用［M］.北京：中國(guó)鐵道出版社，1994.

［4］Anderson E J，Nash P，Philpott A B.A class of continuous network flow problems［J］.Math.Oper.Res.，1982，7：501－514.

［5］董振寧，孔淑蘭.連續(xù)時(shí)間網(wǎng)絡(luò)上的最小費(fèi)用流問(wèn)題［J］.山東大學(xué)學(xué)報(bào)：理學(xué)版，2003，38（2）：50－54.

［6］Ahuja R K，Magnanti T L，Orlin J B.Network flows：theory，algorithms，and applications［M］.Eng1ewood Cliffs，New Jersey：Prentice Hall，1993.

［7］王殿海.交通流理論［M］.北京：人民交通出版社，2002.

［8］任福田.道路通行能力手冊(cè)［M］.北京：中國(guó)建筑工業(yè)出版社，1991.