配送車輛路徑規劃研究

孫暢 宋佩馨

【摘 ?要】隨著經濟的快速增長和人們消費水平的提高，消費者對快遞服務的質量提出了更高的要求。快遞企業在電子商務中面臨著更大、更嚴峻的挑戰。為了解決送快遞慢、送快遞難的問題，使快遞行業更好的服務于大眾，Dijkstra算法和最小生成樹理論可以對快遞行業的配送路徑進行優化，從而提高快遞效率、降低快遞行業成本。通過采用Dijkstra算法和破圈法，系統地研究了ZT速遞服務公司的車輛配送路徑優化問題，得出了該公司快遞配送路徑總距離最短及服務成本最小的優化方案。

【關鍵詞】路徑規劃;Dijkstra算法;破圈法;最短配送路線

Research on Vehicle Route of Delivery of Express——Exemplified on ZT Express Company

1前言

隨著經濟的發展和消費水平的提高，人們對快遞服務的質量也提出了更高的要求。快遞業務在將物品送到客戶手中的同時，還要保證能夠在時間上滿足客戶的需求，更好、更快成為客戶對快遞公司的要求。本文以ZT快遞公司為研究對象，對其快遞配送路徑優化問題進行研究。

本文將從ZT公司快遞基站現狀、位置、配送路線進行分析，利用最短路模型針對速遞配送中的問題提出解決方法，對其發展提出合理化建議。具體思路方法即先根據Dijkstra算法確定兩個主要目標基站之間的最優線路，以此線路作為干路，再利用最小生成樹原理，通過破圈法把其余各點有序地連接成各個支路，與干路相連，達到線路最優解以提高運輸效率。

2相關理論

2.1 Dijkstra算法

戴克斯特拉算法（Dijkstra algorithm，又稱雙標號法）。戴克斯特拉算法使用了廣度優先搜索解決賦權有向圖的單源最短路徑問題。該算法存在很多變體;戴克斯特拉的原始版本找到兩個頂點之間的最短路徑，但是更常見的變體固定了一個頂點作為源節點然后找到該頂點到圖中所有其它節點的最短路徑，產生一個最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個子模塊。

Dijkstra算法的思路：Dijkstra算法采用的是一種貪心的策略，聲明一個數組來保存源點到各個頂點的最短距離和一個保存已經找到了最短路徑的頂點的集合：T，初始時，原點s的路徑權重被賦為0。若對于頂點 s 存在能直接到達的邊（s，m），則把數組設為w（s，m），同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大。最開始時，集合T只有頂點s。然后，在挑選出數值最小的點，那么這個點就是源點s到該值對應的頂點的最短路徑，并且把該點加入到T中，這個時候就又多了一個已知點，隨后，需要看看新加入的頂點是否可以到達其他頂點并且看看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果是，那么就替換這些頂點在數組中的值。然后，繼續挑選數值最小的點，重復以上計算，直到T中包含了圖的所有頂點，此時所有的頂點均已經有了自己的標號，從而推得最短路線。

2.2破圈法

破圈法是求最短生成樹問題的一個相對簡單的算法。這里講的樹，就是一個無圈的連通圖，是圖論里面的一個重要的概念，這里所說的最小生成樹就是在一個賦權的連通圖的無向圖找出一個生成樹，并使這個生成樹的所有邊的權數之和為最小。

破圈法即求最小生成樹的一個比較簡單的算法，破圈算法的具體步驟如下：

（1）在給定的賦權的連通圖上任找一個圈

（2）在所找的圈中去掉一條權數最大的邊（如果有兩條或兩條以上的邊都是權數最大的邊，則任意去掉其中一條。

（3）如果所余下的圖已不含圈，則計算結束，所余下的圖即為最小生成樹，否則返回步驟（1）。

經過若干次地循環上述步驟得到一個最小生成樹，就是所求方案。

3 ZT速遞配送問題分析

3.1快遞基站現狀

下圖是通過騰訊地圖以及實際走訪調查搜索到的基站地址。其中此公司有兩處倉儲物流中心，即集散地A和B，均在圖中有標示。

公司目前擁有2輛載重2噸的貨車，5輛載重1噸的貨車，還有若干量快遞電瓶車供快遞員使用。在快遞最繁忙的時間點，若大型車輛使用欠缺時，還會進行租賃車輛的使用。各基站與公司總部的貨物交流多是單獨運輸，即各基站負責自己的貨物的派送以及收取，對其他基站的貨物不進行操作，這一過程必然會造成大量的人力和物力的浪費。快遞人員對于路線優化能力和時間分配能力不足，導致在一定程度上影響了服務質量。

3.2 分析過程

3.2.1基本假設

根據實際情況，基于快遞車輛路徑優化問題的Dijkstra算法可以描述為：起點為集散地A或B。然后，根據公司的要求去其它各基站進行快遞的分發以及收取。為合理安排車輛的快遞路線，使快遞車輛總距離最短，建立相關的物流模型，現作出假設：

（1）負責干路的車輛容積是無限大，可以一次性地將各個支路匯集上來的貨物一次性地運抵次配送中心;

