基于TSP問題的鋼鐵企業物流配送路徑優化模型研究

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

摘 要：作為國民經濟的基礎產業，鋼鐵企業對國民經濟的發展十分重要。生產物流在鋼鐵企業中是提高企業利潤，降低鋼鐵物流成本的關鍵環節。對某鋼鐵企業物流配送路徑優化進行研究，通過建立模型和求解。可以減少了配送人員的繞行，減少貨物的等待時間，有效地提高提貨效率。

關鍵詞：物流配送;路徑優化;TSP

中圖分類號：F25 文獻標識碼：A doi：10.19311/j.cnki.1672-3198.2019.36.014

0 引言

鋼鐵行業對國家的發展至關重要，也是我國國民經濟的重要支柱產業之一。目前，我國鋼鐵生產物流存在的一個很大問題就是物流成本過高，其中運輸的費用達到了物流總費用的一半，因此，有效地減少運輸成本也是我國鋼鐵生產物流亟待解決的重要問題。基于這樣的物流發展現狀，要減少運輸費用，進而減少配送成本，以達到降低物流成本的目的，就必須實現配送車輛運輸路線優化。

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

1 國內外的研究現狀

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

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

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

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

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

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

（3）司機在送貨途中沒出現意外情況。

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

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

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

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

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

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

（1）邊界條件f0（i，F）的值列如表3。

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

3 結論

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

因為該實例中地點數目不多，所以得出了最優解，但隨著提貨地點數目的增加，用此方法得到的則不一定是最優解，同時計算量也相當大。而且由于提貨是一個比較復雜的問題涉及眾多的變量，在我們的模型中尚有許多因素沒有考慮在內。比如有的路況比較好，有的路比較很不好走，可以繞道等問題沒有考慮在內等。未來可以對模型進行進一步優化，提高物流效率。

參考文獻

[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].信息技術，2006，（7）.

[3]劉芳華，趙建民，朱信忠.基于改進遺傳算法的物流配送路徑優化的研究[J].計算機技術與發展，2009，（7）.

[4]李萍，高雷阜，劉旭旺.一種基于模擬退火和Hopfield神經網絡求解TSP算法[J].科學技術與工程，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.