基于遺傳算法的鐵路集裝箱裝卸門(mén)吊作業(yè)優(yōu)化研究

何 濤，李可佳

(中國(guó)鐵道科學(xué)研究院集團(tuán)有限公司 運(yùn)輸及經(jīng)濟(jì)研究所，北京 100081)

集裝箱運(yùn)輸是鐵路現(xiàn)代物流的重要組成部分，按照鐵路現(xiàn)代物流發(fā)展規(guī)劃，我國(guó)鐵路正在加快發(fā)展集裝箱運(yùn)輸，“十三五”以來(lái)鐵路集裝箱運(yùn)量占貨運(yùn)量的比例不斷升高[1]。隨著集裝箱運(yùn)輸?shù)陌l(fā)展，提高鐵路集裝箱門(mén)吊裝卸作業(yè)效率，降低裝卸線裝卸成本成為當(dāng)前亟需解決的問(wèn)題[2]。集裝箱門(mén)吊裝卸的最大作業(yè)時(shí)間影響列車(chē)的行車(chē)計(jì)劃、裝卸資源作業(yè)量的均衡性和裝卸作業(yè)效率，而目前鐵路集裝箱門(mén)吊裝卸多通過(guò)人工進(jìn)行選箱，由司機(jī)操作門(mén)吊進(jìn)行裝箱和卸箱作業(yè)，存在翻箱倒箱率高、工作效率低等問(wèn)題[3]。由于鐵路集裝箱裝卸線門(mén)吊裝車(chē)作業(yè)過(guò)程是門(mén)吊將停放在集裝箱箱區(qū)的各個(gè)集裝箱按照一定的順序吊裝到裝卸線集裝箱平車(chē)相應(yīng)的預(yù)期位置上(門(mén)吊卸車(chē)作業(yè)將裝車(chē)作業(yè)逆向操作)，由于各集裝箱所在位置不同，各個(gè)集裝箱在平車(chē)上預(yù)期位置也不同，因而不同集裝箱吊裝順序會(huì)導(dǎo)致門(mén)吊運(yùn)行軌跡不同，從而導(dǎo)致門(mén)吊運(yùn)行總距離不同。因此，集裝箱吊裝順序是影響門(mén)吊運(yùn)行總距離的原因，找到最優(yōu)集裝箱吊裝順序則可以得到最短門(mén)吊運(yùn)行總距離。假設(shè)門(mén)吊運(yùn)行速度是一定的，當(dāng)門(mén)吊運(yùn)行距離最小時(shí)，集裝箱裝卸時(shí)間最短，門(mén)吊裝卸作業(yè)效率最高。集裝箱裝卸作業(yè)優(yōu)化過(guò)程找集裝箱吊裝最優(yōu)順序?qū)儆贜P-hard組合優(yōu)化問(wèn)題，研究采用遺傳算法優(yōu)化鐵路集裝箱裝卸線裝卸作業(yè)流程。

1 鐵路集裝箱裝卸門(mén)吊作業(yè)優(yōu)化模型建立

1.1 問(wèn)題描述

鐵路集裝箱裝卸門(mén)吊作業(yè)優(yōu)化模型的優(yōu)化目標(biāo)是軌道門(mén)吊裝卸一列車(chē)集裝箱時(shí)運(yùn)行距離最短，即找出集裝箱裝卸作業(yè)過(guò)程中軌道門(mén)吊裝卸集裝箱的最優(yōu)裝卸序列。由于集裝箱裝車(chē)和卸車(chē)是可逆過(guò)程，對(duì)優(yōu)化模型的應(yīng)用沒(méi)有影響，因而以軌道門(mén)吊裝箱過(guò)程為例，在模型中做出以下假設(shè)：①任何集裝箱裝卸序列都沒(méi)有安全問(wèn)題；②集裝箱在裝卸區(qū)域的堆存位置已知；③集裝箱在列車(chē)上的期望位置已知；④在裝卸作業(yè)過(guò)程中，軌道門(mén)吊連續(xù)作業(yè)不存在中途改變作業(yè)位置的情況；⑤要吊裝的集裝箱已經(jīng)全部存放于集裝箱箱區(qū)[4]。因此，可以根據(jù)集裝箱位置信息和集裝箱在列車(chē)上的期望位置信息計(jì)算軌道門(mén)吊吊裝集裝箱運(yùn)行距離和空載運(yùn)行距離，以軌道門(mén)吊運(yùn)行總距離最短為目標(biāo)函數(shù)，以所有集裝箱吊裝完畢為約束條件，建立集裝箱裝卸軌道門(mén)吊作業(yè)優(yōu)化模型。

1.2 門(mén)吊作業(yè)優(yōu)化模型構(gòu)建

