基于甩掛運輸組織的車輛路徑優(yōu)化

李維　成耀榮　吳百珂

摘 要：傳統(tǒng)大型制造業(yè)內(nèi)部運輸成本較高。文章針對運輸任務(wù)對車輛具有獨占性的特點及甩掛運輸?shù)慕M織特性，分析得到總運輸費用的大小取決于車輛的空車運行費用。在此基礎(chǔ)上，將原有的甩掛運輸任務(wù)問題轉(zhuǎn)換為經(jīng)典的TSP問題。建立了相應(yīng)的數(shù)學(xué)模型，并設(shè)計了改進的自適應(yīng)遺傳。

關(guān)鍵詞：甩掛運輸；車輛路徑；遺傳算法

中圖分類號：U116.2 文獻標(biāo)識碼：A

Abstract： The cost of internal transport in traditional large manufacturing is very high. In this paper， according to the characteristics of the transport task for the exclusive vehicle and the organization characteristics of trailer pick-up transport， the total transportation cost is determined by the empty running cost of vehicles. On this basis， transform the original task of trailer pick-up transport into a classic TSP problem. The corresponding mathematical model is established and an improved adaptive genetic algorithm is designed.

Key words： trailer pick-up transport； vehicle routing； genetic algorithm

在制造業(yè)生產(chǎn)過程中，根據(jù)生產(chǎn)流程和工藝需要將分布在廠區(qū)不同地理位置上的原材料、再制品與半成品、產(chǎn)成品以及回收物料通過廠內(nèi)車輛及時運送到各車間保證生產(chǎn)的正常進行。因此，在生產(chǎn)車間既需要將該車間生產(chǎn)完成的物料運送到下一工序車間，同時也需要將本車間生產(chǎn)所需要的原材料及時送達(dá)。因為甩掛運輸?shù)奶厥庑?，牽引車從某個車間掛上掛車出發(fā)后，甩掛車輛進行組合運行的目的地必然是此掛車所在貨物所對應(yīng)的卸貨點。在任務(wù)開始的最初時刻，所有牽引車輛都位于中心車場，掛車已經(jīng)分配在各客戶點。大型生產(chǎn)企業(yè)場內(nèi)甩掛運輸組織問題，實際上是屬于車輛調(diào)度（VSP）范疇。因為各環(huán)節(jié)搭接的時間有限，所以甩掛模式通常是大型制造業(yè)場內(nèi)運輸?shù)闹饕Ｊ?。國?nèi)外學(xué)者在車輛調(diào)度（Vehicle Scheduling Problem， VSP）方面取得了較多的理論和實際成果[1-3]。在國外TTRP（Truck and Trail Routing Problem）定義為甩掛運輸問題。這類問題涉及到運輸與生產(chǎn)計劃的協(xié)調(diào)、掛車和牽引車在運輸任務(wù)的組織、車輛的行駛路徑規(guī)劃與行駛時間的安排問題。此類問題的優(yōu)化目標(biāo)：在滿足運輸要求下，如何有效組織牽引車和掛車的使用，使得總運輸成本最小[4]。

1 問題描述

節(jié)點Ni為裝貨點，以i為索引卸貨地點為Nn+i。車庫點為0。這樣就區(qū)分了任務(wù)點、裝卸貨點以及其他的點。N

=0，1，…，n，…，2n為所有運輸節(jié)點的集合，p =1，2，…，n為裝貨點集合，D =n+1，n+2，…，2n為卸貨點集合。值得注意的是，不同的點可能帶有相同的物理位置，也就是說有的點可能是虛擬的點。帶時間窗的車輛路徑問題在每個任務(wù)點有硬時間窗e ，l ，最早到達(dá)時間e ，最晚到達(dá)時間l 。c 、t 為對應(yīng)兩點間的車輛行駛費用、時間。q 為客戶i要求從節(jié)點Ni運到節(jié)點Nn+i的運輸量，中間過程不允許服務(wù)別的客戶。對于不能一次完成運輸?shù)娜蝿?wù)，將視為不同的客戶服務(wù)請求。d 為任意兩點間距離。基于甩掛運輸?shù)奶匦?，本文不考慮裝卸貨時間。

2 概念和假設(shè)

（1）掛車裝載能力相同且最大值為Q ；

（2）牽引車只能牽引一輛掛車；

（3）有足夠多的牽引車和掛車可用；

（4）牽引車從車場出發(fā)完成一系列任務(wù)后最終返回車場；

