基于遺傳算法的鐵路技術(shù)站取送車計(jì)劃研究

薛玉璽，朱海笑，甘　寶，韓瑜睿

(蘭州交通大學(xué)　交通運(yùn)輸學(xué)院，甘肅　蘭州　730070)

基于遺傳算法的鐵路技術(shù)站取送車計(jì)劃研究

薛玉璽，朱海笑，甘寶，韓瑜睿

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院，甘肅蘭州730070)

薛玉璽(1990—)，碩士研究生，研究方向：交通運(yùn)輸規(guī)劃與管理；

朱海笑(1989—)，助理工程師，研究方向：客運(yùn)組織管理；

甘寶(1989—)，碩士研究生，研究方向：交通運(yùn)輸規(guī)劃與管理；

韓瑜睿(1990—)，碩士研究生，研究方向：交通運(yùn)輸規(guī)劃與管理。

摘要：為了研究更切合實(shí)際的鐵路技術(shù)站取送車計(jì)劃的合理編制方案，文章在考慮調(diào)機(jī)牽引能力、裝卸線容車限制的約束下，以取送照顧編組為前提，在取送控制時(shí)間窗內(nèi)，對(duì)站存車組及陸續(xù)到達(dá)車組的取送優(yōu)化建立了以調(diào)機(jī)取送成本最小為目標(biāo)的概念模型，并采用改進(jìn)的遺傳算法求解。通過算例求解，驗(yàn)證了該模型的正確性和算法的有效性。

關(guān)鍵詞：取送車；時(shí)間窗；放射性專用線；遺傳算法；整數(shù)編碼

0引言

在我國，鐵路運(yùn)輸有著極其重要的地位，因此有大量專門針對(duì)鐵路取送車作業(yè)的研究。馬許教授[1]率先提出了取送調(diào)車的概念，為取送車問題這一新的研究領(lǐng)域提供了最初的理論基礎(chǔ)。李文權(quán)和杜文[2]針對(duì)組織裝車地始發(fā)直達(dá)列車的樹枝狀車站，建立了圖論模型，考慮取出車輛配合運(yùn)行圖發(fā)車時(shí)間以及機(jī)車作業(yè)和裝卸作業(yè)的協(xié)調(diào)問題，建立了機(jī)器加工的排隊(duì)模型。徐忠民、孔慶鈐[3]對(duì)直達(dá)車流取送順序問題的原理進(jìn)行了分析，提出調(diào)機(jī)中斷時(shí)間最小的方案即為最優(yōu)方案，并改善了求解的效率。

大多文獻(xiàn)都簡化了取送問題，如假定車輛行駛時(shí)間及裝卸時(shí)間確定，調(diào)機(jī)牽引能力和裝卸線能力充分等，而這些都與實(shí)際生產(chǎn)不相符。本文在前人研究的基礎(chǔ)上，從實(shí)際出發(fā)，將取送問題看作一個(gè)整體進(jìn)行研究，從理論和方法兩方面優(yōu)化取送車作業(yè)，使之與車列的解體和編組緊密配合。

1取送車問題的概念模型

由于取送車問題同時(shí)涉及時(shí)間和空間兩個(gè)方面，變量較多，比較復(fù)雜，并且數(shù)學(xué)解析模型難以同時(shí)描述時(shí)空約束，因此考慮建立概念模型。

1.1　變量及含義說明

為描述模型和構(gòu)造解的方便，設(shè)定如下變量：

(1)對(duì)取送作業(yè)按類型編號(hào)，記為k，k=1，2，3分別表示送車、取車、專用線留存車組的取車。

(5)Tji：車組ji貨物作業(yè)時(shí)間，min。

(6)Tj：車站至專用線j的單程走行時(shí)間，min。

(10)用s表示某一車組的一項(xiàng)作業(yè)，設(shè)共有n項(xiàng)工作，送車和取車各算一項(xiàng)工作，一個(gè)編號(hào)唯一對(duì)應(yīng)一個(gè)車組的一項(xiàng)工作，從而s=1，2，…，n。

