基于C-W節約算法的快遞配送路徑優化研究

摘 ?要：隨著經濟社會網絡管理信息化的發展，快遞的數量逐年遞增，人們對快遞配送的時間要求越來越高，提高快遞配送服務的效率也愈發顯得重要，因此做好快遞配送路徑的優化以提高配送效率具有十分重要的意義。本文針對快遞配送路徑優化這一問題進行探討，為解決該問題而建立TSP模型，并以C-W節約算法對其進行求解來解決由于沒做好路徑優化而導致快遞延誤送達的問題，提高消費者的滿意度。

關鍵詞：路徑優化;TSP模型;C-W節約算法

中圖分類號：TP312 ? ? 文獻標識碼：A文章編號：2096-4706（2021）13-0121-04

Research on Express Delivery Path Optimization Based on C-W Saving Algorithm

SHI Yu

（Liaoning University of International Business and Economics， Dalian， 116052， China）

Abstract： With the development of economic social network management informatization， the number of express is increasing year by year. People have higher and higher requirements for the time of express distribution， and it is more and more important to improve the efficiency of express distribution service. Therefore， it is of great significance to optimize the express distribution path to improve the distribution efficiency.This paper discusses the problem of express delivery path optimization， and establishes TSP model to solove the problem， and solves it with C-W saving algorithm to solve the problem of express delay delivery caused by failure to do well in path optimization， so as to improve consumers’ satisfaction.

Keywords： path optimization; TSP model; C-W saving algorithm

0 ?引 ?言

隨著我國社會經濟和互聯網電子商務的蓬勃發展，快遞行業已經逐漸走進了千家萬戶。根據統計數據資料顯示2019年我國的快遞服務量已經突破600億件，累計完工635.2億件，我國的快遞公司日均辦理貨物能力已經超過1.7億件，日最大處理能力5.4億件。2020年以來我國的國內快遞業務數量更是已經再次走向了一個具有歷史性的增長新臺階，國家郵政局再次明確指出自2020年9月10日起，從去年我國的國內快遞配送業務量已經首次達到500億件的大規模以來，每月都有望能夠再次快速登上百億級的歷史臺階，實現"四連跳"增長直至再次超過去年突破800億件的規模大關，創造了當年以來我國國內快遞業務行業數量發展快速歷史的最高數量記錄。近年來，快遞行業蓬勃發展，快遞數量也在急速增長，想要在快遞量持續增加的前提下，使得快遞送到客戶手中的時間縮短，快遞的配送這一環節就顯得尤為重要。而快遞是與消費者直接接觸的物流活動，其成本占據了整個企業（物流公司）成本的很大一部分?？爝f運輸路線的合理性對于整個快遞配送過程中的速度、成本、效益都有著很大的重要影響，特別是針對某一地區或者某一客戶的快遞運輸路線更加復雜。因此，運用科學合理的方法優化配送路線是快遞配送中非常重要的一個環節。那么為了我們可以及時快速地把所有貨物運送到廣大客戶的手中，提高了公司對于客戶的服務和滿意程度，同時還能夠提高我們公司的社會經濟效益，在配送的過程中，快遞配送路徑優化就成了整個配送網絡優化的關鍵環節。它不但可以有效地減少商品的配送工作時間與里程，提高了配送的效率，還能夠大幅度地提高汽車的利用率，降低了配送的成本。因此，如何優化配送路徑進而節約配送里程已經成了一個急需解決的問題。

目前，隨著快遞量的增加，尤其雙十一、618等活動后，許多人都開始關注快遞配送的路徑優化問題。例如藺士文，楊金云，吳昊龍，張月，龔志成等人建立了一套VRP模型，利用節約里程法，優化和設計物流配送的路徑。都雪靜，孫菲菲，王云浩建立了一個成本最低、交付貨物時間最短、碳排放最少的多目標汽車行駛路徑相關性問題的模型，并用遺傳算法進行求解。葉潤舟利用改進的混合粒子群算法解決"最后一公里"的配送優化展問題。謝偉以京東達達物流公司為例對其進行了分析，用 matlab 軟件對其進行了編程，結合 VRP 模型，解決了同城配送的快遞問題。本文從配送的路徑問題入手，對其構建TSP模型，并利用C-W 節約算法進行求解。

