零擔物流中配送路徑優化與接貨整數規劃—以大達物流宜興派送中心為例

陳湘州，文思倩，馮鑫海，陳為民

（湖南科技大學　商學院，湖南　湘潭　411201）

零擔物流中配送路徑優化與接貨整數規劃—以大達物流宜興派送中心為例

陳湘州，文思倩，馮鑫海，陳為民

（湖南科技大學商學院，湖南湘潭411201）

以零擔物流中遇到最普通也最急需優化的成本來源—配送路徑優化和接貨整數規劃為研究對象，結合江蘇百成大達物流有限公司的日常貨物運輸安排進行分析，利用C-W優化算法和整數規劃算法對每天派送中不同的客戶地址和條件進行最低成本方案優化，并通過事例推理的方法對這些最低成本方案進行優化組合，建立起了派送與接貨一體化考慮的優化系統，并用實例進行了驗證。優化結果具有很高的經濟價值，能為公司節約不必要的開支，而且節約下的車輛和司機可以配備到其他地區的配送路線中，或者應對一些突發狀況，從而提高了公司的資源利用率。

零擔物流；派送中心；路徑優化；節約算法；0-1整數規劃

1　前言

公路貨運是國家經濟的命脈，它不僅支撐了國民經濟的發展，而且調整了經濟結構。物流業屬于勞動力密集型產業，在一定程度上是體現地區經濟的晴雨表。隨著經濟的不斷發展，物流技術的逐步更新，我國內地公路零擔物流企業每年以15%左右的速度增長。

零擔物流作為道路物流的主要形式，在公路物流中具有重要作用。作為物流的一個重要組成部分，具有集散為整、化整為零、分路運送、轉運直達、便捷迅速等特點，很大程度上方便了人們的生產生活，越來越成為推動國家經濟發展的重要動力和調整產業結構、增加就業機會的保障。面對電子商務和國際貨代的繁榮發展，零擔物流公司普遍存在著服務水平不高、經營效益不高、經營水平不高等窘狀，因此，尋求科學合理的配送路徑，并以此降低成本，減少不必要的油耗等節能行為、提升貨物裝載率和客戶滿意度、提高部門經濟效益，促進零擔物流健康、快速、節約、可持續發展是亟待解決的問題。

王亞晴等指出物流零擔配送路線問題是物流配送優化的重要問題，他們提出了擴圈法的求解方法［1］。趙新慧采用了MVC的模式進行建模，并基于Java ME的Java手機軟件這一思路，能夠成功地服務于零擔物流運輸，為廣大的貨主和司機建立一個暢通的交流平臺［2］。呂峰等使用Matlab實現對零擔物流運輸卸載路徑優化，當表示路徑的換位矩陣通過迭代計算趨于平衡點時，運費目標函數也趨于最小值［3］。張志清等運用樹形結構的最小樹生成得到多路線方案，最后用層次分析法計算得出最佳路線，但是并未涉及接貨整數規劃［4］。高超鋒等考慮到網絡中樞紐點集散平衡和樞紐點間干線對流平衡對網絡設計的影響，建立二級軸輻式零擔物流網絡混合整數規劃模型，并進行算例仿真分析，得出了當不考慮平衡時，網絡資源有較大的浪費，而隨著平衡程度要求不斷提高，網絡運營總成本有所上升，樞紐集散及干線對流平衡綜合度明顯增加，網絡資源得到均衡利用［5］。

多數零擔物流司機只能簡單的憑經驗和感覺規劃派送路徑，其油耗和保養也只能靠平時的習慣來估計。基于零擔物流派送中心具體情況，本文從成本最小化、利潤最大化的角度出發，加上時間約束，提出了派送環節的路徑優化和接貨環節的0-1整數規劃，從部門每日工作流程和實際出發，把送貨時的路徑最優和接貨時的多種限制作為完整的工作流程都考慮在內，讓部門調度或司機可以輕松合理地安排車輛。

2　派送中心日常工作及接送貨環節概述

零擔物流派送中心的工作大同小異。大達物流宜興派送中心負責整個宜興市的貨物派送任務。部門有三輛4.2m廂式貨車和一輛6.5m廂式貨車。四輛車各負責一片派送范圍，其派送范圍主要按照丁蜀、北線、官林、外圍四片區域劃分，覆蓋了宜興市21個街道和鄉鎮，派送范圍如圖1所示。

圖1　宜興派送中心派送區域分布圖

派送中心的工作主要包括接送貨、開發維護客戶、跟蹤監督貨物、解決客戶難題和日常的維護工作。其中派送中心工作中最為重要的接送貨也是區別其他部門的標志。

（1）把干線車上的貨物按相應的區域卸車，并裝車送往客戶手中；

