基于節(jié)約里程法的車輛配送路徑優(yōu)化研究

王智靈 周薔 王情香

摘 要：為提高快遞公司的配送效率，縮短配送的路程，降低物流配送成本，文章通過對A快遞公司向其下級網(wǎng)點配送快遞的實例研究，運用節(jié)約里程法優(yōu)化設計車輛配送路徑。結果表明：優(yōu)化后的配送路徑更短、消耗的配送時間更少、車輛平均裝載率更高，能夠為車輛配送路徑規(guī)劃提供思路和參考。

關鍵詞：節(jié)約里程法；車輛配送路徑；優(yōu)化；快遞公司

中圖分類號：F426；F252文獻標志碼：ADOI：10.13714/j.cnki.1002-3100.2023.12.004

Abstract： In order to improve the delivery efficiency of express delivery companies， shorten the delivery distance， and reduce logistics delivery costs， the paper uses the mileage saving method to optimize the design of vehicle delivery paths through a case study of A Express Delivery Company delivering express to its subordinate branches. The results indicate that the optimized delivery path is shorter， consumes less delivery time， and has a higher average vehicle loading rate， which can provide ideas and references for vehicle delivery path planning.

Key words： mileage saving method; vehicle distribution route; optimization; express company

0 ? ?引 ? ?言

物流作為現(xiàn)代商業(yè)活動的生命線，隨著我國經(jīng)濟和科學技術的發(fā)展，已成為國民經(jīng)濟的支柱產(chǎn)業(yè)，為解決不斷增長的快遞量所提出的優(yōu)化車輛配送路徑問題已成為現(xiàn)階段企業(yè)降低配送成本的一個重要途徑。因此，在優(yōu)化車輛配送路徑的問題上，眾多學者已展開了大量研究。1964年，Clarke和Wright首次提出節(jié)約里程法，并將其用于解決運輸車輛在向多個目的地配送貨物的過程中經(jīng)過多條運輸路線的最優(yōu)路徑問題。2011年，張穎敏基于節(jié)約里程法對物流配送線路進行優(yōu)化，并運用一組測試數(shù)據(jù)驗證了節(jié)約里程法的可行性，最后提出了將節(jié)約里程法和聚類分析法相結合可以較好解決大型復雜配送網(wǎng)絡中模型的改進方法[1]。2018年，有學者等研究了需求和旅行時間不確定條件下具有硬時間窗的車輛路徑問題，并設計了一種基于改進的自適應可變鄰域搜索啟發(fā)式兩階段算法。2020年，孫藝婕基于對多中心配送路徑問題和時間窗問題的詳細描述確定以配送總成本最小化為優(yōu)化目標，分析優(yōu)化目標的成本構成并引入必要的條件約束，最終建立帶時間窗的多中心配送路徑優(yōu)化模型[2]。2016年，湯齊等針對生鮮產(chǎn)品配送對車輛路徑優(yōu)化選擇進行研究，綜合考慮運輸成本、制冷成本及懲罰成本，結合時間約束建立模型，運用節(jié)約里程法優(yōu)化生鮮產(chǎn)品配送路徑[3]。通常快遞公司在收到快遞后會先把分屬不同區(qū)域的快遞分揀好，然后配送給相應的下級快遞配送網(wǎng)點。A快遞公司從上一級快遞配送節(jié)點收到屬地為A公司的快遞后，把要發(fā)往不同下級快遞配送網(wǎng)點的快遞分揀出來，最后將分揀好的快遞配送到下級配送網(wǎng)點。然而A公司在向其下級配送網(wǎng)點配送快遞的過程中存在著沒有統(tǒng)籌安排配送路徑、沒有統(tǒng)一調(diào)度配送車輛和配送總成本高等問題，導致該公司在配送質(zhì)量和配送效率方面沒有競爭優(yōu)勢，不利于企業(yè)的長期發(fā)展。因此，本文運用節(jié)約里程法來優(yōu)化該公司向其下級網(wǎng)點配送快遞的車輛路徑，從而提高配送效率，降低物流配送成本，為該公司車輛配送路徑規(guī)劃提供思路和參考。

1 ? ?節(jié)約里程法概述

