多場站城際干線甩掛牽引車調(diào)度問題及求解＊

李紅啟 呂 潭

（北京航空航天大學(xué)交通科學(xué)與工程學(xué)院 北京 100191）

迄今學(xué)術(shù)界在甩掛運(yùn)輸汽車列車調(diào)度問題方面的研究成果主要體現(xiàn)為3類：（1）針對(duì)卡車與全掛車組合而成汽車列車調(diào)度的TTRP問題，研究成果以文獻(xiàn)［1－3］等為代表；（2）針對(duì)城市垃圾運(yùn)輸過程的牽引車加掛半掛車組合而成汽車列車調(diào)度的RRVRP問題，研究成果以文獻(xiàn)［4－6］等為代表；（3）針對(duì)廠內(nèi)（局部）運(yùn)輸過程的牽引車加掛半掛車組合而成汽車列車調(diào)度問題，研究成果以文獻(xiàn)［7－8］等為代表；以及針對(duì)城際干線運(yùn)輸過程的牽引車加掛半掛車組合而成汽車列車調(diào)度的TSRP問題［9］.本文定位于多場站的、城際干線運(yùn)輸背景下的牽引車調(diào)度這一問題，建立一類公路牽引車調(diào)度問題數(shù)學(xué)模型，設(shè)計(jì)基于遺傳算法的求解算法，并輔以算例分析.

1 問題特點(diǎn)與數(shù)學(xué)模型

多場站的城際干線甩掛運(yùn)輸牽引車調(diào)度問題（multi－depot intercity line－h(huán)aul tractor routing problem，MD－ILTRP）有以下基本特征：（1）“多對(duì)多”的運(yùn)輸需求.多個(gè)專業(yè)化場站（記數(shù)量為m）可保有大量牽引車，是牽引車運(yùn)行路線的始發(fā)終到點(diǎn).每個(gè)專業(yè)化場站可輻射服務(wù)若干個(gè)客戶點(diǎn)，客戶點(diǎn)的運(yùn)輸需求以載貨半掛車為單位，任意2個(gè)客戶點(diǎn)之間都可以有任意數(shù)量的運(yùn)輸需求.記所有客戶點(diǎn)數(shù)量為n；（2）限定運(yùn)距和開放路線.路線是開放的，且路線的運(yùn)距在一個(gè)合理的范圍內(nèi)，允許牽引車在同一運(yùn)行路線中多次進(jìn)出不同的專業(yè)化場站和特定客戶點(diǎn).牽引車運(yùn)行形式只有兩種，牽引車獨(dú)自行駛，牽引車拖掛載貨半掛車行駛；（3）車型匹配和常量設(shè)定.牽引車和半掛車車型滿足匹配性要求.設(shè)定牽引車獨(dú)自行駛和拖掛載貨半掛車行駛的平均速度為常量，設(shè)定牽引車獨(dú)自行駛或拖掛載貨半掛車行駛的百公里油耗量為常量，設(shè)定載貨半掛車的額定載重量和貨物實(shí)載率為常量；（4）效率型目標(biāo)函數(shù).MD－ILTRP問題的求解目標(biāo)是“t·km CO2排放量”，旨在明確甩掛運(yùn)輸車輛調(diào)度模式的效率和節(jié)能減排效果.依據(jù)聯(lián)合國政府間氣候變化專門委員會(huì)提供的CO2排放量計(jì)算方法，每燃燒1L柴油排放2 730g CO2.

設(shè)定以下變量：rij為節(jié)點(diǎn)i到j(luò)的運(yùn)輸需求，為牽引車獨(dú)自在節(jié)點(diǎn)i與j間行駛的油耗量，表示牽引車拖帶載貨半掛車在節(jié)點(diǎn)i與j間行駛的油耗量，tij為車輛在節(jié)點(diǎn)i與j間的行駛時(shí)間，H為所需牽引車總數(shù)，D1和D2分別為某條牽引車運(yùn)行路線的運(yùn)距的下限和上限.

MD－ILTRP數(shù)學(xué)模型如下.

式中：（1）為運(yùn)輸需求滿足約束；（2）和（3）要求牽引車路線的始發(fā)終到點(diǎn)為場站.在多場站條件下，允許牽引車路線的始發(fā)終到點(diǎn)可以不是同一場站；（4）為牽引車進(jìn)出場站的度平衡約束；（5）為牽引車進(jìn)出客戶點(diǎn)的度平衡約束；（6）為客戶點(diǎn)的度平衡約束；（7）為牽引車路線的運(yùn)距約束；（8）明確所需牽引車總數(shù)，「·?和?·」分別表示向上和向下取整.

