地鐵列車收發(fā)車及檢修計劃優(yōu)化方法研究

摘 要：本文意在解決地鐵運(yùn)營過程中的收發(fā)車和檢修計劃優(yōu)化問題，提出了基于蟻群算法的地鐵列車收發(fā)車與檢修計劃優(yōu)化算法設(shè)計。采用0～1整數(shù)規(guī)劃與決策變量的方式描述地鐵列車的收發(fā)車與檢修計劃的關(guān)鍵決策因素，以車輛維護(hù)成本最低和利用效率均衡為優(yōu)化目標(biāo)、運(yùn)營需求和檢修需求為約束條件建立優(yōu)化模型，利用蟻群算法對模型進(jìn)行求解?，F(xiàn)場應(yīng)用測試表明本優(yōu)化算法可以提高地鐵列車的利用率并降低維護(hù)成本，具有一定的實際意義。

關(guān)鍵詞：城市軌道交通；檢修計劃；蟻群算法；0～1整數(shù)規(guī)劃模型

中圖分類號：U 29" " " 文獻(xiàn)標(biāo)志碼：A

地鐵是城市軌道交通系統(tǒng)的重要組成部分。地鐵運(yùn)營單位根據(jù)運(yùn)營時刻表與設(shè)備修程的要求，編制并實施收發(fā)車計劃與檢修計劃，為市民提供高效、安全的運(yùn)輸服務(wù)。在計劃實施過程中，收發(fā)車計劃與檢修計劃間會相互影響，不同的收發(fā)車計劃會使列車行駛里程發(fā)生變化，隨列車行駛里程變化而觸發(fā)的檢修工作則會影響列車運(yùn)用狀態(tài)，進(jìn)而影響執(zhí)行收發(fā)車計劃[1]。這種影響增加了計劃編制的復(fù)雜程度。目前，人工編排計劃已經(jīng)不能滿足現(xiàn)場使用，需要一種智能化手段實現(xiàn)收發(fā)車與檢修計劃的自動排程與優(yōu)化，進(jìn)而達(dá)到提升運(yùn)營效率、降低運(yùn)營成本的目的。為此本文提出一種基于蟻群算法的地鐵列車收發(fā)車與檢修計劃優(yōu)化算法設(shè)計。

1 收發(fā)車與檢修計劃優(yōu)化算法設(shè)計

1.1 問題描述

地鐵線路的運(yùn)營時刻表規(guī)定了每天所有運(yùn)營任務(wù)的出發(fā)/結(jié)束時間、區(qū)間運(yùn)行時間、沿途各站的到站/出站時間等信息，是地鐵進(jìn)行運(yùn)營工作的指令性文件。地鐵列車的每日收發(fā)車計劃可以看作是列車運(yùn)用部門根據(jù)列車的當(dāng)日狀況，對當(dāng)日運(yùn)營時刻表中的運(yùn)營任務(wù)分配適用車輛的集合。

地鐵列車每日執(zhí)行運(yùn)營任務(wù)，行駛里程逐漸增加。當(dāng)任意列車的行駛里程達(dá)到檢修修程中規(guī)定的條件時，該列車就要進(jìn)行檢修工作。檢修計劃可以看作范圍時間內(nèi)所有列車檢修工作的集合[2]。

實際運(yùn)營中，車輛的行駛里程很難恰巧等于修程規(guī)定的檢修間隔，因此對地鐵運(yùn)營企業(yè)來說，合理安排收發(fā)車計劃，使列車盡可能在接近修程極限的情況下進(jìn)行檢修[3]，可有效避免過度檢修，降低運(yùn)營成本。

上述分析問題可以描述為給定列車運(yùn)營規(guī)則、列車修程規(guī)則，輸入列車數(shù)量、行駛里程和可用狀態(tài)等參數(shù)的集合，輸出指定時間范圍內(nèi)的地鐵列車收發(fā)車與檢修計劃。問題的優(yōu)化目標(biāo)為減少列車的檢修次數(shù)。約束條件包括每日運(yùn)營任務(wù)必須全部執(zhí)行、任意列車同一時刻只能執(zhí)行一個運(yùn)營任務(wù)、運(yùn)營任務(wù)分為工作日和假日2類、列車按修程進(jìn)行檢修（不可欠修）以及同時檢修的數(shù)量不能超過車輛基地的能力。