1.1 ? ?節(jié)約里程法的核心思想

節(jié)約里程法又稱節(jié)約算法，在1964年由Clarke和Wright提出，是解決運輸車輛數(shù)目不確定條件下VRP問題的最有名的啟發(fā)式算法，可以同時確定配送過程中所需的最少車輛數(shù)和車輛行駛的路徑[3]。節(jié)約里程法的核心思想是在滿足約束條件的前提下依次將運輸問題中的兩個回路合并為一個回路，使每次合并后的總運輸距離減小的幅度最大，直到達到一輛車的裝載限制時再進行下一輛車的配送路徑優(yōu)化，以此類推，直到把所有客戶的貨物配送完畢。

1.2 ? ?節(jié)約里程法的基本原理

集散中心P為A、B兩家網(wǎng)點提供配送服務，P到網(wǎng)點A的最短距離為S1、P到網(wǎng)點B的最短距離為S2，網(wǎng)點A、B之間的最短距離為S3，網(wǎng)點A、B的快遞配送量分別為Q1、Q2，（Q1+Q2）之和不能超過配送車輛的最大載重量Q。

若集散中心P用兩輛車分別為A、B網(wǎng)點配送貨物，當貨物配送到網(wǎng)點后，配送車輛再原路返回集散中心P，如圖1所示，則配送車輛的總行駛距離為：

如果將上述配送方案改為在網(wǎng)點A、B兩家的快遞配送量之和不超過配送車輛的最大載重量的前提下，用一輛配送車為網(wǎng)點A、B配送貨物；只有把貨物配送完畢后，配送車才能返回集散中心P，如圖2所示，則配送車輛的總行駛距離為：

對比第一種配送方案，采用第二種配送方案節(jié)約的行駛里程為：

根據(jù)幾何學中的三角形定理：兩邊之和大于第三邊，可得出：S1+S2-S3＞0。

所以，如果集散中心P采用第二種配送方案，既可以少使用一輛配送車，又可以縮短配送車輛的行駛總里程，這樣不僅減少了配送時間，還降低了配送成本。集散中心在為多個網(wǎng)點配送貨物時，可以在不超過一輛配送車最大裝載限制的基礎上安排一輛配送車為節(jié)約里程量最多的網(wǎng)點群依次送貨。當所需配送的貨物量超過一輛配送車的最大裝載限制時就安排下一輛配送車配送貨物，若遇到快遞無法整裝的情況，就以節(jié)約量安排配送路徑；然后用相同的辦法來安排其余網(wǎng)點的配送路徑，直到把全部網(wǎng)點的快遞配送完畢。

1.3 ? ?節(jié)約里程法的主要步驟

1.3.1 ? ?收集A快遞公司各網(wǎng)點的地理位置信息

收集A快遞公司各網(wǎng)點的地理位置信息，利用互聯(lián)網(wǎng)、高德地圖工具測量A快遞公司至各網(wǎng)點和各網(wǎng)點之間的最短距離，制作出最短距離表。

1.3.2 ? ?編制節(jié)約里程表

根據(jù)最短距離表，使用節(jié)約里程量的計算公式3計算各網(wǎng)點之間的節(jié)約里程量。例如，由同一輛配送車從A快遞公司出發(fā)完成網(wǎng)點i和網(wǎng)點j的快遞配送任務，使用節(jié)約里程法得到的結果與初始配送方案相比就可以得到節(jié)約的里程數(shù)Z（i，j）。

1.3.3 ? ?編制節(jié)約里程排序表

按照節(jié)約里程數(shù)的大小排列節(jié)約里程表中的節(jié)約里程數(shù)，若節(jié)約里程數(shù)相同則并列排序，最終得出節(jié)約里程排序表。

1.3.4 ? ?制定配送路線

按照節(jié)約里程排序表中數(shù)據(jù)從大到小的順序及有關約束條件計算幾個網(wǎng)點之間能否用一輛配送車進行快遞的配送，若能，就連接A快遞公司的集散中心P與網(wǎng)點形成配送路線回路。若在一個依次由集散中心P到網(wǎng)點i再到網(wǎng)點j最后返回P的配送路線組成的回路中，可以由一輛配送車同時完成i點、j點的快遞配送任務，且不超過該配送車的最大裝載限制，則這個配送路線回路的合并是可行的。再合并其他網(wǎng)點的配送路線以不斷形成新的配送路線回路，直到?jīng)]有可以合并的符合約束條件的新回路，即得到最優(yōu)解。

