重載鐵路智慧港口站作業(yè)計劃綜合優(yōu)化模型及算法研究

吳藝迪，何世偉*,b，周漢

(北京交通大學(xué)，a.交通運輸學(xué)院；b.綜合交通運輸大數(shù)據(jù)應(yīng)用技術(shù)交通運輸行業(yè)重點實驗室，北京 100044)

0 引言

隨著綜合交通運輸體系的蓬勃發(fā)展，鐵水聯(lián)運憑借其運量大、成本低及污染小等特點，逐步成為多式聯(lián)運的發(fā)展重點。與此同時，信息技術(shù)的創(chuàng)新融合促使港口站數(shù)字化和智能化轉(zhuǎn)型升級，包括智能調(diào)度與控制系統(tǒng)的研發(fā)，調(diào)車機自動駕駛技術(shù)及翻車機無人化操作等智能化手段為鐵水聯(lián)運提供良好保障。2023 年，交通運輸部等印發(fā)《推進鐵水聯(lián)運高質(zhì)量發(fā)展行動方案(2023—2025 年)》中指出：加強大宗貨物鐵路運輸骨干通道與港口集疏運體系規(guī)劃建設(shè)，推動鐵路運輸網(wǎng)絡(luò)和水運網(wǎng)絡(luò)的高效銜接。可以看出，為滿足大宗貨物的鐵水聯(lián)運需求，重載鐵路卸車端智慧港口站的運輸組織水平是推動鐵水聯(lián)運高質(zhì)量發(fā)展的前提和重點。因此，統(tǒng)籌考慮港口站的作業(yè)組織和設(shè)備資源，綜合編制港口站作業(yè)計劃及卸車調(diào)度計劃可以極大提高智能化作業(yè)水平，提升聯(lián)運的綜合運輸效率。

重載鐵路港口站作為鐵路與港口之間的銜接樞紐，承擔(dān)著重車卸車和空車返程排空等任務(wù)。港口站作業(yè)計劃的綜合編制是重載鐵路卸車端作業(yè)計劃和港口卸車計劃的聯(lián)合優(yōu)化問題。目前，已有國內(nèi)外學(xué)者分別針對重載鐵路裝卸端作業(yè)計劃編制問題和港口站卸車調(diào)度問題進行了研究。張進川等[1]根據(jù)重載鐵路空車回送特點，考慮列車組合分解作業(yè)與線路能力的關(guān)系，構(gòu)建空車回送模型，并用網(wǎng)絡(luò)流算法求解。BEKTAS等[2]為減少空車在編組站的停留時間，設(shè)計動態(tài)規(guī)劃算法實現(xiàn)空車的動態(tài)分配。王典等[3]考慮重載裝車端編組站出發(fā)列車編組和追蹤間隔的實際要求，以車輛在本站和前方相鄰站作業(yè)時間最小為目標(biāo)，構(gòu)建多目標(biāo)混合整數(shù)線性規(guī)劃模型，并提出增廣ε-約束法進行求解。梁紫玥等[4]分析重載列車技術(shù)站內(nèi)作業(yè)流程和特點，同時，研究出發(fā)列車追蹤策略和接發(fā)車進路對車站作業(yè)的影響，采用細菌覓食-離散粒子群算法求解列車站內(nèi)組合策略。童瑞詠等[5]針對重載回程運輸運力浪費的問題，以收益最大和碳減排率最高為目標(biāo)，采用非支配排序遺傳算法(NSGA-Ⅱ)優(yōu)化運輸組織方案與定價。徐禾穎等[6]研究重載鐵路裝車端空車調(diào)配與重車列運輸組織的影響，優(yōu)化裝車端空車調(diào)配方案。CHEN等[7]對集裝箱港站的岸橋、堆場集卡及場橋進行聯(lián)合調(diào)度優(yōu)化，考慮了作業(yè)優(yōu)先級和設(shè)備阻塞約束。袁芳[8]將港口煤炭卸車調(diào)度與車間作業(yè)調(diào)度進行類比，基于調(diào)度問題特點運用改進蟻群算法求解。SKINNER 等[9]利用改進的遺傳算法求解碼頭集裝箱轉(zhuǎn)運調(diào)度問題。張建等[10]構(gòu)建翻車機對位卸車模型并運用于柳村南站，計算結(jié)果表明，車站卸車效率得到提升。劉文遠等[11]綜合考慮卸車調(diào)度系統(tǒng)中列車-翻車機-堆場的作業(yè)流程與匹配關(guān)系，為卸車聯(lián)合調(diào)度提供優(yōu)化方案。邰世文等[12]在卸車調(diào)度模型中增加設(shè)備可達性限制和設(shè)備作業(yè)流程不沖突約束。李長安等[13]提出一種基于改進樽海鞘群優(yōu)化算法，可以加快港口卸車調(diào)度問題求解的收斂速度。劉文茜等[14]分析海鐵聯(lián)運集裝箱港口鐵路作業(yè)區(qū)與堆場的協(xié)同作業(yè)流程，提出混合裝卸模式下港口設(shè)備協(xié)同調(diào)度方法。

