李 冰, 徐光蘭, 軒 華

(鄭州大學 管理學院,河南 鄭州 450001)

0 引言

鐵路樞紐系統(tǒng)的貨物流根據(jù)作業(yè)性質可分為中轉流和地方流，而地方流的發(fā)送作業(yè)量往往占據(jù)較大比重。小運轉作業(yè)系統(tǒng)是樞紐內(nèi)本地貨物運轉的主要運輸動力，通過在樞紐內(nèi)開行小運轉列車，將到達編組站的本地作業(yè)車送往公共貨運站或工業(yè)站進行裝卸貨，同時將已完成裝卸的貨車取回至編組站。取送作業(yè)系統(tǒng)在樞紐貨車集結和疏散過程中發(fā)揮著不可替代的作用，直接影響樞紐運送貨物的時效性。

在貨車取送作業(yè)優(yōu)化方面，Jaehn等[1]研究了鐵路專用線取送調(diào)車優(yōu)化問題，構建了取送調(diào)車混合整數(shù)規(guī)劃模型，并設計了多項式時間求解算法。Li等[2]用仿真方法研究了鐵路樹枝形專用線取送車問題。張文晰等[3]針對路企直通列車組織過程中車流整列到發(fā)的取送問題，研究了裝卸區(qū)呈樹枝形布置的取送車優(yōu)化問題。牟峰等[4]以“先順序、后批次”為構造取送車作業(yè)方案的總體思路，設計了取送車作業(yè)問題一般模型解的模塊化構造方法。李冰等[5～7]針對鐵路樞紐地方貨物流的小運轉作業(yè)系統(tǒng)，研究了樹枝形鐵路專用線非直達車流取送問題，并設計了啟發(fā)式求解算法。Bettinelli等[8]研究了城市物流系統(tǒng)中帶客戶和中間設施時間窗要求的多程分離式貨物取送問題，并提出了分支-切割-價格算法。Alyasiry等[9]研究了帶時間窗和后進先出裝載要求的貨物取送問題，并構建了一個松弛網(wǎng)絡流模型，并設計了一個精確求解算法。Zhang等[10]等研究了面向快時尚零售商的多品種貨物同步取送問題，構建了問題模型，并提出了一種元啟發(fā)式算法。Wang等[11]研究了以碳排量最小化為目標的合作綠色取送問題，提出基于合作博弈理論的精確求解策略。Danloup等[12]研究了帶轉運的貨物取送問題，并設計了大規(guī)模鄰域搜索算法和遺傳算法對問題進行求解。Haddad等[13]研究了貨物分批取送問題，并設計了一個局部搜索啟發(fā)式算法。

目前針對鐵路樞紐地方貨物流的取送車問題研究主要集中在放射形和樹枝形專用線網(wǎng)絡，對混合形專用線取送車問題的研究開展較少。本文研究帶能力限制的混合形專用線非直達車流取送問題(Taking-out and placing-in non-through wagons with capacity limited on hybrid siding，簡稱TPNTW&CL-HS)。組建基于貨車在站停留車小時與調(diào)機取送成本之和最小化為目標的數(shù)學規(guī)劃模型，并提出初始取送作業(yè)方案構造-取送作業(yè)方案更新-調(diào)機指派的三階段綜合優(yōu)化策略(Three-stage integrated optimization procedure，簡稱TSIOP)。本文研究對完善服務鐵路樞紐地方貨物流的組織調(diào)度理論方法有重要意義。

1 問題建模

1.1 問題描述

TPNTW&CL-HS定義為混合形專用線網(wǎng)絡中，多趟非直達列車陸續(xù)到達編組站，列車h中各本地作業(yè)車組hci需送往裝卸站i并在裝卸任務完成后取回編組站重新編組發(fā)車。考慮裝卸站裝卸能力、調(diào)機牽引能力、瓶頸區(qū)段能力、調(diào)機日走行時長等能力限制條件及其它可行性約束，以貨車在站停留車小時與調(diào)機取送成本之和最小化為目標，合理安排各調(diào)機取送時機、順序、批次方案。

