基于節約里程法的配送路線優化

顏 穎，賴順天

（福建水利電力職業技術學院，福建 永安，366000）

基于節約里程法的配送路線優化

顏 穎，賴順天

（福建水利電力職業技術學院，福建 永安，366000）

物流配送路徑選擇是否合理直接影響了物流服務水平和運營成本的高低。本文采用節約里程法用于研究物流配送中的路徑規劃問題，對多條件約束下的配送路線優化問題進行了實證研究，結果表明采用節約里程法規劃配送路線可降低配送成本。

節約里程法；路徑規劃；物流配送

配送指在經濟合理區域范圍內，根據客戶要求，對物品進行揀選、加工、包裝、分割、組配等作用，并按時送達指定地點的物流活動。

優化配送網絡的關鍵是規劃合理的配送路線。最優的配送路線就是花最小的代價（包括使用最少的運輸工具，行駛最短的距離，花費最少的費用）將貨物以最快的速度運達目的地。規劃合理的配送路線對配送成本的影響要比一般運輸大得多，因此必須在全面計劃的基礎上，制定高效的運輸路線，選擇合適的運輸方式和運輸工具。然而，在實際中，配送受多方面因素的影響，難以預測的隨機狀況發生也會影響物流配送的效果。在眾多影響因素和我國特殊國情的背景下，如何有效地提高配送效率、降低配送成本是有待更加深入研究的問題。

一、文獻綜述

在一系列的物流管理問題中，車輛路線安排問題（VRP，Vehicle Routing Problem）得到較多關注。VRP是指由配送中心向一定數量的客戶提供不同數量的貨物，由一組數量的車輛負責運送貨物，設計最佳的配送線路，在一定條件約束的情況下（如貨物需求量、發送量、交貨時間、車輛容量限制、行駛里程限制、時間限制等），滿足客戶需求的同時，達到一定的目的，如里程最短、費用最少、時間盡量少、使用車輛數盡量少等。

車輛路線安排問題是現代物流配送系統的核心模塊，同時也是目前學術界研究的熱點問題。科學合理的調度配送車輛，不僅有利于提高服務水平和質量，而且能充分利用現有資源，實現運輸費用的最小化。對配送中心車輛調度進行規劃也就是對發往某地的貨物選擇合適的車型及運輸線路。

車輛路徑問題的實質是研究如何根據實際需要安排車輛的運輸路線，使該車輛在整個運輸過程中所花費的時間最短、費用最小，并能滿足用戶的需求，實現總的運輸成本最小化。在VRP問題中，考慮了車輛在各個卸貨點間巡回訪問的特性，提高了運輸效率。

一般而言，車輛路線安排問題大致可以分為三種類型：單車單點派送；單車多點派送；多車多點派送。配送中心的貨車行駛路線屬于單一配送中心對周邊多家門店進行配送，屬于上述的多車多點類型。

國內外許多學者近年來專注于物流配送線路優化問題的研究，找到了許多解決此類問題的方法。其中，節約里程法是用來解決運輸車輛數目不確定的VRP問題的最有名的啟發式算法。[1]節約里程法主要特點是簡單、易行，能較為靈活處理現實約束條件，在配送點數量不多的情況能較快地給出計算結果，在優化運輸路線的同時能實現物流配送的整合優勢。[2]

二、節約里程法簡介

節約里程法，有稱為節約法，是由Clarke& Wright（1964）提出，該算法以三角不等式為基礎，基本思想是：首先假設一輛車為一個配送點配貨，隨后返回配送中心0，如若有N個配送點就有N條初始線路，此時的行駛路線是最長的；然后依次將運輸問題中的兩個回路（0，….，i，0）和（0，j，….，0）合并為一個回路（0，….，i，j，….，0），合并之后總的運輸距離將發生變化。如果合并后的總運輸距離下降，則成了節約的運輸距離。對應的差值稱作節約距離。[3]

節約值越大，說明兩點連接后節約的費用越多。把節約值進行排序，在滿足車輛容量約束條件下，按照節約值由大到小的順序依次連接各配送點，直到將所有的配送點都納入到配送路線中。