綜上所述，既有文獻中多注重于重載鐵路車流組織優(yōu)化，或是裝車域的車流調(diào)配方案，卸車端集中于對集裝箱港站的作業(yè)優(yōu)化。有關(guān)以重載鐵路煤炭卸車端為背景的港口站作業(yè)計劃綜合優(yōu)化的研究較少，其中，有部分研究僅針對卸車計劃優(yōu)化，在問題描述中未結(jié)合重載鐵路運輸組織特點以及卸車端港口站生產(chǎn)作業(yè)實際，在模型的構(gòu)建中缺少對車站設(shè)備資源，例如，調(diào)機、本務(wù)機及翻車機的綜合調(diào)度優(yōu)化。基于此，本文結(jié)合重載鐵路列車開行特點，充分考慮港口站實際作業(yè)流程約束，研究本務(wù)機擔(dān)當(dāng)調(diào)機運用模式下港口站作業(yè)計劃中列車分解計劃、卸車計劃、調(diào)車作業(yè)計劃及列車組合計劃的綜合編制問題，以車輛在港口站停留時間最小為目標(biāo)，構(gòu)建混合整數(shù)線性規(guī)劃模型，并設(shè)計帶有自適應(yīng)鄰域搜索的微進化算法，求解港口站作業(yè)設(shè)備協(xié)同調(diào)度方案。

1 問題描述

重載鐵路港口站位于重載鐵路卸車端，其主要目的是將列車上的貨物通過翻卸和運輸設(shè)備傳送至港口堆場。站內(nèi)鐵路調(diào)度部門需要按照港口部門的需求，通過對車站資源的合理分配以及設(shè)施設(shè)備的協(xié)同調(diào)度，按時完成卸車作業(yè)的同時加快組織空車排空任務(wù)。

重載鐵路港口站技術(shù)作業(yè)過程不同于傳統(tǒng)技術(shù)站，作業(yè)流程大致可以概括為“到、解、卸、清、組、發(fā)”，具體作業(yè)順序為重載列車到達港口站，進行技術(shù)檢查及分解作業(yè)，隨后，將分解后的列車牽引至翻車機房開始卸車作業(yè)，卸車完畢后，進行清煤以及空車組合作業(yè)，最后，是出發(fā)技術(shù)檢查和發(fā)車作業(yè)。隨著重載鐵路運量不斷提升，相應(yīng)線路和車站均進行擴能改造，與此同時，港口站翻卸設(shè)備的升級和集疏運設(shè)備的完善，為加快卸車端作業(yè)效率創(chuàng)造有利條件。本文考慮運輸大宗散貨的重載鐵路，例如，重載煤運通道卸車端港口站作業(yè)組織的實際問題，該港口站配備貫通式小翻車機卸車系統(tǒng)和環(huán)形大翻車機卸車系統(tǒng)。卸車線形式及翻車機類型如表1 所示，其中，大型翻車機負責(zé)萬噸列車的卸車，小型翻車機負責(zé)小列車，即5000 t列車的卸車，并且大型翻車機的卸車效率是小型翻車機的兩倍。下面按照港口站本務(wù)機擔(dān)當(dāng)調(diào)機運用模式下列車具體作業(yè)流程，對本文研究的具有大小兩套卸車系統(tǒng)的重載鐵路港口站作業(yè)組織模式進行說明。

港口站到達重載列車按編組類型可分為5000 t列車、1萬t列車、1.6萬t列車和2萬t列車。港口站首先需要對到達技術(shù)檢查完畢的列車制定分解計劃，目的是將重載列車分解為與翻車機適配的小列車或萬噸列車。由于翻車機類型以及卸車工藝流程不同，不同編組類型的重載列車對應(yīng)不同的分解方案，如表2 所示，其中，5000 t 列車不需要分解，1萬t列車和1.6萬t列車分別有兩種分解方案，2萬t列車有3種分解方案。分解作業(yè)結(jié)束后，需確定分解后各列車的卸車計劃，即卸車所對應(yīng)的翻車機以及卸車順序，與此同時，生成配套的翻前調(diào)車計劃，具體作業(yè)流程可描述為：翻前調(diào)車機從到達場牽引分解后的小列車至由卸車計劃確定的小翻車機前進行對位作業(yè)等卸車準備工作，而后，返回到達場；在本務(wù)機擔(dān)當(dāng)調(diào)機運用模式下，隨重載列車到達的本務(wù)機車將牽引分解后的萬噸列車至由卸車計劃確定的大翻車機進行卸車作業(yè)。為避免同一翻車機前調(diào)車線運用沖突，后序列車到達翻前調(diào)車線的時間必須晚于當(dāng)前列車卸車完畢時間。

表2 重載列車編組及分解方案Table 2 Formation and break up scheme of heavy haul train

卸車作業(yè)完畢后，按照翻后調(diào)車計劃完成卸后列車在翻后調(diào)車線與清煤場間的調(diào)車作業(yè)，具體流程如下：翻后調(diào)機對卸后小列車進行翻后調(diào)車作業(yè)及牽引至清煤場，而后，調(diào)機返回翻后調(diào)車線；萬噸列車開始卸車時，其本務(wù)機先通過翻車機到達翻后調(diào)車線，此時，至該萬噸列車卸車完畢時本務(wù)機可充當(dāng)翻后調(diào)車機的角色，對已卸完的小列車進行調(diào)移至清煤場的作業(yè)。當(dāng)萬噸列車卸車完畢時，需由原本擔(dān)當(dāng)?shù)谋緞?wù)機負責(zé)翻后調(diào)車作業(yè)將其牽引至清煤場。為避免同一翻車機后調(diào)車線運用沖突，只有當(dāng)前列車開始翻后調(diào)車作業(yè)時，后序列車才可以開始卸車作業(yè)。清煤場完成清煤的小列和萬噸列車按相同車型組合成出發(fā)列車，空車編組形式與到達重載列車相同，組合完畢后，進行列車的發(fā)車作業(yè)。

