基于TSP問(wèn)題的鋼鐵企業(yè)物流配送路徑優(yōu)化模型研究

馬翠鑫 曲曉藝 胡慧斌 陳宇 孫雪

摘 要：作為國(guó)民經(jīng)濟(jì)的基礎(chǔ)產(chǎn)業(yè)，鋼鐵企業(yè)對(duì)國(guó)民經(jīng)濟(jì)的發(fā)展十分重要。生產(chǎn)物流在鋼鐵企業(yè)中是提高企業(yè)利潤(rùn)，降低鋼鐵物流成本的關(guān)鍵環(huán)節(jié)。對(duì)某鋼鐵企業(yè)物流配送路徑優(yōu)化進(jìn)行研究，通過(guò)建立模型和求解。可以減少了配送人員的繞行，減少貨物的等待時(shí)間，有效地提高提貨效率。

關(guān)鍵詞：物流配送;路徑優(yōu)化;TSP

中圖分類號(hào)：F25 文獻(xiàn)標(biāo)識(shí)碼：A doi：10.19311/j.cnki.1672-3198.2019.36.014

0 引言

鋼鐵行業(yè)對(duì)國(guó)家的發(fā)展至關(guān)重要，也是我國(guó)國(guó)民經(jīng)濟(jì)的重要支柱產(chǎn)業(yè)之一。目前，我國(guó)鋼鐵生產(chǎn)物流存在的一個(gè)很大問(wèn)題就是物流成本過(guò)高，其中運(yùn)輸?shù)馁M(fèi)用達(dá)到了物流總費(fèi)用的一半，因此，有效地減少運(yùn)輸成本也是我國(guó)鋼鐵生產(chǎn)物流亟待解決的重要問(wèn)題?；谶@樣的物流發(fā)展現(xiàn)狀，要減少運(yùn)輸費(fèi)用，進(jìn)而減少配送成本，以達(dá)到降低物流成本的目的，就必須實(shí)現(xiàn)配送車輛運(yùn)輸路線優(yōu)化。

本文以某大型鋼鐵企業(yè)M作為研究對(duì)象，通過(guò)分析園區(qū)內(nèi)貨物的堆放情況和運(yùn)輸車輛的運(yùn)行情況，提出了一種基于TSP的物流配送優(yōu)化模型，通過(guò)運(yùn)用動(dòng)態(tài)規(guī)劃的方法對(duì)實(shí)例進(jìn)行了求解，建立了配送路徑的優(yōu)化方案，為鋼鐵企業(yè)節(jié)省物流成本，提高物流效率提供了良好的決策。

1 國(guó)內(nèi)外的研究現(xiàn)狀

物流配送路徑優(yōu)化一直都是國(guó)內(nèi)外研究的重點(diǎn)，許多的學(xué)者都對(duì)此進(jìn)行了研究，很多傾向于用智能算法來(lái)對(duì)配送路徑進(jìn)行優(yōu)化。旅行商問(wèn)題（Traveling Salesman Problem，簡(jiǎn)稱TSP，亦稱郎擔(dān)問(wèn)題）就是典型的組合優(yōu)化問(wèn)題。它可以描述為：對(duì)于N個(gè)城市，它們之間的距離已知，有一旅行商要從某一城市出發(fā)走遍所有的城市，且每一個(gè)城市只能經(jīng)過(guò)一次，最后回到出發(fā)城市，問(wèn)如何選擇路線可使他所走過(guò)的路程最短。國(guó)內(nèi)外主要研究為：

J.F.Cordeau，M.Gendreau，G.Laporte等提出了改進(jìn)的啟發(fā)式算法進(jìn)行路徑優(yōu)化，馮國(guó)莉、楊曉冬對(duì)用Hopfield神經(jīng)網(wǎng)絡(luò)車輛路徑的優(yōu)化進(jìn)行了研究，劉芳華等對(duì)基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化的研究等許多的學(xué)者對(duì)此進(jìn)行了研究。對(duì)于TSP問(wèn)題許多學(xué)者也進(jìn)行了大量的研究，李萍等旺針對(duì)Hopfield神經(jīng)網(wǎng)絡(luò)解旅行商問(wèn)題（TSP）經(jīng)常出現(xiàn)無(wú)效解和局部?jī)?yōu)化解，將模擬退火智能算法與Hopfield神經(jīng)網(wǎng)絡(luò)相結(jié)合，提出了一種混合優(yōu)化算法， Grefenstette J研究了遺傳算法在TSP問(wèn)題中的應(yīng)用。孫雪等提出了一種改進(jìn)的遺傳算法來(lái)求解TSP問(wèn)題。雖然很多學(xué)者對(duì)TSP問(wèn)題及配送路徑優(yōu)化問(wèn)題進(jìn)行了大量的研究，但對(duì)于用TSP模型來(lái)實(shí)現(xiàn)鋼鐵行業(yè)物流配送路徑優(yōu)化的研究則很少，為此我們提出了用TSP模型來(lái)為鋼鐵行業(yè)的物流配送路線的進(jìn)行優(yōu)化研究。

2 模型的建立、求解及分析

