模糊環境下基于改進節約算法的路徑優化

賀書杰

摘要：基于循環取貨理論和背景，從TPL角度研究汽車零部件運輸路徑優化問題。由于需求量及成本這些變量在一個范圍內波動，因此在模糊的條件下，建立最小化運輸成本模糊規劃模型，并運用模糊理論知識將模糊模型轉化成確定型模型，并采用改進的節約算法求解滿載和非滿載的路徑成本。

Abstract： Based on the background of cycle picking theories， from the perspective of TPL， the optimization of auto parts transportation route is studied. As the demand and cost of these variables fluctuated in a range， in the fuzzy condition， it is to establish the fuzzy programming model for minimizing transportation cost， and uses the fuzzy theory knowledge to transfer fuzzy model into the determined model， and uses the modified saving algorithm to solve fully loaded and non loaded path cost.

關鍵詞：模糊環境；循環取貨；路徑優化；改進節約

Key words： fuzzy environment；cycle picking；path optimization；improved saving

中圖分類號：F274 文獻標識碼：A 文章編號：1006-4311（2017）34-0098-03

0 引言

隨著經濟的快速發展，人們生活質量的不斷提高，汽車從高昂的奢侈品變成了日常的消費品進入了千家萬戶。汽車制造企業也面臨挑戰，當經濟市場上占有的份額達到規定的利潤飽和點，企業將新的利潤增長點放在物流費用上，尤其是入場物流。目前，傳統的入場模式已經無法滿足物流產業發展的需求，循環取貨作為在JIT供應和精益思想指導下一種新型的入場物流模式逐漸被采用。因此，TPL采取循環取貨模式具有理論意義和現實意義。

1 研究現狀

邰曉紅，李璐[1]加入了客戶對時間的約束，提出改進的節約法；郭榮[2]對Milk Run模式下配送的多周期問題進行了研究；孫洋等[3]通過構建車輛路徑優化的模型，運用蟻群算法對模型進行求解；王小會[4]考慮了軟時間窗的約束條件，建立車輛行駛的費用和罰函數之和最小的模型；吳健，倪偉等[5]本文主要選取沃爾沃汽車的入廠物流案例研究路徑規劃問題。從文獻來看，大多數對確定的模型進行研究，對不確定模糊模型研究相對更少，由于需求量及成本在一個范圍內波動，所以模糊環境下研究路徑優化具有參考價值。對于不確定的運輸研究多集中在找出統計規律的的隨機車輛路徑問題，但物流系統受到不可控因素的影響而具有模糊不確定性。因此，本文主要集中在模糊環境下基于循環取貨路徑優化研究。

2 模型

2.1 問題的描述

問題描述：一個汽車制造廠和若干個供應商，TPL通過與供應商和制造工廠簽訂協議的條件下，從配送中心出發，在供應商處取貨運至配送中心。每個供應商的位置一定，時間窗一定，每輛車裝載容量一定，車輛的單位運輸成本和固定成本、需求量為三角模糊數，并且不允許缺貨，TPL取貨的同時要歸還供應商的容器。

2.2 模型建立

①d每輛車單次派遣費用d=（C，C，C）；

②f單位行駛費用f=（C，C，C）；

③i表示整車廠對零部件i的單次需求量，i=（Q，Q，Q）；

④dij供應商i到供應商j的距離；

⑤[ET，LT]為客戶要求最佳送貨時間范圍；在[A，ET]和[LT，B]范圍內客戶會收貨，產生等待成本a和延誤成本b；在[A，B]時刻之外到達產生一個無窮大的懲罰成本l。p（t）是懲罰成本；ti到達供應商的時間；tij從供應商i到j的運輸時間；si表示在供應商i處停留時間。

p（ti）=l→+∞ ti？燮A或ti？叟Ba（ETi-ti） A？燮ti？燮ETi0 ETi？燮ti？燮LTib（ti-LTi） LTi？燮ti？燮B

⑥xijm=1 車輛m從供應商i到供應商j；0 否則

⑦yim=1 供應商i的任務由車輛m完成；0 否則

運輸成本包括車輛啟動的固定成本和運輸費用。實際中供應商會設置時間約束，考慮實際中突發狀況的存在采取軟時間窗約束。

模型為：

min=ddijxijm+fx0im+P（ti）（1）

iyim？燮？鄣m* （2）yim=1 （3）xijm=yim （4）xijm=yim （5）ti+si+tij-M（1-xijm）？燮tj （6）ETi？燮ti？燮LTi （7）xijm？燮U-1 （8）

（1）目標函數運輸成本最低；（2）每條線路上車輛載容量的限制；（3）只有一輛車m到供應商i處取貨；（4）車輛m最多能從某一個取貨點出發；（5）車輛m最多到達某一個取貨點一次；（6）在配送路線中相繼到達兩客戶的時間關系；（7）表示要求到達供應商的時間范圍；（8）消除子回路。

3 模型求解

單目標機會約束規劃可以表示為：