(14)調(diào)機(jī)送車包含挑選車組、對(duì)貨位，取車包含收集車輛和分解車組的工作，用t0表示在車站內(nèi)的消耗時(shí)間，t1表示在專用線上消耗的時(shí)間。

(15)M：調(diào)機(jī)最大牽引能力。

(16)B：計(jì)劃階段總時(shí)間。

(17)e0：調(diào)機(jī)的單位小時(shí)取送成本；e1：超過時(shí)間后的單位小時(shí)懲罰成本。

(18)y0：調(diào)機(jī)實(shí)際的總工作時(shí)間。

(19)y1：調(diào)機(jī)實(shí)際工時(shí)y0與B的差值，y1=y0-B，y1>0說明調(diào)機(jī)實(shí)際工時(shí)超過該計(jì)劃時(shí)段，y1≤0說明沒有超過。

綜上，每一項(xiàng)作業(yè)都有一個(gè)編號(hào)s，而每個(gè)編號(hào)都唯一對(duì)應(yīng)一個(gè)數(shù)組：

調(diào)車作業(yè)需要滿足一定的時(shí)間窗約束，現(xiàn)推導(dǎo)不同工作的取送控制時(shí)間窗：

對(duì)于專用線既有車組，上述兩個(gè)取車控制時(shí)刻已知，而計(jì)劃階段內(nèi)從車站送入專用線的車組，僅知道最晚取車時(shí)刻，而貨物作業(yè)時(shí)間需要送入時(shí)刻來計(jì)算。未規(guī)定掛運(yùn)車次的任何一種取車車組，取車只需在貨物作業(yè)完畢之后，同理最晚編組時(shí)刻=∞。

1.2　概念模型的建立

(1)解的形式

對(duì)于每一項(xiàng)工作，都有一個(gè)唯一的編號(hào)s與之對(duì)應(yīng)，可用編號(hào)s的序列來表示取送順序，顯然s是隨機(jī)編排的，因此問題的解可以表示為X=s1s2s3…sn，其中的每一個(gè)su(u=1，2，…，n)代表一項(xiàng)工作，u是該工作在這個(gè)方案中的順序。

該編碼方式雖然不能一眼看出調(diào)機(jī)工作內(nèi)容，但易于解碼還原，可以用遺傳算法來求解。每一個(gè)編碼都唯一對(duì)應(yīng)一個(gè)問題的解，任意解都對(duì)應(yīng)著一個(gè)編碼，這些都符合編碼的不冗余性、合法性和完備性要求，且利于遺傳算法求解時(shí)的操作。

(2)方案值計(jì)算函數(shù)

函數(shù)1批次劃分函數(shù)

根據(jù)相異放射枝不同批約束條件，判斷某個(gè)方案中相鄰的兩項(xiàng)取送作業(yè)是否可以劃分為同一批次。所謂相異放射枝不同批約是指：兩項(xiàng)相繼完成的取送作業(yè)如果對(duì)應(yīng)于不同放射枝，則不屬于同一批次。

函數(shù)2每批作業(yè)取送車數(shù)計(jì)算函數(shù)

對(duì)已經(jīng)劃分批次的取送作業(yè)方案，求得每一個(gè)批次的取送作業(yè)中，調(diào)車機(jī)車所牽引的車輛數(shù)，包括送車作業(yè)的車輛數(shù)和取車作業(yè)的車輛數(shù)，并將其值返回主調(diào)函數(shù)。

函數(shù)3調(diào)機(jī)牽引能力判斷函數(shù)

判斷每一批次的取送作業(yè)中，調(diào)車機(jī)車所牽引的車輛數(shù)是否超出了機(jī)車的最大牽引能力M，若超出給主調(diào)函數(shù)返回0，否則返回1。

函數(shù)4專用線容車限制判斷函數(shù)