1.2 目標(biāo)函數(shù)的建立

在實際運(yùn)營中，檢修任務(wù)的成本基本等于該任務(wù)的人工成本，檢修過程中的零件消耗則按照故障維修計算，因此時間范圍內(nèi)的電動客車維護(hù)成本可表示為所有檢修任務(wù)的總?cè)斯r，由此可得維護(hù)成本最低目標(biāo)函數(shù)如公式（1）所示。

（1）

式中：M={m|m=1，2，3…Nm}為列車集合，m為列車序號，Nm為列車總數(shù)；D={d|d=1，2，3…Nd}為編制計劃時間集合，d為日期的相對序號，Nd為計劃總天數(shù)；S={s|s=0，1，2，3…}為檢修修程的集合，s為檢修項的編號；Bmds為0～1決策變量，表示當(dāng)m號車在d日執(zhí)行修程s時，Bmds=1，否則為0；Cs為s號檢修作業(yè)的工時花費(fèi)。

為避免運(yùn)營任務(wù)分配過于集中，部分列車長期沒有運(yùn)營任務(wù)，停放過久，進(jìn)而造成蓄電池虧損等問題，因此需要保證所有列車均有一定的出動比例，可看作所有列車既不執(zhí)行運(yùn)營任務(wù)，也不執(zhí)行檢修任務(wù)的狀態(tài)的總時長最小，其目標(biāo)函數(shù)如公式（2）所示。

（2）

式中：Q={q|q=0，1，2，3…Nq}為運(yùn)營任務(wù)的集合，q為運(yùn)營任務(wù)的序號，Nq為運(yùn)營任務(wù)的總數(shù)量；Amdq為0～1決策變量，表示當(dāng)m號車在d日執(zhí)行q號任務(wù)時，Amdq=1，否則為0；Cd為一天內(nèi)的運(yùn)營時長。

將公式（1）、公式（2）2個優(yōu)化目標(biāo)函數(shù)進(jìn)行整合并建立優(yōu)化目標(biāo)函數(shù)，如公式（3）所示。

minZ=α·Z1+β·Z2 （3）

式中：α、β分別為列車檢修成本和均衡運(yùn)用情況的權(quán)值，該數(shù)值為經(jīng)驗值，由列車歷史數(shù)據(jù)分析產(chǎn)生。

1.3 約束條件的建立

每天的運(yùn)營任務(wù)要區(qū)分平日與假日，并保證所有任務(wù)均被地鐵列車執(zhí)行，基于此建立運(yùn)營時刻表使用約束，如公式（4）所示。

（4）

式中：δdq為0～1決策變量，運(yùn)營任務(wù)q在d日被執(zhí)行時，δdq=1，否則為0。

根據(jù)一個運(yùn)營任務(wù)只能由一列電動客車承擔(dān)的要求建立運(yùn)營列車唯一性約束，如公式（5）所示。

（5）

根據(jù)任意列車同一時刻只能進(jìn)行一項檢修工作的要求建立檢修工作唯一約束，如公式（6）所示。

（6）

實際運(yùn)營中有早、晚高峰的需求，存在當(dāng)天早高峰回庫列車?yán)^續(xù)執(zhí)行晚高峰任務(wù)的情況。假設(shè)列車m在d日執(zhí)行運(yùn)營任務(wù)q1的結(jié)束時間早于運(yùn)營任務(wù)q2的開始時間，則列車m在q日執(zhí)行q1、q2共2個運(yùn)營任務(wù)，基于此建立運(yùn)營任務(wù)調(diào)度約束，如公式（7）所示。

（7）

式中：Tqstar和Tqend分別為運(yùn)營任務(wù)q的開始、結(jié)束時間。

由于存在早、晚高峰，因此存在同一天的早高峰回庫列車?yán)^續(xù)進(jìn)行檢修的情況。假設(shè)列車m在d日執(zhí)行運(yùn)營任務(wù)q，q的結(jié)束時間早于檢修任務(wù)s的開始時間，則列車m在d日執(zhí)行運(yùn)營任務(wù)q和檢修任務(wù)s，基于此建立檢修任務(wù)調(diào)度約束，如公式（8）所示。

