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

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

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

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

0 引言

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

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

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

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

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

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

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

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

（2）兩點之間的距離是兩點之間的最短路徑。

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

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

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

該物流園區(qū)露天倉庫一共有五個堆場，車輛從大門口進(jìn)入倉庫后，需要分別進(jìn)行揀選。在建模過程中，模型中所應(yīng)用的符號說明如表1所示。

五個堆場的距離矩陣如表2所示。

對于最短路徑的問題，求解步驟如下：

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

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

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

3 結(jié)論

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

因為該實例中地點數(shù)目不多，所以得出了最優(yōu)解，但隨著提貨地點數(shù)目的增加，用此方法得到的則不一定是最優(yōu)解，同時計算量也相當(dāng)大。而且由于提貨是一個比較復(fù)雜的問題涉及眾多的變量，在我們的模型中尚有許多因素沒有考慮在內(nèi)。比如有的路況比較好，有的路比較很不好走，可以繞道等問題沒有考慮在內(nèi)等。未來可以對模型進(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]馮國莉，楊曉冬.基于Hopfield神經(jīng)網(wǎng)絡(luò)車輛路徑的優(yōu)化研究[J].信息技術(shù)，2006，（7）.

[3]劉芳華，趙建民，朱信忠.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化的研究[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.