基于改進點－弧模型的鐵路網(wǎng)車流徑路優(yōu)化模型研究

高明瑤，石紅國

（西南交通大學 交通運輸與物流學院，四川 成都 611756)

0 引言

車流徑路問題是在給定的路網(wǎng)環(huán)境中，確定各支車流的運行徑路，使車流總走行費用最小的問題，是鐵路網(wǎng)規(guī)劃及鐵路貨物運輸組織的重要工作之一，是車流組織工作的核心內(nèi)容。合理恰當?shù)能嚵鲝铰纺軌虼龠M鐵路生產(chǎn)，提高鐵路運輸部門的效率和效益，對于均衡利用各個車站區(qū)間的能力，降低路網(wǎng)車流運輸費用，提高鐵路運營效益具有重大的意義。

眾多學者對鐵路網(wǎng)車流徑路優(yōu)化進行了很多的研究。例如，紀麗君等[1]建立基于多商品流模型的鐵路網(wǎng)車輛分配和徑路優(yōu)化模型，并以我國東北地區(qū)局部鐵路網(wǎng)為例，驗證了模型的有效性和合理性；農(nóng)靜等[2]將鐵路網(wǎng)車流徑路的優(yōu)化問題分解為離散空間中車流排列優(yōu)化問題和車流排列的評價問題，并將其轉化為旅行商問題，采用遺傳算法求解；林柏梁等[3]通過確定合理路徑集的方法，建立路網(wǎng)車流徑路優(yōu)化0-1 規(guī)劃模型，并采用模擬退火算法求解；施其洲[4]對路網(wǎng)雙向重空車流徑路同時進行優(yōu)化，解決了以往只對重車車流徑路優(yōu)化的問題；王保華等[5]考慮不確定情況下的車流徑路優(yōu)化問題，并提出一種隨機模擬的混合遺傳算法；田亞明等[6]研究了車流分配過程中的不可行流問題，采用虛擬弧計算不可行流；林柏梁等[7]考慮不同種類車流權重的差異，提出帶權重的車流徑路優(yōu)化方法；蘇順虎等[8]以運輸時間最少，運輸距離最短，運輸費用最低為目標構建多目標0-1 規(guī)劃模型，并驗證了該模型的有效性。

既有車流徑路相關研究對節(jié)省運輸費用及運輸時間起到了一定作用，但是仍然存在著一些不足之處，如既有的點－弧模型可能在車流的分配過程中對車流進行了拆分，且無法準確獲取車流徑路。為此，針對點－弧模型的缺陷，遵循車流不拆散原理，在滿足弧的能力約束，節(jié)點流量守恒約束的情況下，以車流總走行費用最小為目標函數(shù)，構建基于改進點－弧模型的鐵路網(wǎng)車輛徑路優(yōu)化模型，為鐵路網(wǎng)車流徑路優(yōu)化提供理論依據(jù)。

1 基于改進點－弧模型的鐵路網(wǎng)車流徑路模型

1.1 問題描述

將鐵路網(wǎng)中的分支點車站和路段抽象為網(wǎng)絡中的節(jié)點和弧，構建包含若干車站和路段的鐵路網(wǎng)絡，則網(wǎng)絡可以描述為G= (V，E，C，W)。其中，G表示整個鐵路網(wǎng)；V表示鐵路網(wǎng)上的車站集合，記為V= {1，2，…，n}，n為車站的數(shù)量；E表示鐵路網(wǎng)中弧的集合，E= {(i，j) |i，j∈V}；C表示鐵路網(wǎng)中路段的能力約束集合，C= {cij，i，j∈V}，cij為從i站到j站的能力約束；W表示表示鐵路網(wǎng)中路段的單位運輸費用集合，W= {wij，i，j∈V}，wij為從i站到j站的單位運輸費用。

考慮基于改進點－弧模型的完整性與簡潔性，提出以下假設：①車流無改編通過途中分支點車站；②車站的接發(fā)能力足夠大；③不考慮車流通過分支點車站的費用；④任意2 個車站之間的車流量已知；⑤同一支車流具有相同的車流徑路，即車流不可拆散。

1.2 基于改進點－弧模型的鐵路網(wǎng)車流徑路優(yōu)化模型構建

點－弧模型是以路網(wǎng)中車站和弧段為研究對象設置變量建立模型的，決策變量是各個弧段上的流量，根據(jù)中間點流入量等于流出量這一基本核心規(guī)律列出約束條件進行求解。由于點－弧模型中決策變量是各個弧上的流量，該流量是多股OD 間的車流量的總和，因而模型結果無法直觀顯示各股車輛的最優(yōu)徑路。

針對既有的點－弧模型的局限性進行改進：①引入0-1 變量，使得車流徑路滿足遵循車流不拆散的基本原理，同時使得優(yōu)化結果能夠體現(xiàn)車流徑路；②結合實際鐵路網(wǎng)中的運輸情況，考慮到各支車流的重要度不同，利用弧段阻尼系數(shù)調節(jié)不同車流的運輸費用，確保重要車流能夠優(yōu)先通過。

在鐵路網(wǎng)中，以總的運輸費用最低為目標，構建基于改進點－弧模型的鐵路網(wǎng)車流徑路模型，即所有實際路段上的車流量與單位運輸費用的乘積與虛擬路段上的車流量與虛擬路段上的單位運輸費用的乘積之和最小，具體如下。