M鋼鐵企業(yè)是國(guó)內(nèi)規(guī)模比較大的鋼鐵企業(yè)，隨著鋼鐵倉(cāng)儲(chǔ)品種、現(xiàn)貨交易品種的擴(kuò)大，鋼鐵電子交易量的增加，必須建立高效的鋼鐵倉(cāng)儲(chǔ)優(yōu)化模型，使得堆碼布局最佳，物流通道最簡(jiǎn)，推進(jìn)鋼鐵物流智慧倉(cāng)庫(kù)建設(shè)。為了客戶自行提貨，盡可能的節(jié)省時(shí)間，該鋼鐵企業(yè)的物流園需要客戶將訂單上的貨物分別到指定貨倉(cāng)一一提貨，并在及時(shí)離開(kāi)物流園的情況下實(shí)現(xiàn)路徑最短。在建模過(guò)程中主要考慮如下因素：

（1）忽略因自然原因及人為等因素造成的交通堵塞的可能。

（2）兩點(diǎn)之間的距離是兩點(diǎn)之間的最短路徑。

（3）司機(jī)在送貨途中沒(méi)出現(xiàn)意外情況。

（4）每一條通路的好壞都一樣。

（5）車輛往返的路線相同。

該物流園區(qū)露天倉(cāng)庫(kù)一共有五個(gè)堆場(chǎng)，車輛從大門(mén)口進(jìn)入倉(cāng)庫(kù)后，需要分別進(jìn)行揀選。在建模過(guò)程中，模型中所應(yīng)用的符號(hào)說(shuō)明如表1所示。

五個(gè)堆場(chǎng)的距離矩陣如表2所示。

對(duì)于最短路徑的問(wèn)題，求解步驟如下：

（注：堆場(chǎng)1、堆場(chǎng)2、堆場(chǎng)3、堆場(chǎng)4、堆場(chǎng)5分別對(duì)應(yīng)下面的各步驟）

（1）邊界條件f0（i，F(xiàn)）的值列如表3。

根據(jù)上面的結(jié)果由狀態(tài)k4=（1，{2，3，4，5}）開(kāi)始回溯，得到一條回路為：1→2→5→4→3→1，且最短路徑=30+16+34+32=112米。即車輛按照“堆場(chǎng)1→堆場(chǎng)2→堆場(chǎng)5→堆場(chǎng)4→堆場(chǎng)3→堆場(chǎng)1”走路徑最短，并能最節(jié)省成本。

3 結(jié)論

本文針對(duì)某鋼鐵企業(yè)的實(shí)際需求，對(duì)其物流園內(nèi)倉(cāng)庫(kù)配送路徑優(yōu)化問(wèn)題建立基于TSP的模型，并利用通過(guò)動(dòng)態(tài)規(guī)劃方法來(lái)進(jìn)行求解，最后通過(guò)實(shí)例計(jì)算得出了比較優(yōu)的結(jié)果。通過(guò)本方法不但考慮了提貨路徑，還將回程考慮在內(nèi)，這樣做的好處是可以實(shí)現(xiàn)整個(gè)物流配送的閉合回路，減少了配送人員的迂回繞行，使他在完成了各個(gè)點(diǎn)提貨任務(wù)后能及時(shí)離開(kāi)物流園區(qū)，減少了等待時(shí)間，同時(shí)還能有效地提高提貨效率。

因?yàn)樵搶?shí)例中地點(diǎn)數(shù)目不多，所以得出了最優(yōu)解，但隨著提貨地點(diǎn)數(shù)目的增加，用此方法得到的則不一定是最優(yōu)解，同時(shí)計(jì)算量也相當(dāng)大。而且由于提貨是一個(gè)比較復(fù)雜的問(wèn)題涉及眾多的變量，在我們的模型中尚有許多因素沒(méi)有考慮在內(nèi)。比如有的路況比較好，有的路比較很不好走，可以繞道等問(wèn)題沒(méi)有考慮在內(nèi)等。未來(lái)可以對(duì)模型進(jìn)行進(jìn)一步優(yōu)化，提高物流效率。

參考文獻(xiàn)

[1]J.F.Cordeau，M.Gendreau，G.Laporte，J.-Y.Potvin and F.Semet.A Guide to Vehicle Routing Heuristics[J].Journal of the Operational Research Society，Vol.53，2002，pp.512-522.

[2]馮國(guó)莉，楊曉冬.基于Hopfield神經(jīng)網(wǎng)絡(luò)車輛路徑的優(yōu)化研究[J].信息技術(shù)，2006，（7）.

[3]劉芳華，趙建民，朱信忠.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，（7）.

[4]李萍，高雷阜，劉旭旺.一種基于模擬退火和Hopfield神經(jīng)網(wǎng)絡(luò)求解TSP算法[J].科學(xué)技術(shù)與工程，2008，8（14）：3937-3939.

[5]Grefenstette，John J.Genetic Algorithms for Machine Learning[Z].1994.

[6]Sun，X.，Yang，C.K.，wei，K.，Wu，C-C.，& Chen，L-R.Research on an improved genetic algorithm for logistics distribution path optimization[C]. ACM International Conference Proceeding Series（pp.282-286）. （ACM International Conference Proceeding Series; vol. Part F148260）. Association for Computing Machinery，2018.