遺傳算法在集裝箱拼箱問題的研究

摘 要：隨著世界國際貿易自由化及全球物流的發展，全球海運已經進入蓬勃發展階段。眾所周知，集裝箱運輸和區域經濟發展關系十分密切，而隨著越來越多的集裝箱運輸公司開辟對應的拼箱業務，集裝箱拼箱的重要性也日益彰顯。引言部分從拼箱開始介紹，通過拼箱中急需解決的問題來引出全文。正文部分先把問題定位為三維約束下的車輛路徑問題，然后將具體問題進行對應的描述，并建立相應的數學模型，再提出運用遺傳算法對問題加以解決，最后對實驗結果進行相應的分析。

關鍵詞：集裝箱拼箱 車輛路徑問題 遺傳算法

一、引言

拼箱通常是指由承運人域國際貨運代理人分別攬貨并在集裝箱貨運站或內陸站集中，然后將兩票或兩票以上的貨物拼裝在一個集裝箱內，在目的地的集裝箱貨運站或內陸站拆箱，分別將貨物交于不同收貨人。拼箱的主目的是為了提高集裝箱的利用率，從而節省運輸的成本。

近來年，隨著集裝箱吞吐量的提高，我國各大港的集裝箱拼箱業務也得迅速發展。而拼箱需求的日益增長，伴隨著的問題是拼箱不合理導致海運效率的降低，如何更好的拼箱提高海運效率是目前急需解決的問題。

二、問題描述

本文研究的集裝箱拼箱問題的實質是3L-CVRP問題，即三維約束下的車輛路徑問題。該問題的研究目標是：在滿足一定的約束條件（如貨物需求量、發送量、交發貨時間、船只容量限制、時間限制等）下，對一系列的需求點的路線進行適當的設計，使船只有序地通過，從而能達到一定的優化目標（如里程最短、費用最少、時間盡量少、、船只利用率高等）。

該具體問題可描述如下：

在某初始港到某目的港的航線上，初始港有t輛相同規格的船只，每艘船的長寬高分別為L，W，H，船的最大載重為Q。集裝箱內尺寸分別為l，w，h。每個集裝箱的重量為q。現有n個中轉港港口需要拼箱服務，每個需求點的需求已知，第i個需求點需配送mi個物品，重量之和為qi，其中第i個需求點的第j個物品用Iij表示，Iij的長用lij表示，Iij的寬用wij表示，Iij的高用hij表示，如何在滿足行車線路約束的條件下，使所有船只總的行船路線最短？

行車線路約束是指由于實際運營的需要及船只資源和船只屬性本身的限制，規劃出來的每條行船線路必須符合如下要求：

（1）船只從起始港出發到達目的港。

（2）每個港口必須且只能被抵達一次。

（3）所有物品的總重量不能超過船只的載重，且所有物品的體積不能超過船艙的容積。

（4）規劃出來的線路數目不能超過總共所擁有的船只的數目。

三、數學建模

其中式1是目標函數，表示使所有船只總的行駛路程最短。式2表示規劃出來的航線數目不能超過所分配的船只數目，式3 表示每艘船都不會多次經過同一個中轉港，式4表示同一個中轉港不會同時被不同的船只經過，式3和式4保證了每個中轉港必須且只經過一次。式5表示每一個中轉港點需要拼箱的數目至少有一個，式6表示需要拼箱的集裝箱的數目全部都被船只服務，式7表示每艘船上所裝載的物品的總的重量不能超過船只的載重限制，式8表示每艘船上所有裝載的物品的體積之和不能超過船只的容積。

四、遺傳算法

對于該問題，遺傳算法是一種較好的解決方法，這種算法是在自然界遺傳機制和生物進化論生物生物學理論基礎上，再與隨機統計相關理論基礎相結合的一種算法。遺傳算法的求解過程是在滿足收斂判據或要求的迭代次數條件下，從初始變量群體開始迭代的，通過不斷的迭代，以此找到相應問題的最優解。遺傳算法一種迭代式算法，它是從生物學基礎出發的，且用該方法求得的最優解是一個過程搜索最優解。該算法廣泛應用于自動控制、計算科學、模式識別、工程設計、智能故障診斷、管理科學和社會科學等相關領域，適用于解決復雜的非線性和多維空間尋優問題。