通過對港口站作業(yè)計劃全過程的梳理，分析得到，港口站組織模式具有流程環(huán)節(jié)復(fù)雜并且作業(yè)之間存在相互影響，設(shè)備資源調(diào)度靈活存在動態(tài)耦合關(guān)系的特點。與此同時，在本務(wù)機擔(dān)當(dāng)調(diào)機運用模式下，調(diào)車作業(yè)計劃的合理編制及調(diào)機和本務(wù)機的高效協(xié)同是提升車站作業(yè)效率的關(guān)鍵。綜上所示，本文研究的重載鐵路港口站作業(yè)計劃綜合編制問題概述為：給定一個時間段內(nèi)港口站到達列車和出發(fā)列車的信息以及港口站配屬調(diào)車機和翻車機的數(shù)量和類型等，以車輛在站停留時間最小為目標(biāo)，在滿足車站各項作業(yè)流程約束的前提下，確定列車分解方案、翻車機卸車計劃、出發(fā)列車組合計劃以及調(diào)機本務(wù)機運用計劃。

2 模型建立

2.1 模型假設(shè)

本文主要針對港口站各階段作業(yè)流程，重點分析設(shè)備的分工和作業(yè)執(zhí)行順序，為方便模型對實際問題的描述，做出以下假設(shè)：

(1)車站技術(shù)檢查能力充足，不存在等待技術(shù)檢查時間。

(2)列車的組合和發(fā)車能力充足，不存在等待發(fā)車作業(yè)時間。

(3)車站各站場間線路能力充足，線路有效長度滿足所有類型列車作業(yè)。

2.2 符號定義

本文使用的集合和參數(shù)定義如表3所示，變量定義如表4所示。

表3 集合和參數(shù)定義Table 3 Definition of sets and indices

表4 變量定義Table 4 Definition of parameters

2.3 目標(biāo)函數(shù)

重載鐵路港口站的目標(biāo)是協(xié)同管控車站各作業(yè)設(shè)備，在安全有序的條件下完成重車的卸車作業(yè)，并組織空車的排空任務(wù)。為最大限度加速重空車的轉(zhuǎn)換，滿足車站排空任務(wù)的同時提高空車回送的運輸能力，本文以車輛在站時間z最小化為目標(biāo)函數(shù)，即

2.4 約束條件

(1)列車分解約束

式(2)為到達列車分解方案唯一性約束，即每列到達列車只能選擇一種對應(yīng)的分解方案。式(3)確定了到達列車分解后得到的列車。式(4)表明分解后的列車只能選擇一個對應(yīng)的翻車機進行卸車。

(2)翻車機卸車、翻前調(diào)機和本務(wù)機運用約束

式(5)表示分解后的小列車由某臺翻前調(diào)機在最早翻前調(diào)車時刻后進行翻前調(diào)車作業(yè)。式(6)表示分解后的萬噸列車由隨車到達的本務(wù)機在最早翻前調(diào)車時刻后進行翻前調(diào)車作業(yè)。式(7)為翻前調(diào)機作業(yè)不沖突約束，表示翻前調(diào)機在一次翻前調(diào)車作業(yè)周期內(nèi)只能完成一列車的調(diào)車作業(yè)。式(8)和式(9)定義了小列車和萬噸列車到達翻車機前并完成對位的時刻。式(10)確保列車卸車開始時刻晚于列車到達翻前時刻。式(11)為同一翻車機上列車卸車順序約束。式(12)為占用同一翻車機前調(diào)車線不沖突約束，后序列車到達翻前時間必須晚于當(dāng)前列車卸車完畢時間。

(3)翻后調(diào)機和本務(wù)機運用約束

式(13)表示只有隨萬噸列車卸車的本務(wù)機車才允許進行翻后調(diào)車作業(yè)。式(14)表示本務(wù)機車只有在開始卸車并通過翻車機后才能進行翻后調(diào)車作業(yè)。式(15)確保萬噸列車卸車完畢后開始翻后調(diào)車作業(yè)，本務(wù)機在翻后對小列車進行調(diào)車作業(yè)的最晚開始時刻不能晚于規(guī)定時間。式(16)表示翻后小列車由某臺翻后調(diào)機或本務(wù)機在最早翻后調(diào)車時刻后進行翻后調(diào)車作業(yè)。式(17)表示萬噸列車由原本務(wù)機負責(zé)翻后調(diào)車作業(yè)。式(18)為翻后調(diào)機和本務(wù)機作業(yè)不沖突約束，表示翻后調(diào)機或本務(wù)機在一次翻后調(diào)車作業(yè)周期內(nèi)只能完成一列車的調(diào)車作業(yè)。式(19)和式(20)定義了小列車和萬噸列車開始翻后調(diào)車作業(yè)的時刻。式(21)確保翻后調(diào)車作業(yè)開始時刻晚于卸車完畢時刻。式(22)為占用同一翻車機后調(diào)車線不沖突約束，只有當(dāng)前列車開始翻后調(diào)車作業(yè)時，后序列車才可以開始卸車作業(yè)。

