徐智，陳軍，唐萍

1湖南省煙草公司物流處，湖南省長沙市芙蓉南路一段628號 410004；

2 湖南湘郵科技股份有限公司運營行業(yè)部，湖南省長沙市岳麓區(qū)玉蘭路2號 410205

經(jīng)濟與管理

卷煙商零物流動態(tài)線路優(yōu)化和在途監(jiān)控的研究及實現(xiàn)

徐智1，陳軍2，唐萍2

1湖南省煙草公司物流處，湖南省長沙市芙蓉南路一段628號 410004；

2 湖南湘郵科技股份有限公司運營行業(yè)部，湖南省長沙市岳麓區(qū)玉蘭路2號 410205

為優(yōu)化湖南煙草工商物流和商零物流操作流程，分析了省內(nèi)市州煙草公司配送現(xiàn)狀，運用GPS、GIS 、GPRS等技術(shù)，采用基于啟發(fā)式的禁忌搜索聚類算法、車載導航系統(tǒng)等，建立了一套完整的智能化卷煙商零在途動態(tài)監(jiān)管系統(tǒng)，可大幅提高卷煙商業(yè)配送運輸效率，降低配送成本。

煙草物流；禁忌搜索算法；批零聚類；路徑規(guī)劃；車輛導航；動態(tài)監(jiān)管

近年來，如何提升卷煙物流配送效率，降低成本，提高客戶服務(wù)水平，是全行業(yè)面臨的重大挑戰(zhàn)。物流以其運輸量大、單位商品價值高的特點，成為卷煙經(jīng)營的重要一環(huán)。構(gòu)建面向市場的精益物流，大力發(fā)展智能化的卷煙配送模式，降低物流成本，已成為煙草企業(yè)戰(zhàn)勝挑戰(zhàn)的重要手段。

目前我國煙草行業(yè)已經(jīng)構(gòu)建了較為完善的配送體系，力圖實現(xiàn)從工商物流到商零物流的全程監(jiān)控，然而，還是存在一些問題，例如：1.訪銷區(qū)域劃分不合理；2.配送線路不合理，車輛裝載量無法合理利用，以致送貨效率低，成本高；3.缺乏配送在途異常監(jiān)控及處理機制。

本文主要討論問題2和3并提出方案。

針對問題2，在一定客戶數(shù)量的前提下，線路配送的方式有多種，制定配送線路的目標是在滿足各類約束條件的前提下，給出盡可能優(yōu)化的線路規(guī)劃方案。本文采用禁忌搜索算法解決該問題。

針對問題3，在卷煙配送過程中，為方便管理人員進行車輛調(diào)度和實時監(jiān)控，借助GPS定位技術(shù)，通過在車輛上安裝定位終端，實現(xiàn)對車輛位置的跟蹤，并在控制中心對位置進行處理和分析后，使得車輛位置、車輛運行軌跡準確反映在電子地圖上。

借助這些技術(shù)手段和方法，建設(shè)卷煙商零動態(tài)線路優(yōu)化和在途監(jiān)控系統(tǒng)，以期達到提高送貨效率、降低配送成本、提升客戶滿意度，并最終達到提高公司利潤的效果。

1 算法基礎(chǔ)與系統(tǒng)實現(xiàn)

1.1 算法介紹

禁忌搜索算法（Tabu Search，TS）在1986年提出，通過模擬人類智能的記憶機制，采用禁忌策略限制搜索過程中片面追求局部最優(yōu)而設(shè)計，同時，引入破禁準則來釋放一些被禁忌的優(yōu)良狀態(tài)，以保證所有過程的有效性和多樣性[1]。TS算法已廣泛用于組合優(yōu)化、函數(shù)優(yōu)化、線路設(shè)計、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域[2]。

運用禁忌搜索算法進行卷煙配送線路設(shè)計，是為滿足煙草行業(yè)現(xiàn)階段卷煙配送模式而引入的。目前煙草公司的卷煙配送已經(jīng)從商戶購買取貨方式轉(zhuǎn)換成物流中心直接配送模式[3]，因此，在卷煙配送前，根據(jù)客戶訂貨量制定合理的線路，動態(tài)調(diào)度送貨車輛，能有效的降本增效，并在此基礎(chǔ)上實行商零在途的監(jiān)控和服務(wù)。

1.2 算法實現(xiàn)

將煙草卷煙配送過程進行抽析可概括為：N臺車從1個配送中心出發(fā)為M個客戶服務(wù)，并在完成任務(wù)后返回該配送中心。為保證車輛裝載量和行駛距離相對均衡，引入禁忌算法時，考慮的因素如表1：

