三維裝載約束下的汽車零部件循環(huán)取貨路徑優(yōu)化研究

王長瓊 戚小振

（武漢理工大學(xué)物流工程學(xué)院 武漢 430063）

0 引 言

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

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

1 3L－CVRP模型建立

1.1 問題描述

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

圖1 3L－CVRP示意圖

1.2 假設(shè)條件

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

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

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

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

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

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

7）每個供應(yīng)商只由一輛車完成服務(wù)，且只服務(wù)一次.

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

9）考慮汽車零部件供應(yīng)的準(zhǔn)時性，每輛貨車必須在規(guī)定時間以內(nèi)返回配送中心.

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

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

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

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

1.3 參數(shù)與變量說明

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

2）決策變量說明

1.4 模型建立

1）目標(biāo)函數(shù) 以車輛總行駛路徑最短為目標(biāo)函數(shù)，即

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

（1）車輛路徑約束

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

（2）車輛裝載約束

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

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

圖2 2個箱子在底面的投影關(guān)系圖

2 算法設(shè)計

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

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

2.1 遺傳禁忌算法設(shè)計

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

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

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

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

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

2.2 車輛裝載檢驗算法

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

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

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

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

圖3 空間選擇示意圖

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

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

（1）當(dāng)車廂為空時，其剩余空間為整個車廂，車廂坐標(biāo)原點為關(guān)鍵點，第一個待裝貨物將放在該關(guān)鍵點；

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

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

圖4 關(guān)鍵點示意圖

3 實例分析

3.1 實例數(shù)據(jù)

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

表1 供應(yīng)商地理坐標(biāo) km

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

3.2 結(jié)果分析

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

圖5 循環(huán)取貨路線圖

由圖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.

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

4 結(jié)束語

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

［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］朱 玲，吳 迪.需求可拆分的汽車零部件循環(huán)取貨路徑優(yōu)化研究［J］.計算機應(yīng)用研究，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］.計算機應(yīng)用，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］彭碧濤，周永務(wù).三維裝載約束的車輛路徑問題的模擬退火算法［J］.工業(yè)工程，2011，10（5）：71－74.