基于TSP模型的企業(yè)配送線路優(yōu)化設(shè)計(jì)

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

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

關(guān)鍵詞：配送運(yùn)輸成本；配送路徑優(yōu)化；TSP模型

中圖分類號(hào)：F252文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1005-6432（2024）14-0167-04

DOI：10.13939/j.cnki.zgsc.2024.14.040

1?北京農(nóng)夫山泉配送線路現(xiàn)狀

配送是整個(gè)物流活動(dòng)系統(tǒng)中一個(gè)重要因素，產(chǎn)品可以通過(guò)配送產(chǎn)生更高的價(jià)值。而在北京農(nóng)夫山泉的配送過(guò)程中，由于公司沒有規(guī)定具體的配送路徑，這就需要司機(jī)憑借自己的經(jīng)驗(yàn)來(lái)做出判斷。北京農(nóng)夫山泉的配送方法是從配送中心向各個(gè)水站配送，車輛會(huì)經(jīng)過(guò)每個(gè)水站然后返回配送中心。

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

圖1?北京農(nóng)夫山泉桶裝水配送路徑

2?配送線路現(xiàn)存問(wèn)題分析

2.1?存在迂回運(yùn)輸

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

2.2?存在過(guò)遠(yuǎn)運(yùn)輸

在配送點(diǎn)E、F、G、H四個(gè)配送點(diǎn)中存在多種路線可以選擇，司機(jī)在配送這幾個(gè)站點(diǎn)時(shí)選擇了先去站點(diǎn)G再轉(zhuǎn)到站點(diǎn)H，最后去到站點(diǎn)F，然后在返回時(shí)還要去到站點(diǎn)I，這就造成了整個(gè)運(yùn)輸過(guò)程中產(chǎn)生了過(guò)遠(yuǎn)運(yùn)輸。

2.3?存在空駛情況

在實(shí)際走訪中，了解到在實(shí)際配送中，有時(shí)候運(yùn)輸組織人員為了緊急調(diào)運(yùn)不得不將未裝滿的車輛進(jìn)行緊急調(diào)運(yùn)。北京農(nóng)夫山泉在實(shí)際配送中，不能夠?qū)Ω鱾€(gè)水站的存量進(jìn)行統(tǒng)計(jì)，需要另發(fā)單車進(jìn)行補(bǔ)貨，這就會(huì)造成空車行駛和空車返程的問(wèn)題。

3?北京農(nóng)夫山泉配送路徑優(yōu)化模型構(gòu)建

3.1?配送路徑優(yōu)化模型構(gòu)建

3.1.1?具體問(wèn)題描述

北京農(nóng)夫山泉桶裝水的配送路徑優(yōu)化問(wèn)題可以描述為：從北京農(nóng)夫山泉的配送中心出發(fā)，依次向其所有的水站進(jìn)行貨物配送，并最終返回配送中心。在這過(guò)程中會(huì)有很多的路線進(jìn)行選擇，需要找到配送里程最短的方案。

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

3.1.2?整理收集數(shù)據(jù)

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

通過(guò)對(duì)數(shù)據(jù)進(jìn)行整理和實(shí)際調(diào)研，可以假設(shè)北京農(nóng)夫山泉由一輛運(yùn)力充足的車輛負(fù)責(zé)配送各個(gè)水站所需的貨物，在不考慮配送的時(shí)間條件下，在其配送過(guò)程中尋找最短路徑。文章的研究對(duì)象是從配送中心出發(fā)，然后經(jīng)過(guò)所有配送水站進(jìn)行補(bǔ)貨，最后返回配送中心，其中配送中心到各個(gè)水站之間的直線距離如表1所示。

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

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

在Lingo軟件中輸入收集的數(shù)據(jù)，使用Lingo軟件運(yùn)行TSP的程序算法。得到優(yōu)化后的配送路徑，如表2所示。并將運(yùn)行結(jié)果用表格的形式展現(xiàn)出來(lái)，由表2可知，0代表不經(jīng)過(guò)該路線，1代表經(jīng)過(guò)該路線。北京農(nóng)夫山泉配送路徑以及總距離如表3所示。

3.3?求解結(jié)果分析

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

4?解決方案

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

對(duì)于配送運(yùn)輸不必只局限于對(duì)本公司的貨物運(yùn)輸，還可以在不影響本公司配送的前提下，尋找可以合作的企業(yè)，在本公司的運(yùn)輸路線下對(duì)其企業(yè)的貨物進(jìn)行運(yùn)輸并收取相應(yīng)的運(yùn)費(fèi)，建立互通有無(wú)的合作關(guān)系。

同時(shí)，也可以在返程的途中購(gòu)買企業(yè)所需的用品。還需要通過(guò)自身的數(shù)據(jù)庫(kù)，盡己所能地把握貨物信息、車輛信息及采購(gòu)信息，并做到及時(shí)與貨車司機(jī)溝通，將返程空駛的問(wèn)題解決。

比如在配送站I附近有一家小的商店，他們每次進(jìn)貨需要跑到配送中心O附近的批發(fā)市場(chǎng)進(jìn)行采購(gòu)，每次采購(gòu)東西的時(shí)候批發(fā)市場(chǎng)是不會(huì)派車輛給他們進(jìn)行運(yùn)輸?shù)?，需要他們自己去找車輛。

如果可以和北京農(nóng)夫山泉達(dá)成合作，不僅可以減少一部分采購(gòu)費(fèi)用，還可以使北京農(nóng)夫山泉在這個(gè)過(guò)程中解決返程空駛的問(wèn)題，同時(shí)增加一部分盈利。

5?結(jié)論

隨著現(xiàn)代物流產(chǎn)業(yè)的急速發(fā)展，配送路徑是否合理一直是物流配送過(guò)程中不斷研究討論的問(wèn)題。文章以北京農(nóng)夫山泉的配送路徑優(yōu)化為研究目標(biāo)，通過(guò)研究其現(xiàn)有配送路徑以及其在配送過(guò)程中存在過(guò)遠(yuǎn)運(yùn)輸、迂回運(yùn)輸和返程空駛等問(wèn)題，從現(xiàn)有配送路徑進(jìn)行分析，建立相對(duì)應(yīng)的數(shù)學(xué)模型，運(yùn)用Lingo軟件的TSP算法進(jìn)行求解，得出最優(yōu)的配送路徑，同時(shí)也能為其他企業(yè)的配送路徑優(yōu)化提供借鑒。總結(jié)本篇文章，得出以下結(jié)論。

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

第二，為了確保司機(jī)能夠在新規(guī)劃的路徑上進(jìn)行運(yùn)輸，北京農(nóng)夫山泉還需加強(qiáng)監(jiān)管機(jī)制，對(duì)每次運(yùn)輸?shù)倪^(guò)程進(jìn)行記錄，規(guī)范員工們的行為；還應(yīng)尋找合作企業(yè)，可以對(duì)其公司的商品在自身路線中進(jìn)行運(yùn)輸，解決返程空駛的問(wèn)題。建立自身數(shù)據(jù)庫(kù)，更明確地把握車輛的運(yùn)輸情況。

參考文獻(xiàn)：

[1]尚猛，萬(wàn)志鵬，曹峻瑋，等.基于改進(jìn)鯨魚優(yōu)化算法的物流路徑優(yōu)化[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2019，49（15）：210-218.

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

[3]田鴿，薛冬娟，梁斌，等.基于改進(jìn)蟻群算法的冰鮮水產(chǎn)品配送路徑優(yōu)化方法研究[J].大連海洋大學(xué)學(xué)報(bào)，2019，34（5）：746-751.

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