（2）大票貨物（占一輛車有效容積的70%）優先派送，然后派送其余貨物；

（3）當有客戶需要發貨時，物流專員通知負責派送該區域的司機安排接貨，客戶數和預計的貨量很少時，司機一般原地待命；

（4）當通知客戶數和預計貨量達到一定程度時接貨，并在途中估算時間和容納貨物量；

（5）接收到的貨物還要有開單打單、稱重量方、簡單的包裝、粘貼標簽、裝車封車等工序。公司規定干線車必須要在當天晚上九點前發車，接貨司機一般每日的工作時長為11h，在下午7點前車輛就要到達部門并卸下接來的貨。

每日接送貨流程及條件如圖2所示。

2.1送貨環節特點及要求

里程最短、時間最短。零擔物流的客戶絕大部分是工廠企業，貨物多是生產原料或產品配件，為了保證生產的連續性，收發貨人都十分重視派送的準時率。對于派送中心來說，按時、及時地把貨物送到客戶手中就是最大的目標。送貨時要提前規劃好線路，盡量不重復相同的路，縮短里程就是節約時間。這樣也為司機節省出更多的時間去接貨、去規劃路線。

圖2　派送中心每日車輛工作流程圖

2.2接貨環節特點及要求

貨量最多、客戶數最多。部門的收入是由每天接到貨物的運費決定的，在有限的時間內如何盡可能多地經過客戶并且盡可能接貨量大的貨，是每個部門每天都會遇到的問題。這也是本篇論文討論的核心。在接貨環節也有幾個限制條件：

（1）車輛的容積和載重是一定的，載重限制為5t，容積為13.5m3。

（2）工作時間是一定的，不能超過11h。

（3）客戶的貨物可能不能一次裝下，需要根據每個客戶的貨量來決定走什么樣的路線。

3　派送環節路徑優化方案設計

3.1模型原理及步驟

本文所用的路徑優化方法是節約里程法，原理如下：

假設有n個點，把每個要去的地方看成一個點，取其中的一個點為基點，例如以1為基點。首先聯接基點和其他所有的點，構成1→j→1（j=2，3，…，n），得到一個含有n-1條路徑的圖，按此路線訪問n個點所走的里程總和為：

其中c1j為由點1到 j（j=2，3，…，n）的里程長度，此處假定c1j=cj1（對所有的 j）。假如聯接了點i和 j且走弧這時就不再走弧和節約的里程值可計算如下：

計算步驟如下：

（1）選取基點，例如選取點0為基點。將基點和其他各點相聯接，得到n-1條線路1→j→1（j=2，3，…，n）。

（2）如果這些可連接的點不違反限制條件，就可以計算其節約值（i，j不為基點）：

（3）將所有的s（i，j）從大到小排列。

（4）按s（i，j）從大到小的順序，逐個考查其端點i和j是否滿足如下條件，如果滿足下列條件，就可將弧插入到線路中。

①點i和j不在一條線路上。

②點i和j均與基點相鄰。

3.2C-W節約算法實現路徑優化的基本應用

以2015年5月8日派送貨物清單為例，見表1。

表1　收貨地址列表

根據表1建立各派送點間的距離表，見表2。以派送中心0為基點，構成初始線路圖。按照式（2）計算將弧插入到線路中時引起的里程節約值，并按節約值從大到小的順序將它們填入節約值表3。

對每條弧按照節約值從大到小的順序檢查，看它是否能插入到線路上。如果能插入，就改變線路。

由表3可知：用該方法得到的線路為0→1→7→8→2→9→3→6→4→5→0。

該條路線的總長度為：

表2　派送點距離表（km）

表3　節約值表

3.3隨機選取幾條送貨路徑及與最優路徑的比較結果

若隨機選取幾條派送路徑計算其路程：

路徑1：0→6→1→5→7→8→3→2→4→9→0

路徑2：1→6→8→3→9→7→4→1→5→2→0

路徑3：0→7→5→3→9→1→8→2→4→6→0

路徑4：0→9→6→3→8→5→2→7→4→1→0

路徑5：0→7→8→9→4→5→6→1→2→3→0

路徑6：0→3→6→9→8→7→4→1→2→5→0

路徑7：0→1→5→9→6→3→2→4→7→8→0

這7條路徑方案的路程長度見表4。

表4　路徑值

由此可見，經過節約里程算法優化后的路徑明顯比其他七個路徑要短。這七條路徑的平均長度為44.124 29，這比優化后的路徑要長9.054 286km。如果按4.2m廂式貨車平均油耗0.9元/km來算，則這臺車出車一次大概可以為部門節約8元。而且部門有四臺車，每天可以節省32元左右。

