三維裝載約束下的汽車零部件循環取貨路徑優化研究

王長瓊 戚小振

（武漢理工大學物流工程學院 武漢 430063）

0 引 言

汽車零部件供應物流采用循環取貨（milkrun）模式不僅能解決零部件供應中的高成本、低效率問題，還能提高整個供應鏈運作效率.而車輛路徑問題（vehicle routing problem，VRP）和車輛裝載問題（vehicle filling problem，VFP）是零部件循環取貨的核心.Yi Junmin［1］研究建立了發動機廠零部件循環取貨路徑優化模型.Jennify［2］研究了循環取貨過程中運輸與庫存的整合優化問題.朱玲等［3］研究了循環取貨過程中時間窗約束下的需求可拆分路徑優化問題，并建立了取貨總成本最小的數學模型.在車輛裝載問題研究方面，Lim等［4］采用空間分割合并法對車廂裝載進行求解；Bortfeldt［5］以集裝箱裝載問題為對象，分別運用禁忌搜索算法和模擬退火算法對單純的三維裝載問題進行求解.江娜等［6］以遺傳算法為總算法，引入模擬退火算法思想，提出退火／遺傳算法混合策略提高了算法的運算效率.Homberger［7］將車輛路徑問題與車輛裝載問題進行整合優化，并在路徑優化中考慮車輛裝載體積和質量約束.

目前關于VRP與VFP整合優化的研究比較少，且多數為二維裝載問題.因此有必要考慮零部件裝載優先級、零部件擺放位置及方向限制、零部件的易碎性、零部件的穩定性以及車輛安全性等三維裝載約束，即三維裝載約束下的汽車零部件循環取貨路徑優化問題（vehicle routing problem with three dimensional loading constraints，3LCVRP）.因此，本文將綜合考慮三維裝載約束與車輛路徑約束，研究3L－CVRP優化模型及求解算法.

1 3L－CVRP模型建立

1.1 問題描述

考慮汽車零部件循環取貨供應物流中三維裝載約束下的循環取貨路徑優化問題，具體描述為：假設主機廠附近有一個區域配送中心進行取貨、集貨，共有p輛貨車可供使用，每輛車規格相同，每輛取貨車輛車箱的長寬高分別為L，W，H，車輛的最大載重質量為Q.現有n個零部件供應商需要取貨，每個供應商的地理位置已知，且零部件供應需求已知，包括每個供應商處的零部件包裝箱（簡稱箱子，下同）個數、長寬高、重量等，要求如何在滿足車輛路徑約束和車輛三維裝載約束下，保證取貨路線成功裝載，且使得車輛總行駛路徑最短、車輛裝載率最大？圖1給出了三維裝載約束下的循環取貨路徑優化問題示意圖.

圖1 3L－CVRP示意圖

1.2 假設條件

1）只有一個配送中心，且車輛從配送中心出發，最后均回到配送中心.

2）每輛貨車車廂規格（即長、寬、高，載重質量等）均相同.

3）每輛貨車勻速行駛，且行駛速度已知；不存在交通堵塞情況.

4）配送中心與各零部件供應商地理位置已知.

5）各供應商處提供的零部件均由長方體箱包裝，且各長方體箱的尺寸、數量、重量等參數已知.

6）每個供應商提供的零部件總量小于一輛車的容量.

7）每個供應商只由一輛車完成服務，且只服務一次.

8）每條線路上的貨物總重量、總體積不得超過貨車載重質量及容積.

9）考慮汽車零部件供應的準時性，每輛貨車必須在規定時間以內返回配送中心.

10）零部件（指長方體包裝箱，下同）必須在車廂內部，不得超出車廂車門.

11）零部件的邊總是與車廂的邊平行或者垂直、高度方向與車廂高度方向平行，且不得倒置.

12）貨物的重心即為幾何中心.

13）三維空間坐標系以車廂的最后、最左、最下為坐標原點（0，0，0），以車廂寬為X 軸，車廂長為Y軸，車廂高為Z軸.

1.3 參數與變量說明

1）參數說明 A ＝ ｛i／i＝0，1，2，…，n｝為節點集合，i＝0為配送中心，i＝1，2，…，n為零部件供應商；dij為各節點之間的距離，（ij∈A；i≠j）且dij＝dji；tij為從節點i到節點j的行駛時間，（ij∈A；i≠j）且tij＝tji；ti為供應商i的裝卸時間；T為每條線路必須在規定時間內取回零部件；mi為第i個零部件供應商處的箱子數量；i＝1，2，…，n；Iik為第i個供應商的第k個零部件箱子，i＝1，2，…，n，k＝1，2，…，mi；lik，wik，hik，qik分別為第i個供應商處的第k個零部件的長、寬、高及質量，i＝1，2，…，n，k＝1，2，…，mi；qi，si分別為第i個供應商處的零部件總質量和總體積，i＝1，2，…，n；其中qi＝ ＝ ；p ＝｛p／p＝1，2，3，…，v｝為車輛的集合；Q 為車輛最大載重質量；（）為第i個供應商處第k個零部件在車廂中的重心坐標，i＝1，2，…，n，k＝1，2，…，mi；）分別為車輛p中第i個供應商處第k個零部件在車廂中的正面右上角和側面左下角坐標；［X1，X2］為車廂沿X軸的重心范圍要求；［Y1，Y2］為車廂沿Y軸的重心范圍要求；［0，Z］為車廂沿Z軸的重心范圍要求；α：支撐面積系數.

