（武漢理工大學，湖北 武漢 430070）

1 引言

物流行業(yè)作為支撐國民經濟發(fā)展的重要行業(yè)，對經濟增長的貢獻力度越來越大，隨著“物流冰山”理論廣泛被證實，降低物流成本成為企業(yè)新利潤的增長點。而配送運輸作為物流的中心環(huán)節(jié)，成本占到了物流總成本的一半以上，運輸線路規(guī)劃的合理性直接影響了運輸效率、運輸成本和客戶滿意程度。青島保稅港區(qū)物流企業(yè)A公司作為國內綜合性物流服務供應商，通過大力發(fā)展國際國內物流運輸服務，成為保稅港區(qū)具有良好競爭力的物流運輸公司。但是，隨著綜合性物流行業(yè)的競爭日益激烈以及客戶對于貨運要求的不斷提升，A公司必須在營運過程中提高客戶滿意率的同時降低配送運輸成本，以獲得可持續(xù)發(fā)展的競爭優(yōu)勢。因此，針對A公司現(xiàn)有的配送運輸方案，采用節(jié)約里程法進行貨運路線優(yōu)化，進而節(jié)約了總運輸里程，降低了公司的運營成本并提高了運營效率。

經過不斷的發(fā)展，對運輸線路優(yōu)化問題的研究獲得了不錯的成績。節(jié)約里程法因其邏輯結構清晰及算法實現(xiàn)容易的特點，在解決運輸線路優(yōu)化問題中得到了廣泛的應用。Gajpal等[1]同時考慮了配送車輛線路規(guī)劃（VRP）與同步的裝載和交付（VRPSPD）的線路優(yōu)化問題，開創(chuàng)了對VRPSPD的節(jié)約啟發(fā)式和并行節(jié)約啟發(fā)式算法，通過合并現(xiàn)有的多條線路來創(chuàng)建一個新的巡回線路。Wang等[2]建立了一輛滿載并帶有配送時間約束的貨車整車配送線路優(yōu)化模型，針對該模型的時間窗約束，設計了一種基于節(jié)約的算法，對車輛的整車調度問題進行了求解。占義芳[3]研究了考慮時間窗約束的配送車輛路徑優(yōu)化問題，用改進的節(jié)約里程算法進行優(yōu)化模型的求解，以某一物流公司的運輸線路規(guī)劃問題為研究對象，進行了該算法可行性的驗證。陶穎[4]采用節(jié)約里程法對耐克太倉物流中心的配送路徑問題進行了優(yōu)化研究。竇冰潔等[5]研究了考慮待退貨情況的配送車輛路徑優(yōu)化問題，其優(yōu)化目標是使得總的配送成本和總的啟動成本之和最低，采用了改進的節(jié)約算法進行了模型的求解。王海燕等[6]以武漢中百連鎖超市的門店貨物配送路徑優(yōu)化問題為研究內容，綜合運用節(jié)約里程法、最遠插入法進行優(yōu)化求解，通過對比優(yōu)化前后的配送成本，驗證了節(jié)約里程法-最遠插入法的有效性，優(yōu)化后的方案使得總的物流費用得到了有效的降低。

本文將基于現(xiàn)有的研究理論及其研究成果，結合青島保稅港區(qū)A公司的運輸現(xiàn)狀，構建跨區(qū)域貨運路線優(yōu)化模型，運用改進的節(jié)約里程方法，考慮客戶對于希望貨物抵運時間范圍的要求，運用考慮時間約束的節(jié)約里程法對其進行求解。

2 青島市保稅港區(qū)A公司貨運路線VRP模型構建

2.1 問題描述

青島市保稅港區(qū)A公司貨運路線優(yōu)化問題，實際是為了滿足每個區(qū)域的貨運需求，在運輸車輛容量限制下，確定適當?shù)能囕v運輸路線，使得車輛總的行駛路線最短，從而節(jié)約公司的總體運營成本。在這個過程中，又必須要考慮達到一定的客戶滿意率，因此必須盡量滿足客戶提出的貨物送達時間要求。因此，青島市保稅港區(qū)A公司貨運路線優(yōu)化問題就是帶有時間約束的車輛路徑問題。A公司貨運路線優(yōu)化問題最終目標是：在同時滿足運輸路徑、運輸時間、運輸載重、車輛需求等約束條件下實現(xiàn)總運輸成本最低。