（8）

式中：Tsstar'為檢修任務(wù)s的開始時間。

根據(jù)車輛基地內(nèi)每天同時進(jìn)行的檢修作業(yè)不能超過車輛基地最大檢修能力的要求建立車輛基地能力約束，如公式（9）所示。

（9）

式中：Nc為車輛基地同時進(jìn)行檢修作業(yè)的最大數(shù)量。

列車執(zhí)行多次運(yùn)營任務(wù)后，其累計行駛里程逐漸接近修程規(guī)定的檢修周期，當(dāng)累計行駛里程無法滿足可執(zhí)行任意運(yùn)營任務(wù)時，必須安排檢修作業(yè)。計算列車當(dāng)日行駛里程與前一次檢修作業(yè)行駛里程的差值，將修程規(guī)定的檢修周期與差值相減，所得結(jié)果如小于所有未來待執(zhí)行的運(yùn)營任務(wù)里程，可以安排該車輛進(jìn)行檢修。所建立的修程規(guī)則約束如公式（10）所示。

（lmd-lmds）+lqquest≤lsservice；m∈M，d∈D，q∈D，s∈S

（10）

式中：lsservice為第s號修程項規(guī)定的檢修里程；lqquest為第q號運(yùn)營任務(wù)的行駛里程；變量lmd為m號車在d日的行駛里程；變量lmds為m號車在d日進(jìn)行s號檢修作業(yè)時的行駛里程。

列車日常運(yùn)營中常見“因故障扣車”等臨時任務(wù)，可以將這些臨時任務(wù)看作用時1d、檢修周期無窮大的虛擬檢修任務(wù)，長時間的臨時任務(wù)可以拆解為多個用時1d的虛擬任務(wù)。所建立的臨時任務(wù)約束如公式（11）所示。

Bmds=θmd；m∈M，d∈D，s∈S0 （11）

式中：θmd為0～1決策變量，當(dāng)列車m在d日執(zhí)行臨時任務(wù)時，θmd=1，否則為0。

列車檢修成本和均衡運(yùn)用情況的權(quán)值α和β的約束條件如公式（12）所示。

α+β=1 （12）

1.4 基于蟻群算法的目標(biāo)函數(shù)最優(yōu)解求解

通過數(shù)學(xué)模型可以判斷本節(jié)問題是一個以時間、順序為二維特征且約束條件復(fù)雜的整數(shù)線性規(guī)劃問題[4]，該類問題可以使用蟻群算法求解，其具體流程如圖1所示。1）初始化迭代次數(shù)、蟻群數(shù)量、信息素濃度和信息素?fù)]發(fā)率；初始化列車集合、日期集合、修程集合、任務(wù)集合和臨時任務(wù)集合；初始化列車行駛里程和檢修里程。2）迭代次數(shù)M=M+1。3）開始第K=K+1次（螞蟻）搜索過程。4）篩選可用任務(wù)集合，順序選取可用任務(wù)執(zhí)行搜索計算，集合為空則跳轉(zhuǎn)第11步。5）判斷d日的列車m是否存在臨時任務(wù)，跳轉(zhuǎn)第11步，否則繼續(xù)執(zhí)行。6）篩選d日任務(wù)集合，如檢索結(jié)果為空，跳轉(zhuǎn)第9步，否則繼續(xù)執(zhí)行。7）判斷檢修約束，檢索任務(wù)集合的所有元素，判斷列車執(zhí)行任務(wù)后是否超過檢修周期，超出則該任務(wù)在d日任務(wù)集合中不可用。8）再次篩選d日可用的任務(wù)集合，如為空，判斷列車執(zhí)行檢修任務(wù)，跳轉(zhuǎn)第10步，否則根據(jù)選擇規(guī)則選取列車。選取后該列車在當(dāng)日可用列車集合中不可用。9）更新列車行駛里程，判斷當(dāng)日運(yùn)營任務(wù)是否都已分配，未分配則跳轉(zhuǎn)第4步，都分配則跳轉(zhuǎn)第12步。10）獲取當(dāng)前檢修承載能力，承載能力已滿，則列車m閑置1d。11）根據(jù)修程合集、行駛里程、檢修里程以及回庫時間判斷列車待執(zhí)行檢修修程s，更新檢修里程，跳轉(zhuǎn)第4步。12）判斷d=D，如不等于則跳轉(zhuǎn)第3步，如等于則表示本次（螞蟻）的搜索計算完成。13）獲取本代計算次數(shù)（螞蟻）是否等于預(yù)設(shè)蟻群數(shù)量，不等于則跳轉(zhuǎn)第2步。14）檢索本代所有搜索結(jié)果（計算路徑），帶入各計算變量、常量，對模型目標(biāo)函數(shù)進(jìn)行求解，篩選本代最優(yōu)解結(jié)果并更新信息素。15）判斷迭代次數(shù)結(jié)束條件，未結(jié)束則跳轉(zhuǎn)第1步。16）輸出最優(yōu)解，轉(zhuǎn)制輸出圖形化的收發(fā)車與檢修計劃，算法結(jié)束。