(4)出發(fā)列車組合約束

式(23)為列車組合唯一性約束，表示分解后的列車只能編入一輛出發(fā)列車。式(24)為出發(fā)列車車型約束，每列出發(fā)列車需確定一種車型。式(25)規(guī)定編入同一出發(fā)列車的列車類型需一致。式(26)為出發(fā)列車編組唯一性約束，每列出發(fā)列車需確定一種編組類型。式(27)規(guī)定每一列出發(fā)列車需按編組類型進行組合。式(28)為列車接續(xù)的時間約束，表示列車的清煤完成時間要早于出發(fā)列車最晚組合及技術(shù)檢查時刻，才可以編入該出發(fā)列車。

3 算法設(shè)計

港口站作業(yè)計劃綜合編制優(yōu)化模型中各子問題間帶有復(fù)雜耦合約束，屬于聯(lián)合決策優(yōu)化問題。其本質(zhì)與帶阻塞的分布式混合流水車間調(diào)度問題相近，在此基礎(chǔ)上，具有多種加工產(chǎn)品、多機并行、加工時間窗及裝配要求等特征，因此，在求解中具有較大的挑戰(zhàn)。傳統(tǒng)的精確求解算法與商用求解器在針對大規(guī)模問題時，解的收斂速度較慢，無法在短時間內(nèi)得到滿意解。啟發(fā)式智能優(yōu)化算法在求解大規(guī)模車間調(diào)度問題中已被廣泛應(yīng)用，并且具有優(yōu)異性。基于優(yōu)勢基因結(jié)構(gòu)的微進化算法有助于分解方案子問題的快速收斂，自適應(yīng)鄰域搜索算法可以增強調(diào)度子問題跳出局部最優(yōu)的能力，而啟發(fā)式策略的應(yīng)用能夠減少解空間的搜索范圍，因此，綜合考慮模型中各子問題與優(yōu)化算法的特點，提出帶有啟發(fā)式策略的微進化與自適應(yīng)鄰域搜索相結(jié)合的混合算法。

3.1 編碼與種群初始化

本問題的編碼方案需要包括列車分解方案及分解后各階段調(diào)機、本務(wù)機、翻車機的指派以及作業(yè)順序，由于信息量過大，單個染色體編碼很難實現(xiàn)對問題的完整描述，因此，采用雙層編碼方法。編碼方案如圖1 所示，第一層為分解方案部分，該部分編碼設(shè)計應(yīng)滿足列車分解方案唯一性約束，因此，編碼長度等于到達列車的數(shù)量，每個基因位用表1 中分解計劃的標(biāo)號表示該到達列車選擇的分解方案，所有分解方案染色體組成分解方案種群。第二層為對應(yīng)分解方案下的調(diào)度作業(yè)順序編碼，由于單元萬噸列車與小列車分別作業(yè)于兩套卸車系統(tǒng)，因此，編碼按列車編組類型分為兩段，前一段為分解后的萬噸列車作業(yè)順序，后一段為分解后的小列車作業(yè)順序，其編碼長度為分解后萬噸列車數(shù)與小列車數(shù)的總和。

圖1 染色體編碼方案Fig.1 Chromosome coding scheme

進一步，通過推導(dǎo)目標(biāo)函數(shù)可以看出，目標(biāo)值與出發(fā)列車的編組數(shù)密切相關(guān)，而出發(fā)列車均由相同車型組合而成，不同車型的作業(yè)順序會影響列車的組合情況，從而改變出發(fā)列車的編組導(dǎo)致目標(biāo)函數(shù)值發(fā)生改變。因此，為縮小編碼搜索范圍，在保證最優(yōu)性的前提下，減少等價的重復(fù)編碼和適應(yīng)度較差的編碼，以車型作為編碼的基因，即調(diào)度作業(yè)編碼前半段為萬噸列車車型的作業(yè)順序，后半段為小列車車型的作業(yè)順序，編碼中各車型的總數(shù)應(yīng)與分解后的車型數(shù)保持一致，此時，只需將同一車型的列車以先到先服務(wù)的原則及列車的到達順序?qū)?yīng)到作業(yè)順序編碼，即可保證此車型編碼下得到最優(yōu)列車作業(yè)順序編碼。

分解方案種群的初始化對于求解質(zhì)量有著至關(guān)重要的影響，分解方案作為調(diào)度問題的輸入，決定著調(diào)度子問題的最優(yōu)解取值。如果未能求得最優(yōu)的分解列車方案，即使調(diào)度問題獲得最優(yōu)解，也無法得到全局最優(yōu)解。分解方案等同于確定大翻車機和小翻車機兩套卸車作業(yè)系統(tǒng)中列車的分配，根據(jù)兩套系統(tǒng)的綜合作業(yè)能力分配列車，可以最大化整體作業(yè)效率，減少各系統(tǒng)中等待作業(yè)及阻塞的時間。系統(tǒng)的綜合作業(yè)能力取決于各階段中最小作業(yè)能力，各階段的作業(yè)能力與該階段可利用的資源數(shù)量成正比，與作業(yè)時間成反比。為簡化問題，在不考慮列車到達時間和翻后調(diào)車作業(yè)能力的影響下，計算并比較兩套系統(tǒng)在翻前調(diào)車作業(yè)階段與翻車機卸車作業(yè)階段的兩階段系統(tǒng)作業(yè)能力，計算式為