2 ? ?當前配送概況

2.1 ? ?配送范圍

A快遞公司只為廣漢市城區(qū)內(nèi)距離超過一公里遠的韻達快遞網(wǎng)點及與韻達有合作的菜鳥驛站配送快遞，共有14個配送網(wǎng)點，地理位置如圖3所示，其中P代表A快遞公司，P1至P14代表客戶網(wǎng)點。

2.2 ? ?現(xiàn)有配送路徑

A快遞公司現(xiàn)有最大載重量為500千克、800千克的快遞配送車各2輛，在快遞體積小、重量輕且體積分布均勻的情況下，最大載重量為500千克的配送車一次最多可裝載600件快遞，最大載重量為800千克的配送車一次最多可裝載1 000件快遞。為了減少配送時間和配送成本，公司規(guī)定每輛車的單次配送最大行駛距離不得超過15公里。

目前，A快遞公司的配送路徑不固定，配送員都是根據(jù)自己的經(jīng)驗選擇配送路線。通過實際調(diào)查該快遞公司的配送員，得到這14個網(wǎng)點配送最常行駛的配送路徑分別如下。

配送路徑一：P→P1→P2→P3→P4→P；

配送路徑二：P→P5→P6→P7→P；

配送路徑三：P→P8→P14→P13→P12→P；

配送路徑四：P→P9→P10→P11→P。

2.3 ? ?配送路徑現(xiàn)存問題

A快遞公司在向其下級配送網(wǎng)點配送快遞的過程中，管理人員按照配送范圍內(nèi)的快遞網(wǎng)點所處位置為配送員劃分其所需負責配送的快遞網(wǎng)點區(qū)域，然后配送員根據(jù)自己所需配送的快遞網(wǎng)點位置隨機選擇配送路徑，無法統(tǒng)籌安排配送路徑。配送員根據(jù)自己的經(jīng)驗來選擇配送路線和配送車輛，在配送過程中容易出現(xiàn)車輛裝載率低、車輛配置多、車輛行駛總里程偏高的現(xiàn)象，從而導致車輛成本和配送員工資成本偏高，最終使配送總成本偏高，導致該公司的客戶滿意度、物流配送效率與其競爭對手相比偏低，不利于企業(yè)的長期發(fā)展。

3 ? ?基于節(jié)約里程法車輛配送路徑優(yōu)化

選取配送范圍內(nèi)的14個網(wǎng)點，這些網(wǎng)點位于居民小區(qū)內(nèi)或小區(qū)周邊，客戶群體較穩(wěn)定，除了大型的網(wǎng)絡購物活動，如淘寶雙11、618等時間段外，每日代收的快遞量波動不大，而且大部分快遞體積小、重量輕，14家網(wǎng)點的地址和各個需求點的快遞量如表1所示。各網(wǎng)點間距離及A快遞公司與網(wǎng)點間的距離以高德地圖導航的方式獲取，如表2所示。

根據(jù)各網(wǎng)點之間及A快遞公司與網(wǎng)點之間的距離，利用公式3計算各網(wǎng)點間的節(jié)約里程，按照節(jié)約里程大小，從大到小進行排列，若節(jié)約里程數(shù)相同則并列排序，最終得出節(jié)約里程排序表，如表3所示。

從節(jié)約里程最多的路段P12—P13開始規(guī)劃路線，首先考慮將網(wǎng)點P12和P13的快遞使用一輛車進行配送，這兩點的快遞數(shù)量之和為140+100=240件，兩點間距離為1.6公里，均沒有超過約束條件的限制，此路線可行，可以繼續(xù)合并下一個客戶需求點。連接節(jié)約里程處在第二位的P12—P14，但是從這三個客戶需求點與A快遞公司的地理位置來看，P12不適合與P14連接，因此放棄合并網(wǎng)點P12、P14。接下來，兩點間節(jié)約里程最大的是P13—P14，把網(wǎng)點P14加入P12—P13這條配送路線中，三點的快遞數(shù)量之和為240+150=390，行駛里程為1.6+1.6=3.2公里，均未超過約束條件的限制，此路線①：P12→P13→P14可行，進行下一步合并。