2.2 模型假設

根據(jù)青島市保稅港區(qū)A公司貨運路線優(yōu)化問題界定及公司貨運實際情況，本文為了建立A公司VRP模型提出如下假設：

（1）只有一個配送中心，設置配送中心為配送起點；

（2）各區(qū)域配送點的配送需求量已知；

（3）各區(qū)域配送點到配送中心的距離，以及各區(qū)域配送點之間的距離為真實距離；

（4）配送車輛為多車型，且車載容量已知；

（5）由于客戶對配送時間有要求，客戶對配送有時間窗限制；

（6）每輛配送車輛僅配送一條運輸回路，由配送中心出發(fā)并最終返回配送中心；

（7）每輛配送車輛進行配送時的實際載重量不超過車輛載重限制；

（8）每輛配送車輛的配送行駛距離不受限制；

（9）各區(qū)域配送點能且只能被配送一次；

（10）每輛配送車輛可以配送多個區(qū)域配送點。

2.3 變量及參數(shù)的符號說明

對構建的A公司VRP模型中的變量及參數(shù)進行定義如下：

N：所有區(qū)域配送點的集合；

i,j：節(jié)點，i,j=0,1,2,…,N，其中0表示配送中心；

dij：配送點i到配送點j的距離，i,j=0,1,2,…,N；

qi：第i個配送點的貨物需求量，i=0,1,2,…,N；

k：第k輛配送車輛，k=1,2,…,K；

Wk：第i輛配送車輛的載重量，k=1,2,…,K；

c：配送車輛單位運距的運輸費用；

f1：配送車輛提前達到配送點的懲罰成本；

f2：配送車輛延遲達到配送點的懲罰成本；

ETi：客戶配送點希望貨物送達的最早時間；

LTi：客戶配送點希望貨物送達的最晚時間；

tij：配送車輛從配送點i行駛到配送點j的行駛時間；

UTi：配送車輛在配送點i的卸貨時間。

2.4 A公司貨運路線VRP模型

結合A公司貨運路線優(yōu)化問題的最終目標，構造目標函數(shù)如下：

所構建的目標函數(shù)的約束條件如下：

（1）一個回路的運輸線路上配送點的貨物需求量的總和不超過配送車輛的載重量限制：

（2）每個配送點的貨物需求量只能由同一配送車輛來配送，并且每個配送點只能被配送一次：

（3）每個配送車輛從配送中心出發(fā)，完成配送任務后返回到配送中心：

3 青島市保稅港區(qū)A公司貨運路線VRP模型求解

3.1 基于時間窗的節(jié)約里程法方法概述

3.1.1 節(jié)約里程算法基本原理。節(jié)約里程算法是啟發(fā)式算法的一種，Clarke等[7]在研究車輛巡回問題時曾使用該計算方法，其基本思想是按照節(jié)約值由大到小排序，在車輛容量限制下按照順序將相應的客戶點納入研究路徑中，直到所有的客戶完全被納入路徑為止。假設有三個點o，i，j，在原路徑下貨物從配送中心o到點i，然后再從點i返回至配送中心o，這是完成從配送中心至點i的運輸任務。從配送中心o到點j，再從點j返回至配送中心o，這是完成從配送中心到點j的運輸任務。如果按照原路徑進行配送就會發(fā)現(xiàn)存在較為嚴重的重復性運輸現(xiàn)象。較短路徑下，物品只需要從配送中心o運輸?shù)近cj，再從點j運輸?shù)近ci，最后返回配送中心，節(jié)約了一定的里程。相較于原路徑，較短路徑能夠在較短的時間內通過較短的運輸距離實現(xiàn)高效運輸。

如果用d(i,0)表示從客戶點i到配送中心的距離；d(0,j)表示從配送中心到客戶點j的距離；d(i,j)表示從客戶點i到客戶點j的距離；s(i,j)表示點i與點j的節(jié)約值，即原路徑與較短路徑之間的差值。