式中：Z為總運輸費用；m，n，i，j為車站；fmn為從m到n的車流；為路段阻尼系數(shù)，表示車流fmn通過路段(i，j)時的阻尼系數(shù)；為0-1 決策變量，若車流fmn經(jīng)過路段(i，j)，則xijmn取值為1，否則為0；M為一個很大的正數(shù)；為OD 對(m，n)之間的虛擬弧對應的指示變量，若該變量取值為1，代表車流fmn為不可行流，只能通過虛擬弧運送至終點，若取值為0，則代表車流fmn為可行流。

公式⑴為目標函數(shù)，表示最小化總運輸費用(加權的廣義費用)；公式 ⑵ 表示弧的能力約束，經(jīng)過弧(i，j)的所有車流量必須小于弧(i，j)的能力；公式 ⑶ 表示節(jié)點流量守恒約束(共同徑路約束)，同一車流fmn對于弧(i，j)，要么全部通過弧(i，j)，即= 1，要么全部不通過弧(i，j)，即= 0，解決了傳統(tǒng)點－弧模型中弧的流量車流歸屬不清的局限性。

1.3 模型求解

基于改進點－弧模型的鐵路網(wǎng)車流徑路優(yōu)化模型中決策變量是，該變量是0-1 變量，因而該模型為0-1 規(guī)劃模型，且該模型的目標函數(shù)和約束條件都是線性的，可采用Lingo 軟件進行求解，求解結果為所有的取值，對照鐵路網(wǎng)中各個車站編號，即可得到各支車流是否通過各條路段，進一步將各支車流的連續(xù)的運行路段相連接，即可得到鐵路網(wǎng)中各支車流的運行徑路。

2 案例分析

以我國東北地區(qū)14 個車站及其弧段構成的局部鐵路網(wǎng)為例，將各個鐵路車站抽象為節(jié)點，將各個路段抽象為弧段采用基于改進點－弧模型的鐵路網(wǎng)車流徑路優(yōu)化模型，路網(wǎng)結構示意圖如圖1 所示。為保證各個弧段都能通行車流，除了實際存在的弧段之外，建立虛擬弧段。

圖1 路網(wǎng)結構示意圖Fig.1 Railway network structure

2.1 基礎數(shù)據(jù)

東北地區(qū)14 個車站之間有部分路段連接，各個路段的單位車流運輸費用和年通過能力存在較大差異，部分路段通過能力較小，因而存在瓶頸路段。路段相關參數(shù)如表1 所示。不可行流的懲罰費用M取值1 000 元/車。

2019 年我國東北地區(qū)部分車站之間的年OD量在5 萬 ～ 90 萬t 之間。2019 年車流的年OD 量如表2 所示。對于部分年OD 量較大的車站，應盡量保證其選擇單位運輸費用較小的路段。在表2 中，OD 序號為1，7，9，11 的車流量較大，為重要車流，應選擇單位運輸費用較小的路段，可令路段阻尼系數(shù)為0.8，即保證重要車流以較低的費用通過弧段。

2.2 模型求解

利用Lingo 軟件對構建的基于改進的點－弧模型的車流徑路優(yōu)化模型進行求解，可以得到車流徑路優(yōu)化方案如表3 所示。

由表3 分析可知，從大安北到梅河口車流的車流徑路為虛擬弧大安北—梅河口，因而該車流為不可行流，從朝陽川到讓湖路最短徑路為朝陽川—吉林北—哈爾濱—讓湖路，但是由于弧段能力限制，需要優(yōu)先保證從朝陽川到白城的重要車流通過，因而從朝陽川到讓湖路車流需要繞行朝陽川—牡丹江—哈爾濱—讓湖路路徑，而從朝陽川到白城的車流徑路是最短徑路。從求解結果可以看出，所有車流都滿足不拆散的基本原理，起訖點相同的一支車流，或共同經(jīng)過某一弧段，或均不經(jīng)過該弧段。

將表3 中各支車流疊加到鐵路網(wǎng)的各個弧段上，匯總得到東北部分鐵路網(wǎng)的路段流量如表4 所示。

表1 路段相關參數(shù)Tab.1 Parameters of sections

表2 2019 年車流的年OD 量Tab.2 OD train flow volume in 2019

表3 車流徑路優(yōu)化方案Tab.3 Train flow route optimization plan

表4 東北部分鐵路網(wǎng)的路段流量Tab.4 Flow of sections in Northeast China’s railway network

根據(jù)模型求解結果，不可行流為大安北到梅河口的車流，其余均為可行流，可行流的廣義運輸費用為6 106 元，不可行流的懲罰費用為80 000 元。模型結果表明，利用基于改進點－弧模型的鐵路網(wǎng)車流徑路模型可以準確快速地計算出可行流與不可行流的數(shù)量與費用，以及各支車流的運行徑路，進一步驗證了基于改進點－弧模型的鐵路網(wǎng)車流徑路模型的合理性與可行性。

3 結束語

車流徑路的確定是鐵路路網(wǎng)規(guī)劃及鐵路貨物運輸組織的重要工作之一，是車流組織工作的核心內(nèi)容。車流徑路優(yōu)化對于降低路網(wǎng)車流運輸費用，提高鐵路運輸部門的效率和效益意義重大。基于改進點－弧模型的鐵路網(wǎng)車流徑路模型，遵循各個車流在運行過程中不拆開的基本原理，能夠準確定位各支車流的運行徑路和不可行流的大小，在現(xiàn)實中具有較強的應用前景，尤其是在鐵路網(wǎng)中各個車流重要度不同，路網(wǎng)瓶頸比較突出時更有效。今后應進一步深入研究在鐵路網(wǎng)規(guī)模過大、基于中間節(jié)點的車流徑路模型會產(chǎn)生過多的變量時的運算效率，以更好地滿足鐵路網(wǎng)車流徑路優(yōu)化需求。