1.2 符號變量

為構建模型，引入以下參量與變量：

1)集合

D：取送作業(yè)性質集合，記為D={d|d=1,2}，其中d=1表送車，d=2表取車。

R：取送車組集合，記為R={hci|h∈H,c∈C,i∈I}，表示隨貨物列車h到達并前往位于放射枝c中裝卸站i作業(yè)的車組，其中0ci表示放射枝c中裝卸站i的站存車組。

2)參數(shù)

O(hci)：車組hci的貨車編組數(shù)，其中O(0ci)表示開始時車站內(nèi)站存車編組數(shù)。

t1(hci)：車組hci掛運列車最晚編組時刻。

t2(hci)：車組hci裝卸作業(yè)時間。

t(i,j)：裝卸站i到裝卸站j的走行時間。

Q：調(diào)機牽引能力。

T：調(diào)機日走行時長。

Oi：裝卸站i的裝卸能力。

F(i,j)：裝卸站i到j瓶頸區(qū)段通過能力。

α1：調(diào)機的單位分鐘運營成本。

α2：貨車的單位分鐘在站停留空費成本。

3)狀態(tài)變量

t3(hci)：車組hci裝卸作業(yè)完成時刻。

t4(hci)：車組hci取回后待編組時刻。

Zijg：第g批次取送作業(yè)中，調(diào)機途徑裝卸站(i,j)路段時所牽引的貨車總編組數(shù)。

4)決策變量

1.3 模型構建

以在站停留車小時與調(diào)機取送成本之和最小為目標，考慮帶能力限制的混合形專用線非直達車流取送中的實際約束，構建問題模型。

(1)

(11)

目標函數(shù)(1)表示貨車在站停留車小時費用與調(diào)機取送成本之和最?。患s束(2)要求同一車組先送后??；約束(3)要求在一個裝卸站內(nèi)同時作業(yè)的貨車數(shù)量不能超過裝卸站裝卸能力；約束(4)要求相異放射枝上的取送作業(yè)所屬批次不同；約束(5)要求任意路段牽引貨車數(shù)不超過調(diào)機牽引定數(shù)限制；約束(6)要求對于路網(wǎng)中的特殊線路，攜帶貨車數(shù)不超過線路通過能力限制；約束(7)要求車組取回編組站時間不超過所掛運列車最晚編組時間；約束(8)要求調(diào)機m負責的所有批次取送作業(yè)時間之和不超過調(diào)機日走行時長限制；約束(9)要求每批作業(yè)只能由一臺調(diào)機來完成；約束(10)～(11)為變量取值約束。

2 三階段綜合優(yōu)化策略

TPNTW&HCL-HS問題模型為典型的NP問題，利用傳統(tǒng)算法很難求解且效率不高。故設計初始取送作業(yè)方案構造-取送作業(yè)方案更新-調(diào)機指派的三階段綜合優(yōu)化策略。

2.1 基于TPA的初始取送作業(yè)方案構造

基于作業(yè)編碼-順序調(diào)整-批次劃分的初始取送作業(yè)方案生成過程(Three phases approach for operation coding, sequence modification, and batch division，簡稱TPA)，具體步驟如下：

Stage1初始取送作業(yè)順序集合。

Stage1.1取送作業(yè)編碼集合。

Stage1.2基于Randperm函數(shù)的取送作業(yè)順序集合。對作業(yè)編碼集合R利用Randperm函數(shù)生成n個初始取送作業(yè)順序。

Stage2取送作業(yè)順序調(diào)整。要求生成的初始取送作業(yè)順序滿足同一車組先送后取的偏序約束和裝卸能力限制。若不滿足約束，則對相應的作業(yè)執(zhí)行局部調(diào)整，順序互換。

Stage3取送作業(yè)批次劃分。

Stage3.1基于相異放射枝的批次劃分。將取送作業(yè)順序中去往不同放射枝且相鄰的兩項作業(yè)劃入不同取送作業(yè)批次。

