卷烟商零物流动态线路优化和在途监控的研究及实现

徐智，陈军，唐萍

1湖南省烟草公司物流处，湖南省长沙市芙蓉南路一段628号 410004；

2 湖南湘邮科技股份有限公司运营行业部，湖南省长沙市岳麓区玉兰路2号 410205

经济与管理

卷烟商零物流动态线路优化和在途监控的研究及实现

徐智1，陈军2，唐萍2

1湖南省烟草公司物流处，湖南省长沙市芙蓉南路一段628号 410004；

2 湖南湘邮科技股份有限公司运营行业部，湖南省长沙市岳麓区玉兰路2号 410205

为优化湖南烟草工商物流和商零物流操作流程，分析了省内市州烟草公司配送现状，运用GPS、GIS 、GPRS等技术，采用基于启发式的禁忌搜索聚类算法、车载导航系统等，建立了一套完整的智能化卷烟商零在途动态监管系统，可大幅提高卷烟商业配送运输效率，降低配送成本。

烟草物流；禁忌搜索算法；批零聚类；路径规划；车辆导航；动态监管

近年来，如何提升卷烟物流配送效率，降低成本，提高客户服务水平，是全行业面临的重大挑战。物流以其运输量大、单位商品价值高的特点，成为卷烟经营的重要一环。构建面向市场的精益物流，大力发展智能化的卷烟配送模式，降低物流成本，已成为烟草企业战胜挑战的重要手段。

目前我国烟草行业已经构建了较为完善的配送体系，力图实现从工商物流到商零物流的全程监控，然而，还是存在一些问题，例如：1.访销区域划分不合理；2.配送线路不合理，车辆装载量无法合理利用，以致送货效率低，成本高；3.缺乏配送在途异常监控及处理机制。

本文主要讨论问题2和3并提出方案。

针对问题2，在一定客户数量的前提下，线路配送的方式有多种，制定配送线路的目标是在满足各类约束条件的前提下，给出尽可能优化的线路规划方案。本文采用禁忌搜索算法解决该问题。

针对问题3，在卷烟配送过程中，为方便管理人员进行车辆调度和实时监控，借助GPS定位技术，通过在车辆上安装定位终端，实现对车辆位置的跟踪，并在控制中心对位置进行处理和分析后，使得车辆位置、车辆运行轨迹准确反映在电子地图上。

借助这些技术手段和方法，建设卷烟商零动态线路优化和在途监控系统，以期达到提高送货效率、降低配送成本、提升客户满意度，并最终达到提高公司利润的效果。

1 算法基础与系统实现

1.1 算法介绍

禁忌搜索算法（Tabu Search，TS）在1986年提出，通过模拟人类智能的记忆机制，采用禁忌策略限制搜索过程中片面追求局部最优而设计，同时，引入破禁准则来释放一些被禁忌的优良状态，以保证所有过程的有效性和多样性[1]。TS算法已广泛用于组合优化、函数优化、线路设计、神经网络等领域[2]。

运用禁忌搜索算法进行卷烟配送线路设计，是为满足烟草行业现阶段卷烟配送模式而引入的。目前烟草公司的卷烟配送已经从商户购买取货方式转换成物流中心直接配送模式[3]，因此，在卷烟配送前，根据客户订货量制定合理的线路，动态调度送货车辆，能有效的降本增效，并在此基础上实行商零在途的监控和服务。

1.2 算法实现

将烟草卷烟配送过程进行抽析可概括为：N台车从1个配送中心出发为M个客户服务，并在完成任务后返回该配送中心。为保证车辆装载量和行驶距离相对均衡，引入禁忌算法时，考虑的因素如表1：

表1 禁忌算法所考虑的约束条件Tab.1 Constraints of tabu search algorithm

算法的核心步骤有三步：1.建立距离矩阵；2.任务分配；3.线路排序及线路改进。

1.2.1 建立距离矩阵

距离矩阵包含每个客户之间的行驶距离和行驶时间，为任务分配、线路排序和线路改进提供基本信息。

1.2.2 任务分配

任务分配的算法是把客户分配给相应的车辆。在分配时，依照车辆工作时间基本均衡、装载量通过加权的方法采用“近的多送、远的多运”原则，通过加权的方法把约束条件、有利因素加以合并，成为一个多目标函数，对任务进行划分。工作任务划分完成后，系统按照以下步骤进行线路制定和优化。

系统首先为一台车r建立一条最初的行驶线路，此线路一般仅包含出发点（配送中心）和最远的目的地。

其次，将矩阵中本任务对应的其他客户信息逐个加入，依次求解，不断形成新的线路。当所有任务客户加入后，线路初始线路制定结束，则任务分配初步完成。

1.2.3 线路排序和线路改进