2）決策變量說明

1.4 模型建立

1）目標函數 以車輛總行駛路徑最短為目標函數，即

2）約束條件 將車輛路徑優化問題和三維裝載問題統一考慮，要求同時滿足車輛路徑約束和三維裝載約束.

（1）車輛路徑約束

其中式（2）～（4）為每個供應商由一輛車服務，且只服務一次；式（5）為每條線路上的貨物總體積不得超過車輛載貨容積上限；式（6）為每條線路上的貨物總載重質量不得超過車輛載重質量上限；式（7）為貨車由配送中心出發，最后回到配送中心；式（8）為每條線路上的車輛行駛時間不得超過T.

（2）車輛裝載約束

為了快速安全地將零部件從供應商處送至配送中心，每輛車廂內的零部件擺放必須滿足以下要求.

式（9）為貨物背面左下角和正面右上角之間的關系；式（10）為所有貨物必須處在車廂內；式（11）為箱子的邊有車廂的邊正交或平行；式（12）為箱子可以在水平線上旋轉90°，但不得倒置；式（13）為車廂中所有箱子的重心必須在一定范圍之內；式（14）為每個零部件空間不得重疊，如圖2所示，2個箱子在車廂底面XY平面上的投影，當2個箱子空間存在重疊部分的時候，則這2個箱子在任何平面上投影均存在重疊部分，并且x1＞x2且y1＞y2，同理在XZ和YZ平面上的投影結論相同，反之，只要2個箱子在任意一個平面上的投影沒有重疊部分，則說明這2個箱子空間不存在重疊；式（15）為支撐面積約束.

圖2 2個箱子在底面的投影關系圖

2 算法設計

考慮許多二維裝載理論往往因為箱體三維（長、寬、高）尺度原因無法有效裝載，本文在循環取貨路徑優化分析中考慮三維約束，保證車輛成功裝載.

算法由遺傳禁忌算法和車輛裝載檢驗算法組合而成.遺傳禁忌算法用來優化車輛路徑問題，找出循環取貨路徑及車輛數；然后調用車輛裝載檢驗算法對每條取貨路徑進行裝車檢驗，根據貨物選擇順序和空間選擇順序，確定貨物裝車位置，確保該路線上每個供應商的全部貨物成功裝載.

2.1 遺傳禁忌算法設計

將遺傳算法與禁忌搜索算法進行組合，遺傳算法作為“主算法”，禁忌搜索作為“從算法”加入遺傳算法的某個操作中.

1）編碼方案設計 采用自然數編碼方法，例如取貨方案：［1 3 1 4 2 2 3 1 3 4 2 1 2 1 2 4 3 1 3 4］，該編碼共有20個自然數，表示供應商數量；每個基因點上是1～4的自然數，表示車輛編號.

2）適應度函數 為使總路徑最短、車輛利用率最大，令t表示取貨總時間，t＝0.4×20＋f1／v，適應度函數為f2×f3×t－9

3）遺傳禁忌交叉算子 按照設定交叉方法進行交叉操作，產生兩個新個體；以父代染色體適應度函數值平均值為渴望水平，以個體的適應度函數值為禁忌對象，生成禁忌表，并對禁忌對象設置一定的禁忌長度；如果交叉操作產生的新個體的適應度函數值大于渴望水平，則無論該個體是否禁忌，該個體均被復制到下一代；如果交叉產生的后代沒有達到渴望水平，也沒有處在禁忌表中，則該個體被復制到下一代；如果交叉產生的后代沒有達到渴望水平，且被禁忌，則復制較優的父代進入下一代.

4）變異算子 采用的變異操作方法為單點變異方式和倒位變異方式.

2.2 車輛裝載檢驗算法

1）貨物裝載順序的確定 將每個供應商處的箱子依次按照體積a1（l×w×h）、底面積a2（l×w）、高度a3（h）的降序規則進行排序，即根據裝載空間剩余的變化，優先裝載體積較大的箱子；當2個箱子體積相同時，優先裝載底面積較大的箱子，為后續裝載的貨物提供較大的底面支撐面積；最后為了有效利用空間，優先裝載高度較高的貨物.

2）空間選擇策略 當一個箱子裝進車廂后，該車廂的剩余空間被分為前方（Y軸方向）、上方（Z軸方向）和右方（X軸方向）3個部分.