Stage3.2基于牽引定數(shù)的批次劃分,若批次g包含某項取送作業(yè)后超過調(diào)機牽引能力，將該項取送作業(yè)劃為不同批次。

Stage3.3基于區(qū)段通過能力的批次劃分,若批次g包含某項取送作業(yè)后超過區(qū)段通過能力。將該項取送作業(yè)劃為不同批次。

Stage3.4基于取回時間窗的批次劃分。假定某項取送作業(yè)為批次g的最后一項作業(yè)，計算批次g中帶時間窗要求的車組取回站內(nèi)的時刻，若不滿足取回時間窗要求，則將該項作業(yè)劃分為下一取送作業(yè)批次。

Stage3.5基于調(diào)機走行時長的批次劃分。假定某項取送作業(yè)為批次g最后一項作業(yè)，判斷第g批次是否滿足走行時長要求，若不滿足則將該項作業(yè)劃分為下一批次。

2.2 基于FPUA的取送作業(yè)方案更新

基于迭代尋優(yōu)思路，設計四階段更新過程(Four phases updating approach，簡稱FPUA)，具體步驟如下：

Stage1初始化設置

Stage2基于L*-L0交叉的取送方案一次更新

Stage3基于L′-lbest交叉的取送方案二次更新

Stage4基于L″自變異的取送方案三次更新

Stage5基于局部搜索的取送方案四次更新

Stage6四階段更新過程中L*和lbest的確定

Stage7輸出最優(yōu)取送作業(yè)方案

輸出第q次迭代得到的最新取送作業(yè)方案集合、狀態(tài)傳遞集合L*和最優(yōu)取送作業(yè)方案lbest。進而依次執(zhí)行四次更新過程，直到迭代次數(shù)達到nMax為止，目標函數(shù)值最小的方案為最優(yōu)取送作業(yè)方案。

2.3 基于批次時間窗-空閑原則-調(diào)機走行的調(diào)機配置

基于批次時間窗-空閑原則-調(diào)機走行的調(diào)機配置過程(engine assignment approach considering batch time, leisure principle, and engine workload，簡稱EAA)具體步驟如下：

Stage1基于發(fā)車時間的取送作業(yè)方案排列

Stage2基于批次時間窗的調(diào)機分派

對批次g=1分配編號為m=1的調(diào)機，再對批次g=2進行調(diào)機分派，此時判斷調(diào)機m=1是否回到編組站，若沒有回到編組站則啟用調(diào)機m=2。

Stage3基于空閑原則的調(diào)機分派

對批次g分派調(diào)機時，優(yōu)先選擇先處于空閑狀態(tài)的調(diào)機負責配送。如對g=4批次配送，假定此時編組站停留的調(diào)機為m=1，m=2，比較兩臺調(diào)機返回編組站時刻，并選擇先返回的調(diào)機負責g=4批次配送。

Stage4基于走行時長的調(diào)機分派

3 實驗驗證及結果分析

3.1 實驗場景

1)混合形專用線網(wǎng)絡

設計由3條放射枝，15個裝卸站組成的混合形專用線網(wǎng)絡，如圖1所示。

混合形專用線網(wǎng)絡中各裝卸站及編組站間的調(diào)機走行時間數(shù)據(jù)如表1所示。

表1 裝卸站間走行時間表(單位：min)

2)樞紐內(nèi)本地作業(yè)車取送信息表

設計實驗時段內(nèi)有4列貨物列車相繼到達編組站，各列車解體后根據(jù)貨車目的裝卸站產(chǎn)生不同車組，包含列車及車組信息的車流及取回時間窗數(shù)據(jù)如表2所示。

表2 樞紐內(nèi)本地作業(yè)車取送信息表

3)裝卸站裝卸能力限制信息表

混合形專用線網(wǎng)絡內(nèi)的15個裝卸站由于專用線有效長度有限，有最大裝卸能力限制。各裝卸站裝卸能力信息如表3所示。

表3 裝卸站裝卸能力限制信息表

4)瓶頸區(qū)段通過能力限制信息表

