基于TSP模型的企業配送線路優化設計

高一丹 張鈺瑤 鄭巧 徐成鈺 趙萌

摘?要：隨著現代社會經濟的蓬勃發展，物流行業的發展逐漸成為一個國家現代化進程和綜合國力的重要標志。物流行業的成本也漸漸成為一個熱點問題，而配送成本在物流成本中占據較大的比例。文章以北京農夫山泉桶裝水的配送路徑問題作為研究目標，首先描述了研究背景與意義，并依次分析了國內外學者對于配送路徑問題的研究現狀，說明了本篇文章的研究內容；其次通過分析對北京農夫山泉實際走訪與調研的結果，了解并提出北京農夫山泉配送過程中存在的一些問題；最后建立相對應的數學模型，利用Lingo軟件中的TSP模型進行運算求解并分析得到結果，得出優化后的配送路徑。

關鍵詞：配送運輸成本；配送路徑優化；TSP模型

中圖分類號：F252文獻標識碼：A文章編號：1005-6432（2024）14-0167-04

DOI：10.13939/j.cnki.zgsc.2024.14.040

1?北京農夫山泉配送線路現狀

配送是整個物流活動系統中一個重要因素，產品可以通過配送產生更高的價值。而在北京農夫山泉的配送過程中，由于公司沒有規定具體的配送路徑，這就需要司機憑借自己的經驗來做出判斷。北京農夫山泉的配送方法是從配送中心向各個水站配送，車輛會經過每個水站然后返回配送中心。

通過實地走訪調查，了解到在一般沒有規定的前提下，配送車輛司機自己所走的配送路徑如圖1所示，配送所走的路徑是O-D-C-B-A-E-G-H-F-I-O，這樣配送可以保證會經過所有水站并且返回到配送中心，在不加以考慮其他因素的條件下，配送路徑的總里程為54.6km。

圖1?北京農夫山泉桶裝水配送路徑

2?配送線路現存問題分析

2.1?存在迂回運輸

配送水站H至配送水站I之間相距5.4km，通過配送路徑圖可知，從配送水站H到達配送水站I的時候中間先去到了配送水站F，還有就是配送水站I距離配送中心距離最遠，可是返回時直接返回，由此可見，北京農夫山泉桶裝水的配送路徑中存在迂回運輸。

2.2?存在過遠運輸

在配送點E、F、G、H四個配送點中存在多種路線可以選擇，司機在配送這幾個站點時選擇了先去站點G再轉到站點H，最后去到站點F，然后在返回時還要去到站點I，這就造成了整個運輸過程中產生了過遠運輸。

2.3?存在空駛情況

在實際走訪中，了解到在實際配送中，有時候運輸組織人員為了緊急調運不得不將未裝滿的車輛進行緊急調運。北京農夫山泉在實際配送中，不能夠對各個水站的存量進行統計，需要另發單車進行補貨，這就會造成空車行駛和空車返程的問題。

3?北京農夫山泉配送路徑優化模型構建

3.1?配送路徑優化模型構建

3.1.1?具體問題描述

北京農夫山泉桶裝水的配送路徑優化問題可以描述為：從北京農夫山泉的配送中心出發，依次向其所有的水站進行貨物配送，并最終返回配送中心。在這過程中會有很多的路線進行選擇，需要找到配送里程最短的方案。

通過整理北京農夫山泉的數據，可以將路徑優化看作是一個帶權完全圖G=（N，X）的問題，在這里面配送水站的地點可以用N表示，去到每一個水站的距離可以用X表示。用數學語言描述為：賦權圖是G=（N，X），各水站之間的集合為N=（1，2，…，n），各水站之間的距離為dij（dij=∞，i，j∈N），知道各個水站和配送中心之間的距離，還有各水站之間的距離，這樣就可以將這個問題轉化為一個TSP問題，只需要求出經過所有配送水站之后的最短距離即可。

3.1.2?整理收集數據

文中以北京農夫山泉各個配送水站之間的配送路徑優化為研究目標，在其中求得最優最短的配送路徑。配送中心用字母O表示，其他九個配送水站依次用字母A、B、C、D、E、F、G、H、I表示。

通過對數據進行整理和實際調研，可以假設北京農夫山泉由一輛運力充足的車輛負責配送各個水站所需的貨物，在不考慮配送的時間條件下，在其配送過程中尋找最短路徑。文章的研究對象是從配送中心出發，然后經過所有配送水站進行補貨，最后返回配送中心，其中配送中心到各個水站之間的直線距離如表1所示。

3.2?在Lingo軟件中求解TSP模型

在Lingo軟件中TSP模型的編碼程序的求解步驟如下所示：第一步，輸入相應的變量和系數，然后輸入北京農夫山泉配送中心和各個配送水站，每個水站之間的距離、配送中心到各水站的直線距離的數據；第二步，對已有數據進行程序運算；第三步，輸出相對應的結果。程序運算結果如圖2所示。

