基于Dijsktra-PSO算法求解城市配送路線優(yōu)化問題研究

摘 要：對城市配送路線的設(shè)計進行了研究，在復(fù)雜的城市道路選擇上，首先采用Dijsktra算法求解單源最短可行性路徑，從而得到配送中心到客戶以及客戶到客戶之間的物流配送網(wǎng)絡(luò)；其次運用粒子群算法的自適應(yīng)性和魯棒性，設(shè)計出城市配送路線優(yōu)化方案；最后將優(yōu)化后的配送效果與原來的配送計劃進行對比分析，發(fā)現(xiàn)優(yōu)化后的路徑更短，效果更優(yōu)，可為解決城市配送問題提供實際參考。

關(guān)鍵詞：路徑優(yōu)化；Dijsktra算法；粒子群算法

中圖分類號：TP18；F252 文獻標(biāo)識碼：A 文章編號：2096-4706（2024）08-0156-06

DOI：10.19850/j.cnki.2096-4706.2024.08.034

收稿日期：2023-09-12

基金項目：江蘇省高等教育教改研究立項課題項目（2019JSJG367）；江蘇高?！扒嗨{工程”

0 引 言

相比較于長距離的運輸，城市配送的交通道路四通八達，可選擇性路徑的數(shù)量更多，在每一次交通道路交叉點就面臨一次線路選擇，而每一次選擇的不同，構(gòu)成的路徑就不同，因此，配送路線的選擇更加復(fù)雜。車輛路徑問題（Vehicle Routing Problem， VRP）是運籌學(xué)領(lǐng)域研究的熱點問題之一，由Dantzing等人于1959年首先提出來[1]，是配送優(yōu)化中的關(guān)鍵問題，也是組合優(yōu)化問題中經(jīng)典的NP難題[2]。

在車輛路徑問題的求解方法上，目前學(xué)者們展開了豐富的研究。張莉[3]采用粒子群算法中的學(xué)習(xí)因子優(yōu)化技術(shù)，設(shè)定船只調(diào)度計算模塊，完成海上物流智能配送系統(tǒng)的設(shè)計工作；劉娜翠等[4]通過使用改進的遺傳算法求解以費用最小為目的的帶時間窗的整車物流配送問題；楊倩等[5]認(rèn)為改進粒子群算法的解優(yōu)于自適應(yīng)粒子群算法且運行時間短；明小菊等[6]認(rèn)為利用萊維飛行和反向?qū)W習(xí)對粒子群算法進行優(yōu)化用于模型求解；李董潔等[7]認(rèn)為整車運輸問題可以分為兩段模型進行求解，長距離跨省運輸采用Dijsktra算法進行求解，對于整車短距離省內(nèi)運輸可以采用改進粒子群算法以成本最小為模型進行求解。

本文在滿足需求點配送輛和配送時間要求的前提下，以配送距離最短為模型目標(biāo)，利用Dijsktra算法和粒子群算法相結(jié)合的方法求解最優(yōu)配送方案，以期為城市物流配送的優(yōu)化提供參考。

1 VRP模型假設(shè)和參數(shù)描述

1.1 VRP模型假設(shè)

為了提高研究的效率和實用性，提出以下假設(shè)：

1）配送中心能夠滿足所有客戶的需求量。

2）配送中心的車輛的容量、型號、運量都已知，且每輛車在裝載過程中都不會超載，中途不會出現(xiàn)拋錨現(xiàn)象，不會超過當(dāng)天車輛的最大里程數(shù)。

3）每個客戶的貨物需求量和需求時間均為已知。

4）假設(shè)車輛不論是什么路段，均采用勻速行駛，不同路段的速度根據(jù)擁堵情況根據(jù)擁堵指數(shù)呈倍數(shù)關(guān)系。

5）假設(shè)操作工的單位貨物卸載速度不變，卸貨時間與貨物量呈正比的線性關(guān)系。

6）假設(shè)客戶需要的貨物在裝車的過程中可以進行混裝。

7）假設(shè)每個客戶每日只能由一個配送車輛為其送貨，但每個配送車輛可以配送多個客戶。

1.2 模型相關(guān)參數(shù)的描述

根據(jù)本文需要，相關(guān)參數(shù)所示的意義如下：

