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

黃 博，金志揚

（1.海南大學 應用科技學院，海南 儋州 571737；2.海南大學 機電工程技術學院，海南 ?？?570228）

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

黃 博1，金志揚2

（1.海南大學 應用科技學院，海南 儋州 571737；2.海南大學 機電工程技術學院，海南 海口 570228）

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

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

1 引言

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

2 節(jié)約算法概述

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

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

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

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

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

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

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

3.1 建立VRP模型

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

圖2 VRP模型

3.2 原配送路線基本數據分析

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

根據某公司物流配送情況，各點的香蕉運量和配送距離見表1。

確定各點之間的最短距離表，見表2。

表2 各點間最短距離表（單位：km）

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

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

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

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

根據表3數據，按節(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兩 點 ，則

（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兩點，則 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兩點，則 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,余下的各點還剩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兩點，則 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兩點，則 I5'=I4'?I7={1,3,7}，r5'=402，L5'=321.3km，B1=B7=1，最后得到優(yōu)化的結果，見表4。

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

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

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

4 結論

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

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

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

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

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

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

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

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

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

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

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

[10]陶羿,朱建青,李明,等.軍事物流選址分配模型及遺傳算法優(yōu)化[J].信息工程大學學報,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

國家科技支撐項目“熱帶特色農產品電子標簽技術研究與應用”（2009BADA1B03）；海南省教育廳科學研究項目“洋浦港物流發(fā)展模式研究”（HNKY2014-21）

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