基于節(jié)約法的海南某公司物流配送路徑優(yōu)化

黃 博，金志揚(yáng)

（1.海南大學(xué) 應(yīng)用科技學(xué)院，海南 儋州 571737；2.海南大學(xué) 機(jī)電工程技術(shù)學(xué)院，海南 ?？?570228）

基于節(jié)約法的海南某公司物流配送路徑優(yōu)化

黃 博1，金志揚(yáng)2

（1.海南大學(xué) 應(yīng)用科技學(xué)院，海南 儋州 571737；2.海南大學(xué) 機(jī)電工程技術(shù)學(xué)院，海南 海口 570228）

針對海南某公司的物流配送問題，通過建立VRP模型，運(yùn)用節(jié)約算法對原配送路線基本數(shù)據(jù)進(jìn)行分析，并列出節(jié)約里程順序表，然后按節(jié)約里程從大到小合并路徑，繪制成配送中心與各客戶點(diǎn)優(yōu)化線路圖，從而對配送線路進(jìn)行優(yōu)化，提出了最優(yōu)配送方案。

低碳物流；配送路徑；VRP模型；節(jié)約算法；優(yōu)化線路

1 引言

海南作為中國的國際旅游島，低碳物流成為了海南國際旅游島經(jīng)濟(jì)發(fā)展的重要指導(dǎo)理念，也是低碳經(jīng)濟(jì)發(fā)展不可或缺的一部分[1-3]。物流配送路徑優(yōu)化是低碳物流的重要組成部分，主要專注于商品的發(fā)貨、運(yùn)輸、到貨等作業(yè)的計(jì)劃、控制和反饋過程的優(yōu)化系統(tǒng)，達(dá)到可以提高物流配送效率，降低物流配送成本的目的[4-7]。物流配送路徑算法有節(jié)約算法[8]、蟻群算法[9]和遺傳算法[10]等，通過優(yōu)化算法應(yīng)用到實(shí)際問題中，不僅可以緩解社會交通壓力，減少能源浪費(fèi)，也可降低運(yùn)輸成本，提高企業(yè)物流配送運(yùn)作效率，客戶的服務(wù)質(zhì)量以及公司的整體競爭力。因此，運(yùn)用優(yōu)化算法解決實(shí)際配送問題的方式，廣泛應(yīng)用于彈藥物流、低碳物流等領(lǐng)域，對社會和企業(yè)的長遠(yuǎn)發(fā)展具有深遠(yuǎn)的意義。

2 節(jié)約算法概述

2.1 節(jié)約算法核心思想

節(jié)約算法是用來解決運(yùn)輸車輛數(shù)目不確定的VRP問題最有名的啟發(fā)式算法，其核心思想是將運(yùn)輸問題中的兩個回路合并成一個回路，若合并后的總運(yùn)輸距離減少，則稱節(jié)約了運(yùn)輸距離?？傔\(yùn)輸距離減少的幅度最大，達(dá)到一輛車的裝載限制時，再進(jìn)行下一輛車的優(yōu)化，使得全局總運(yùn)輸距離達(dá)到最優(yōu)。

總運(yùn)輸距離的變化值，稱為節(jié)約距離ΔCij，如式（1）所示：

節(jié)約算法運(yùn)用過程如圖1所示：

圖1 節(jié)約算法圖解

2.2 節(jié)約算法主要步驟

3 節(jié)約算法在海南某公司的具體應(yīng)用

3.1 建立VRP模型

多回路運(yùn)輸問題是用于現(xiàn)實(shí)生活中比較常見的一種處理多條路線優(yōu)化的經(jīng)濟(jì)運(yùn)輸問題。VRP（Vehicle Routing Problem）模型改善了車輛調(diào)度的整合，成為了多回路問題最為成功的模型。該模型研究的問題要遵守以下配送路線原則：以效率最高，成本最低，路程最短，噸公里數(shù)最小，準(zhǔn)確性最高和運(yùn)力利用最合理，勞動消耗最低為目標(biāo)。一個典型的VRP模型約束條件主要為：客戶需求和公司利益及社會價值。針對海南某公司物流配送問題，建立的VRP模型如圖2所示。