為最大限度地防止空間浪費，剩余體積最小的空間優先被選擇.

如圖3所示，若v上≤v右，優先將貨物裝在上方空間（a）空間分割方式，若上方不滿足裝載約束，則考慮右方剩余空間，最后是前方空間.

圖3 空間選擇示意圖

若v上≥v右，優先將貨物裝在右方空間（b）空間分割方式，若右方不滿足裝載約束，則考慮上方空間，最后是前方空間依此類推.

3）裝載位置確定 某一空間中可供選擇裝載某一箱子的位置很多，具體選擇哪一個？在此，引入“關鍵點”，見圖4，其尋找思路如下.

（1）當車廂為空時，其剩余空間為整個車廂，車廂坐標原點為關鍵點，第一個待裝貨物將放在該關鍵點；

（2）當放入第一個箱子后，將產生另外3個關鍵點1，2，3，并刪除原來的關鍵點；下一個待裝貨物將選擇這3個關鍵點擺放.根據上文提出的按照（a）和（b）空間分割方法，按照a1，a2，a3降序規則，若v上≤v右，則選擇（a）空間分割方法，將貨物擺放在1號關鍵點，若1號關鍵點不滿足貨物裝載要求，則考慮3號關鍵點；若v上≥v右，則選擇（b）空間分割方法，將貨物擺放在3號關鍵點，若3號關鍵點不滿足貨物裝載要求，則考慮1號關鍵點，依此類推.

（3）按照上述空間選擇規則和貨物裝載規則，依次選擇待裝貨物的裝載位置.

圖4 關鍵點示意圖

3 實例分析

3.1 實例數據

某汽車制造企業委托第三方物流公司從20家零部件供應商處取零部件，由于篇幅原因零部件詳細信息未上傳.供應商位置分別見表1.

表1 供應商地理坐標 km

所有車輛均為7.2×2.2×2.2式貨車，載重上限為8t，車輛平均速度40km／h，每個供應商處裝卸時間為0.4h，且每輛車必須在5h之內返回配送中心.

3.2 結果分析

設定種群數目為1 200、迭代次數為500代、交叉概率0.8、變異概率為0.1.改進算法的運算結果見圖5.

圖5 循環取貨路線圖

由圖5可知，共有4條取貨路線，即：0－6－7－9－8－0；0－10－3－1－2－4－5－0；0－16－18－19－20－17－0；0－15－14－13－12－11－0.該方案的車輛行駛總路徑約241km，平均每輛車行駛60.25km.

在保證各參數不變的前提下，筆者還采用傳統遺傳算法進行了算例求解，結果同樣是4條取貨路線，即車輛使用數相同；但總路徑為259km，平均每輛車行駛64.75km.即改進算法的總路徑降低了7.5%，提高了零部件供應效率.另外，改進算法將禁忌思想引入遺傳算法，提升了算法的局部搜索能力，使得算法可以較快地跳出局部最優解得到全局近似最優解，因此改進算法收斂更快、運算時間更短，且近似最優解更好.

4 結束語

文中以汽車零部件供應物流為研究對象，對循環取貨模式中的兩個核心內容—路徑優化問題和車輛裝載問題結合在一起進行研究，考慮取貨過程中的實際路徑約束問題和裝載約束問題，建立了三維裝載約束下的汽車零部件循環取貨路徑優化模型，并針對優化模型設計了遺傳禁忌算法進行求解，保證了在最佳取貨路線上的所有貨物裝載成功，為汽車制造企業實施零部件循環取提供了一定的科學依據.算例結果表明了本文模型的有效性，與傳統遺傳算法的結果對比表明，改進型禁忌遺傳算法具有更好的計算性能.

［1］YI Junming.Tactical planning and optimization of a milk run system of parts pickup for an engine manufacturer［J］.Journal of southeast University，2008，23（9）：99－104.

［2］JENNIFER N K.Defining the lean logistics learning enterprise examples from Toyota’s north American supply chain［D］.Miehigan：Miehigan University，2004.

［3］朱 玲，吳 迪.需求可拆分的汽車零部件循環取貨路徑優化研究［J］.計算機應用研究，2013.2：16－26

［4］LIM A，RODRIGUES B，YANG B.3－D Container packing heursitics［J］.Applied Intelligence，2005，22（2）：125－134.

［5］ANDREAS B.A hybrid algorithm for the capacitated vehicle routing problem with three－dimensional loading constraints［J］.Computers ＆ Operations Research，2011（11）：2248－2257.

［6］江 娜，丁香乾.集裝箱裝載問題的模擬退火遺傳算法［J］.計算機應用，2005（10）：14－16.

［7］JORG H.Packing first，routing second－a heuristic for the vehicle routing and loading problem［J］.Computers ＆ Operations Research，2012（9）：873－885.

［8］彭碧濤，周永務.三維裝載約束的車輛路徑問題的模擬退火算法［J］.工業工程，2011，10（5）：71－74.