圖1 典型的節約方案示意圖

如上圖所示，由配送中心P0分別向兩家門店Pi和Pj兩點配送，原先選擇（a）中的往返發貨路線送貨（P0—Pi—P0和P0—Pj—P0），送貨距離為2（L1+L2）；現在采用（b）中的巡回路線送貨（P0—Pi—Pj—P0），送貨距離變為L1+L2+L3，變動路線后汽車節約的行駛里程數為(2L1+2L2)-(L1+L2+L3)=L1+L2-L3。

利用節約里程法確定配送路線的主要出發點是，根據配送方的運輸能力及其到卸貨點之間的距離和各卸貨點之間的相對距離來制定使配送車輛總的周轉量達到或接近最小的配送方案。

本文以配送中心的配送任務為例，運用節約里程法對配送路徑進行優化，使得企業能在眾多的路徑集合中找到一組最優路徑，這組路徑完成配送任務的效果比其他任何一組路徑效果要好。

三、數學建模與分析

（一）數學建模

1.問題描述

某零售連鎖店下設一個配送中心（P），該配送中心備有載重量為1.5t和1t的貨車負責對周邊10家門店（A～J）進行貨物的運輸，規定每輛貨車一次巡回距離不超過32公里。假設每家門店的需求量為q（ii=1，2，…，10），每家門店的具體需求量如表1所示。每輛貨車都需要從配送中心出發開往各家門店進行送貨，最后都需要返回至配送中心。假設每輛車單位里程的配送成本為5元/公里，車輛固定出車費用為100元/輛。在此約束條件下，確定車輛運行方案，使得總配送費用最少。

圖2 配送中心與各門店位置分布示意圖

表1 各個門店需求量 單位：噸

2.優化目標

一般而言，配送成本的高低和配送距離呈較強的正相關性，即配送線路越長，所耗費的時間和成本也就越高。所以，科學合理的調整配送路線將極大地提升配送效果。在對配送中心現有的配送能力和水平進行綜合分析的基礎上，掌握各門店的地理位置和需求量，了解運輸路線的基本交通情況，優化調整配送路線以實現總成本最低，盡可能爭取用最短的線路來運輸最多的貨物，同時兼顧效率和成本。在實際配送中，線路優化問題需要考慮的因素很多，包括運輸距離、時間、費用等。本文只考慮最重要的兩個成本，即車輛數和行駛距離。車輛數少使得車輛的購置費、駕駛員工資和車輛維修費都能降低；行駛路徑越短，使得油耗、汽車損耗越小。因此優化目標是在滿足約束條件的基礎上，計算所有參加配送車輛的總運輸距離的最短配送路線。

3.模型的建立

每輛貨車都從配送中心出發開往各家門店進行送貨，最后需要返回至配送中心。門店i到門店j的距離為Cij。Xijk為0—1變量，若車輛K經由需求點i到j則值為1，否則為0。在約束條件以及優化目標下，建立如下有關車輛路徑問題的數學模型。

表2 約束條件表

本文在研究過程中簡化了研究模型，不考慮道路交通狀況的限制，即城市交通狀況不會對運輸效果產生重要影響。并且車輛從配送中心出發后，客戶需求信息一般不會發生改變，即車輛一般不需要臨時變更行車路線。

在運輸單價既定的情況下，要實現總運輸費用最小的目標，就是要對運輸任務進行合理優化組合，選擇最優的車輛行駛路線使得總的行駛距離最短。

（二）優化分析

1.從配送中心與各門店位置分布示意圖中計算出配送中心至各門店之間的最短距離，繪制出最短距離表，見表。

表3 兩點間最短距離表

2.計算節約值。通過計算，利用最短距離表，用P到任意兩個門店的距離之和減去兩點之間的距離得出各門店之間的節約里程，繪制出節約里程表。

表4 節約里程表

3.按從大到小的順序將節約里程數進行排列，如下表所示，最先選擇節約里程最多的點進行組合裝車配送。