那么，在原路徑下完成的里程為：

在最短路徑下完成的里程為：

根據(jù)三角形的基本原理，原路徑下的里程是要大于較短路徑下的里程。那么，節(jié)約里程算法就是用s1減去s2，最終得到節(jié)約值：

3.1.2 帶時間約束的節(jié)約里程算法。建立的VRP模型可以劃分為兩個部分：運輸成本函數(shù)、懲罰成本函數(shù)。

運輸成本函數(shù)。模型的第一部分是運輸成本函數(shù)，是車輛運輸成本與駕駛員人工成本之和，其中運輸成本占主要的費用支出部分，是由配送車輛行駛里程和單位距離配送成本共同決定的，駕駛員人工成本是根據(jù)不同車輛的車型所確定的。通過運輸成本部分的控制，可以通過配送車輛數(shù)量、運輸距離的調整，實現(xiàn)運輸成本的節(jié)約。

懲罰成本函數(shù)。模型中的第二部分和第三部分是懲罰成本函數(shù)。懲罰成本是由于增加了配送時間約束而需要根據(jù)貨物配送到達時間是否滿足客戶希望時間要求來確定是否額外支付費用的成本。當配送車輛將需求貨物在客戶希望送達時間范圍內送達時，客戶的滿意程度高。當配送車輛將需求貨物在客戶希望送達時間范圍外送達時，將對貨運公司進行懲罰，需向客戶支付一定費用作為客戶經濟上的補償，以此給予客戶一定的心理安慰來提高客戶滿意度，這部分支付的費用就稱為懲罰成本。懲罰函數(shù)的表達式如下：

其中，配送車輛到達配送點j的時間為RTj=RTi+UTi+tij，ETj-( )RTi+UTi+tij表示配送車輛在客戶希望貨物送達時間之前到達的時間，( )RTi+UTi+tij-LTj表示配送車輛在客戶希望貨物送達的時間之后達到的時間。一般配送車輛延遲到達的單位懲罰成本要高于配送車輛提前到達的單位懲罰成本。當配送車輛在客戶希望的時間范圍內到達配送點，則懲罰費用為0。另外懲罰成本可以間接表示客戶對于貨運公司的服務滿意度，懲罰成本越高表示客戶對于貨運公司的服務滿意度越低，懲罰成本越低表示客戶對于貨運公司的服務滿意度越高。

3.2 模型求解

A公司以青島保稅港區(qū)為配送中心，向其服務的配送點運送貨物。配送點包括天津、西安、上海、杭州、武漢、重慶、深圳，單次平均運輸需求量、各區(qū)域配送點的卸貨時間、希望貨物送達時間區(qū)間匯總見表1。由于運輸線路都為跨區(qū)域范圍，均盡量選擇高速公路或高等級公路，因此平均運輸速度為75km/h。同時《中華人民共和國道路交通安全法》規(guī)定，駕駛人連續(xù)駕駛4h以上，停車休息的時間不得少于20min，駕駛員休息時間計入行駛時間考慮。早于時間窗到達，懲罰成本為25元/h，若晚于時間窗到達懲罰成本為35元/h，不足一小時按一小時計算。青島保稅港區(qū)配送中心與其服務的各配送點的運輸距離以及各配送點之間的運輸距離見表2，A公司擁有足夠的載重量為5t-20t的車輛以提供貨物運輸，其運費標準和人工成本見表3。

表1 各配送點需求量、卸貨處理時間及滿意時間窗

表2 各配送點之間的運輸距離（單位：km）

表3 不同車型運輸價格

初始方案：A公司為了打開市場范圍，十分注重客戶服務滿意度，體現(xiàn)在及時滿足貨運需求上。A公司貨運線路的初始方案為每個服務配送區(qū)域配一輛車，每條配送路線的總配送量小于車輛的最大載重量。

A公司可以采取兩種目標策略來進行貨運線路優(yōu)化。