C表示總的運輸距離；dij表示運輸車輛在客戶i點至客戶j點之間的距離，當(dāng)i = 0時，表示配送中心；I = {i | i = 0，1，2，3，…，n}表示配送點集合，i = 0時，表示的含義是配送中心；K = {k | k = 0，1，2，3，…，m}表示可選擇的車輛的集合；m表示車輛總數(shù)；n表示客戶總數(shù)；Qj表示表示配送點j的運載量； 表示第k輛車從配送中心到客戶j的運輸時間；Mk表示第k輛車的最大載重量； 表示第k輛車到達客戶i后卸貨花費的作業(yè)時間；Tij表示配送車輛從客戶i到客戶j花費的貨運時間；[ei，li] （i = 1，2，3，…，n）表示配送中心與客戶i預(yù)先定好的送貨時間窗。

2 VRP模型目標(biāo)函數(shù)的構(gòu)建

2.1 VRP目標(biāo)函數(shù)的構(gòu)建

本文基于對城市物流配送問題的分析，根據(jù)南通大數(shù)據(jù)顯示，南通交通的擁堵現(xiàn)狀依舊位列文明交通暢通城市前三名，因此在文章的模型構(gòu)建中基本可以忽略南通城市擁堵因素對路徑優(yōu)化的影響，所以將物流配送距離作為目標(biāo)，構(gòu)建目標(biāo)函數(shù)。目標(biāo)函數(shù)算式為：

（1）

2.2 VRP約束條件構(gòu)建

根據(jù)配送目標(biāo)為配送距離最小化，本文所建立模型的約束條件包括車輛、客戶和配送時間窗，具體表現(xiàn)如下。

2.2.1 車輛的約束

1）公司每輛車都參與配送：

（2）

2）每輛車的實際貨物載重量小于車輛最大載重量：

（3）

3）所有車輛的總運輸量大于所有客戶的總運輸量：

（4）

2.2.2 客戶的約束

1）所有的客戶需求均被滿足：

（5）

2）每一個客戶配送過程由唯一車輛提供服務(wù)：

（6）

2.2.3 配送時間窗的約束

1）每個客戶的配送時間都在時間窗允許的范圍內(nèi)：

（7）

2）到達客戶點的時間由到達前一個客戶的時間，加上前一個客戶的卸貨時間和車輛在客戶之間的運輸時間：

（8）

3 案例介紹

3.1 企業(yè)案例介紹

本文研究區(qū)域主要為南通市的主城區(qū)，以企業(yè)配送中心為起點，對客戶進行每日配送。通過前期實踐調(diào)研發(fā)現(xiàn)，在日常的配送安排中，調(diào)度員會根據(jù)各個客戶的地理位置對其進行區(qū)域劃分，再根據(jù)各個點的需求量將每輛車輛發(fā)貨任務(wù)安排好了之后，貨車司機根據(jù)被安排到的客戶，由地圖多個目的地進行導(dǎo)航，或者是按照自身經(jīng)驗來進行配送。實際上，由于客戶的每日要貨需求變化不大，在調(diào)度安排和路線選擇時變化也不是特別大。數(shù)據(jù)收集包括門店信息、客戶需求量、貨物均價、送貨時間窗以及配送點之間的可行路徑數(shù)據(jù)，如表1所示。

3.2 企業(yè)配送現(xiàn)狀

在日常配送中，配送路線計劃主要是根據(jù)駕駛員的配送經(jīng)驗或是TMS手機APP軟件或是導(dǎo)航地圖推薦來安排具體工作的，這樣的線路安排在某種程度上是十分合理的，但卻不是我們要尋求的最短配送路徑。通過實地走訪調(diào)研，獲得原始的配送方案，如表2所示，其中0表示配送中心，數(shù)字1～12指每一個客戶點。

4 VRP模型求解企業(yè)案例

4.1 Dijkstra算法求解最短距離

4.1.1 基本思想

Dijkstra算法采用的是一種貪心的策略，解決的是有權(quán)圖中單源最短路徑問題[8]，基本思想可以表述為，在一個圖G = （V，E）中，有n個點，邊上的權(quán)重記為兩點距離，計算過程以起始點為中心向外層層擴展求解距離起點的最短路徑，直到擴展到終點為止。計算方法一般有兩種方式，一種是標(biāo)號法，一種是用OPEN、CLOSE表的方式。

4.1.2 可行路徑網(wǎng)絡(luò)構(gòu)建

文章研究的是城市配送，城市道路錯綜復(fù)雜、四通八達，可選擇通行的道路有很多，配送點之間的可通行路徑并不唯一。因此，為解決點到點的最短路徑問題可以采用構(gòu)建可行性路徑網(wǎng)絡(luò)的方式，在此基礎(chǔ)上，相較于采用坐標(biāo)計算的方式確定兩點之間的距離，文章采用地圖推薦路線的方式，在地圖中輸入地點名稱，選擇駕車搜索方式，地圖中會推薦多條可選擇性路徑，根據(jù)推薦的多條路線規(guī)劃的方式在實踐中可操作性更強一些，計算出的結(jié)果更加符合實際。