表5 節約里程排序表 單位：公里

4.組成配送路線，由上表，按節約里程大小的順序組成路線圖。

初次解：總行駛距離148公里，需要車輛10輛，總費用為1740元。

圖3 配送線路初次解

二次解：按節約里程數的大小，依次連接A—B，A—J，B—C，D—E，C—D。

圖4 配送線路二次解

在P—J、A—J、A—B、B—C、C—D、D—E和E—P構成的巡回線路中，行駛距離為39，超過了最大行駛距離的要求，故線路1不能要，斷開C—D。

圖5 最佳配送路線圖

三次解：接著上述步驟，在上圖所示的路線圖中所有點都納入到線路中，而合并后的三條線路均能滿足單車最大行駛距離的要求，并且三條線路的貨物需求量均能滿足貨車運載量的要求，故完成配送線路的制定。

（三）優化結果

由上述分析可知，在考慮車輛最大承重量和最大行駛距離的情況下，一共提出了三條配送路線。

線路1：P—J—A—B—C—P：1.5t車1輛，距離28公里，載重量1.28t，車輛費用240元；

線路2：P—D—E—F—G—P：1.5t車1輛，距離30公里，載重量1.28t，車輛費用250元；

線路3：P—H—I—P：1t車1輛，距離23公里，載重量0.72t，車輛費用215元。

因此，經過優化后，總的運行距離為81公里，配送總費用為705元。與之前從配送中心單獨向各門店配貨總運行距離相比，優化后的方案節省了67公里，節約費用1035元。

四、結論

物流配送環節的關鍵在于配送路徑的優化，而節約里程法對于配送路線的優化、成本的節約和效率的提高有很大的幫助。一般情況下，配送終端位置比較分散，分布面較廣，假如單純依靠經驗判斷來確定貨車的行駛路線，很難準確制訂較優方案。因此，有必須通過科學合理的方法，提升物流配送的效率，縮減配送成本。

[1]Gianpaolo Ghiani and Gennaro Improta,An efficient transformation of the generalized vehicle routing problem,European Journal of Operational Research,

122,2000,11-17.

[2]張皓陽.我國中小型超市物流集成配送系統研究[D].天津：天津大學,2011.

[3]Mole，R.H.&Jameson，S.R.，1976，“A sequential route-building algorithm employing generalized savings criterion”，Operation research quarterly，27，503-511.

[4]張潛,高立群,胡祥培.集成化物流中的定位運輸路線安排問題(LRP)優化算法評述[J].東北大學學報,2003（01）:31-34.

[5]萬鳳嬌.多倉庫定位-運輸路線安排問題的模型和算法研究[J].江漢大學學報(自然科學版),2012（03）:26-32.

[6]林巖,胡祥培,王旭茵.物流系統優化中的定位——運輸路線安排問題(LRP)研究評述[J].管理工程學報,2004（04）:45-49.

[7]汪壽陽,趙秋紅,夏國平.集成物流管理系統中定位—運輸路線安排問題的研究[J].管理科學學報,2000（02）:69-75.

[8]楊棟.物流配送系統設計與算法應用研究[D].武漢：華中科技大學,2005.

The Optimization of Distribution Routing Based on Saving Algorithm

YAN Ying,LAI Shun-tian
(Fujian college of Water Conservancy and Electric Power，Yong’an 366000,Fujian)

A reasonable logistics distribution routing selection directly determines the level and operating costs of logistics services.This paper uses the saving algorithm to research the route planning of logistics distribution,and carries out an empirical research on the issue of distribution route optimization under the conditional constraint.The research result indicates that planning distribution route by saving algorithm can reduce delivery costs

saving algorithm;route planning;logistics distribution

F252

A

1671-5004（2017）01-0029-04

2016-9-30

顏穎（1982-），女，福建永安人，福建水利電力職業技術學院實驗師、碩士，研究方向：電子商務物流。賴順天（1969-），男，福建永安人，福建水利電力職業技術學院副教授，研究方向：電子商務物流。