在Lingo軟件中輸入收集的數據，使用Lingo軟件運行TSP的程序算法。得到優化后的配送路徑，如表2所示。并將運行結果用表格的形式展現出來，由表2可知，0代表不經過該路線，1代表經過該路線。北京農夫山泉配送路徑以及總距離如表3所示。

3.3?求解結果分析

根據Lingo軟件TSP模型的運算結果分析，優化后的路線為：1-4-3-2-6-7-9-8-10-5-1，將優化后的路線用字母表示為：O-C-B-A-E-F-H-G-I-D-O，最終優化后的配送路徑總里程約為45.4km，對比之前所用路線的總里程54.6km，可以明確地看出配送路徑總里程減少了9.2km。優化后的路徑如圖3所示。

4?解決方案

在前文中知道北京農夫山泉的配送路線中存在迂回運輸，其原本的配送路線中從配送點H先去到了配送點F然后才到達配送點I，造成了迂回的運輸路線。通過運算結果顯示，在配送點H處可以先去往配送點G然后再去往配送點I可以減緩迂回路線；在其原本的配送路線中從配送點E開始依次去到了配送點G、H、F、I，這樣造成了過遠路線。通過運算結果顯示，從配送點E開始可以先去到配送點F，然后依次去往配送點H、G、I，以這樣的配送路線來配送，可以大大地減少運輸總里程，降低運輸成本。

對于配送運輸不必只局限于對本公司的貨物運輸，還可以在不影響本公司配送的前提下，尋找可以合作的企業，在本公司的運輸路線下對其企業的貨物進行運輸并收取相應的運費，建立互通有無的合作關系。

同時，也可以在返程的途中購買企業所需的用品。還需要通過自身的數據庫，盡己所能地把握貨物信息、車輛信息及采購信息，并做到及時與貨車司機溝通，將返程空駛的問題解決。

比如在配送站I附近有一家小的商店，他們每次進貨需要跑到配送中心O附近的批發市場進行采購，每次采購東西的時候批發市場是不會派車輛給他們進行運輸的，需要他們自己去找車輛。

如果可以和北京農夫山泉達成合作，不僅可以減少一部分采購費用，還可以使北京農夫山泉在這個過程中解決返程空駛的問題，同時增加一部分盈利。

5?結論

隨著現代物流產業的急速發展，配送路徑是否合理一直是物流配送過程中不斷研究討論的問題。文章以北京農夫山泉的配送路徑優化為研究目標，通過研究其現有配送路徑以及其在配送過程中存在過遠運輸、迂回運輸和返程空駛等問題，從現有配送路徑進行分析，建立相對應的數學模型，運用Lingo軟件的TSP算法進行求解，得出最優的配送路徑，同時也能為其他企業的配送路徑優化提供借鑒。總結本篇文章，得出以下結論。

第一，文章利用Lingo軟件對北京農夫山泉的配送路徑進行分析優化，成功地將其配送路徑總里程從54.6km降低到45.4km，總配送路徑減少9.2km。設計了新的配送路徑，解決了原有配送路徑中存在的過遠運輸和迂回運輸問題，能夠有效地提升配送運輸效率，控制運輸配送成本，對企業的實際運營管理有著較大的現實意義。

第二，為了確保司機能夠在新規劃的路徑上進行運輸，北京農夫山泉還需加強監管機制，對每次運輸的過程進行記錄，規范員工們的行為；還應尋找合作企業，可以對其公司的商品在自身路線中進行運輸，解決返程空駛的問題。建立自身數據庫，更明確地把握車輛的運輸情況。

參考文獻：

[1]尚猛，萬志鵬，曹峻瑋，等.基于改進鯨魚優化算法的物流路徑優化[J].數學的實踐與認識，2019，49（15）：210-218.

[2]郭寶恩.基于Spark的蟻群算法在物流配送路徑優化問題中的應用研究[J].信息與電腦（理論版），2018（3）：50-52.

[3]田鴿，薛冬娟，梁斌，等.基于改進蟻群算法的冰鮮水產品配送路徑優化方法研究[J].大連海洋大學學報，2019，34（5）：746-751.

［作者簡介］高一丹（2002—），女，山西忻州人，天津科技大學經濟與管理學院，研究方向：財務管理；張鈺瑤（2002—），女，山西晉城人，上海師范大學化學與材料科學學院，研究方向：應用化學；鄭巧（2001—），女，重慶人，西南財經大學國際商學院，研究方向：國際商務（中外合作辦學）；徐成鈺（2003—），女，山東濰坊人，山東科技大學外國語學院，研究方向：英語；通訊作者：趙萌（2004—），女，河北承德人，西南財經大學管理科學與工程學院，研究方向：信息管理與信息系統。