混合形專用線網(wǎng)絡內(nèi)部分專用線區(qū)段上的車流通過量有限，設計當前路網(wǎng)中共有5條瓶頸區(qū)段有通過能力限制，如表4所示。

表4 瓶頸區(qū)段通過能力限制信息表

3.2 求解過程驗證

在解決優(yōu)化排序問題上，可以采取傳統(tǒng)枚舉法(enumeration method，簡稱EM)，也可以采取智能優(yōu)化算法。智能優(yōu)化算法中，標準遺傳算法GA能夠很好解決此類問題；標準粒子群算法PSO求解速度快、參數(shù)少、具有記憶性，在求解NP問題上具有較大的優(yōu)勢；改進粒子群算法wPSO對于粒子群算法中的慣性權重采取非線性權值遞減策略，在粒子群算法基礎上大幅提高收斂速度。為驗證本文所提出TSIOP方法的高效性，引入EM傳統(tǒng)算法和GA、PSO、wPSO等智能優(yōu)化算法作為對比。

因GA、PSO、wPSO和EM法僅能優(yōu)化取送作業(yè)順序批次，無法進一步完成調(diào)機指派。故均需引入基于批次時間窗-空閑原則-調(diào)機走行的調(diào)機指派過程(EAA)來實現(xiàn)。從而四種對比算法簡寫為GA-EAA、PSO-EAA、wPSO-EAA和EM-EAA。為便于算法表述，四種比對算法分別簡記為A1、A2、A3和A4。算法運行結果如表5所示。

表5 五種算法的計算結果比對

3.3 算法性能評估

針對實驗場景中給出的由3條放射枝、15個裝卸站組成的混合形專用線網(wǎng)絡，分別安排牽引定數(shù)為30輛和40輛的兩種列車編組方案，算法種群規(guī)模分別安排在10和30，從而形成四組實驗，對算法性能進行進一步評估。為避免運行結果的隨機性，所有實驗獨立運行50次，設置智能優(yōu)化算法最大迭代次數(shù)為400，傳統(tǒng)EM-EAA枚舉次數(shù)為智能優(yōu)化算法種群規(guī)?！磷畲蟮螖?shù)。

取平均目標函數(shù)值、平均目標函數(shù)改進率和平均CPU運行時間作為算法性能的衡量標準，結果如表6所示。平均目標函數(shù)值用于衡量算法求解質量，值越小，算法質量越好。TSIOP對其他四種算法的平均目標函數(shù)改進率計算方法為：

β1=(GA-EAA-TSIOP)/TSIOP×100%

β2=(PSO-EAA-TSIOP)/TSIOP×100%

β3=(wPSO-EAA-SIOP)/TSIOP×100%

β4=(EM-EAA-SIOP)/TSIOP×100%

表6 五種算法在三放射枝混合形專用線網(wǎng)絡中的性能測試比對

由表6數(shù)據(jù)可知，TSIOP的CPU耗時要高于其他四種對比算法，但在平均目標函數(shù)值與改進率上表現(xiàn)出明顯的優(yōu)勢。

4 結論

本文研究了一類帶能力限制的混合形專用線非直達車流取送優(yōu)化問題。以在站停留車小時費用和調(diào)機取送成本之和最小化為目標，考慮裝卸站裝卸能力、調(diào)機牽引能力、瓶頸區(qū)段能力、調(diào)機日走行時長等能力限制條件，構建問題模型，并提出三階段綜合優(yōu)化策略。該策略首先利用基于作業(yè)編碼、順序調(diào)整與批次劃分的TPA過程完成初始取送作業(yè)方案生成，進而基于迭代尋優(yōu)思路設計FPUA更新過程完成取送作業(yè)方案的優(yōu)化，最后考慮批次時間窗、空閑原則、調(diào)機走行利用EAA過程完成調(diào)機分配。設計實驗場景，對所提出的算法進行過程驗證。本文研究沒有考慮作業(yè)車在樞紐內(nèi)不同裝卸站間的調(diào)移問題。下一步研究工作將聚焦帶調(diào)移的混合形專用線混合取送優(yōu)化問題。