貨物配裝和車輛路徑問題的一種聯(lián)合求解方法

孫 焰，張俊杰（同濟大學 交通運輸工程學院，上海 201804）

SUN Yan,ZHANG Jun-jie (School of Transportation Engineering,Tongji University,Shanghai 201804,China)

0 引 言

車輛路徑問題 （VRP）是物流和相關(guān)領(lǐng)域的研究熱點和難點，眾多專家學者提出多種理論方法。這些求解方法主要分為兩類：（1）精確求解算法：包括分支定界法、動態(tài)規(guī)劃法、網(wǎng)絡流算法、割平面法等； （2）（亞）啟發(fā)式算法：遺傳算法、蟻群算法等。精確算法不適用于求解大型VRP問題，遺傳算法由于它模擬自然界 “物競天擇，適者生存”的進化機制，能很好地求解此問題。

通常，遺傳算法求解VRP問題時分為兩個階段：首先確定需要安排配送任務的車輛數(shù)，再結(jié)合客戶點數(shù)隨機生成每個個體的染色體并進行遺傳操作[1]。此類方法對于單車型且不考慮貨物體積時適用，本文將探究考慮此兩種因素時的解法設計，這也更符合實際情形。

1 問題提出

一個物流中心負責配送一塊區(qū)域，現(xiàn)有多個訂單分別配送到各客戶點，請給出較合理配送方案，要求總成本最小。

已知：①客戶點的收貨時間窗、平均卸貨速度 （kg/min）；②客戶點之間的行程時間和費用；③配送中心有多種廂型 （長方體）車輛，最大載重和車廂內(nèi)尺寸已知；④同一客戶的多個訂單組成一張臨時訂單，貨物均認為是長方體包裝，重量和尺寸均已知。

說明：①貨物允許混裝。②臨時訂單超出一輛車的重量或容積的裝載能力時將分割成直送和配送兩部分，配送部分不會超過任一類型的車輛的裝載能力，本文僅考慮配送部分。③貨物有三種裝載要求：a.允許水平旋轉(zhuǎn)，b.允許按任意坐標軸旋轉(zhuǎn)，c.不可旋轉(zhuǎn)。本文暫僅考慮a，較符合實際情況。

2 求解思路

要考慮貨物的體積因素，就需要記錄每個貨物在車廂中的位置和碼放方式，這正是典型貨物配裝問題。貨物配裝問題本身較復雜，三叉樹算法是求解此問題的一種有效的啟發(fā)式算法。為了結(jié)合使用遺傳算法和三叉樹算法，本文將會使用雙層結(jié)構(gòu)表示個體染色體，具體方法將在后文闡述。

3 貨物配裝問題

貨物配裝是NP完全問題，本文采用三叉樹算法求解[2]，單個訂單配裝流程如下：首先將各訂單的貨物按體積遞減排序，此后將按此順序取貨[3]；在初始空間 （空車廂）的左下角放入一定數(shù)量的貨物 （若貨物不能堆成長方體，將貨物分成兩部分，取能堆成長方體部分）后，空間被分隔成貨物空間、邊空間、前空間和上空間4個子空間。每次裝貨按照右、上、前的順序遍歷找出可用空間，然后裝貨。滿足a.車輛的剩余載重不夠裝一件貨物，b.車廂剩余空間都不夠裝一件貨物，c.貨物全部裝完中任一配裝結(jié)束。

裝載完一個訂單，檢查車廂狀態(tài) （滿足上文a或b或者c已裝貨物的重量或體積達到指定閥值，即認為已裝滿）。未裝滿時繼續(xù)裝下一個訂單，若裝滿時最后一個訂單未裝完，撤消此訂單的裝載，選擇下一輛空車裝貨。

顯見，訂單和車輛需要事先確定一個選取順序。車輛本文暫按與所有訂單的貨物平均容重比C的接近程度從大到小排序[3],訂單的排列順序?qū)⑷〉?節(jié)的所述的染色體結(jié)構(gòu)第一層序列。

4 車輛路徑問題

車輛路徑問題是一個NP困難問題，本文借鑒了染色體的雙層結(jié)構(gòu)表示方法[5]，并融入了一些新的想法，設計了滿足求解本問題的并行遺傳算法，現(xiàn)作詳細介紹。

（1）客戶點序號

從1開始給客戶點 （即臨時訂單）編號，配送中心記為0；