圖2 VRP模型

3.2 原配送路線基本數(shù)據(jù)分析

已知該公司以A點(diǎn)（儋州）為基點(diǎn)，分別向C點(diǎn)（海口）、D點(diǎn)（文昌）、E點(diǎn)（瓊海）、F點(diǎn)（萬寧）、G點(diǎn)（東方）、H點(diǎn)（三亞）7個客戶點(diǎn)配送香蕉，該公司擁有一輛7t的車，可最多運(yùn)輸300箱香蕉，還有兩輛11t的車，每輛最多可運(yùn)輸500箱香蕉。設(shè)各點(diǎn)間的距離為節(jié)約距離為Δcij，各點(diǎn)的需求量Ni(i=1,2,…,7),每輛車行車?yán)锍虨?Li(i=1,2,…,7)，Li≤600km，以A點(diǎn)為中心點(diǎn)，客戶點(diǎn)分別為B,C,…,H，對應(yīng)i=1,2,…,7。

根據(jù)某公司物流配送情況，各點(diǎn)的香蕉運(yùn)量和配送距離見表1。

確定各點(diǎn)之間的最短距離表，見表2。

表2 各點(diǎn)間最短距離表（單位：km）

然 后 令 Ik={k}(k=1,2,...,7) ， 最 短 路 徑Li=2c0i（i=1,2,…,7），滿足Li≤600km；載貨量ri=Ni，滿足Li≤500，對 能 合 并 的 7個 客 戶 點(diǎn) 進(jìn) 行 標(biāo) 記 ，B1=B2=…=B7=0，且Bi≤2。

緊接著，算出節(jié)約里程順序表。根據(jù)最短距離表，根據(jù)式（1）計(jì)算出用戶間的節(jié)約里程,并由大到小排列，編制節(jié)約里程△Cij順序表，見表3。

表3 節(jié)約里程順序表（單位：km）

3.3 配送路線優(yōu)化

根據(jù)表3數(shù)據(jù)，按節(jié)約里程從大到小合并路徑：

（1）對于Δc24=241.1km,r2+r4=60+225=285＜500，L2+L4-Δc24=165.1×2+157.5×2-241.1=404.1km＜600km，B2=B4=0因 此 合 并 C、E兩 點(diǎn) ，則

（2）對于Δc45=162.4km,r1'+r5=285+68=353＜500，L1'+L5-Δc45=404.1+89.7×2-162.4=421.1km＜600km，B4=1，B5=0，因此合并 E、F兩點(diǎn)，則 I2'=I1'?I5={2,4,5},r2'=353，L2'=421.1km，B2=B5=1。

（3）對于Δc56=134.5km,r2'+r6=353+89=442＜500,L2'+L6-Δc56=421.1+79.8×2-134.5=446.2km＜600km，B5=1，B6=0，因此合并F、G兩點(diǎn)，則 I3'=I2'?I6={2,4,5,6}，r3'=442，L3'=446.2km，B2=B6=1，B4=B5=2。

（4）對于Δc12=133.3km,r2'+r1=442+120=562＞500，不符合條件。

（5）對于Δc46=123.8km，因E與G處于同一回路中，不滿足合并條件。

（6）回路A-C-E-F-G-A,余下的各點(diǎn)還剩B、D和H。

（7）對于Δc13=83.8km,r1+r3=120+80=200＜500，L1+L3-Δc13=84.2×2+48.2×2-83.8=181km＜600km，B1=0，B3=0，因此合并B、D兩點(diǎn)，則 I4=I1?I3={1,3},r4=200,L1=181km, B1=B3=1。

（8）對于Δc37=26.7km,r4'+r7=200+202=402＜500，L1'+L7-Δc13=181+83.5×2-26.7=321.3km＜600km，B3=1，B7=0，因此合并 D、H兩點(diǎn)，則 I5'=I4'?I7={1,3,7}，r5'=402，L5'=321.3km，B1=B7=1，最后得到優(yōu)化的結(jié)果，見表4。