4　收貨環節0-1整數規劃方案設計

4.1收貨環節0-1整數規劃的基本模型及運算

接貨工作的流程如圖3所示。

圖3　接貨流程圖

假設各變量：

單票貨物帶來的利潤為a1，a2，a3，...，ai；

單票貨物所耗費的時間為b1，b2，b3，...，bi；

單票貨物的重量為v1，v2，v3，...，vi；

單票貨物的體積為w1，w2，w3，...，wi；

送貨環節所用時間為B（一般為5）；

貨車最大容積Wi為13m3；

貨車最大載重量Vi為5t；

某一區域總客戶為n。

目標函數（求最大利潤）：

約束條件：

（1）所裝貨物重量不能超過貨車載重的上限，即：

（2）所裝貨物體積不能超過貨車容積的上限，即：

（3）送貨環節和接貨環節總工作時長不能超過11h。

由于公司上班時間為08:00，21:00干線車準時出發，即下班時間最晚為21:00。但貨物不僅需要運到派送中心，還要根據客戶和貨物進行簡單包裝、稱重量方、粘貼標簽等工作，所以貨車實際在19:00就需要返回部門，工作時間為11h。

（4）接貨的客戶數要大于該區域總客戶數的80%：

公司對部門的考核不僅在貨量上有規定，對客戶的數量也有規定。

某天某區域通知接貨的客戶信息見表5。

表5　客戶接貨信息表

運用MATLAB軟件求解可得：

由此可知：司機可接除3號、14號客戶以外的全部客戶的貨物。

約束內最大收益為1 395元。

4.2按通知順序接貨的模型及運算結果

如果只按照通知接貨的順序去接貨的話，即：

目標函數（求最大利潤）：

約束條件：

（1）所裝貨物重量不能超過貨車載重的上限，即：

（2）所裝貨物體積不能超過貨車容積的上限，即：

（3）送貨環節和接貨環節總工作時長不能超過11h。

（4）按照通知從1到15號客戶依次接貨：

可建立重量、體積、時長、收益的累積表，見表6。

表6　累積表

由此可知當貨車裝完第12個客戶時，總時長快要達到最大限值，即是滿足方程限制的最優解。此時，部門可獲得的收益為1 190.4元。這明顯小于優化后的1 395元。所以，優化還是比較成功的。

［1］王亞晴，覃運梅.物流企業零擔配送路線的優化方法［J］.物流工程與管理，2012，（1）:125-126.

［2］趙新慧.零擔物流運輸信息系統的設計與實現［J］.交通信息與安全，2009，（1）:134-136.

［3］呂峰，趙衛東，邱會魯，等.連續Hopfield神經網絡零擔物流運輸路徑優化研究［J］.軟件導刊，2015，（6）:26-27.

［4］張志清，汪世志.制造業零擔運輸優化—以湖北為例［J］.物流技術，2013，（9）:148-150.

［5］高超鋒，林慶福，胡志華.基于樞紐集散和干線對流平衡的二級軸輻式零擔物流網絡設計［J］.華中師范大學學報（自然科學版），2015，（4）:551-556.

Distribution Route Optimization and Cargo Pick-up Integer Programming in LTL Logistics:In the Case of Yixing Delivery Center of Dada Logistics

Chen Xiangzhou，Wen Siqian，Feng Xinhai，Chen Weimin
（School of Business，Hunan University of Science&Technology，Xiangtan 411201，China）

In this paper，with the distribution route and cargo pick-up integer programming as the object，we analyzed the routine cargo transportation schedule of the Jiangsu Baicheng Dada Logistics Company，used the C-W algorithm and integer programming algorithm to optimize the customer address and condition in its everyday delivery so as to achieve minimum cost，then through the case-based reasoning，combined and optimized the solutions with the minimum cost，established the optimized system that integrated cargo delivery and pick-up，and at the end，verified its validity through an empirical case.

LTL logistics；delivery center；route optimization；saving algorithm；0-1 integer programming

TQ520.62；F224

A

1005-152X（2016）06-0129-05

10.3969/j.issn.1005-152X.2016.06.031

2016-05-03

湖南省研究生科研創新項目（CX2015B512）

陳湘州（1969-），女，湖南婁底人，湖南科技大學商學院副教授，碩士研究生導師，研究方向：企業管理；文思倩（1991-），女，湖南永州人，湖南科技大學商學院碩士研究生，研究方向：企業管理、閉環供應鏈管理；馮鑫海（1993-），男，湖南長沙人，任職于山西怡園酒莊有限公司，研究方向：物流管理；陳為民（1973-），男，河南澠池人，湖南科技大學商學院副教授，研究方向：數據挖掘、決策支持系統、風險管理。