（5）行駛的費用和時間與距離成正比。

2.1 策略和模型

根據(jù)甩掛運輸?shù)慕M織模式特性，當(dāng)牽引車在某點掛上掛車后，那么牽引車和掛車運行的下一個點必然是該掛車的目的點。因此，總運費的大小將取決于車輛的空車運行費用。對甩掛運輸模型進行一定的變型，將節(jié)點Ni和其運輸目的點Nn+i組合起來看成一個甩掛運輸任務(wù)點N i。如圖1各組合點間以運輸任務(wù)的形式構(gòu)建任務(wù)模型。轉(zhuǎn)化后的問題就是典型的TSP問題[5]。

在一個有向圖G =N ，D 中，N =0，1 ，2 ，…，n ，節(jié)點0表示甩掛運輸車輛所在車場，其他節(jié)點為轉(zhuǎn)化后的運輸任務(wù)節(jié)點，D 為連接任意兩個任務(wù)間的距離。轉(zhuǎn)化后的N i狀態(tài)參數(shù)變?yōu)閑 ，l ， e =e ； l =l ； t =t ；a 車輛k到達(dá)i 點的服務(wù)時間；

c =c 車輛在轉(zhuǎn)化后的點停留時間w =t ； d =d 。綜上所述可將甩掛運輸模型描述為一個經(jīng)典的TSP模型，并便于求解。

決策變量：x = ；y =

minf= c x +λ y （1）

y =1 ？坌i ∈N ＼0 （2）

x = x =y ？坌i ∈N ， ？坌k （3）

ET ≤a +w t ≤LT ？坌i ， j ∈N ， k∈K （4）

x = x =1 k∈K （5）

x ≤S-1， ？坌S？哿N ＼0， S≥2， ？坌k （6）

x ， y =0或1， ？坌i ，j ，k （7）

目標(biāo)函數(shù)（1）總運輸費用最?。患s束條件（2）、（3）表示每個客戶點有且只能被訪問一次；約束條件（4）牽引車服務(wù)客戶j的時間要滿足j點的時間窗要求；約束條件（5）每輛牽引車從車場出發(fā)完成一系列任務(wù)后回到車場；約束條件（6）防止客戶間的子回路。

3 算法設(shè)計

因為將裝貨點i和其卸貨點i+n整合成一個任務(wù)點來建立模型，所以需要對原來運輸網(wǎng)絡(luò)中節(jié)點距離做一些改變，變成甩掛任務(wù)距離矩陣[6-8]。

3.1 任務(wù)距離矩陣生成算法

輸入 原始甩掛運輸網(wǎng)絡(luò)狀態(tài)參數(shù)。

輸出 改造后運輸任務(wù)網(wǎng)絡(luò)G =N ，D 。

開始

確定每個運輸任務(wù)的裝貨點和卸貨點，編制成運輸任務(wù)屬性表；將運輸任務(wù)編號，創(chuàng)建一個空矩陣M。

開始1

對每個運輸任務(wù)，計算該任務(wù)的卸貨點到其他所有運輸任務(wù)裝貨點的距離，按編號將結(jié)果記錄到矩陣M相應(yīng)的行中。

返回1

輸出任務(wù)距離矩陣M。

結(jié)束

獲取甩掛運輸任務(wù)距離矩陣后，選用遺傳算法求解運輸任務(wù)的最佳完成順序。遺傳算法是借助生物進化過程中自然選擇和自然遺傳機制的隨機搜索算法，對解決復(fù)雜和非線性優(yōu)化問題比傳統(tǒng)搜索算法有更強的適應(yīng)能力。

3.2 運輸任務(wù)最佳完成順序生成算法

輸入 任務(wù)距離矩陣M，遺傳算法控制因子MAXGEN、NIND、GGAP、P 、P 等，其他計算系數(shù)如：車輛行駛成本、車輛核載等。

輸出 運輸任務(wù)完成路徑。

開始

確定編碼方案，

生成初始種群。

當(dāng)?shù)螖?shù)gen

開始1

當(dāng)種群m

開始2

計算種群適應(yīng)度值，

選擇操作，

交叉操作，

變異操作，

進化逆轉(zhuǎn)操作。

返回2

算法終止判斷。

返回1

繪制迭代示意圖、目標(biāo)函數(shù)變化圖以及路徑圖。

結(jié)束

3.3 算法關(guān)鍵參數(shù)設(shè)計