（2） 染色體

雙層結(jié)構(gòu)表示：①865412739②0247，第一層是客戶點序列，第二層是車輛序列。②的長度為4，表示需要四輛車，第一輛車從①的位置0開始，位置2前結(jié)束，即配送①的0,1兩個位置點 （客戶點8和6，裝車順序8、6，配送順序6、8，二者順序相反是因為先裝后卸），以此類推，各車的配送客戶分別為

程序在運行時，首先隨機生成染色體第一層，然后據(jù)此利用第3節(jié)介紹的三叉樹貨物配裝算法運算得到染色體第二層。隨著第一層的客戶點序列的不同，第二層序列的數(shù)字和長度也動態(tài)變化，這有別于傳統(tǒng)方法需要事先確定所需車輛個數(shù)。

（3）種群初始化

設定種群規(guī)模N，選擇概率Ps，交叉概率Pc，變異概率Pm。隨機產(chǎn)生初始種群隊列：對于每一個個體，首先產(chǎn)生染色體第一層，接著生成第二層車輛序列；計算配送方案的總費用，包括走行費用和懲罰成本；個體的適應度取總費用的倒數(shù)，適應度數(shù)值可適當放大。產(chǎn)生N個個體 （下標從0記起），個體按照適應度從大到小排序，記錄最優(yōu)個體。

（4） 選擇

選擇種群隊列中前N*Ps個個體，作為下一代個體。

（5） 交叉

在種群隊列的前Np=N*（1-Pc-P m）-1個個體中選擇兩個不同個體作為雙親，采用改進的順序交叉 （允許雙親交叉長度不同）產(chǎn)生子代，從Np位置開始按順序替換種群中個體。

（6） 變異

在種群隊列的前Np個個體中隨機選擇一個作為父親，從四種變異方法 （①交換變異，②反轉(zhuǎn)變異，③插入變異，④子路徑互換變異：交換兩條子路徑基因）中隨機選擇一種方法，變異產(chǎn)生子代。從Np+N*Pc開始按順序替換種群中個體。

（7） 鄰域搜索

取種群中第一個個體作為父親，順次采用 （6）的四種變異方法和⑤子路徑交換變異⑥子路徑反轉(zhuǎn)變異⑦子路徑插入變異三種方法產(chǎn)生子代。

需要設定鄰域搜索的次數(shù)，每次搜索的結(jié)果都儲存在第N-1位置個體中，并記錄最優(yōu)個體。

（8）2-opt路徑優(yōu)化

取種群中第一個個體作為父親，對于染色體中的子路徑 （需加入考慮配送中心），若圖1中的ab+cd>ac+bd成立，則刪除邊ab和cd，連接ac和bd，并將b和c之間的客戶點順序反轉(zhuǎn)。產(chǎn)生臨時子代，記錄最優(yōu)個體。依次對各子路徑 （長度大于2時）的邊重復以上判斷。

（9）重復步驟4,5,6,7,8,9

統(tǒng)計種群的代數(shù)和最優(yōu)結(jié)果保持代數(shù)，滿足結(jié)束條件時停止運行。

圖2是遺傳算法的算法流程：

圖2 遺傳算法流程圖

圖3是并行計算的詳細設計：

對于父代種群和子代種群實際利用同一數(shù)組保存，遺傳操作時種群個體按適應度排序，種群被分為適應度高和適應度低的兩部分個體集合，即數(shù)組的前一部分保存適應度高的個體，剩下的部分保存適應度低的個體。算法步驟5,6,7,8中用來進行遺傳操作的父代個體均來自適應度高個體集合，只進行讀操作。復制其染色體，按順序替換適應度低的個體，寫操作發(fā)生在不同的適應度的個體上，相互沒有影響。因而交叉、變異、鄰域搜索和2-opt優(yōu)化可以同時進行，即并行計算，可有效縮短運算時間，提高運行效率。

5 算例驗證

物流中心的配送車輛技術(shù)參數(shù)見表1，將要配送貨物的類型數(shù)據(jù)見表2，現(xiàn)有8輛空車等待分配運輸任務見表3；表4是11張待送的臨時訂單數(shù)據(jù)。

表1 車輛類型數(shù)據(jù)

表2 貨物類型數(shù)據(jù)

表3 現(xiàn)有空車數(shù)據(jù)

表4 臨時訂單數(shù)據(jù)