1 ?快遞配送路徑優化的主要概念

1.1 ?快遞配送的概述和主要步驟

配送是指按照客戶對商品訂單的需求分類，在配送中心進行配送，并及時將相應的貨物送到客戶手中的活動。它是一種生產或者消費之間相互聯系的中介，涉及物流活動主要是指根據客戶訂單需求配送貨物，在自己的物流服務中心向客戶分發貨物并及時把這些貨物運輸給收貨人。配送環節是整個物流環節中重要組成環節，主要分為以下步驟：（1）公司收貨：即應客戶要求或公司賣方聯系業務接收貨物。一般來說，大型物流公司是擁有自己長期合作關系和大量貨物的客戶，其中一些通常會找到客戶的貨物并將其運送到他們的家中。（2）車輛的裝載：主要由公司運營管理部門負責執行，將根據顧客的時效需求對其做出相應的安排。裝載原則上就是盡量有效利用和充分合理的車輛空間。（3）運輸：將貨物運送到樞紐，與駕駛員保持良好的溝通。（4）到達樞紐處：到達時卸下貨物。卸貨時，可以根據貨物的目的地不同放在不同的地方。（5）分類：可以根據目的地不同對貨物進行分類，如將旅順口區放在一起、將甘井子區放在一起以便于運輸，貨物少時也可以直接裝上。（6）過車：裝載運輸貨物的機動車輛抵達后直接把運輸貨物交付到送貨車上，并在裝車前將貨物歸檔。即在進行裝車時對所有需要的裝車貨物的相關信息都進行了電子記錄，其中所有貨物的相關信息主要包括有裝車的時間、配送員、配送人員的電話、發貨地、目的地、客戶姓名、客戶電話等基本信息。記錄完成后，需要在電腦中將信息匯編到計算機中，打印紙質面單，以便于進行貨物的分配。（7）派送貨物：派送員將所需派送的貨物送到客戶手中，且對派送的貨物進行處理。在派送過程中可能出現貨物仍需中轉，貨物分揀錯誤等情況，派送員需要對這些具體問題進行具體分析。如果在派送中有由于特殊原因不能按時交貨的情況出現，派送員要及時地進行溝通。（8）客戶簽收：為客戶配送之前客服或進行配送的人員要及時與客戶取得聯系，以溝通交貨時間和貨物到達時的交貨地點等基本情況。為了避免與客戶不必要的糾紛，需要看清客戶在簽收單上的備注并加以注意，在貨物送達后，需客戶驗收貨物確定貨物沒有問題并在簽收單上簽字后視為配送成功。

1.2 ?配送路徑優化的意義

配送路徑優化是配送優化中的一個重要環節。在配送的過程中，配送的路徑是否合理對配送的速度，成本和收益有重大影響。設計合理，有效的配送途徑，不僅可以大大縮短物流配送的時間，降低運營成本和改善運營效果，而且還可以帶來更好的客戶服務，更高的客戶滿意度和良好的公司形象。配送路徑的合理性對交付速度，成本和收益產生重大影響，尤其是對于快遞這樣的多個用戶而言，配送的路徑更為復雜，對配送過程的路徑做出優化就更有意義。配送的合理化是否正確是整個物流過程中配送路徑是否能夠得到合理化的一個重要組成部分，而且這也是配送過程能夠得到正確性的關鍵。所以配送途徑優化在整個企業、社會中都非常有重大的作用。

1.2.1 ?縮短企業配送時間

對于公司來說，優化配送途徑和路線就能夠縮短配送的時間及公里數，進而改善配送的效率。配送管理效率的改善不僅能夠增加車輛在行駛過程中的使用量，降低了企業在運輸過程中所需要的時間費用，還能及時地將商品送達顧客，提高了顧客的滿意度;不僅能夠如此，對配送途徑問題進行分析和優化還能夠使整個公司在物流配送中的工作過程變得更加合理化，提升自己公司的作業效率，這樣一來更加有利于增強我國公司在物流行業中的市場競爭能力和效果。

1.2.2 ?降低社會非必要成本

對于整個現代化社會來說，優化貨物配送的路線不僅能夠節省運輸人員和車輛，降低了空車的概率，降低了社會的物流費用和成本，同時，它還能夠緩解交通緊張，減少運輸過程中的污染。例如噪音和廢氣。

