李維　成耀榮　吳百珂

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

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

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

1 問(wèn)題描述

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

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

2 概念和假設(shè)

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

（2）牽引車(chē)只能牽引一輛掛車(chē)；

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

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

（5）行駛的費(fèi)用和時(shí)間與距離成正比。

2.1 策略和模型

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

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

c =c 車(chē)輛在轉(zhuǎn)化后的點(diǎn)停留時(shí)間w =t ； d =d 。綜上所述可將甩掛運(yùn)輸模型描述為一個(gè)經(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）總運(yùn)輸費(fèi)用最??；約束條件（2）、（3）表示每個(gè)客戶點(diǎn)有且只能被訪問(wèn)一次；約束條件（4）牽引車(chē)服務(wù)客戶j的時(shí)間要滿足j點(diǎn)的時(shí)間窗要求；約束條件（5）每輛牽引車(chē)從車(chē)場(chǎng)出發(fā)完成一系列任務(wù)后回到車(chē)場(chǎng)；約束條件（6）防止客戶間的子回路。

3 算法設(shè)計(jì)

因?yàn)閷⒀b貨點(diǎn)i和其卸貨點(diǎn)i+n整合成一個(gè)任務(wù)點(diǎn)來(lái)建立模型，所以需要對(duì)原來(lái)運(yùn)輸網(wǎng)絡(luò)中節(jié)點(diǎn)距離做一些改變，變成甩掛任務(wù)距離矩陣[6-8]。

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

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

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

開(kāi)始

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

開(kāi)始1

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

返回1

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

結(jié)束

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

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

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

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

開(kāi)始

確定編碼方案，

生成初始種群。

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

開(kāi)始1

當(dāng)種群m

開(kāi)始2

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

選擇操作，

交叉操作，

變異操作，

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

返回2

算法終止判斷。

返回1

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

結(jié)束

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

選擇操作

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

p = （8）

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

（1）交叉操作

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

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

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

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

（2）變異操作

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

a = （11）

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

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

在選擇、交叉、變異之后，進(jìn)行多次單方向的逆轉(zhuǎn)操作來(lái)改善遺傳算法的局部搜索能力，在逆轉(zhuǎn)操作后，只有適應(yīng)度值提高的才接受該逆轉(zhuǎn)，否則逆轉(zhuǎn)無(wú)效。例如在1，10隨機(jī)產(chǎn)生兩個(gè)數(shù)4和7，在一條染色體確定兩個(gè)位置，將其位置調(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）判斷終止條件

因?yàn)檫z傳算法是隨機(jī)搜索算法的特性，很難找到一個(gè)明確的終止條件。一般的解決辦法要么是設(shè)置固定的進(jìn)化迭代次數(shù)

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

4 結(jié) 論

（1）運(yùn)輸任務(wù)對(duì)車(chē)輛具有獨(dú)占性，分析得出總運(yùn)輸費(fèi)用的大小將取決于車(chē)輛的空車(chē)運(yùn)行費(fèi)用。

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

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

參考文獻(xiàn)：

[1] 劉云忠，宣慧玉. 車(chē)輛路徑問(wèn)題的模型及算法研究綜述[J]. 管理工程學(xué)報(bào)，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] 孫國(guó)華. 帶時(shí)間窗的開(kāi)放式滿載車(chē)輛路徑問(wèn)題建模及其求解算法[J]. 系統(tǒng)工程理論與實(shí)踐，2012，32（8）：1801-1807.

[6] 李建祥，唐立新. 鋼鐵供應(yīng)鏈生產(chǎn)計(jì)劃與調(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ò)型甩掛運(yùn)輸模式下的車(chē)輛調(diào)度問(wèn)題研究[J]. 物流技術(shù)，2014，33（1）：254-258.