基于遺傳算法的鐵路技術站取送車計劃研究

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

(蘭州交通大學　交通運輸學院，甘肅　蘭州　730070)

基于遺傳算法的鐵路技術站取送車計劃研究

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

(蘭州交通大學交通運輸學院，甘肅蘭州730070)

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

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

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

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

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

關鍵詞：取送車；時間窗；放射性專用線；遺傳算法；整數編碼

0引言

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

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

1取送車問題的概念模型

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

1.1　變量及含義說明

為描述模型和構造解的方便，設定如下變量：

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

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

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

(10)用s表示某一車組的一項作業，設共有n項工作，送車和取車各算一項工作，一個編號唯一對應一個車組的一項工作，從而s=1，2，…，n。

(14)調機送車包含挑選車組、對貨位，取車包含收集車輛和分解車組的工作，用t0表示在車站內的消耗時間，t1表示在專用線上消耗的時間。

(15)M：調機最大牽引能力。

(16)B：計劃階段總時間。

(17)e0：調機的單位小時取送成本；e1：超過時間后的單位小時懲罰成本。

(18)y0：調機實際的總工作時間。

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

綜上，每一項作業都有一個編號s，而每個編號都唯一對應一個數組：

調車作業需要滿足一定的時間窗約束，現推導不同工作的取送控制時間窗：

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

1.2　概念模型的建立

(1)解的形式

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

該編碼方式雖然不能一眼看出調機工作內容，但易于解碼還原，可以用遺傳算法來求解。每一個編碼都唯一對應一個問題的解，任意解都對應著一個編碼，這些都符合編碼的不冗余性、合法性和完備性要求，且利于遺傳算法求解時的操作。

(2)方案值計算函數

函數1批次劃分函數

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

函數2每批作業取送車數計算函數

對已經劃分批次的取送作業方案，求得每一個批次的取送作業中，調車機車所牽引的車輛數，包括送車作業的車輛數和取車作業的車輛數，并將其值返回主調函數。

函數3調機牽引能力判斷函數

判斷每一批次的取送作業中，調車機車所牽引的車輛數是否超出了機車的最大牽引能力M，若超出給主調函數返回0，否則返回1。

函數4專用線容車限制判斷函數

判斷某批次的行車作業中，調車機車牽引的車輛數加上專用線原有的車輛數是否會超出專用線的容車能力限制，若超出給主調函數返回0，否則返回1。

函數5取送時刻判斷函數

函數6方案值計算主函數

輸入：解序列

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

Step2：調用函數1，對初始解劃分批次，記錄最大批次max g；對每個批次判斷批次規模Bg。

Step3：調用函數2，計算每批次的送、取車數。

Step4：調用函數3，判斷每批次是否超過調機牽引能力；若未超出轉step6；否則，將該初始解放入第二類不可行解集合內，結束。

Step5：調用函數4，判斷每批次是否超過專用線容車量；若未超出轉step7；否則，將該初始解放入第二類不可行解集合內，結束。

Step6：調用函數5，判斷取送作業時刻是否滿足時間窗，并記錄每批作業的離站時間和返站時間；若滿足轉step8；否則，將該初始解放入第三類不可行解集合內，結束。

Step7：計算調機總取送時間y0。

y1=y0-B；

3算法描述及改進

由于遺傳算法本身的高度并行、隨機、自適應等優點，本文用改進的遺傳算法求解。

(1)初始群體的產生

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

(2)交叉操作

交叉操作用于組合出新的個體，并使算法能夠搜索更多的解[4]。本文中選擇部分映射交叉。先任選兩個交叉點，交換兩個個體交叉點之間的基因片段，對于原有基因，如果與交換過來的基因片段不沖突則保留，否則通過映射來找交換所得基因原位置的基因，直到沒有沖突基因為止。

(3)變異操作

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

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

互換變異，將送、取作業顛倒變為可行方案；第二類是不滿足調機、專用線容量限制采用隨機互換變異，將大規模的批次分開作業，使其滿足約束，成為可行解；第三類是不滿足最晚編組時刻，采用向前插入變異，即將該工作的順序提前從而滿足時刻，成為可行解。

(4)選擇和替換操作

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

(5)算法終止條件

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

4算例分析

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

表1　專用線車組信息表

表2　到達車組信息表

首先需要按照時段對各作業編上唯一的編號，如表3所示。

表3　工作編號表

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

X1=1531281620621410139172471921252218411231526

X2=1531281620621410139172471921252241811231526

兩等值方案中，雖然調機最終的取送離站與返站時間相同，但方案2少一個批次，從調機能耗方面顯然優于方案1，之所以全部取送完成返站時間相同，是方案2在1專用線等取車組23。

實際作業時，可以進行調整，讓調機在做完第10批作業以后，可以先做取送以外的調車工作，如輔助解體、編組等，在第686 min時開始第11批作業，達到1專用線時車組23剛好作業完畢取回，然后緊接著做第12批作業。調整以后取送調機多出近1 h時間輔助其他調機作業，合理利用了調機能力，加強了各作業間的協調配合。調整前調機總取送工作時間678 min，成本是203.4元，調整之后總取送時間為624 min，總取送成本187.2元。因此，現場操作時，可以按照表4所示時間及內容進行取送作業。

表4　取送批次及時機數值表

計劃時段起始時間為6：00，而第一批作業開始時間為7：32，另外第10批和第11批作業之間也有空閑時間，取送調機可以輔助其他調機作業。

5結語

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

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

(1)在建立模型的假設中，將調機的走行時間假設為定值，不符合實際。

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

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

參考文獻

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

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

[3]徐忠民，孔慶鈴.直達列車取送車順序的優化[J].北方交通大學學報，1988.2：70-74.

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

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

[6]玄光男，程潤偉.遺傳算法與工程優化[M].北京：清華大學出版社，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

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

中圖分類號：U292.2+9

文獻標識碼：A

DOI：10.13282/j.cnki.wccst.2015.12.013

作者簡介

收稿日期：2015-11-18