2 求解算法設(shè)計(jì)

2.1 染色體編碼和結(jié)構(gòu)設(shè)置

MD－ILTRP問題的求解結(jié)果為由專業(yè)化場站和客戶點(diǎn)組成的點(diǎn)的序列，可將一組可行解排列在一起組成一個(gè)染色體基因序列.當(dāng)有m個(gè)專業(yè)化場站（1，2，…，m）以及n個(gè)客戶點(diǎn)時(shí)，為避免將不同路線組合在一起時(shí)無法以專業(yè)化場站作為不同路線區(qū)分節(jié)點(diǎn)的問題，在構(gòu)造染色體時(shí)添加一個(gè)虛擬節(jié)點(diǎn)0.染色體的形式為“0—（場站1或2或…或m）—客戶點(diǎn)i—…—客戶點(diǎn)j—（場站1或2或…或m）—0—（場站1或2或…或m）—客戶點(diǎn)k—…—客戶點(diǎn)l—（場站1或2或…或m）—0”.

2.2 初始種群

考慮到MD－ILTRP中運(yùn)輸需求分布于路段上的特點(diǎn)，本文以概率選擇方式生成染色體.

1）隨機(jī)選擇某一專業(yè)化場站a（節(jié)點(diǎn)1或2或…或m）作為牽引車路線的第一個(gè)點(diǎn).

2）選擇不同于a的一個(gè)點(diǎn)b，判斷a與b之間是否有運(yùn)輸需求.當(dāng)a與b之間有運(yùn)輸需求時(shí)，若b為專業(yè)化場站，則以概率p1選擇b；若b為客戶點(diǎn)，以概率p2選擇b；當(dāng)a與b之間無運(yùn)輸需求時(shí)，以概率p3選擇b.搜索所有可用的節(jié)點(diǎn)b，若都未成功選取，則隨機(jī)生成b.

3）計(jì)算路線a—b—d（d為場站）的運(yùn)距，當(dāng)增加點(diǎn)c（搜索所有不同于b的點(diǎn)）使a—b—c—d的運(yùn)距超出約束時(shí)，確定a—b—d作為一條路線；否則，以第2步的方法繼續(xù)增加路線中的點(diǎn).

4）搜索需求矩陣，判斷是否存在非零項(xiàng).若存在非零項(xiàng)，則通過以上三步產(chǎn)生新路線；若不存在非零項(xiàng)，則路線生成過程結(jié)束，將各條路線組合在一起并在首尾以0加以區(qū)分.

2.3 適應(yīng)度函數(shù)

本文選取以下形式的適應(yīng)度函數(shù).

式中：M為足夠大的正數(shù)；κ為整數(shù)；p為懲罰數(shù).

2.4 遺傳操作

2）“先破壞后重組”操作 采用“先破壞后重組”的方法進(jìn)行交叉操作，具體如下：（1）搜索染色體上作為路線分隔的所有“0”點(diǎn)，隨機(jī)選擇其中的兩個(gè)并將染色體從這兩個(gè)點(diǎn)處斷裂；（2）將破壞操作產(chǎn)生的染色體段作為新染色體的開始段，根據(jù)染色體段中的路線情況對(duì)需求矩陣進(jìn)行處理，運(yùn)用概率選擇生成的方法產(chǎn)生染色體的后半段.

3）變異操作 設(shè)定一個(gè)較小的變異概率Pm；針對(duì)種群中每個(gè)染色體的任意非0且非路線兩段的基因位的數(shù)值進(jìn)行操作.隨機(jī)生成一個(gè)［0，1］區(qū)間的浮點(diǎn)數(shù)p，當(dāng)p＜Pm時(shí)，隨機(jī)生成一個(gè)不等于該基因位原來數(shù)值且不同于前后基因位數(shù)值的點(diǎn)序號(hào)，代替該基因位的數(shù)值.

2.5 主要參數(shù)設(shè)置及終止條件

參照本文針對(duì)若干算例的試算經(jīng)驗(yàn)，設(shè)定染色體的長度為運(yùn)輸需求總數(shù)的5～10倍，種群的大小設(shè)定為運(yùn)輸需求總數(shù)的2～4倍.變異操作中的Pm值設(shè)定為0.05左右.

“先破壞后重組”操作是整個(gè)算法中的關(guān)鍵部分，其發(fā)生概率Pd的設(shè)置至關(guān)重要.在遺傳進(jìn)化前期，個(gè)體的適應(yīng)度一般較低，Pd取較大值可擴(kuò)大搜索范圍；而在進(jìn)化后期，較大的Pd很可能破壞已產(chǎn)生的優(yōu)良個(gè)體.本文采用自適應(yīng)式的破壞重組概率.