該算法的步驟可描述為：

第一步：對問題和約束條件的確定，在本問題中是提出相應的海運拼箱的具體問題，然后對它需要滿足的行車線路約束進行相應的約束。

第二步：根據提出的問題建立對應的數學模型。在本問題中是將提出的問題和約束條件轉化為對應的數學公式。

第三步：確定可行解的染色體編碼方法，在本問題中主要是設置初始種群和新生種群來確定。

第四步：確定相應的解碼方法，在本問題中主要是對總加工時間進行設置，進而找到種群的最優個體。

第五步：確定出由目標函數值到個體適應度的轉換規則，在本問題中是時間越短，適應度越高。主要是先構建輪盤，輪盤賭選下一代，小于交叉發生的概率則進行交叉運算，小于變異發生的概率則進行變異運算。最后通過新種群對老種群的替代，最終把最優解進行保留。

第六步：對遺傳算子進行設置，在本問題中主要是對交叉運算、變異運算等遺傳算子的具體流程進行確定，其中交叉運算主要是交叉互換運算，變異運算包含了單鏈切點互換運算、單鏈片段翻轉運算、單鏈片段互換運算。

第七步：對遺傳算法的有關參數進行設置，在本問題中主要是對仿真迭代次數、群體規模、交叉發生的概率進行設置。

五、實驗

1.數據源。本文所使用的標桿問題由Gendreau等[4]提出。該文獻一共提供了27個測試數據，這些數據中的道路網絡、客戶所需貨物的重量和車輛最大載重量的數據分別來源于27個平面CVRP的測試數據，車廂尺寸、貨物尺寸和最大車輛數的數據則由Gendreau等人生成。本文選取了其中的15個平面數據進行測試。車廂的尺寸全部設定為W=25，H=30，L=60，每個需求點所需的貨物數在1到3之間隨機產生，而每件貨物的寬、高和長分別在區間[0.2W，0.6W]、[0.2H，0.6H]和[0.2L，0.6L]內隨機產生。

2.實驗環境。本文所提出的算法用C語言在MATLAB開發平臺下實現，算法執行的平臺環境如下：CPU是英特爾酷睿I7-4610M雙核處理器（ 3GHz，睿頻可達3.7 GHz），內存為8GB，操作系統是Windows7系統。

3.參數設置。在參數設置方面，本文主要對遺傳算法里的仿真迭代次數、群體規模、交叉發生的概率仿真、變異發生的概率進行設置。其中迭代次數T_iter設置為200，群體規模N_num設置為100，交叉發生的概率Pc設置為0.8，變異發生的概率Pm設置為0.08。

4.實驗結果。

通過實驗結果可以看出，對于我們選用的數據，算法生成的初始解的質量也較高，而且每次運行求得的最終解的路徑數都滿足最大車輛數的限制。我們將最終解與初始解相比，路徑總長度有了一定的優化。

六、結語

本文結合海運貨物拼箱運輸的特點，提出了相應的問題，建立了相應的數學模型，并提出應用遺傳算法對相應的拼箱配裝優化問題進行求解，然后介紹了相應的步驟，并用實例計算進行相應的求解，最后發現通過遺傳算法，本問題得到了一定的優化。

參考文獻：

[1]楊占林.拼箱操作三流程[J].中國海關，2009，（07）：42-44.

[2]方金城，張岐山.物流配送車輛路徑問題（VRP）算法綜述[J].沈陽工程學院學報（自然科學版），2006，（04）：357-360.

[3]周昕，凌興宏.遺傳算法理論及技術研究綜述[J]. 計算機與信息技術，2010.

[4]Gendreau M，Iori M，Laporte G.A Tabu Search Algorithm for a Routing and Container Loading Problem[J].Transportation Science，2006，40（3）：342-350.

作者簡介：王林榮（1993—）男。浙江臺州人。碩士研究生。研究方向：遺傳算法。