4.1.3 物流配送網(wǎng)絡(luò)構(gòu)造

根據(jù)地圖的搜索結(jié)果，將可行性路徑抽象為網(wǎng)絡(luò)模型，可以直接得到無權(quán)有向可行路徑網(wǎng)絡(luò)，但這還無法直接計算出兩點之間的最短路徑，需要進一步計算得出連接點之間的距離，即對每條邊賦予權(quán)值。根據(jù)經(jīng)驗，本文運用了地圖的測距工具獲取每條路段的地理距離，以佳源食品（南通）有限公司到南通業(yè)佳商貿(mào)有限為例，如圖1所示，距離單位為米。

4.1.4 Dijkstra算法求解步驟

運用Dijsktra算法計算從佳源食品（南通）有限公司到南通業(yè)佳商貿(mào)有限公司的可行性網(wǎng)絡(luò)之間的最短距離，本文在計算過程中主要采用標(biāo)號法進行計算，具體計算步驟如下：

1）首先給佳源食品（南通）有限公司以P標(biāo)號。P佳= 0，X = {佳源食品（南通）有限公司}。

2）min{d佳a} = min{0 + 330} = 330，X = {佳源食品（南通）有限公司，a}，pa = 330。

3）min{dai，dab} = {330 + 980，330 + 600}={1 310，930} = 930，X = {佳源食品（南通）有限公司，a，b}，pb = 930。

4）min{dai，dbc} = min{330 + 980，930 + 2 000} = min{1 310，2 930} = 1 310，X = {佳源食品（南通）有限公司，a，b，i}，Pi = 1 310。

5）min{dih，dbc} = min{1 310 + 3 140，930 + 2 000} = min{4 450，2 930} = 2 930，X = {佳源食品（南通）有限公司，a，b，i，c}，pc = 2 930。

6）min{dch，dcd，dih} = {2 930 + 900，2 930 + 750，1 310 + 3 140} = min{3 830，3 680，4 450} = 3 680，X = {佳源食品（南通）有限公司，a，b，i，c，d}，pd = 2 930。

7）min{dch，dih，dde} = {2 930 + 900，1 310 + 3 140，3 680 + 1 130} = min{3 830，4 450，4 810} = 3 830，X = {佳源食品（南通）有限公司，a，b，i，c，d，h}，ph = 3 830。

8）min{dhg，dhe，dde} = {3 830 + 1 300，3 830 + 860，3 680 + 1 130} = min{5 130，4 690，4 810} = 4 690，X = {佳源食品（南通）有限公司，a，b，i，c，d，h，e}，pe = 4 690。

9）min{dhg，def} = min{3 830 + 1 300，4 690 + 970} = min{5 130，5 660} = 5 130，X = {佳源食品（南通）有限公司，a，b，i，c，d，h，e，g}，pg = 5 130。

10）min{dgf，def} = min{5 130 + 1 000，4 690 + 970} = min{6 130，5 660} = 5 660，X = {佳源食品（南通）有限公司，a，b，i，c，d，h，e，g，f}，pf = 5 660。

11）min{df南} = min{5 660 + 670} = 6 330，X = {佳源食品（南通）有限公司，a，b，i，c，d，h，e，g，f，南通業(yè)佳商貿(mào)有限公司}，p南 = 6 330。

通過計算，可以得出p南 = 6 330。因此，從佳源食品（南通）有限公司到南通業(yè)佳商貿(mào)有限公司的可行性網(wǎng)絡(luò)之間的最短距離為6.33千米，路徑為佳源食品（南通）有限公司→ a → b → c → h → e → f →南通業(yè)佳商貿(mào)有限公司。這條路徑在地圖線路推薦和最短路徑中并未顯示，但卻是最短距離。對本文13個點每兩個點組成的156條路徑運用Dijsktra算法篩選出兩兩點之間的唯一路徑，因數(shù)據(jù)較多，本文采用Dijsktra代碼的方法計算結(jié)果，構(gòu)成一個物流配送網(wǎng)絡(luò)，如表3所示。

4.2 粒子群算法求解最優(yōu)車輛路徑

4.2.1 基本思想