（2）各個基站的貨物數量權重是一樣的，無大小多少之分;

（3）不考慮道路的擁堵情況以及突發情況的發生。

（4）各點之間的路徑為直線

（5）兩個集散地A、B權重遠遠大于其它基站

3.2.2最短配送路線的求解

已知公司總部（集散地A）位置以及另一個次配送中心（集散地B）位置，即起點和終點位置，即可建立快遞路徑優化問題的數學模型。

Dijkstra算法的基本思想是，在快遞車輛分布的最短路徑問題描述的路徑網絡圖中為每個節點分配一個標號（an，bn），路徑網絡圖中的每個節點表示快遞公司每個基站的位置或快遞公司自己的配送中心的位置。從起點s到節點n的快遞車輛最短配送路徑長度將被記作an，從起點s到節點n的最短快遞配送路徑中n點的前一點會被記為bn，一個節點到其自身的最短路徑長度設為0，若兩節點之間不存在車輛行駛路徑，則其距離設為inf（即無窮大）。

在MATLAB計算程序中，集散地A設置為起點s。各基站都編上相應號碼，其中集散地A為2號，集散地B為20號。其次，根據圖1建立距離矩陣。然后在程序中編制相應的參數。最后，代碼運行后的解決方案結果如下所示：

Start id=2;

Finish id=20;

Distance=40.35

Path=[2 16 12 11 20];

Computing time=4;

即通過該算法在Matlab中的程序實現結果可得，起點為基站2即集散地A，終點為基站20即為集散地B，兩個集散地間距離為40.35km。分別經過基站2、16、12、11、20。

如上結果所示，如果該快遞車輛配送路徑網絡圖中基站數越多，則相應的算法循環次數越多，所以計算時間會相應增加。Dijkstra算法的執行過程會產生以s為頂點的一棵樹，同時伴隨著算法的進一步執行該樹會向四面八方延伸，直至最后到達終點為止，通過該算法可以準確的在快遞車輛配送路徑網絡圖中尋找出從起始點s到其他所有基站的最短路徑。利用Dijkstra算法可以迅速的對現有的快遞基站實施廣范圍的、最優化的配送路線的求解。

現在已知由集散地A到集散地B的行駛軌跡，已經確定了干路的路徑2-16-12-11-20。下一步將各個基站之間隨機連接起來，此時出現了若干個由基站組成的連通圖，利用破圈法，逐步去掉權數最大的邊，得到最小生成樹，如下圖

根據以上最小生成樹，可以發現所有基站都是通過2-16-12-11-20這條干路鏈接起來的，以派送快遞為例，外地送來以及要送到外地的包裹通過一輛經過基站2-16-12-11-20的大車依次分發和收集，所以派遣一輛大車專門負責集散地A和B之間的運輸，期間有其它專門車輛負責支路的運輸。這兩個集散地擁有同等的地位，車輛在配送過程中同時也負責包裹收取的工作，也就是說一輛車從集散地A到集散地B的過程中不僅進行了快遞的分發，同時也將各個基站收取上來的包裹運達集散地B。外發快件可以從集散地A和B出發，運至上級處理中心。

4結論

通過對ZT速遞服務公司配送路徑的現狀分析研究，構建出配送路徑優化的最佳模型，提出適合本企業現狀的送路徑優化方案，進而使中通快遞公司配送系統得到了規范化提升。現有工作快遞員有23名，采用快遞配送路線優化之后可以減少10人，人員成本節約了78%，快遞車輛數目也得到節約。

參考文獻：

[1]李建軍，沈嘯林，陳明賀，劉碩，陳舒研.基于最小生成樹算法的懷柔區快遞站點選址問題研究[J].南方農機，2019，50（01）：91-93.

[2]黃杭.淺談Dijkstra算法與Floyd算法[J].中國新通信，2019，21（03）：162-163.

[3]白玉鳳.共同配送下區域速遞配送中心選址和配送路徑優化[D].北京郵電大學，2016.

[4]鄭琰，孟曉露，伍佩琪，何雨飛.電子商務企業物流配送路徑優化研究[J].物流工程與管理，2018，40（06）：111-113

[5]都雪靜，孫菲菲，王云浩.小件快遞配送路徑優化研究[J].物流技術，2018，37（04）：29-35+40.

[6]丁浩，萇道方.基于Dijkstra算法的快遞車輛配送路徑優化[J].價值工程，2014，33（03）：15-18.

[7]劉艷紅.物流企業商品配送路徑規劃與優化分析[J].山西農經，2019（01）：159-160.

[8]郭儀，梁微，蘇相清，王暉.柳州融水電子商務物流配送路徑優化[J].價值工程，2018，37（16）：91-94

[9]都雪靜，孫菲菲，王云浩.小件快遞配送路徑優化研究[J].物流技術，2018，37（04）：29-35+40.

[10]孫蘇文.基于C2B2F模式的生鮮電商車輛路徑規劃研究[D].江蘇科技大學，2018.

[11]張欣.B2C電子商務下物流配送優化研究[D].江西財經大學，2017.

（作者單位：1保定理工學院（原中國地質大學長城學院）;2保定理工學院（原中國地質大學長城學院））