式中：sb、sx分別為大翻車機和小翻車機系統(tǒng)作業(yè)能力；|K|為翻前調(diào)機數(shù)量，|Fb|和 |Fx|分別為大翻車機和小翻車機數(shù)量；和分別為大翻車機和小翻車機卸車作業(yè)時間。為盡可能均衡兩套系統(tǒng)的能力利用率，生成分解方案編碼時應(yīng)滿足|sbsx-nwnl|≤20%，其中，nw和nl分別為分解后萬噸列車和小列車的數(shù)量。列車作業(yè)順序編碼則按照分解后列車的到達順序，以先到先服務(wù)的原則生產(chǎn)初始編碼。

3.2 解碼策略與適應(yīng)度計算

有效的解碼方法需要在符合約束條件的基礎(chǔ)上，得到更優(yōu)的目標(biāo)值。針對問題具有分布式并行同速機、帶阻塞約束及保證翻車機前后調(diào)車線運用不沖突等特征，本文構(gòu)造兩階段置換解碼的方式，采用最早可利用機械原則(First Available Machine,FAM)，通過對設(shè)備上作業(yè)完成時刻的更新與比較，避免作業(yè)流程沖突。具體到本問題，第1 階段，確定萬噸列車的作業(yè)計劃，萬噸列車的調(diào)車作業(yè)全程由隨車到達的本務(wù)機完成，因此，不需要考慮本務(wù)機的指派問題。通過對大翻車機和本務(wù)機的最早作業(yè)完成時刻的比選與迭代，滿足作業(yè)時間接續(xù)以及設(shè)備占用約束，按列車作業(yè)順序得到萬噸列車完整的調(diào)度方案，同時，獲得本務(wù)機的調(diào)車作業(yè)計劃。仿照上述流程，第2 階段，確定小列車的作業(yè)計劃，由于本務(wù)機可以參與小列車翻后調(diào)車作業(yè)，因此，小列車的調(diào)車作業(yè)需由本務(wù)機與調(diào)機共同比選后確定。為便于對解碼步驟的描述，引入符號如表5所示。

表5 符號定義Table 5 Definition of symbols

解碼算法具體步驟如下。

Step 1 以同車型先到先服務(wù)的原則，將車型作業(yè)順序解碼為列車作業(yè)順序。

Step 2 第1 階段，確定萬噸列車的作業(yè)計劃，分解后的萬噸列車按編碼給定的作業(yè)順序依次進行以下計算：

Step 2.3 得到該萬噸列車的完整調(diào)度方案，若所有萬噸列車分配完畢，轉(zhuǎn)入Step 3；否則，返回Step 2。

Step 3 第2 階段，確定小列車的作業(yè)計劃，按照分解后的小列車作業(yè)順序依次進行以下計算：

Step 3.8 得到該小列車的完整調(diào)度方案，若所有小列車分配完畢，算法結(jié)束；否則，返回Step 3。

通過上述解碼步驟，所有列車均已得到完整的調(diào)度方案，此時，問題轉(zhuǎn)化為靜態(tài)配流問題。依據(jù)啟發(fā)式方法，確定列車的組合方案及適應(yīng)度函數(shù)的計算。通過式(29)對目標(biāo)函數(shù)的轉(zhuǎn)化可以看出，當(dāng)出發(fā)列車盡可能編發(fā)2萬t列車時，目標(biāo)函數(shù)越優(yōu)，以優(yōu)先盡早編發(fā)2萬t列車和相鄰兩列車最優(yōu)組合為原則，設(shè)計靜態(tài)配流啟發(fā)式算法如下。

Step 1 出發(fā)列車按出發(fā)時刻由小到大進行排序C={1,2,…,|C|}，令c=1，初始待分配列車集合D={1,2,…,|D|}為所有分解后的列車集合。

Step 2 若c ＞||C出發(fā)列車配流結(jié)束，轉(zhuǎn)入Step 5；否則，轉(zhuǎn)入Step 3。

Step 3 通過式(28)判斷每列待分配列車與出發(fā)列車c接續(xù)的可行性。若c=||C或列車c可由同一車型組合成2 萬t 列車，即滿足編入同一出發(fā)列車的類型一致和編組唯一約束，那么則車c的組合方案確定，將分配完的列車從待分配列車集合D中移除，更新待分配列車集合D，c=c+1，并返回Step 2；否則，轉(zhuǎn)入Step 4。

Step 4 根據(jù)式(28)計算出發(fā)列車c+1 的可行組合方案，同時，比較兩列出發(fā)列車在不同車型選擇下的總編組輛數(shù)wcnn+wc+1nn，在保證總編組輛數(shù)最大的情況下，計算目標(biāo)函數(shù)值Tcwcnn+Tc+1wc+1nn最小的組合方案，即為相鄰兩列車最優(yōu)組合方案，將分配完的列車從待分配列車集合D中移除，更新待分配列車集合D，c=c+2，并返回Step 2。