粒子群算法（Particle Swarm Optimization， PSO）是由Eberhart等于1995年共同提出的一種進化計算技術(shù)[9]，該算法通過模擬鳥群捕食行為進行設(shè)計，利用群體中個體對信息的共享使整個群體的運動從無序演化為有序，每個優(yōu)化問題的潛在解稱之為“粒子”（Particle），在算法不同時期采用不同的慣性權(quán)重和學(xué)習(xí)因子，能夠在一定程度上改善算法的收斂[10]。

D維空間中，有m個粒子，粒子i位置：xi = （xi1，xi2，…，xiD）T，粒子i速度：vi = （vi1，vi2，…，viD）T，1≤i≤m，1≤d≤D；粒子i經(jīng)歷過的歷史最好位置：pi = （pi1，pi2，…，piD）T，群體內(nèi)（或領(lǐng)域內(nèi)）所有粒子所經(jīng)歷過的最好位置：pg = （pg1，pg2，…，pgD）T。

基本的PSO計算式為：

粒子i的第d維速度更新算式：

（9）

粒子i的第d維位置更新算式：

（10）

其中： 表示第K次迭代粒子i飛行速度矢量的第d維分量； 表示第K次迭代粒子i位置矢量的第d維分量；c1、c2表示學(xué)習(xí)因子或加速系數(shù)，即粒子自身加速度權(quán)重系數(shù)，一般取值在0～2之間；r1、r2表示介于[0，1]之間的隨機數(shù)；Vmax表示粒子速度能達到的最大值；W表示慣性權(quán)重系數(shù)，調(diào)節(jié)對解空間得搜索能力，隨迭代次數(shù)線性減少。

4.2.2 求解步驟

粒子群算法具有一定的復(fù)雜性，算法流程如下所示：

1）隨機初始化粒子群X、V。

2）計算每個粒子的適應(yīng)值。

3）根據(jù)適應(yīng)值更新Pi、Pg，更新粒子位置速度和位置。

4）確認(rèn)達到迭代次數(shù)或者精度要求，達到要求，轉(zhuǎn)至5），若沒有達到要求，返回至2）。

5）輸出所需參數(shù)。

4.2.3 參數(shù)設(shè)置與分析

根據(jù)粒子群算法的描述和已有的研究成果，粒子群算法的模型中，主要有以下參數(shù)變量：慣性權(quán)值w，加速因子c1、c2，種群數(shù)N，迭代次數(shù)Loop_max，粒子維數(shù)D。本文的參數(shù)設(shè)置如下：

1）慣性權(quán)重w的大小決定了粒子在多大程度上保留了原來的速度，w值設(shè)置的過大或過小，都會影響到算法在求解時收斂能力。本文將w的值設(shè)置為0.729，并將其運用到粒子位置更新的幅度。

2）加速因子c1和c2分別用于控制指向自身或鄰域最佳位置的運動，一般取值在0～4，兩者的和小于等于4。本文取c1 = c2 = 1.494 45，用于計算粒子位置更新的速度。

3）種群規(guī)模N的設(shè)置，根據(jù)經(jīng)驗，種群規(guī)模太小則通常不能提供足夠的采樣點，容易導(dǎo)致算法性能較差，難以獲取最優(yōu)解；可是，如果種群規(guī)模過大，勢必會增加整體計算量，從而導(dǎo)致收斂時間過長，即收斂速度緩慢。本文根據(jù)實際情況將N設(shè)置為12用于求解最優(yōu)路徑。

4）迭代次數(shù)Loop_max的大小決定了解的收斂，太小解值不太穩(wěn)定，太大計算浪費時間，本文將Loop_max設(shè)置為50。

5）粒子維數(shù)D取決于有待優(yōu)化函數(shù)的維數(shù)，即粒子群中粒子的個數(shù)，本文取1 000。

4.2.4 算法實現(xiàn)

本文選擇MATLAB軟件進行配送路徑優(yōu)化工作，得出粒子群算法收斂圖如圖2所示，其中橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)表示路徑長度。

本次算法在第20次迭代中趨于穩(wěn)定，數(shù)值穩(wěn)定在164.72千米，具體粒子群算法結(jié)果如表4所示，其中0表示南通某配送中心，數(shù)字1～12指每一個客戶點。

4.3 優(yōu)化結(jié)果分析