2 ?TSP模型的建立

2.1 ?TSP模型概念

TSP問題模型，也可稱為旅行者問題，首先被認為是1759年歐拉所研究的一個騎士巡回問題，1948年美國RAND公司于此推出。 TSP問題被認為是最基本的道路問題，該問題是在尋求由一個旅行商從固定原點出發，遍歷過所有需要到達的定點后再回到固定原點的最小路徑成本。

2.2 ?建立TSP模型的核心思想

TSP問題的在物流學中所說的描述就是指對應于一個物流配送企業，欲將n個客戶的所有訂貨沿著最短時間路線完整地運送到。就是指從以我們為主要服務的物流配送中心為出發點，將所有的貨物運送到n個客戶手中的（n-1）！條路線中選取距離最短的那一條。即已知起始點和其他點之間的距離，尋找一條路徑使起始點和其他點之間的路徑總和最小。并且兩兩點之間都有直達的路線，這條路線不需要經過中間其他點或偶爾有兩個點之間的路線需要經過其他中間點。

2.3 ?模型建立的步驟

首先，找到起始的點A，得到起始點A與其他點之間B、C、D、E、F、G的距離，并將點與點之間的距離整理成點距離表格。接著，用圓圈來表示需要到達的每一個點，并對每一個點進行標號，用線段來表示點與點之間的距離并且根據畫出模型圖。最終要求找到一條路線遍歷所有的點使得點與點的距離和最小。

3 ?C-W節約算法的概述和主要步驟

3.1 ?C-W節約算法的概述

C-W節約算法是克拉克和賴特于1964年提出的求解汽車路徑問題的一種啟發式構造方法。其基本理念就是首先把各個已經擁有的定點和所在原點0（也就是配送中心）連接起來，構成一條包含所有定點且最終能夠返回到所在原點0的運輸路線?？傎M用是指以兩倍于原點連接到各個固定定點之間距離的費用，然后通過計算使點i和j分別連接在同一條線路上的費用“節約值”：S（i，j）=c0i+ci0+c0j+cj0-（c0i+cij+cj0）= ci+c0j-cij

S（i，j）越大，說明把i和j，連接在一起時總路程減少越多。

該公式中S（i，j）表示節約的路徑距離，c0i表示起點0到i點的距離，c0j表示起點0到j點的距離，cij表示i點到j點的距離。

3.2 ?C-W節約算法的主要步驟

（1）將所有點排序，起始處所屬的點為0點對應快遞公司A，其他點任意排序，選取點0為基點，將基點與其他各點連接。（2）構建可連接點對S（i，j），按公式S（i，j）=c1i+c1j-cij計算各點對的節約值。（3）將所有點對S（i，j）按其值大小由大到小排列。（4）從節約值最大的點對開始依次向下構建路線，滿足點i和點j不在一條路線上和點i和點j均為基點相鄰這兩個條件即可將點對納入路線，否則舍去。（5）通過以上各迭代步驟，考察完所有點對，達到路徑配送優化的目的。

4 ?論證分析

假設A為一家快遞公司，其快遞員每天都會對其公司的顧客進行上門取件送件。本文對該快遞公司進行論證分析，選取該公司配送范圍附近的6個客戶作為研究對象。目前該公司采取的是門到門一對一的配送方式，即直接由該快遞公司向客戶點進行配送。這里所有客戶之間的路線都是連通的，總是可達的，對于不連通的情況不是本文考慮范疇。對此，我們采用C-W節約算法來進行求解并與不采用C-W節約算法進行求解來進行對比。

4.1 ?建立模型

第一步：已知將6個客戶點分別設為B、C、D、E、F、G，假設快遞公司和6個客戶之間的距離已知，如表1所示。

第二步：根據表1畫出TSP問題的模型圖，如圖1所示。

4.2 ?算法求解

4.2.1 ?未選用C-W節約算法求解上述問題模型