確定了配送路線①后，接下來，節(jié)約里程最大的是P9—P10，這兩點的快遞數(shù)量之和為135+200=335件，兩點間車輛行駛里程為0.1公里，均未超過約束條件的限制，這兩點的快遞可由一輛車進行配送。然后是P9—P11，因為P9、P10、P11三個網(wǎng)點的快遞數(shù)量之和為335+180=515件，路線②：P10→P9→P11的車輛行駛里程為0.1+0.8=0.9公里，均未超過約束條件的限制，因此此路線可行。

接下來，節(jié)約里程最大的是P11—P12，將網(wǎng)點P11合并到路線①中，這四個網(wǎng)點的快遞數(shù)量之和為390+180=570件，行駛里程為3.2+4.2=7.4公里，均未超過約束條件的限制，此路線③：P11→P12→P13→P14可行。此時將路線②和路線③合并，合并后的快遞數(shù)量之和為515+570-180=905件，行駛里程為0.9+7.4=8.3公里，均未超過約束條件的限制，此路線可行，形成配送路線④：P9→P10→P11→P12→P13→P14。

接下來是路段P2-P3，兩點快遞數(shù)量之和為190+200=390件，行駛里程為0.7公里，路線可行。然后是路段P3—P4，因為P2、P3、P4的快遞數(shù)量之和為390+130=520件，行駛里程為0.7+0.5=1.2公里，此線路可行，所以可形成配送路線⑤：P2→P3→P4。不斷重復上面的過程，最后得到優(yōu)化后的配送路徑方案，如表4所示。

優(yōu)化后的配送路徑方案中，A快遞公司完成所有客戶需求點的快遞配送任務共需要使用2輛最大裝載量為1000件快遞的配送車，車輛行駛總里程為24.3公里。

4 ? ?結果分析

優(yōu)化前，完成這14個網(wǎng)點的所有配送任務共需要使用4輛配送車。其中，路徑一和路徑四使用最大裝載量為1 000件快遞的配送車，路徑二和路徑三使用最大裝載量為600件快遞的配送車，車輛行駛總里程為32.3公里，如表5所示。

運用節(jié)約里程法對配送路徑進行優(yōu)化后，車輛總里程節(jié)約了8公里、平均裝載率提高了36.46%，如表6所示。

使用節(jié)約里程法對A快遞公司的車輛配送路徑進行優(yōu)化后，只需要2輛配送車就能完成這14個網(wǎng)點的所有配送任務，減少了車輛在配送快遞過程中的行駛總里程，還能降低車輛成本和配送人員的工資成本。同時車輛平均裝載率提高，可以充分利用配送車輛，合理配置資源以減少浪費，提高企業(yè)的配送質(zhì)量并縮短配送總時間，從而增加企業(yè)的核心競爭力。

5 ? ?結 ? ?論

車輛配送路徑優(yōu)化是降低企業(yè)物流配送成本的關鍵環(huán)節(jié)之一，本文采用節(jié)約里程法對A快遞公司的車輛配送路徑進行優(yōu)化，減少了車輛配送總里程、提高了車輛平均裝載率、降低了配送總成本。優(yōu)化后的結果表明，運用節(jié)約里程法對A快遞公司配送路徑進行優(yōu)化是可行的，為該公司車輛配送路徑規(guī)劃提供了思路和參考。

參考文獻：

[1] 張穎敏．基于節(jié)約里程法的物流配送線路優(yōu)化與改進研究[J]．物流科技，2011，34（4）：113-115.

[2] 孫藝婕．帶時間窗的城市物流多中心配送路徑優(yōu)化研究[D]．舟山：浙江海洋大學，2020.

[3] 湯齊，張亞麗．基于時間約束的生鮮產(chǎn)品配送路徑優(yōu)化[J]．鐵道運輸與經(jīng)濟，2016，38（6）：40-43.