判斷某批次的行車作業(yè)中，調(diào)車機(jī)車牽引的車輛數(shù)加上專用線原有的車輛數(shù)是否會(huì)超出專用線的容車能力限制，若超出給主調(diào)函數(shù)返回0，否則返回1。

函數(shù)5取送時(shí)刻判斷函數(shù)

函數(shù)6方案值計(jì)算主函數(shù)

輸入：解序列

Step1：剔除不合理方案，同一車組先取后送的方案不可行，將該解放入第一類不可行解集合內(nèi)，結(jié)束；否則轉(zhuǎn)step2。

Step2：調(diào)用函數(shù)1，對(duì)初始解劃分批次，記錄最大批次max g；對(duì)每個(gè)批次判斷批次規(guī)模Bg。

Step3：調(diào)用函數(shù)2，計(jì)算每批次的送、取車數(shù)。

Step4：調(diào)用函數(shù)3，判斷每批次是否超過調(diào)機(jī)牽引能力；若未超出轉(zhuǎn)step6；否則，將該初始解放入第二類不可行解集合內(nèi)，結(jié)束。

Step5：調(diào)用函數(shù)4，判斷每批次是否超過專用線容車量；若未超出轉(zhuǎn)step7；否則，將該初始解放入第二類不可行解集合內(nèi)，結(jié)束。

Step6：調(diào)用函數(shù)5，判斷取送作業(yè)時(shí)刻是否滿足時(shí)間窗，并記錄每批作業(yè)的離站時(shí)間和返站時(shí)間；若滿足轉(zhuǎn)step8；否則，將該初始解放入第三類不可行解集合內(nèi)，結(jié)束。

Step7：計(jì)算調(diào)機(jī)總?cè)∷蜁r(shí)間y0。

y1=y0-B；

3算法描述及改進(jìn)

由于遺傳算法本身的高度并行、隨機(jī)、自適應(yīng)等優(yōu)點(diǎn)，本文用改進(jìn)的遺傳算法求解。

(1)初始群體的產(chǎn)生

由于取送車問題的約束條件多且時(shí)間要求苛刻，可行解較少，所以選用改進(jìn)方法來產(chǎn)生初始群體。本文中染色體X=s1s2s3…sn，每一個(gè)su代表一個(gè)基因，u是該基因在整個(gè)染色體中的位置，也是工作順序，su的取值范圍是[1，n]。在每個(gè)基因位隨機(jī)產(chǎn)生編號(hào)時(shí)，對(duì)前r個(gè)基因位的取值給定一個(gè)范圍，來保證靠后時(shí)段的作業(yè)編碼不會(huì)在靠前位置。通過這種優(yōu)化，就能很快產(chǎn)生N個(gè)可行解。

(2)交叉操作

交叉操作用于組合出新的個(gè)體，并使算法能夠搜索更多的解[4]。本文中選擇部分映射交叉。先任選兩個(gè)交叉點(diǎn)，交換兩個(gè)個(gè)體交叉點(diǎn)之間的基因片段，對(duì)于原有基因，如果與交換過來的基因片段不沖突則保留，否則通過映射來找交換所得基因原位置的基因，直到?jīng)]有沖突基因?yàn)橹埂?/p>

(3)變異操作

變異操作可以擴(kuò)大算法的搜索范圍，經(jīng)過變異的染色體將成為一個(gè)全新的個(gè)體，操作之前會(huì)賦予每一個(gè)基因一個(gè)相對(duì)較小的變異概率。組合優(yōu)化問題中一般會(huì)采用互換、逆序和插入變異[5]。本文中，算法的優(yōu)化主要就是通過變異操作，將各類不可行解調(diào)整為可行解。

第一類是同車組取車作業(yè)在送車之前的，采用

互換變異，將送、取作業(yè)顛倒變?yōu)榭尚蟹桨?；第二類是不滿足調(diào)機(jī)、專用線容量限制采用隨機(jī)互換變異，將大規(guī)模的批次分開作業(yè)，使其滿足約束，成為可行解；第三類是不滿足最晚編組時(shí)刻，采用向前插入變異，即將該工作的順序提前從而滿足時(shí)刻，成為可行解。