表1 禁忌算法所考慮的約束條件Tab.1 Constraints of tabu search algorithm

算法的核心步驟有三步：1.建立距離矩陣；2.任務(wù)分配；3.線路排序及線路改進。

1.2.1 建立距離矩陣

距離矩陣包含每個客戶之間的行駛距離和行駛時間，為任務(wù)分配、線路排序和線路改進提供基本信息。

1.2.2 任務(wù)分配

任務(wù)分配的算法是把客戶分配給相應(yīng)的車輛。在分配時，依照車輛工作時間基本均衡、裝載量通過加權(quán)的方法采用“近的多送、遠的多運”原則，通過加權(quán)的方法把約束條件、有利因素加以合并，成為一個多目標函數(shù)，對任務(wù)進行劃分。工作任務(wù)劃分完成后，系統(tǒng)按照以下步驟進行線路制定和優(yōu)化。

系統(tǒng)首先為一臺車r建立一條最初的行駛線路，此線路一般僅包含出發(fā)點（配送中心）和最遠的目的地。

其次，將矩陣中本任務(wù)對應(yīng)的其他客戶信息逐個加入，依次求解，不斷形成新的線路。當所有任務(wù)客戶加入后，線路初始線路制定結(jié)束，則任務(wù)分配初步完成。

1.2.3 線路排序和線路改進

本步驟改進了由任務(wù)分配算法所產(chǎn)生的最初線路。定義線路R=（V，A），其中V是線路中包括始發(fā)點和客戶點的信息點，A 是線路內(nèi)連接信息點之間的有向弧。每條弧的屬性中包含其連接兩點之間的距離。線路排序和線路改進過程，基于全盤線路最優(yōu)考慮，對初始線路進行優(yōu)化，為每一個信息點安排最優(yōu)的順序。

1.2.4 禁忌搜索技術(shù)在此過程中的核心代碼

1.3 商零在途監(jiān)管的研究與應(yīng)用

基于動態(tài)線路規(guī)劃成果，使商零在途的動態(tài)監(jiān)控得到實現(xiàn)。系統(tǒng)在構(gòu)建過程中，運用GPS、GIS和GPRS技術(shù)，實現(xiàn)對卷煙配送在途的全程跟蹤和動態(tài)監(jiān)管。

通過GPRS、3G等無線網(wǎng)絡(luò)，車載導航終端將路單信息、客戶信息、客戶訂單信息下載至本地保存，通過車載GPS導航儀，車輛根據(jù)路單提示進行卷煙配送，同時借助GPRS將車輛位置實時返回至后臺系統(tǒng)。通過GIS技術(shù)，將本區(qū)域客戶信息在地圖上顯示出來，反映車輛行駛?cè)糖闆r。系統(tǒng)將所有配送車輛行駛軌跡、行駛時長、行駛里程和歷史行駛情況統(tǒng)計分析，并將信息可視化展示。

2 應(yīng)用效果

2.1 系統(tǒng)功能

2.1.1 線路制定和線路優(yōu)化

系統(tǒng)基于啟發(fā)式禁忌搜索算法根據(jù)每日訂單進行動態(tài)路徑規(guī)劃。該模塊的功能包括：參數(shù)信息管理（如：配送中心信息、客戶地理位置信息和卸貨方式、配送車輛時間窗和裝載信息、送貨歸集點信息等）、訪銷分區(qū)劃片、優(yōu)化參數(shù)設(shè)定、優(yōu)化計算、優(yōu)化微調(diào)、線路規(guī)劃最優(yōu)成果。根據(jù)優(yōu)化結(jié)果指導配送調(diào)度，并通過物流綜合管理平臺同步至煙草其他相關(guān)系統(tǒng)。

2.1.2 交互式導航

交互導航模塊分為通信平臺和嵌入式車載導航終端兩部分。通信平臺完成系統(tǒng)與車載終端無線通信及調(diào)度功能，車載導航終端通過屏幕和語音指導駕駛員進行車輛駕駛。功能包括：配送路單下載、配送客戶信息下載、配送信息查詢、語音導航、卸貨確認等交互功能。

系統(tǒng)根據(jù)車輛位置信息、客戶點信息、路單信息等統(tǒng)計車輛行駛里程信息、車輛油耗量信息，并評價工作人員的任務(wù)執(zhí)行情況。

2.1.3 客戶服務(wù)