表4 節(jié)約法優(yōu)化結(jié)果

從表4中可以看出，路線可以組成兩條回路，公司每周需要2輛11t貨車，分別運(yùn)輸446.2km和321.3km。據(jù)此，可畫出配送中心與各客戶點(diǎn)的簡單線路圖，如圖3所示。

圖3 配送中心與各客戶點(diǎn)優(yōu)化后線路圖

4 結(jié)論

（1）針對海南某公司物流配送問題，建立了VRP模型，以客戶需求和公司利益及社會價值為約束條件，以效率、成本、路程、噸公里數(shù)、勞動力等作為變化條件。

（2）運(yùn)用節(jié)約算法對原配送路線基本數(shù)據(jù)進(jìn)行分析，并列出節(jié)約里程順序表，然后按節(jié)約里程從大到小合并路徑，繪制成配送中心與各客戶點(diǎn)優(yōu)化線路圖，從而對配送線路進(jìn)行優(yōu)化，提出了最優(yōu)配送方案，解決了實(shí)際生活中某公司物流運(yùn)輸配送方面的難題，從而節(jié)約了企業(yè)成本，為海南低碳物流提供理論指導(dǎo)意義。

[1]吳仁亮,金志揚(yáng),薛文瓏.危險品水路運(yùn)輸事故致因過程研究[J].物流技術(shù),2015,(1):58-60.

[2]薛文瓏,金志揚(yáng).海南省能源消費(fèi)和碳排放預(yù)測研究[J].環(huán)境工程, 2015,(2):153-155.

[3]薛文瓏,金志揚(yáng).海南省低碳經(jīng)濟(jì)綜合評價方法研究[J].特區(qū)經(jīng)濟(jì), 2014,(5):15-19.

[4]王永亮.物流配送路徑優(yōu)化問題的研究與應(yīng)用[D].太原:太原理工大學(xué),2009.

[5]占焱發(fā).基于遺傳算法的物流配送車輛路徑問題研究[D].西安:長安大學(xué),2010.

[6]王鑫.物流配送中車輛優(yōu)化調(diào)度問題的研究與實(shí)踐[D].沈陽:沈陽航空工業(yè)學(xué)院,2006.

[7]許星.物流配送路徑優(yōu)化問題的研究[D].杭州:浙江大學(xué),2006.

[8]劉俊娥,李奇.基于節(jié)約里程法的北京市家樂福超市配送線路優(yōu)化方案[J].物流技術(shù),2015,(1):107-109.

[9]陳建軍.蟻群算法在物流配送路徑優(yōu)化中的研究[J].計(jì)算機(jī)仿真, 2011,(2):268-271.

[10]陶羿,朱建青,李明,等.軍事物流選址分配模型及遺傳算法優(yōu)化[J].信息工程大學(xué)學(xué)報,2007,(1):110-113.

Optimization of Logistics Distribution Route of Certain Hainan-based Company Based on Saving Algorithm

Huang Bo1,Jin Zhiyang2
(1.School of Applied Technology,Hainan University,Danzhou 571737; 2.School of Mechanical&Electrical Engineering&Technology,Hainan University,Haikou 570228,China)

In this paper,in view of the logistics distribution problem of a certain company based in Hainan and through establishing the VRP model and using the saving algorithm,we analyzed the basic data of the original distribution route of the company,then obtained the ranking of the saved mileage of different routes,and at the end,proposed the optimal distribution plan.

low-carbon logistics;distribution route;VRP model;saving algorithm;optimal routing

F252.13

A

1005-152X(2015)11-0124-03

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

2015-10-09

國家科技支撐項(xiàng)目“熱帶特色農(nóng)產(chǎn)品電子標(biāo)簽技術(shù)研究與應(yīng)用”（2009BADA1B03）；海南省教育廳科學(xué)研究項(xiàng)目“洋浦港物流發(fā)展模式研究”（HNKY2014-21）

黃博（1992-），男，新疆阜康人，主要研究方向：物流工程；金志揚(yáng)（1978-），通訊作者，男，湖南邵東人，副教授，主要研究方向：低碳物流。