minf

s.t. Pos{f（x，ξ）？燮f}？叟β

Pos{gj（x，ξ）？燮0，j=1，2，…，p}？叟αendprint

其中β和α分別是事給定的目標和約束的置信水平，是一種minmax模型。

設三角模糊數（q1，q2，q3），則對任意給定的置信水平α（0？芻α？芻1），當且僅當z？叟（1-α）q1+αq2時有pos{q？燮z}？叟α成立。

三角模糊數的數乘和加法運算規則：

①1？茌2=（l1+l2，m1+m2，μ1+μ2）；

②1？茚2≈（l1l2，m1m2，μ1μ2）；

③λ？茌1≈（λl1，λm1，λμ1）；

④（1）-1≈（1/μ1，1/m1，1/l1）

目標函數模糊部分轉化為清晰的函數可得：

令=ddijxijm+fx0im

pos{？燮z}？叟α1

則posddijxijm+fx0im？燮z？叟α1

posiyim？燮？鄣m*？叟α2

則min z

dijxijm[（1-α1）C+α1C]+x0im[（1-α1）C+α1C]？燮z

（（1-α2）Q+α2Q）yim？燮？鄣m*

節約算法是解決車輛路線優化問題一個簡單易行的方法，但隨著各種具體約束的衍生，必須將傳統的節約算法進行適當修改。改進節約算法非滿載和滿載步驟如下：

非滿載時：

Step1：配送中心0為起點，起點與各點相連，有n-1條線路，0-j-0（j=1，2，...，n）；

Step2：計算所有可連接點對（i，j）節約值s（i，j）=C0i+C0j-Cij，將計算出的s（i，j）按從大到小的順序進行排列；

Step3：初始化參數：路線n=0，集合S=？覫；

Step4：選擇時間窗最早的客戶點i（i？埸S），將i加入集合S中，q=0；

Step5：依次選擇距離i距離節約值最大的點j，j？埸S；并做以下判斷：若Q>q+qj，（q為車載貨運量，Q為額定載重量），轉到step6；否則不連接i，j，選擇下一個節約值；

Step6：軟時間窗設計：主要考慮i和j連接后所產生的懲罰函數，將產生的懲罰函數和所節約的里程費用進行比較判斷是否實現連接。具體判斷準則為：

①減少的里程費用為：

Fij=Wij*d=Wij*

②時間變化引起的懲罰成本：

p（ti）=l→+∞ ti？燮A或ti？叟Ba（ETi-ti） A？燮ti？燮ETi0 ETi？燮ti？燮LTi b（ti-LTi） LTi？燮ti？燮B

③若p（ti）>Fij，說明懲罰成本大于節約成本，則不連接，轉到step5；若p（ti）=Fij，可連可連；若p（ti）

Step7：是否客戶點均在集合S中，若是，結束，否則令n=n+1，轉Step4。

滿載時：

Step1-Step4，Step7：同非滿載；

Step5：依次選擇距離i距離節約值最大的點j，j？埸S；并做以下判斷：若Q>q+qj，（q為車載貨運量，Q為額定載重量），轉到step6；若當第一次Q

Step6：軟時間窗設計：主要考慮i和j連接后所產生的懲罰函數，將產生的懲罰函數和所節約的里程費用進行比較判斷是否實現連接。具體判斷準則為：

①減少的里程費用為：

Fij=Wij*d=Wij*

②時間變化引起的懲罰成本：

p（ti）=l→+∞ ti？燮A或ti？叟Ba（ETi-ti） A？燮ti？燮ETi0 ETi？燮ti？燮LTi b（ti-LTi） LTi？燮ti？燮B

③若p（ti）>Fij，說明懲罰成本大于節約成本，則不連接轉到step5；若p（ti）=Fij，可連可連；若p（ti）q+qj，令j∈S，若Q>q+qj，令j？埸S，點對考察完畢進入step7；

具體流程如圖1。

4 總結

針對模糊環境下運輸問題，本文建立了一個最小化運輸模糊規劃模型，以運輸成本最小為目標。在運算的過程中，僅對供應鏈的上游就行了研究，對于三級供應鏈的研究可作為進一步研究的方向。

參考文獻：

[1]邰曉紅，李璐.改進節約法下的物流配送路徑優化問題[J].遼寧工程技術大學學報（自然科學版），2016，35（6）：667-672.

[2]郭榮.MilkRun模式下汽車零部件配送的多周期ITIO問題研究[D].武漢理工大學，2014.

[3]孫洋，嚴偉.基于蟻群算法的循環取貨車輛路徑優化[J].物流工程與管理，2015，37（7）：85-86.

[4]王小會.多車場帶時間窗車輛路徑問題的粒子群優化算法[J]，蘭州工業學院學報，2015，22（2）：52-55.

[5]吳健，倪偉，等.面向循環取貨路徑優化問題的改進遺傳算法研究[J].物流工程與管理，2015，10（39）：31-34.