基于節(jié)約里程法的配送路線優(yōu)化

顏 穎，賴順天

（福建水利電力職業(yè)技術(shù)學(xué)院，福建 永安，366000）

基于節(jié)約里程法的配送路線優(yōu)化

顏 穎，賴順天

（福建水利電力職業(yè)技術(shù)學(xué)院，福建 永安，366000）

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

節(jié)約里程法；路徑規(guī)劃；物流配送

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

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

一、文獻綜述

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

車輛路線安排問題是現(xiàn)代物流配送系統(tǒng)的核心模塊，同時也是目前學(xué)術(shù)界研究的熱點問題?？茖W(xué)合理的調(diào)度配送車輛，不僅有利于提高服務(wù)水平和質(zhì)量，而且能充分利用現(xiàn)有資源，實現(xiàn)運輸費用的最小化。對配送中心車輛調(diào)度進行規(guī)劃也就是對發(fā)往某地的貨物選擇合適的車型及運輸線路。

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

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

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

二、節(jié)約里程法簡介

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

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

圖1 典型的節(jié)約方案示意圖

如上圖所示，由配送中心P0分別向兩家門店P(guān)i和Pj兩點配送，原先選擇（a）中的往返發(fā)貨路線送貨（P0—Pi—P0和P0—Pj—P0），送貨距離為2（L1+L2）；現(xiàn)在采用（b）中的巡回路線送貨（P0—Pi—Pj—P0），送貨距離變?yōu)長1+L2+L3，變動路線后汽車節(jié)約的行駛里程數(shù)為(2L1+2L2)-(L1+L2+L3)=L1+L2-L3。

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

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

三、數(shù)學(xué)建模與分析

（一）數(shù)學(xué)建模

1.問題描述

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

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

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

2.優(yōu)化目標(biāo)

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

3.模型的建立

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

表2 約束條件表

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

在運輸單價既定的情況下，要實現(xiàn)總運輸費用最小的目標(biāo)，就是要對運輸任務(wù)進行合理優(yōu)化組合，選擇最優(yōu)的車輛行駛路線使得總的行駛距離最短。

（二）優(yōu)化分析

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

表3 兩點間最短距離表

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

表4 節(jié)約里程表

3.按從大到小的順序?qū)⒐?jié)約里程數(shù)進行排列，如下表所示，最先選擇節(jié)約里程最多的點進行組合裝車配送。

表5 節(jié)約里程排序表 單位：公里

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

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

圖3 配送線路初次解

二次解：按節(jié)約里程數(shù)的大小，依次連接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構(gòu)成的巡回線路中，行駛距離為39，超過了最大行駛距離的要求，故線路1不能要，斷開C—D。

圖5 最佳配送路線圖

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

（三）優(yōu)化結(jié)果

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

線路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元。

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

四、結(jié)論

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

[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]張皓陽.我國中小型超市物流集成配送系統(tǒng)研究[D].天津：天津大學(xué),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)優(yōu)化算法評述[J].東北大學(xué)學(xué)報,2003（01）:31-34.

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

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

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

[8]楊棟.物流配送系統(tǒng)設(shè)計與算法應(yīng)用研究[D].武漢：華中科技大學(xué),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-），女，福建永安人，福建水利電力職業(yè)技術(shù)學(xué)院實驗師、碩士，研究方向：電子商務(wù)物流。賴順天（1969-），男，福建永安人，福建水利電力職業(yè)技術(shù)學(xué)院副教授，研究方向：電子商務(wù)物流。