模糊環(huán)境下基于改進節(jié)約算法的路徑優(yōu)化

賀書杰

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

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.

關(guān)鍵詞：模糊環(huán)境；循環(huán)取貨；路徑優(yōu)化；改進節(jié)約

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

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

0 引言

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

1 研究現(xiàn)狀

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

2 模型

2.1 問題的描述

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

2.2 模型建立

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

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

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

④dij供應(yīng)商i到供應(yīng)商j的距離；

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

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

⑥xijm=1 車輛m從供應(yīng)商i到供應(yīng)商j；0 否則

⑦yim=1 供應(yīng)商i的任務(wù)由車輛m完成；0 否則

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

模型為：

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）目標(biāo)函數(shù)運輸成本最低；（2）每條線路上車輛載容量的限制；（3）只有一輛車m到供應(yīng)商i處取貨；（4）車輛m最多能從某一個取貨點出發(fā)；（5）車輛m最多到達(dá)某一個取貨點一次；（6）在配送路線中相繼到達(dá)兩客戶的時間關(guān)系；（7）表示要求到達(dá)供應(yīng)商的時間范圍；（8）消除子回路。

3 模型求解

單目標(biāo)機會約束規(guī)劃可以表示為：

minf

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

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

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

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

三角模糊數(shù)的數(shù)乘和加法運算規(guī)則：

①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）

目標(biāo)函數(shù)模糊部分轉(zhuǎn)化為清晰的函數(shù)可得：

令=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*

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

非滿載時：

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

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

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

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

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

Step6：軟時間窗設(shè)計：主要考慮i和j連接后所產(chǎn)生的懲罰函數(shù)，將產(chǎn)生的懲罰函數(shù)和所節(jié)約的里程費用進行比較判斷是否實現(xiàn)連接。具體判斷準(zhǔn)則為：

①減少的里程費用為：

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，說明懲罰成本大于節(jié)約成本，則不連接，轉(zhuǎn)到step5；若p（ti）=Fij，可連可連；若p（ti）

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

滿載時：

Step1-Step4，Step7：同非滿載；

Step5：依次選擇距離i距離節(jié)約值最大的點j，j？埸S；并做以下判斷：若Q>q+qj，（q為車載貨運量，Q為額定載重量），轉(zhuǎn)到step6；若當(dāng)?shù)谝淮蜵

Step6：軟時間窗設(shè)計：主要考慮i和j連接后所產(chǎn)生的懲罰函數(shù)，將產(chǎn)生的懲罰函數(shù)和所節(jié)約的里程費用進行比較判斷是否實現(xiàn)連接。具體判斷準(zhǔn)則為：

①減少的里程費用為：

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，說明懲罰成本大于節(jié)約成本，則不連接轉(zhuǎn)到step5；若p（ti）=Fij，可連可連；若p（ti）q+qj，令j∈S，若Q>q+qj，令j？埸S，點對考察完畢進入step7；

具體流程如圖1。

4 總結(jié)

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

參考文獻：

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

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

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

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

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