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

李紅啟 呂 潭

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

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

1 問題特點與數學模型

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

設定以下變量：rij為節點i到j的運輸需求，為牽引車獨自在節點i與j間行駛的油耗量，表示牽引車拖帶載貨半掛車在節點i與j間行駛的油耗量，tij為車輛在節點i與j間的行駛時間，H為所需牽引車總數，D1和D2分別為某條牽引車運行路線的運距的下限和上限.

MD－ILTRP數學模型如下.

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

2 求解算法設計

2.1 染色體編碼和結構設置

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

2.2 初始種群

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

1）隨機選擇某一專業化場站a（節點1或2或…或m）作為牽引車路線的第一個點.

2）選擇不同于a的一個點b，判斷a與b之間是否有運輸需求.當a與b之間有運輸需求時，若b為專業化場站，則以概率p1選擇b；若b為客戶點，以概率p2選擇b；當a與b之間無運輸需求時，以概率p3選擇b.搜索所有可用的節點b，若都未成功選取，則隨機生成b.

3）計算路線a—b—d（d為場站）的運距，當增加點c（搜索所有不同于b的點）使a—b—c—d的運距超出約束時，確定a—b—d作為一條路線；否則，以第2步的方法繼續增加路線中的點.

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

2.3 適應度函數

本文選取以下形式的適應度函數.

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

2.4 遺傳操作

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

3）變異操作 設定一個較小的變異概率Pm；針對種群中每個染色體的任意非0且非路線兩段的基因位的數值進行操作.隨機生成一個［0，1］區間的浮點數p，當p＜Pm時，隨機生成一個不等于該基因位原來數值且不同于前后基因位數值的點序號，代替該基因位的數值.

2.5 主要參數設置及終止條件

參照本文針對若干算例的試算經驗，設定染色體的長度為運輸需求總數的5～10倍，種群的大小設定為運輸需求總數的2～4倍.變異操作中的Pm值設定為0.05左右.

“先破壞后重組”操作是整個算法中的關鍵部分，其發生概率Pd的設置至關重要.在遺傳進化前期，個體的適應度一般較低，Pd取較大值可擴大搜索范圍；而在進化后期，較大的Pd很可能破壞已產生的優良個體.本文采用自適應式的破壞重組概率.

式中：Pdmax與Pdmin分別為最大和最小破壞重組概率；t為當前進化代數；T為設定最大進化代數.本文以進化代數達到設定最大進化代數作為算法的終止條件.

3 算例設計及其求解

參照文獻［9］提供的單場站小規模隨機算例，對其中數個算例采用隨機方式選取某個節點作為另一個場站，從而將這些算例改變為雙場站隨機算例.借助CPLEX12.4求解 MD－ILTRP問題數學模型獲得算例的精確解，借助GA算法尋求算例的滿意解，并同時與文獻［9］提供的精確解進行對比，計算結果見表1.

表1 小規模隨機算例求解結果一覽

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

4 結束語

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

［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］梁 波.大型鋼鐵企業廠內車輛循環甩掛運輸模式研究［D］.長沙：中南大學，2009.

［8］裴育希.大型鋼鐵企業甩掛運輸實證研究［D］.太原：山西大學，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.