(4)選擇和替換操作

本文中：不可行解直接變異產(chǎn)生新個(gè)體；可行解用輪盤賭的方法選擇優(yōu)秀個(gè)體交叉變異產(chǎn)生新個(gè)體，二者共同產(chǎn)生N-a個(gè)新個(gè)體，并保留父代中較好的前a個(gè)個(gè)體，這樣共產(chǎn)生N個(gè)子代。

(5)算法終止條件

遺傳算法理論上能以概率1收斂到最優(yōu)，但實(shí)際中很難實(shí)現(xiàn)，因此實(shí)際中通常求得具有一定質(zhì)量的滿意解。常用的終止規(guī)則有：給定最大遺傳迭代步數(shù)、給定最佳搜索解的最大滯留步數(shù)、給定問題的下界和一個(gè)偏差度，若當(dāng)前最優(yōu)解與下界的差不大于偏差度時(shí)停止運(yùn)算[6]。本文采取最大迭代步數(shù)終止法。

4算例分析

以連接4條放射形專用線的鐵路技術(shù)站為例，各專用線的調(diào)機(jī)走行時(shí)間及需取回車組的各時(shí)刻信息如表1所示，陸續(xù)到達(dá)的各趟列車包含的車組信息如表2所示。M=30車，B=720 min，t0=t1=10 min，e0=18元/h，e1=6元/h，現(xiàn)需確定調(diào)機(jī)的作業(yè)順序及批次信息。

表1　專用線車組信息表

表2　到達(dá)車組信息表

首先需要按照時(shí)段對(duì)各作業(yè)編上唯一的編號(hào)，如表3所示。

表3　工作編號(hào)表

(1)對(duì)上述案例采用C++語言編寫的遺傳算法求解，編譯環(huán)境為CodeBlocks13.12，運(yùn)行環(huán)境為RAM4G，CPU2.53 GHz，計(jì)算時(shí)間為8 s左右。將案例內(nèi)各時(shí)間轉(zhuǎn)換為十進(jìn)制數(shù)，以6：00為起點(diǎn)0，各參數(shù)設(shè)置為N=100，pc=0.85，pm=0.03，保留父代較優(yōu)的10個(gè)個(gè)體，最大迭代步數(shù)為500，所得滿意解解碼如下：

X1=1531281620621410139172471921252218411231526

X2=1531281620621410139172471921252241811231526

兩等值方案中，雖然調(diào)機(jī)最終的取送離站與返站時(shí)間相同，但方案2少一個(gè)批次，從調(diào)機(jī)能耗方面顯然優(yōu)于方案1，之所以全部取送完成返站時(shí)間相同，是方案2在1專用線等取車組23。

實(shí)際作業(yè)時(shí)，可以進(jìn)行調(diào)整，讓調(diào)機(jī)在做完第10批作業(yè)以后，可以先做取送以外的調(diào)車工作，如輔助解體、編組等，在第686 min時(shí)開始第11批作業(yè)，達(dá)到1專用線時(shí)車組23剛好作業(yè)完畢取回，然后緊接著做第12批作業(yè)。調(diào)整以后取送調(diào)機(jī)多出近1 h時(shí)間輔助其他調(diào)機(jī)作業(yè)，合理利用了調(diào)機(jī)能力，加強(qiáng)了各作業(yè)間的協(xié)調(diào)配合。調(diào)整前調(diào)機(jī)總?cè)∷凸ぷ鲿r(shí)間678 min，成本是203.4元，調(diào)整之后總?cè)∷蜁r(shí)間為624 min，總?cè)∷统杀?87.2元。因此，現(xiàn)場操作時(shí)，可以按照表4所示時(shí)間及內(nèi)容進(jìn)行取送作業(yè)。

表4　取送批次及時(shí)機(jī)數(shù)值表