Step 5 若待分配列車集合D為空集，則通過式(29)計算此配流方案下的總目標(biāo)函數(shù)；否則，出現(xiàn)因無法滿足列車配流而產(chǎn)生的調(diào)度方案不可行解，規(guī)定此時目標(biāo)函數(shù)取值為 |D|M。

3.3 鄰域搜索算子

高效的鄰域搜索可以在有限的迭代范圍內(nèi)快速提升解的質(zhì)量，鄰域搜索算子作用于調(diào)度作業(yè)編碼，目的是能夠快速得到各分解方案下的最優(yōu)調(diào)度作業(yè)方案。結(jié)合編碼和問題特征，本文提出基于相同車型組合和縮小等待組合時間的兩種結(jié)合解碼信息的鄰域算子，每種均包括插入和交換操作。

(1)相同車型插入算子

根據(jù)解碼時得到的配流信息，將未編發(fā)2 萬t空車的出發(fā)列車車型對應(yīng)基因在編碼中刪除，并依次插入到相同車型基因位后方，相同車型的集中作業(yè)可以改變出發(fā)列車的編組，以此提升適應(yīng)度函數(shù)值，在不打破整體方案的基礎(chǔ)上，對鄰域解進行快速搜索并得到最優(yōu)插入方案。

(2)相同車型交換算子

將(1)中車型對應(yīng)基因依次與同車型基因位的后方基因進行互換，選擇適應(yīng)度函數(shù)提升最優(yōu)的互換位置。

(3)縮小等待時間插入算子

刪除配流方案中等待組合時間最長的待分配列車所對應(yīng)的基因，依次插入后方編碼中，選取最優(yōu)插入位置。合理的作業(yè)順序調(diào)整可以加快有效配流，以此提升適應(yīng)度函數(shù)值。

(4)縮小等待時間交換算子

將(3)中分配列車對應(yīng)基因依次與后方基因進行互換，選擇適應(yīng)度函數(shù)提升最優(yōu)的互換位置。

基于解碼信息的鄰域算子作用于不同編碼時搜索效果也會不同，為了能夠在每次迭代中提升搜索效率，本文采用一套自適應(yīng)鄰域算子選擇機制，根據(jù)各算子的選擇權(quán)重以輪盤賭的方式選擇算子。初始4種算子權(quán)重相同，在每輪鄰域搜索后更新鄰域算子的權(quán)重，即

式中：γα為算子α的選擇權(quán)重；λ0和λ1分別為本次迭代中選擇該算子的次數(shù)以及算子提升適應(yīng)度函數(shù)的次數(shù)；β為權(quán)重更新系數(shù)。

3.4 優(yōu)勢基因塊

微進化算法把種群中優(yōu)秀染色體存在的相似基因結(jié)構(gòu)定義為優(yōu)勢基因塊，在生成下一代種群個體時，優(yōu)勢基因塊可以得到保留。本算法在確定優(yōu)勢基因塊時，抽取種群中適應(yīng)度函數(shù)值排在前15%的染色體，設(shè)計兩類優(yōu)勢基因塊結(jié)構(gòu)，第一種是任意相鄰的基因位，在實際問題中表示相鄰到達列車的分解方案；第二種是相鄰相同車型的基因位，在實際問題中表示相鄰的相同車型到達列車的分解方案。統(tǒng)計染色體分解方案編碼中符合兩類基因塊結(jié)構(gòu)的賦值，若同一賦值占比超過50%，則將此基因納入優(yōu)勢基因塊中。

3.5 微進化算子

(1)選擇策略

為保持種群在全局搜索中的多樣性和優(yōu)異性，在選擇操作中采用精英保留策略，即在每一次迭代時，將種群中適應(yīng)度值前5%的染色體直接復(fù)制到下一代，并將作為父代與種群中其余染色體進行交叉變異操作，直至產(chǎn)生完整的下一代種群。

(2)基于同編組類型列車交叉算子

根據(jù)分解方案編碼的形式，每個基因位對應(yīng)不同編組類型的列車，隨機選擇基因?qū)M行交叉會導(dǎo)致編碼的不可行，因此，本文選擇相同編組類型列車所對應(yīng)的基因?qū)M行多點位順序交叉，既能滿足編碼的可行性又可以保證解的質(zhì)量不受破壞，具體思路如下：將父代染色體中的優(yōu)勢基因保留，選取若干相同編組類型列車的基因位并按順序進行互換，同時，按先到先服務(wù)的原則順序替換作業(yè)順序編碼中對應(yīng)的車型基因，生成完整的子代個體。

(3)基于同車型列車變異算子

為防止種群的過早收斂并保持多樣性，采用同車型列車變異算子，即改變相同車型列車的分解方案，實現(xiàn)不同的組合情況以此在搜索過程中跳出局部最優(yōu)區(qū)域，具體思路如下：隨機選取父代染色體中相同車型列車的基因位，若為優(yōu)勢基因，則保留；否則，進行隨機變換，生成子代個體的分解方案編碼部分，再通過先到先服務(wù)的原則新增或刪除作業(yè)順序編碼中對應(yīng)的車型基因。