2 算例分析和現(xiàn)場測試

為驗證上述模型和算法的有效性，本文基于現(xiàn)場實例進(jìn)行實證研究并收集現(xiàn)場數(shù)據(jù)，見表1～表3。

設(shè)置蟻群算法參數(shù)：蟻群迭代次數(shù)N=50，蟻群個體數(shù)量K=20，信息素濃度為1.0，信息素?fù)]發(fā)速度為0.3。對算法執(zhí)行3次，計算過程中的目標(biāo)函數(shù)值變化情況如圖2所示。

由圖2可以看出，3次計算均發(fā)生優(yōu)化目標(biāo)值逐步下降，并隨迭代次數(shù)增加而收斂的現(xiàn)象，表明蟻群算法對收發(fā)車和檢修計劃的求解優(yōu)化有效。

算法生成的計劃與歷史同期檢修數(shù)據(jù)比較見表4。由算法生成的計劃可以滿足運(yùn)營任務(wù)的需求，檢修任務(wù)S1、S2比歷史同期減少8次和6次，以每次檢修成本0.3萬元和0.5萬元計算，共計可節(jié)約檢修成本5.2萬元。

自2023年11月1日起使用算法生成收發(fā)車與檢修計劃進(jìn)行現(xiàn)場測試。截至2024年2月1日，以S1檢為例進(jìn)行追蹤，比較其測試期間表現(xiàn)和歷史同期表現(xiàn)，如圖3、圖4所示。可以看出優(yōu)化算法使用后，列車的檢修間隔更穩(wěn)定且表現(xiàn)比歷史同期有所提高，S1檢平均檢修間隔由8827km提升至9583km。在運(yùn)營總里程不變的前提下，提升平均檢修間隔等同于減少檢修次數(shù)，降低檢修成本。

3 結(jié)論

本文基于地鐵列車在日常運(yùn)營中的實際使用情況，提出了收發(fā)車和檢修計劃優(yōu)化問題，完成了數(shù)學(xué)模型搭建，設(shè)計了求解算法，并帶入現(xiàn)場實際數(shù)據(jù)進(jìn)行求解分析與現(xiàn)場測試。結(jié)果表明，本文提出的方法有效，是解決地鐵列車運(yùn)營計劃排程與優(yōu)化問題的可行方案之一，具有一定的實際意義與參考價值。

參考文獻(xiàn)

[1]鄧飛飛.淺述現(xiàn)代化城軌客車的維護(hù)與保養(yǎng)技術(shù)[J].科學(xué)與信息化，2017（21）：86-88.

[2]王家喜.動車所檢修作業(yè)計劃優(yōu)化方法研究[D].北京：北京交通大學(xué)，2018.

[3]王忠凱，史天運(yùn)，張惟皎，等.動車組運(yùn)用計劃和檢修計劃一體化編制模型及算法[J].中國鐵道科學(xué)，2012（3）：102-108.

[4]楊艦.基于蟻群算法的分布式微電網(wǎng)控制方法研究[D].保定：華北電力大學(xué)（保定），2018.