計(jì)劃時(shí)段起始時(shí)間為6：00，而第一批作業(yè)開始時(shí)間為7：32，另外第10批和第11批作業(yè)之間也有空閑時(shí)間，取送調(diào)機(jī)可以輔助其他調(diào)機(jī)作業(yè)。

5結(jié)語

本文分析了放射形專用線非直達(dá)車流的取送車流程，從取車照顧編組的角度，利用取送車控制時(shí)刻的概念，考慮了調(diào)機(jī)牽引能力及專用線裝卸區(qū)的容車約束，建立了以調(diào)機(jī)取送成本最小為目標(biāo)的概念模型。優(yōu)化后的解不僅包括取送順序還自動(dòng)劃分了批次，使取送順序、時(shí)機(jī)與批次得到統(tǒng)一，以調(diào)機(jī)取送成本最小為目標(biāo)的優(yōu)化，會(huì)使取送作業(yè)計(jì)劃盡量以較少的批次完成所有作業(yè)，充分利用調(diào)機(jī)與裝卸線的能力，更加經(jīng)濟(jì)合理。

論文雖然做了一定的改進(jìn)，但依然存在很多需要改進(jìn)和完善的地方：

(1)在建立模型的假設(shè)中，將調(diào)機(jī)的走行時(shí)間假設(shè)為定值，不符合實(shí)際。

(2)為了簡化，超過調(diào)機(jī)或裝卸線能力限制就全部不送或不取，與實(shí)際情況有些出入。

(3)本文采用了常用的遺傳算法求解模型，并沒有與其他智能算法相比較或相結(jié)合，因此不能說明該算法是最優(yōu)的，只能說明其有效性。所以算法方面需要更深入地研究。

參考文獻(xiàn)

[1]馬許.車站與專用線在統(tǒng)一技術(shù)作業(yè)過程中相互配合條件之研究[C].北京鐵道學(xué)院第一次科學(xué)討論會(huì)論文選集(鐵道運(yùn)輸部分)，1956.

[2]李文權(quán)，杜文.樹枝狀鐵路專用線取送車問題的數(shù)學(xué)模型及算法[J].河南大學(xué)學(xué)報(bào)(自然科學(xué)版)，1997，27(2)：11-8.

[3]徐忠民，孔慶鈴.直達(dá)列車取送車順序的優(yōu)化[J].北方交通大學(xué)學(xué)報(bào)，1988.2：70-74.

[4]曾凡超.車輛路徑問題的改進(jìn)遺傳算法[D].重慶：重慶大學(xué)，2007.

[5]占焱發(fā).基于遺傳算法的物流配送車輛路徑問題研究[D].西安：長安大學(xué)，2010.

[6]玄光男，程潤偉.遺傳算法與工程優(yōu)化[M].北京：清華大學(xué)出版社，2004.

Research on Vehicle Pick-up and Return Plan of Railway Technical Station Based on Genetic Algorithm

XUE Yu-xi，ZHU Hai-xiao，GAN Bao，HAN Yu-rui

(School of Traffic and Transportation，Lanzhou Jiaotong University，Lanzhou，Gansu，730070)

Abstract：In order to study more realistic and reasonable preparation for vehicle pick-up and return plan of railway technical station，then under the constraints of considering the machine towing capacity of and vehicle capacity limitations of loading/unloading lines，with the priority pickup and return grouping as the premise，and within the pickup/return control time window，this article established the concept model for the pickup/return optimization of vehicle groups stored in the station and vehicle groups arriving with the minimum machine pickup/return cost as the goal，and used the improved genetic algorithm for the solu-tions.Through the solutions of numerical examples，it verified the correctness of this model and the va-lidity of this algorithm.

Keywords：Vehicle pick-up and return；Time window；Radioactive dedicated line；Genetic algorithm；In-teger coding

文章編號(hào)：1673-4874(2015)12-0053-05

中圖分類號(hào)：U292.2+9

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.13282/j.cnki.wccst.2015.12.013

作者簡介

收稿日期：2015-11-18