選擇操作

選擇操作是從原群體以一定的概率將優(yōu)良個體選擇出來，組成新的種群繁殖得到下一代個體。個體的適應(yīng)度值越高，被選擇的概率越大。選擇算子是計算適應(yīng)度比例的選擇策略，選擇算子：

p = （8）

其中：F 為個體i的適應(yīng)度值，N為種群個體數(shù)目。

（1）交叉操作

交叉操作從種群中隨機選擇兩個個體，通過兩個染色體的交換組合，把父代的優(yōu)良特性遺傳給子代，從而產(chǎn)生新的優(yōu)秀個體。由于個體采用實物編碼，所以交叉操作采用實數(shù)交叉法，第k個染色體a 和第l個染色體a 在j位的交叉變換為：

a =a 1-b+a b （9）

a =a 1-b+a b （10）

其中：b是0，1區(qū)間的隨機數(shù)。

（2）變異操作

變異操作主要是為了維持種群的多樣性。進行變異操作，首先從種群中隨機選取一個個體，選擇該個體基因中的一點進行變異以產(chǎn)生更優(yōu)秀的個體。第i個個體的第j個基因a 進行變異的操作：

a = （11）

其中：a 是基因a 的上界，a 是基因a 的下界，fg=r 1-g/G ，r 是一個隨機數(shù)，g是當(dāng)前的迭代次數(shù)，G 是最大進化次數(shù)，r為0，1區(qū)間的隨機數(shù)。

（3）進化逆轉(zhuǎn)操作

在選擇、交叉、變異之后，進行多次單方向的逆轉(zhuǎn)操作來改善遺傳算法的局部搜索能力，在逆轉(zhuǎn)操作后，只有適應(yīng)度值提高的才接受該逆轉(zhuǎn)，否則逆轉(zhuǎn)無效。例如在1，10隨機產(chǎn)生兩個數(shù)4和7，在一條染色體確定兩個位置，將其位置調(diào)換。

9 5 1 | 7 3 8 | 6 10 4 2

逆轉(zhuǎn)操作之后成為：

9 5 1 | 8 3 7 | 6 10 4 2

（4）判斷終止條件

因為遺傳算法是隨機搜索算法的特性，很難找到一個明確的終止條件。一般的解決辦法要么是設(shè)置固定的進化迭代次數(shù)

G （一般G ∈100，1 000），或者當(dāng)前的優(yōu)化解在連續(xù)進化若干代也沒有變化作為算法的終止條件，本文選用設(shè)置固定的迭代次數(shù)作為算法的終止條件。

4 結(jié) 論

（1）運輸任務(wù)對車輛具有獨占性，分析得出總運輸費用的大小將取決于車輛的空車運行費用。

（2）提出新的策略，將原有的甩掛運輸任務(wù)模型變?yōu)榻?jīng)典的TSP問題；并建立帶時間窗的TSP模型。

（3）本文設(shè)計了改進的遺傳算法進行相應(yīng)的優(yōu)化求解；能夠較為快速地計算出較優(yōu)的牽引車行駛路徑。

參考文獻：

[1] 劉云忠，宣慧玉. 車輛路徑問題的模型及算法研究綜述[J]. 管理工程學(xué)報，2005，19（1）：124-130.

[2] Anderson E， Phillips C， Sicker D， et al. A simple and effective evolutionary algorithm for the vehicle routing problem[J]. Computers & Operations Research， 2004，31（12）：1985-2002.

[3] Salhi S， Nagy G. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J]. European Journal of Operational Research， 2005，162（1）：126-141.

[4] Cheng Y R， Liang B， Zhou M H. Optimization for vehicle scheduling in iron and steel works based on semi-trailer swap transport[J]. Journal of Central South University， 2010，17（4）：873-879.

[5] 孫國華. 帶時間窗的開放式滿載車輛路徑問題建模及其求解算法[J]. 系統(tǒng)工程理論與實踐，2012，32（8）：1801-1807.

[6] 李建祥，唐立新. 鋼鐵供應(yīng)鏈生產(chǎn)計劃與調(diào)度研究綜述[J]. 控制工程，2010，17（1）：123-126.

[7] Tang L， Zhao J， Liu J. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research， 2014（236）：978-990.

[8] 辛曼玉. 網(wǎng)絡(luò)型甩掛運輸模式下的車輛調(diào)度問題研究[J]. 物流技術(shù)，2014，33（1）：254-258.