①假設隨機生成的個體的染色體第一層為7、4、6、2、9、5、11、10、3、8、1。

②車輛按照與貨物的容重比的接近程度排序，形成空車隊列：V2、V7、V6、V4、V1、V8、V3、V5。每個臨時訂單的貨物按照體積從大到小的順序重新排列 （顯然四種類型的貨物體積順序為GT2,GT1,GT3,GT4），將各臨時訂單按照①中順序排列，形成訂單隊列：C7、C4、C6、C2、C9、C5、C11、C10、C3、C8、C1。

③取空車隊列中的第一輛空車V2。

④取訂單隊列中第一個臨時訂單C7。

⑤將臨時訂單C7中的貨物試裝進V2。

表5給出訂單C7的配裝步驟：

表5 試裝客戶C7

此時車廂未滿，取訂單C4繼續(xù)裝貨……

配裝完畢，得到染色體的第二層序列為：0、2、3、7、9。

⑥計算個體的適應度，這需要以下數(shù)據(jù)：a.車輛離開物流中心的時間；b.每個客戶點的收貨時間窗數(shù)據(jù)和平均卸貨速度；c.物流中心以及各客戶點之間的路徑費用和行程時間。如果已知數(shù)據(jù)中沒有某兩點之間的路徑成本和行程時間數(shù)據(jù)，此路徑被認為目前不能通過。可將路徑成本設為0，行程時間設為1441min（大于一天）。

計算個體總成本需要以下數(shù)據(jù)：各點之間的路徑成本和行程時間 （0是物流中心）數(shù)據(jù)，以及客戶點的時間窗和平均卸貨速度數(shù)據(jù)，篇幅關(guān)系不再列出。設定車輛離開物流中心的時間設為400，時間窗罰值為100 000，車輛的容積利用率和載重利用率達到80%以上認為車輛裝滿。得到總成本，取倒數(shù)，并放大1 000倍，得本例個體適應度為0.3155。

按照上面方法生成初始種群，設定Ps為0.3，Pc為0.5，Pm為0.1，最優(yōu)個體保持代數(shù)為500，種群最大進化代數(shù)為3 000，其他遺傳操作參見前文。經(jīng)運算得到最優(yōu)個體見表6：

根據(jù)最優(yōu)個體的染色體得到配送清單，見表7：

表7中可以看出，共需要5輛車，第一輛車V2，貨物的裝車順序為C3的120件GT1和C2的130件GT1（具體配裝方案略），V2順次配送客戶C2和C3（非C3、C2）……

表6 最優(yōu)個體

表7 配送清單

6 性能測試

本文在遺傳算法中考慮了貨物配裝，不能采用Solomon基準測試集進行測試，本節(jié)將測試算法的收斂性。

圖4是某次運算種群進化3 000代的最優(yōu)個體的總成本曲線，可見曲線收斂較快，總成本迅速下降。

7 結(jié)束語

本文通過對車輛配裝問題和車輛配送路徑問題進行簡明扼要的分析，始終從解決一個實際問題的角度出發(fā)，給出了一種聯(lián)合求解此類問題的可行方法，經(jīng)算例驗證方法切實可行，算法收斂快。同時該方法還存在一些不足：如①鄰域搜索在某個空間范圍內(nèi)增加了搜索深度，一方面能加快算法收斂，同時容易造成早熟；②算法中將車輛按照與貨物平均容重比的接近程度排序，這樣可以保證車廂空間盡可能得到利用，在單一車型的情況下可保證車輛數(shù)最少，在多車型情況下比較復雜，有待進一步論證。

總的來說，本算法對實際作業(yè)有一定的借鑒意義。

[1]孫焰.現(xiàn)代物流管理技術(shù)[M].上海：同濟大學出版社，2004:153-158.

[2]姜義東，查建中，何大勇.集裝箱裝載矩形貨物的布局研究[J].鐵道學報：2000,22(6):13-18.

[3]劉霞，呂漢興.集裝箱裝載矩形貨物的一種啟發(fā)式算法[J].起重運輸機械，2003(1):16-18.

[4]孫焰，李致中.求雙目標配裝方案的多項式近似算法[J].長沙鐵道學報，1997,15(2):33-39.

[5]姜昌華.遺傳算法在物流系統(tǒng)優(yōu)化中的應用研究[D].上海：華東師范大學 （博士學位論文），2006:81-103.