用MATLAB仿真軟件優(yōu)化得出的優(yōu)化后新配送方案中，新計劃中依然使用3輛冷藏運輸車，每輛車的總載重量都在額定載重3.5噸以下。從每輛車分配客戶的個數(shù)上看，新方案中車輛分配的客戶個數(shù)比老方案總個數(shù)更均勻，每輛車的配送客戶數(shù)量和貨物載重相對一致，較之前的配送方案，不會產(chǎn)生因為某輛車配送客戶較多而開關(guān)門的次數(shù)較多的現(xiàn)象，減少了貨損機會；從車輛載重的對比分析可得，新老方案車輛都沒有超載，貨量分配相對都相對比較均勻，能夠滿足客戶需求；從每輛車的配送里程對比發(fā)現(xiàn)，新方案中總的配送路程為164.72千米，比原來方案中配送里程179千米縮短了14.28千米，在城市小范圍的配送中具有一定的效果，如表5所示。

5 結(jié) 論

文章在滿足需求點的配送量和配送時間窗的前提下，以最短配送距離為目標(biāo)構(gòu)建城市配送路線優(yōu)化模型，運用Dijkstra算法和粒子群算法相結(jié)合的求解方法設(shè)計了城市配送路線，結(jié)果表明，優(yōu)化后的配送方案效果更優(yōu)，驗證了Dijkstra算法和粒子群算法在解決配送路徑優(yōu)化問題的價值，所得研究成果能夠幫助企業(yè)在城市配送中合理安排配送方案，有效降低企業(yè)成本。然而，文章在研究配送路線方案時未考慮交通堵塞、單行道問題以及客戶對配送時間先后順序的要求，后續(xù)研究中將盡可能地考慮一些可能性因素對模型的影響，從而提升模型的適應(yīng)度。

參考文獻：

[1] DANTZIG G B，RAMSER J H. The Truck Dispatching Problem [J].Management Science，1959，6（1）：80-91.

[2] 楊笑笑，柯琳，陳智斌.深度強化學(xué)習(xí)求解車輛路徑問題的研究綜述 [J].計算機工程與應(yīng)用，2023，59（5）：1-13.

[3] 張莉.基于粒子群算法的海上物流智能配送系統(tǒng) [J].艦船科學(xué)技術(shù)，2020，42（10）：196-198.

[4] 劉娜翠，張?zhí)m怡，楊映艷，等.基于遺傳算法的汽車整車銷售物流配送路徑優(yōu)化 [J].數(shù)學(xué)的實踐與認(rèn)識，2021，51（7）：35-42.

[5] 楊倩，陳再良.基于改進粒子群算法的車間物料配送方法研究 [J].機械設(shè)計與制造，2022（8）：238-241.

[6] 明小菊，珠蘭.城市生鮮食品冷鏈物流配送路徑優(yōu)化技術(shù)研究 [J].包裝與食品機械，2022，40（2）：76-81.

[7] 李董潔，梁革英.整車智能調(diào)度運輸研究 [J].物流工程與管理，2022，44（2）：103-109.

[8] 張亞東，李起宏，陸濤濤，等.基于多源迪杰斯特拉搜索和擁塞協(xié)商的詳細(xì)布線 [J].中國集成電路，2022，31（4）：53-58+63.

[9] EBERHART R C，SHI Y. Comparing inertia weights and constriction factors in particle swarm optimization [C].Proceedings of the 2000 Congress on Evolutionary Computation.La Jolla：IEEE，2000：84-88.

[10] 王翼虎，王思明.基于改進粒子群算法的無人機路徑規(guī)劃 [J].計算機工程與科學(xué)，2020，42（9）：1690-1696.

作者簡介：孫紅冉（1989—），女，漢族，江蘇徐州人，經(jīng)濟師、實驗師，碩士，研究方向：物流工程、物流實踐教學(xué)；施彥（1984—），男，漢族，江蘇南通人，經(jīng)濟師、高級實驗師，碩士，研究方向：物流工程。

Research on Urban Delivery Path Optimization Problem Based on Dijsktra-PSO Algorithm

SUN Hongran， SHI Yan

（Jiangsu Vocational College of Business， Nantong 226011， China）

Abstract： A study is conducted on the design of urban delivery paths. In the selection of complex urban roads， the Dijsktra algorithm is first used to solve the shortest feasible path of a single source， thereby obtaining the logistics delivery network from the delivery center to customers and from customers to customers. Secondly， it designs an optimization plan for urban delivery paths using the adaptability and robustness of particle swarm optimization. Finally， the optimized delivery effect is compared with that of the original delivery plan， and it is found that the optimized path is shorter and the effect is better， which can provide practical reference for solving urban delivery problems.

Keywords： path optimization; Dijsktra algorithm; Particle Swarm Optimization