本步骤改进了由任务分配算法所产生的最初线路。定义线路R=（V，A），其中V是线路中包括始发点和客户点的信息点，A 是线路内连接信息点之间的有向弧。每条弧的属性中包含其连接两点之间的距离。线路排序和线路改进过程，基于全盘线路最优考虑，对初始线路进行优化，为每一个信息点安排最优的顺序。

1.2.4 禁忌搜索技术在此过程中的核心代码

1.3 商零在途监管的研究与应用

基于动态线路规划成果，使商零在途的动态监控得到实现。系统在构建过程中，运用GPS、GIS和GPRS技术，实现对卷烟配送在途的全程跟踪和动态监管。

通过GPRS、3G等无线网络，车载导航终端将路单信息、客户信息、客户订单信息下载至本地保存，通过车载GPS导航仪，车辆根据路单提示进行卷烟配送，同时借助GPRS将车辆位置实时返回至后台系统。通过GIS技术，将本区域客户信息在地图上显示出来，反映车辆行驶全程情况。系统将所有配送车辆行驶轨迹、行驶时长、行驶里程和历史行驶情况统计分析，并将信息可视化展示。

2 应用效果

2.1 系统功能

2.1.1 线路制定和线路优化

系统基于启发式禁忌搜索算法根据每日订单进行动态路径规划。该模块的功能包括：参数信息管理（如：配送中心信息、客户地理位置信息和卸货方式、配送车辆时间窗和装载信息、送货归集点信息等）、访销分区划片、优化参数设定、优化计算、优化微调、线路规划最优成果。根据优化结果指导配送调度，并通过物流综合管理平台同步至烟草其他相关系统。

2.1.2 交互式导航

交互导航模块分为通信平台和嵌入式车载导航终端两部分。通信平台完成系统与车载终端无线通信及调度功能，车载导航终端通过屏幕和语音指导驾驶员进行车辆驾驶。功能包括：配送路单下载、配送客户信息下载、配送信息查询、语音导航、卸货确认等交互功能。

系统根据车辆位置信息、客户点信息、路单信息等统计车辆行驶里程信息、车辆油耗量信息，并评价工作人员的任务执行情况。

2.1.3 客户服务

客户通过手机上网、电脑上网实时查询订单执行状态信息；通过短信告知客户货物数量，预结算金额、预到达时间等；通过FID卡实现电子签收，将客户身份、签收地理位置、签收时间等信息实时上传；通过“语音自动回访”建立反馈通道，采集考核数据。

2.2 系统运行效果

系统开发投入运行两年来，在送货总量增加、工作时间减少的前提下，实现了送货车辆、配送人员减少、装载量及送货户数增加的效果，实现了提高卷烟配送效率、降低配送成本的建设目标。以我省常德市烟草公司为例，使用本系统后，取得了如下成效：

1) 配送日常使用车辆由60辆减少到48辆，用车量下降了20%；

2) 配送人员由140名减少至112人，用工人数下降了20%；

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

4) 单车日均送货户数由74户增加到90户左右，增长了21.62%；

5) 卷烟单件配送成本由14.28元下降为11.31元，下降了20.79%。

3 结语

烟草商业卷烟商零在途监管系统是从烟草工业在途监管向商零在途监管的延伸，该系统应用信息化管理，实现了从烟草工业经烟草商业最终到达零售客户的全面感知和监控，使工商物流供应链全程贯通，实现了由分散的单一企业物流向适度规模的整合物流转变；同时，通过优化现有作业流程，有效提高了烟草商业配送运输的精益管理，实现了工商协同物流的有益探索。

[1]陈小丽，曲媛，肖鸿.宜春市烟草公司物流配送线路优化[J].佳木斯大学学报，2012(01)：49-52.

[][]

[2]夏洁，高金源，余舟毅.基于禁忌搜索的启发式任务路径规划算法[J].控制与决策，2002(11) ：774-776.

[3]徐立华.求解最短线路问题的一个计算机算法[J].系统工程，1989(05).

[4]朱延昌，王志学.动态规划中最短问题的计算机解法[J].长春工业大学学报：自然科学版，2007(04).

[5]杜亮.重庆烟草物流研究[J].中国市场，2010，45(11) ：18-19.

[6]董祥俊.烟草商业企业物流运行现状及发展方向探讨[J].物流工程与管理，2009，31(4) ：24-27.

[7]王勇，池洁，樊建新.基于遗传算法烟草物流配送区域划分优化研究[J].重庆交通大学学报，2009，28(3) ：621-624.

[8]周胜，吴琼，程章杰.基于GIS的南昌烟草物流配送线路优化调度研究[J].企业研究，2011，8(02) ：63-65.

[9]曹娟.电子商务环境下烟草行业现代物流的发展[J].河南工业大学学报：社会科学版，2008，(02).

[10]雷同飞，张宏.物流配送中心车辆路径优化问题[J].商场现代化，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—），男， 高级工程师，高级物流师，从事信息化建设规划与建设，Email：xuz@hntobacco.com

2013-03-25