式中：Pdmax與Pdmin分別為最大和最小破壞重組概率；t為當(dāng)前進(jìn)化代數(shù)；T為設(shè)定最大進(jìn)化代數(shù).本文以進(jìn)化代數(shù)達(dá)到設(shè)定最大進(jìn)化代數(shù)作為算法的終止條件.

3 算例設(shè)計(jì)及其求解

參照文獻(xiàn)［9］提供的單場站小規(guī)模隨機(jī)算例，對(duì)其中數(shù)個(gè)算例采用隨機(jī)方式選取某個(gè)節(jié)點(diǎn)作為另一個(gè)場站，從而將這些算例改變?yōu)殡p場站隨機(jī)算例.借助CPLEX12.4求解 MD－ILTRP問題數(shù)學(xué)模型獲得算例的精確解，借助GA算法尋求算例的滿意解，并同時(shí)與文獻(xiàn)［9］提供的精確解進(jìn)行對(duì)比，計(jì)算結(jié)果見表1.

表1 小規(guī)模隨機(jī)算例求解結(jié)果一覽

隨機(jī)算例求解結(jié)果顯示：（1）本文求解 MDILTRP的GA算法能夠獲得滿意解，滿意解與相應(yīng)精確解之間的誤差大多保持在10%以內(nèi)；（2）相比于單場站情形，盡管新增設(shè)場站會(huì)導(dǎo)致基礎(chǔ)設(shè)施建設(shè)投入的增加，但增加場站數(shù)量有助于降低牽引車使用量，也有助于提高運(yùn)輸效率（表1第3和5列對(duì)比，即第9列）；（3）算例中場站位置布局是隨機(jī)的，一些特殊的場站選址明顯影響著計(jì)算結(jié)果.如算例 RAND7－1，RAND7－2和 RAND8－2的計(jì)算效果不佳，而這些算例中場站多位于研究區(qū)域的邊界.

4 結(jié)束語

本文針對(duì)多場站情景下的城際干線甩掛運(yùn)輸過程所用的公路牽引車的優(yōu)化調(diào)度問題（MD－IL－TRP問題）開展研究.該問題的基本特征包括：貨運(yùn)需求為“多對(duì)多”式、以載貨半掛車為計(jì)量單位，路線是開放的、且運(yùn)距在一個(gè)合理的范圍內(nèi)，優(yōu)化目標(biāo)為貨運(yùn)噸公里碳排放量最小化.算例求解結(jié)果顯示，本文所設(shè)計(jì)的模型與基于遺傳算法的求解流程是可行和有效的；此外，多場站體系有助于減少甩掛運(yùn)輸車輛使用量和提高貨運(yùn)效率.后續(xù)研究工作可從多個(gè)角度展開，如：增加時(shí)間窗等約束而形成新的模型，尋求求解效率和效果更好的混合啟發(fā)式算法，等等.

［1］CHAO I M.A tabu search method for the truck and trailer routing problem［J］.Computers ＆ Operations Research，2002，29（1）：33－51.

［2］LIN S W，YU V F，CHOU S Y.Solving the truck and trailer routing problem based on a simulated annealing heuristic［J］.Computers ＆ Operations Research，2009，36（5）：1683－1692.

［3］VILLEGAS J G，PRINS C，PRODHON C，et al.A matheuristic for the truck and trailer routing problem［J］.European Journal of Operational Research，2013，230（2）：231－244.

［4］BODIN L，MINGOZZI A，BALDACCI R，et al.The rollon－rolloff vehicle routing problem ［J］.Transportation Science，2000，34（3）：271－288.

［5］DERIGS U，PULLMANN M，VOGEL U.A short note on applying a simple LS／LNS－based metaheuristic to the rollon－rolloff vehicle routing problem ［J］.Computers ＆ Operations Research，2013，40（3）：867－872.

［6］WY J，KIM B I.A hybrid metaheuristic approach for the rollon－rolloff vehicle routing problem ［J］.Computers ＆ Operations Research，2013，40（8）：1947－1952.

［7］梁 波.大型鋼鐵企業(yè)廠內(nèi)車輛循環(huán)甩掛運(yùn)輸模式研究［D］.長沙：中南大學(xué)，2009.

［8］裴育希.大型鋼鐵企業(yè)甩掛運(yùn)輸實(shí)證研究［D］.太原：山西大學(xué)，2012.

［9］LI H Q，LI Y，ZHAO Q，et al.The tractor and semitrailer routing considering carbon dioxide emissions［J］.Mathematical Problems in Engineering，2013（S1）：1－12.