3.6 算法流程

帶有啟發(fā)式策略的微進化與自適應(yīng)鄰域搜索算法主要流程如下。

Step 1 算法參數(shù)初始化：分解方案種群規(guī)模、微進化迭代次數(shù)、每輪鄰域搜素次數(shù)、鄰域搜索算子的權(quán)重更新系數(shù)及微進化算子的交叉和變異操作概率。

Step 2 根據(jù)系統(tǒng)能力及種群初始化方法，得到初始分解方案種群，再以先到先服務(wù)原則在分解方案編碼的基礎(chǔ)上生成調(diào)度作業(yè)順序編碼，由此得到完整編碼方案。

Step 3 根據(jù)提出的解碼策略以及靜態(tài)配流算法，計算種群中所有個體的適應(yīng)度值，結(jié)合解碼信息，采用自適應(yīng)鄰域算子選擇機制對每個個體調(diào)度作業(yè)順序編碼部分進行鄰域搜索。

Step 4 若達到每輪鄰域搜索迭代次數(shù)，轉(zhuǎn)Step 5；否則，更新鄰域搜索算子權(quán)重，返回Step 3。

Step 5 是否達到算法終止條件，若是，輸出結(jié)果算法，結(jié)束；否則，轉(zhuǎn)入Step 6。

Step 6 計算并更新種群中的優(yōu)勢基因塊。

Step 7 通過精英保留策略選擇個體進行交叉和變異操作，生成下一代種群，返回Step 3。

4 算例分析

4.1 算例描述

本文以某重載鐵路港口站為例，對階段內(nèi)車站作業(yè)計劃綜合編制進行優(yōu)化研究，驗證模型和算法的有效性。該港口站配備大型翻車機3臺，小型翻車機4 臺，翻前調(diào)車機2 臺，翻后調(diào)車機1 臺，列車到達技術(shù)檢查以及分解作業(yè)時間為30 min，翻前調(diào)車作業(yè)及返回時間分別為20 min，10 min，大小翻車機卸車作業(yè)時間均為60 min，本務(wù)機通過大型翻車機的時間為15 min，翻后調(diào)車作業(yè)及返回時間分別為20 min，10 min，清煤作業(yè)時間為20 min，空車組合以及技術(shù)檢查時間為30 min。研究選取某日8:00-10:00 時段內(nèi)的12 列到達列車，信息如表6 所示。鑒于站內(nèi)各項作業(yè)時長，選取12:20-14:20時段內(nèi)的9列出發(fā)列車。

表6 到達列車信息Table 6 Arrival train information

4.2 算例結(jié)果分析

算法程序利用Python編寫，運算環(huán)境在處理器為Intel(R) Core(TM) i7-11800H @ 2.30 GHz，內(nèi)存為32 GB的計算機上。通過多次實驗比較，本算例的算法參數(shù)設(shè)置如下：分解方案種群規(guī)模為30，迭代次數(shù)為50，每輪鄰域搜素次數(shù)為20，鄰域搜索算子的權(quán)重更新系數(shù)為0.6，微進化算子的交叉和變異操作概率為0.7和0.1。

求解得列車分解方案如表7所示，各列車分解方案與表1 中相應(yīng)編組類型列車的分解方案對應(yīng)。將分解后得到的萬噸列車與小列車進行編號，兩者的數(shù)量比例為10∶12，與由式(30)計算得到的兩卸車系統(tǒng)能力比值接近。

表7 到達列車分解方案Table 7 Break up scheme of arrival train

出發(fā)空車組合方案如表8所示。出發(fā)空車中，前7列是2萬t編組，均由1列萬噸列車和2列小列車或2列萬噸列車組合而成，滿足空車編組要求的同時能夠壓縮車輛在站停留時間，最大限度提升車站配空效率和發(fā)車作業(yè)能力，合理優(yōu)化運行線使用。

表8 出發(fā)空車組合方案Table 8 Combination scheme of departure empty train

為更加直觀地還原各設(shè)備的占用情況和作業(yè)順序，兩套卸車系統(tǒng)的作業(yè)流程以甘特圖的形式呈現(xiàn)，如圖2 和圖3 所示。以分解后的萬噸列車4 和小列車11 為例對甘特圖進行說明。小列車11 隨28551次列車于8:12到達，完成分解作業(yè)后，在8:42由翻前調(diào)機1 從到達場開始牽引，9:02 到達小翻車機1并開始卸車，此時，翻前調(diào)機1完成調(diào)移任務(wù)返回到達場。萬噸列車4 隨28649 次列車于8:42 到達，完成分解作業(yè)后，在9:12 由隨車到達的本務(wù)機車4牽引至大翻車機3，9:32到達并開始卸車作業(yè)，9:47 本務(wù)機4 通過翻車機，此時至萬噸列車4 卸車完畢時刻，即10:32，本務(wù)機4 可在翻后代替調(diào)車機作業(yè)。10:02 小列車11 卸車完畢，此時，翻后調(diào)機1 為同時卸車完畢的小列車12 作業(yè)，小列車11則由本務(wù)機4 調(diào)移至清煤場進行清煤作業(yè)，隨后，與萬噸列車2 和小列車12 組合成出發(fā)列車28032次。本務(wù)機4 完成小列車11 的調(diào)移作業(yè)后，在10:32返回翻后調(diào)車線并牽引卸車完畢的萬噸列車4至清煤場，隨后，與萬噸列車5組合成出發(fā)列車28680次。