客戶通過手機上網(wǎng)、電腦上網(wǎng)實時查詢訂單執(zhí)行狀態(tài)信息；通過短信告知客戶貨物數(shù)量，預結(jié)算金額、預到達時間等；通過FID卡實現(xiàn)電子簽收，將客戶身份、簽收地理位置、簽收時間等信息實時上傳；通過“語音自動回訪”建立反饋通道，采集考核數(shù)據(jù)。

2.2 系統(tǒng)運行效果

系統(tǒng)開發(fā)投入運行兩年來，在送貨總量增加、工作時間減少的前提下，實現(xiàn)了送貨車輛、配送人員減少、裝載量及送貨戶數(shù)增加的效果，實現(xiàn)了提高卷煙配送效率、降低配送成本的建設(shè)目標。以我省常德市煙草公司為例，使用本系統(tǒng)后，取得了如下成效：

1) 配送日常使用車輛由60輛減少到48輛，用車量下降了20%；

2) 配送人員由140名減少至112人，用工人數(shù)下降了20%；

3) 單車日均配送量由83件增加到108件，增加了30%；

4) 單車日均送貨戶數(shù)由74戶增加到90戶左右，增長了21.62%；

5) 卷煙單件配送成本由14.28元下降為11.31元，下降了20.79%。

3 結(jié)語

煙草商業(yè)卷煙商零在途監(jiān)管系統(tǒng)是從煙草工業(yè)在途監(jiān)管向商零在途監(jiān)管的延伸，該系統(tǒng)應(yīng)用信息化管理，實現(xiàn)了從煙草工業(yè)經(jīng)煙草商業(yè)最終到達零售客戶的全面感知和監(jiān)控，使工商物流供應(yīng)鏈全程貫通，實現(xiàn)了由分散的單一企業(yè)物流向適度規(guī)模的整合物流轉(zhuǎn)變；同時，通過優(yōu)化現(xiàn)有作業(yè)流程，有效提高了煙草商業(yè)配送運輸?shù)木婀芾?，實現(xiàn)了工商協(xié)同物流的有益探索。

[1]陳小麗，曲媛，肖鴻.宜春市煙草公司物流配送線路優(yōu)化[J].佳木斯大學學報，2012(01)：49-52.

[][]

[2]夏潔，高金源，余舟毅.基于禁忌搜索的啟發(fā)式任務(wù)路徑規(guī)劃算法[J].控制與決策，2002(11) ：774-776.

[3]徐立華.求解最短線路問題的一個計算機算法[J].系統(tǒng)工程，1989(05).

[4]朱延昌，王志學.動態(tài)規(guī)劃中最短問題的計算機解法[J].長春工業(yè)大學學報：自然科學版，2007(04).

[5]杜亮.重慶煙草物流研究[J].中國市場，2010，45(11) ：18-19.

[6]董祥俊.煙草商業(yè)企業(yè)物流運行現(xiàn)狀及發(fā)展方向探討[J].物流工程與管理，2009，31(4) ：24-27.

[7]王勇，池潔，樊建新.基于遺傳算法煙草物流配送區(qū)域劃分優(yōu)化研究[J].重慶交通大學學報，2009，28(3) ：621-624.

[8]周勝，吳瓊，程章杰.基于GIS的南昌煙草物流配送線路優(yōu)化調(diào)度研究[J].企業(yè)研究，2011，8(02) ：63-65.

[9]曹娟.電子商務(wù)環(huán)境下煙草行業(yè)現(xiàn)代物流的發(fā)展[J].河南工業(yè)大學學報：社會科學版，2008，(02).

[10]雷同飛，張宏.物流配送中心車輛路徑優(yōu)化問題[J].商場現(xiàn)代化，2009(01) ：119-120.

Study of dynamic route optimization and monitoring in cigarette distribution

XU Zhi1，CHEN Jun2，TANG Ping2
1 Logistics Department，Hunan Provincial Tobacco Company，Changsha 410004，China；
2 Department of Industry Operation，Hunan Post Science & Technology CO.，LTD，Changsha 410205，China

A complete set of smart system of dynamic monitoring and route optimization in logistic management in cigarette sale was developed based on GPS,GIS,GPRS,heuristic-based tabu search clustering algorithm and car navigation system.Results showed that the new system could reduce costs and improve ef ficiency.

tobacco logistics; tabu search algorithm; wholesale and retail clustering; path planning; navigation; dynamic monitoring

10.3969/j.issn.1004-5708.2014.01.013

TP315

A

1004-5708（2014）01-0071-03

徐智（1959—），男， 高級工程師，高級物流師，從事信息化建設(shè)規(guī)劃與建設(shè)，Email：xuz@hntobacco.com

2013-03-25