帶能力限制的混合形專用線非直達(dá)車流取送問題優(yōu)化

李 冰, 徐光蘭, 軒 華

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

0 引言

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

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

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

1 問題建模

1.1 問題描述

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

1.2 符號(hào)變量

為構(gòu)建模型，引入以下參量與變量：

1)集合

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

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

2)參數(shù)

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

t1(hci)：車組hci掛運(yùn)列車最晚編組時(shí)刻。

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

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

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

T：調(diào)機(jī)日走行時(shí)長。

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

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

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

α2：貨車的單位分鐘在站停留空費(fèi)成本。

3)狀態(tài)變量

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

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

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

4)決策變量

1.3 模型構(gòu)建

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

(1)

(11)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Stage1初始化設(shè)置

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。進(jìn)而依次執(zhí)行四次更新過程，直到迭代次數(shù)達(dá)到nMax為止，目標(biāo)函數(shù)值最小的方案為最優(yōu)取送作業(yè)方案。

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

3.1 實(shí)驗(yàn)場(chǎng)景

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 求解過程驗(yàn)證

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

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

表5 五種算法的計(jì)算結(jié)果比對(duì)

3.3 算法性能評(píng)估

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

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

β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)絡(luò)中的性能測(cè)試比對(duì)

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

4 結(jié)論

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