按自然數(shù)序列對(duì)待裝車(chē)的集裝箱進(jìn)行編號(hào)，箱號(hào)i= 1，2，…，n，其中n為集裝箱總數(shù)；按自然數(shù)序列對(duì)車(chē)輛進(jìn)行編號(hào)，車(chē)號(hào)k= 1，2，…，q，其中q為車(chē)輛總數(shù)；按自然數(shù)序列對(duì)列車(chē)上集裝箱預(yù)期位置進(jìn)行編號(hào)，集裝箱預(yù)期位置e= 1，2，…，m，其中m為列車(chē)上集裝箱預(yù)期位置總數(shù)。

以門(mén)吊的起始點(diǎn)作為坐標(biāo)原點(diǎn)，X軸為門(mén)吊運(yùn)行方向，Y軸為門(mén)吊小車(chē)的運(yùn)行方向，構(gòu)建鐵路集裝箱裝卸線的平面坐標(biāo)圖。車(chē)輛位置和集裝箱位置示意圖如圖1所示。

記車(chē)輛上集裝箱預(yù)期位置中心點(diǎn)坐標(biāo)為(xe，ye)，其中e為集裝箱預(yù)期位置；設(shè)集裝箱堆存位置中心點(diǎn)坐標(biāo)為(xi，yi)。按照假設(shè)，已知集裝箱位置和預(yù)期位置的情況下，集裝箱在裝卸線上裝車(chē)過(guò)程中，門(mén)吊吊裝集裝箱i從集裝箱箱區(qū)到對(duì)應(yīng)集裝箱平車(chē)預(yù)期位置e上，因而吊裝一個(gè)集裝箱的門(mén)吊運(yùn)行距離就是該集裝箱在箱區(qū)的位置到平車(chē)上集裝箱預(yù)期位置的距離，即門(mén)吊運(yùn)行距離可表示為

式中：Li為箱號(hào)為i的集裝箱吊裝到列車(chē)上對(duì)應(yīng)預(yù)期位置門(mén)吊運(yùn)行距離。

門(mén)吊在吊裝完畢集裝箱i后，從集裝箱i預(yù)期位置運(yùn)行到下一集裝箱所在位置的距離可表示為

式中：Ri為集裝箱預(yù)期位置e到集裝箱號(hào)為i+ 1所在位置的距離。

門(mén)吊裝卸一個(gè)集裝箱的走行距離可表示為

式中：Di為門(mén)吊裝卸一個(gè)集裝箱的走行距離，需要說(shuō)明的是當(dāng)門(mén)吊吊裝到最后一個(gè)集裝箱n時(shí)，門(mén)吊吊裝完畢即為整個(gè)吊裝作業(yè)結(jié)束，門(mén)吊無(wú)需運(yùn)行到下一集裝箱，Dn=Ln。

裝卸優(yōu)化模型可表示為

式中：Z為門(mén)吊裝卸整列車(chē)集裝箱的最小運(yùn)行總距離。

圖1 車(chē)輛位置和集裝箱位置示意圖Fig.1 Locations of trains and containers

2 鐵路集裝箱裝卸門(mén)吊作業(yè)優(yōu)化遺傳算法

由于建立的鐵路集裝箱裝卸線門(mén)吊作業(yè)優(yōu)化模型是一個(gè)組合優(yōu)化模型，屬于NP問(wèn)題[5]，考慮采用遺傳算法進(jìn)行求解。

2.1 編碼方案

將集裝箱吊裝順序用整數(shù)進(jìn)行編碼，門(mén)吊吊裝順序可表示為W：i1—i2—…—in-1—in，其中n為集裝箱總個(gè)數(shù)，需要說(shuō)明的是編碼順序不能重復(fù)，不能缺失。個(gè)體編碼的產(chǎn)生方法為：將輸入的n個(gè)數(shù)字從1到n之間所有數(shù)字隨機(jī)排列，每個(gè)個(gè)體代表一種吊裝順序，每種吊裝順序代表一個(gè)裝載方案，每種方案的路程代價(jià)即個(gè)體適應(yīng)度，路程越短，則代價(jià)越小，個(gè)體適應(yīng)度越高。

2.2 適應(yīng)值計(jì)算和選擇策略

在模型中適應(yīng)值函數(shù)就是目標(biāo)函數(shù)，算法的目標(biāo)是通過(guò)染色體上的基因(每個(gè)基因代表每個(gè)吊裝集裝箱)的交叉和變異進(jìn)行個(gè)體的遺傳[6]，從而計(jì)算出每代個(gè)體的門(mén)吊運(yùn)行總距離，最終經(jīng)過(guò)數(shù)次迭代計(jì)算得到最小門(mén)吊運(yùn)行總距離，即集裝箱裝車(chē)過(guò)程中門(mén)吊運(yùn)行總距離最短，門(mén)吊運(yùn)行總距離最小時(shí)得到的個(gè)體即為最優(yōu)門(mén)吊吊裝順序。