優(yōu)化方案1：以降低運輸成本為貨運線路優(yōu)化的主要目標，客戶滿意度為次要目標。這時候可以采取傳統(tǒng)的節(jié)約里程算法，不用優(yōu)先考慮客戶對希望貨物送達的時間約束，配送車輛提前或者延遲到達配送點時就向客戶支付懲罰成本，給予客戶一定的心里安慰。

優(yōu)化方案2：同時考慮客戶的滿意度和降低運輸成本，盡量安排滿足客戶希望貨物送達的時間約束并盡量節(jié)約配送車輛運輸里程以降低運輸成本，此時公司必須在懲罰成本和節(jié)約的運輸成本之間進行權衡，以實現(xiàn)總配送成本最低的目標。這時候可以采取帶有時間約束的節(jié)約里程法進行貨運線路優(yōu)化。

采用節(jié)約里程法計算初始方案和優(yōu)化方案的線路和成本見表4-表6。

表4 初始方案配送線路和成本

表5 優(yōu)化方案1配送線路和成本

表6 優(yōu)化方案2配送線路和成本

3.3 優(yōu)化結果分析

匯總各貨運路線方案的結果，見表7。

表7 不同方案的比較

由表7可知，A公司貨運路線原始方案的運輸線路共有7條，總行駛里程為13 284.8km，運輸總成本為44 369.84元；基于傳統(tǒng)節(jié)約里程的貨運路線優(yōu)化方案1的運輸線路共有3條，總行駛里程為8 186.1km，運輸總成本為38 616.93元；基于考慮時間約束的節(jié)約里程的貨運路線優(yōu)化方案2的運輸線路共有4條，總行駛里程為8 951km，運輸總成本為37 691.71元。

對比不同方案的結果，基于傳統(tǒng)節(jié)約里程法的優(yōu)化方案1的配送線路較公司原始方案節(jié)約了5 098.7km，優(yōu)化方案1的配送總成本較公司原始方案下降了5 752.91元?；诳紤]時間約束的節(jié)約里程法的優(yōu)化方案2的配送線路較公司原始方案節(jié)約了4 333.8km，較基于傳統(tǒng)節(jié)約里程法的優(yōu)化方案增加了764.9km，優(yōu)化方案2的配送總成本較公司原始方案下降了6 678.13元，較優(yōu)化方案1下降了925.22元。

綜上所述，基于考慮時間約束的節(jié)約里程法的優(yōu)化方案2為最終優(yōu)化方案。雖然該方案較方案1的配送車輛行駛里程有所增加，但該方案在盡量滿足客戶對于希望貨物送達時間約束要求的同時盡量降低運輸成本，兼顧了客戶服務滿意度和運輸成本節(jié)約，最終使得公司總配送成本最低。

4 結論

通過采用考慮時間約束的節(jié)約里程算法進行貨運路線的優(yōu)化，可以得到同時滿足運輸路徑、運輸時間、運輸載重、車輛需求等約束條件下實現(xiàn)總運輸成本最低的運輸路線，為青島保稅港區(qū)A公司貨運決策提供了科學參考，能夠有效降低物流總成本并提高客戶服務滿意水平。

[1]Gajpal Y,Abad P.Saving-based algorithms for vehicle routing problem with simultaneous pickup and delivery[J].Journal of the Operational Research Society,2010,61(10):1 498-1 509.

[2]Wang L.Saving algorithm for VRP of with time windows[J].Journal of Heilongjiang Institute of Technology,2011,25(3):18-20.

[3]占義芳.基于軟時間窗節(jié)約里程法在某物流公司實際應用[J].物流工程與管理,2015,37(4):58-59.

[4]陶穎.基于節(jié)約里程法的耐克中國物流中心配送路線優(yōu)化研究[J].市場研究,2016,(10):30-32.

[5]竇冰潔,張麗華,趙麗娜,等.帶退貨的周期車輛路徑問題的C-W節(jié)約算法[J].物流科技,2016,39(3):67-72.

[6]王海燕,王曉莉.基于節(jié)約里程法的中百超市配送路徑優(yōu)化[J].物流技術,2017,36(3):84-87,157.

[7]Clarke G,Wright J W.Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J].Operations Research,1964,12(4):568-581.