圖2 小翻車機卸車系統(tǒng)Fig.2 Small tippler unloading system

圖3 大翻車機卸車系統(tǒng)Fig.3 Large tippler unloading system

綜合分析上述圖表展示的結(jié)果可以得出，機車與翻車機作業(yè)相互配合，流程連續(xù)，不存在翻前和翻后調(diào)車線運用沖突。兩套系統(tǒng)的最晚卸車完畢時刻接近，各作業(yè)設(shè)備未出現(xiàn)中斷與空閑的狀態(tài)，在現(xiàn)有的設(shè)備配置下，該分解方案較好地平衡了兩套卸車系統(tǒng)的作業(yè)負荷。在作業(yè)順序方面，滿足同種車型先到先卸原則，且同種車型的卸車順序相對集中。本務(wù)機4、5、6、8、10在翻后分別擔(dān)當(dāng)了小列車11、15、13、16、20 的調(diào)移作業(yè)任務(wù)，加快翻后作業(yè)效率的同時有效分擔(dān)翻后調(diào)機的作業(yè)壓力。

為驗證卸車系統(tǒng)在不同機車運用模式下的車站作業(yè)效率，假設(shè)港口站的調(diào)車作業(yè)均由該站配備的調(diào)車機車完成，即本務(wù)機不參與調(diào)車作業(yè)，對比分析不同調(diào)機配備與分工情況下港口站作業(yè)計劃結(jié)果。通過修改上文模型與算法，將本務(wù)機指派的相關(guān)變量和約束改為調(diào)車機車，為防止出現(xiàn)不可行解，增加一虛擬出發(fā)列車，設(shè)該列車的出發(fā)時刻為一較大正數(shù)，虛擬出發(fā)列車沒有編組的限制，且任意車型的列車均可編入。求得計算結(jié)果如表9 所示，當(dāng)本務(wù)機不參與調(diào)車作業(yè)時，原有調(diào)機配備數(shù)量無法滿足港口站調(diào)車作業(yè)需求，通過增加調(diào)機數(shù)量，更多列車在時間段內(nèi)完成卸車并配空。當(dāng)翻前和翻后均為4輛調(diào)機時，所有列車在階段內(nèi)完成組合和出發(fā)作業(yè)，求得的目標(biāo)函數(shù)值與原本務(wù)機參與作業(yè)時相同。因此，在保證階段計劃編制質(zhì)量不變的前提下，針對本算例采用本務(wù)機擔(dān)當(dāng)調(diào)機運用模式后，港口站調(diào)機可從8臺縮減至3臺，節(jié)省5臺。

表9 不同機車運用模式對比Table 9 Comparison of different locomotive operation modes

4.3 算法比較

為驗證本文提出算法的求解性能，將其與Gurobi 商業(yè)求解器在求解速度和精度方面進行對比，具體計算結(jié)果如表10所示?？梢钥闯?，本文算法在193 s 求得結(jié)果為68.59 萬t 車小時，與最優(yōu)下界間隔的gap 值為0.31%。在規(guī)定計算時間內(nèi)(7200 s)相比于Gurobi 求解器，求解時間減少97.32%，gap值減少0.06%。

表10 算法對比Table 10 Algorithm comparison

5 結(jié)論

本文以重載鐵路卸車端智慧港口站作業(yè)為背景進行研究。首先，分析不同卸車系統(tǒng)下車站作業(yè)方案，提出本務(wù)機擔(dān)當(dāng)調(diào)機的運用模式，構(gòu)建港口站作業(yè)計劃綜合編制優(yōu)化模型；其次，根據(jù)模型特點，設(shè)計帶有啟發(fā)式策略的微進化與自適應(yīng)鄰域搜索算法；最后，通過算例驗證模型和算法的有效性。本文得出的主要結(jié)論如下。

(1)本文以提高車站作業(yè)效率，加速車輛周轉(zhuǎn)為目標(biāo)，在目標(biāo)函數(shù)中等價為車輛在站停留時間最小。算例計算結(jié)果中，前7列出發(fā)列車均按2萬t空車進行編組，說明該配流方案在滿足車站作業(yè)要求的基礎(chǔ)上，充分發(fā)揮重載鐵路回空方向的運輸能力，為裝車端提供充足的車輛保障。與此同時，站內(nèi)資源利用充分，調(diào)車機、本務(wù)機及翻車機調(diào)度方案相互吻合，各設(shè)備未出現(xiàn)空閑等待時間。所提出的算法能夠在193 s 求得與最優(yōu)下界間隔gap 值為0.31%的接近最優(yōu)解，在計算效率和求解質(zhì)量方面均優(yōu)于Gurobi商業(yè)求解器。

(2)本文對比分析不同機車的運用模式，結(jié)果表明，在該算例中為達到相同的配流結(jié)果，本務(wù)機擔(dān)當(dāng)調(diào)機運用模式可以減少5臺港口站調(diào)機，說明該模式能夠優(yōu)化調(diào)車作業(yè)中調(diào)機與本務(wù)機的綜合運用方案，提高機車運用效率。