裝卸優(yōu)化模型以遺傳算法為主體，采用精英選擇法，每次迭代過(guò)程中，經(jīng)過(guò)個(gè)體染色體交叉和個(gè)體染色體變異，得到的適應(yīng)值函數(shù)越小，代表個(gè)體適應(yīng)度越高，則個(gè)體遺傳到下一代中的概率越高，而經(jīng)過(guò)迭代得到的適應(yīng)值函數(shù)越大，則個(gè)體適應(yīng)度越低，該個(gè)體被淘汰概率越高[7]。

2.3 交叉算子

選擇2個(gè)父代個(gè)體W1，W2進(jìn)行染色體基因交叉，隨機(jī)選擇染色體上的交叉點(diǎn)進(jìn)行位置交換，生成2個(gè)子代個(gè)體W1'，W2

'，判斷2個(gè)父代W1，W2是否可交叉得到有效的子代染色體，如果交叉后染色體中出現(xiàn)重復(fù)的數(shù)字，相當(dāng)于對(duì)已經(jīng)吊裝完畢的集裝箱進(jìn)行重復(fù)吊裝，而忽略了有些集裝箱沒(méi)有吊裝，是無(wú)效的方案，這種情況下不生成子代個(gè)體。當(dāng)生成2個(gè)有效子代個(gè)體時(shí)進(jìn)行下一次交叉[8]。

2.4 變異算子

選擇個(gè)體染色體上2個(gè)不同基因進(jìn)行交換，按照一定基因突變概率使參數(shù)染色體發(fā)生基因突變得到突變后的子代染色體，即將門(mén)吊吊裝順序中的2個(gè)集裝箱進(jìn)行交換，生成新的集裝箱吊裝順序。

3 計(jì)算實(shí)例

設(shè)集裝箱箱區(qū)有30個(gè)隨機(jī)擺放的20 ft集裝箱，n= 30；裝車(chē)線上有15輛NX17型空車(chē)，q= 15；每輛車(chē)上有2個(gè)集裝箱位置，預(yù)期位置m= 30。集裝箱在箱區(qū)位置和在車(chē)上預(yù)期位置如表1所示。

應(yīng)用裝卸優(yōu)化模型和遺傳算法，在Matlab R2018b軟件環(huán)境下進(jìn)行計(jì)算，其中參數(shù)設(shè)置為群體大小popsize= 100；迭代次數(shù)MaxGeneration=500；變異概率pmutation= 0.5；交叉概率crossover probability= 1[9]。模型計(jì)算結(jié)果如圖2所示。

表1 集裝箱在箱區(qū)位置和在車(chē)上預(yù)期位置表Tab.1 Locations of containers in container area and expected locations on trains

按照算例中的集裝箱位置和預(yù)期位置，應(yīng)用遺傳算法進(jìn)行286次迭代后門(mén)吊將全部集裝箱吊裝完畢的運(yùn)行最短距離Z= 2 463 m，而按照箱號(hào)依次吊裝時(shí)門(mén)吊的運(yùn)行總距離為3 300 m，門(mén)吊運(yùn)行距離縮短了25.4%，因而最優(yōu)集裝箱吊裝順序?yàn)?9—7—2—16—22—17—20—21—5—8—26—1—3—6—11—24—4—23—13—18—15—12—9—14—19—25—27—10—28—30。

算例表明，在集裝箱門(mén)吊作業(yè)流程中，相比較于傳統(tǒng)作業(yè)方式，應(yīng)用鐵路集裝箱裝卸門(mén)吊作業(yè)優(yōu)化模型可以減少門(mén)吊裝卸整列車(chē)集裝箱的最小運(yùn)行總距離Z，從而減少集裝箱門(mén)吊作業(yè)時(shí)間，提高鐵路集裝箱裝卸門(mén)吊作業(yè)效率。

圖2 模型計(jì)算結(jié)果Fig.2 Calculation results

4 結(jié)束語(yǔ)

隨著我國(guó)鐵路集裝箱運(yùn)輸?shù)母咚侔l(fā)展，我國(guó)鐵路集裝箱運(yùn)量逐步提升?；谶z傳算法的鐵路集裝箱裝卸作業(yè)優(yōu)化研究通過(guò)尋找最優(yōu)集裝箱吊裝順序得出門(mén)吊運(yùn)行總距離，進(jìn)一步提高鐵路集裝箱運(yùn)輸能力，節(jié)約運(yùn)輸成本，提升鐵路運(yùn)輸效率效益，為鐵路集裝箱裝卸線門(mén)吊作業(yè)優(yōu)化提供理論方法支持。另外，還需要對(duì)鐵路集裝箱運(yùn)輸過(guò)程中翻箱、集卡運(yùn)輸?shù)茸鳂I(yè)流程進(jìn)行深入研究，從而更進(jìn)一步提高鐵路集裝箱運(yùn)輸效率。