如果不采用C-W節約算法進行求解，在本案例中我們要送達6個客戶，從快遞公司A出發，最后回到快遞公司A。顯然，從快遞公司A出來后，我們隨即可以選擇6個客戶之一進行快遞的送取，那么很顯然這里就有6種選擇，分別為B、C、D、E、F、G。則此時可能的路線為：A→B，A→C，A→D，A→E，A→F，A→G.在進行第一次客戶的選擇后我們又可以從剩余的5個客戶中進行選擇，此時又有5種選擇，也就是說此時就有5×6=30條路線，以此類推，下一次就有4種選擇，將會產生5×6×4=120條路線。經過計算，本案例中的可選路線數為6！=720條，也就是說首先需要找出的這720條路線的過程就是非常復雜的，然而為了篩選出最短的那條路線，還需要計算出每一條路線的路徑距離進行比較。這無疑是困難的，這僅僅只是送達到6個客戶手中，如果是更多的客戶則其路線便會更加復雜，就算利用計算機來計算，所耗費的時間也是很長的。

4.2.2 ?選用C-W節約算法來分析和求解上述的問題模型

選用C-W節約算法來分析和求解上述問題模型的具體步驟為：

第一步：將快遞公司A所屬的點為設為0點，將客戶B、C、D、E、F、G設為1、2、3、4、5、6，并將0點與1、2、3、4、5、6點連接，如表2所示。

第二步：構建可連接點對S（i，j），按公式S（i，j）=c1i+c1j-cij計算各點對的節約值并以節約值從大到小排序，如表3所示。

第三步：按照表2所示的節約值排序表，從節約值最大的點對開始依次向下構建路線。首先把節約值最大的構成回路，根據表2，節約值最大的是連接為5、6點對應的客戶為F、G即連接0-5-6-0構成第一個回路，在剩下的節約值中最大的為連接3、5點構成回路，此時路線為0-3-5-6-0，按照上述方法下一步連接的應為4-5，但是5點所對應的客戶已經與3點和6點所對應的客戶構成回路且節約值都要大于s（4，5）點對，因此舍棄4-5回路。下一個1-5回路也是同樣的道理，所以被舍棄。到4、6回路后可以和6回路進行連接中間沒有別的客戶，因此可以連接，此時的路線為0-3-5-6-4-0。以此類推，經過迭代舍棄了s（2，5）、s（3，6）、s（2，6）、s（1，6）、s（3，4）所構成的回路，與點對s（2，4）、s（1，3）構成回路形成最終路線為：0-1-3-5-6-4-2-0即從配送中心4出發先向客戶B配送，再向客戶D配送，在前向客戶F進行配送，再從客戶F到客戶G，到客戶E，再到客戶C最后回到配送中心A。該線路的路程總和為：S=40+40+40+50+65+100+60=395

未優化前，該快遞公司采用的是一對一的優化方式，耗時耗力總配送里程為S=2×（40+60+65+110+190+120）= 1 170，優化后與優化前相比節約了775，提高了配送效率，也節約了配送成本。

5 ?結 ?論

本文對快遞配送的問題進行分析，通過模型的構建和算法的應用對配送的路徑進行了優化，縮短了配送路線的距離，節約了配送成本，對于快遞公司降低成本具有一定意義。但本文的研究還有一些不足，對于論證的條件過于理想化，在實際配送中要考慮的因素會十分復雜，對于這一方面還待與加強研究。

參考文獻：

[1] 楊粟涵，于蕾.基于遺傳算法的快遞配送路徑優化問題研究 [J].現代信息科技，2020，4（9）：99-100+103.

[2] 鄧學平，孫芹，田帥輝.基于不同車型的城市快遞配送車輛路徑優化研究 [J].價值工程，2020，39（12）：275-280.

[3] 李瑞吉.城市末端快遞配送現狀及配送模式研究 [J].南方農機，2019，50（22）：215-216.

[4] 藺士文，楊金云，吳昊龍，等.基于節約里程法的物流配送低碳路徑優化 [J].物流工程與管理，2019，41（4）：80-82.

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

[6] 葉潤舟.基于改進混合粒子群算法的快遞最后一公里配送優化 [D].合肥：合肥工業大學，2019.

[7] 陳先受.眾包模式下快遞企業末端配送路徑優化研究 [D].杭州：浙江工商大學，2018.

[8] 謝偉.基于同城配送的快遞配送路徑優化及應用研究 [D].沈陽：東北大學，2018.

作者簡介：時宇（2000—），女，漢族，遼寧大連人，本科在讀，研究方向：物流管理。