引入交通指数的节约法对电力物资配送寻优研究

张云翔

（深圳供电局有限公司，广东　深圳　518000）



引入交通指数的节约法对电力物资配送寻优研究

张云翔

（深圳供电局有限公司，广东深圳518000）

由于电力企业的特殊性，仅凭现阶段采用的人工经验判断或是固定班车调度配送已经难以满足物资需求急剧增长对于配送效率最优、资源节约的需求。针对深圳供电局的实证数据，通过引入道路交通运行指数（以下全文简称“交通指数”）的节约法规划整体线路与实时路况导航推荐最终行车路线结合的方式，为电力物资配送完成路径寻优模型。在此模型基础上开发了电力物资配送管理信息系统，经过反复实证数据研究，证明该模型能够较高程度地实现物资配送过程效率最优，路径最短，为电力物资配送的补仓、调度和优化提供了有力的支持，为监管层提供了较合理高效的决策。

交通指数；节约法；电力物资；物资配送；路径寻优

1　引言

电力企业是典型的拥有技术与资产密集型特点的资源型企业。其拥有的物资设备品类多、数量大，而电力生产又具有高度的连续性，电力物资配送是否及时直接关系到电网的正常运行。

随着中国社会进入互联网时代，大数据理念快速发展，如何更加合理高效的安排电力物资配送，以更好的契合当今时代倡导的资源共享、节能减排的政策主题，满足供电局各层级人员在管理和操作上的需求，达到物资配送有序进行、资源合理利用已经成为电力物资智能调配领域的热点研究课题。

2　智能配送的必要性

深圳作为典型的沿海城市，深圳供电局辖区内自然灾害频发，台风、暴雨等极端恶劣天气频繁出现，对电网安全生产与运行带来了巨大的冲击，在此环境和背景下，如何加强电力物资快速调配管理，提高物资调配供应效率，将灾害的损失控制在最低限度范围内，为电网的安全生产和运行保驾护航具有迫切的需求和重大的意义。

随着全球物联网信息化技术的发展以及大数据的快速兴起，结合电网企业对于管理的精细化和规范化的需求，建立针对电力物资的智能配送模型变得尤为重要。

3　现阶段物资配送存在的问题

物资配送是由备货、存储、分拣、配货、配装、配送运输、送达服务、配送加工几大基本要素组合构成，它是一个完成物品时空调动的过程［1］。其中运力能否运用的合理高效化取决于配送规划和整个配送管理信息系统的合理流程设计及与社会运输系统适当合理的衔接。并且运输配送环节是物流管理信息系统中最主要的一个子环节。其中，运输车辆的调度和路线设计是否合理，直接影响整个过程的配送效率、客户服务水平，特别是多用户配送路线的确定和优化是一项非常庞大的系统工程［2］。然而合理适当地选择运输车辆和行驶路径，提升客户需求的反应速度和服务质量，对于增进客户对物流环节的满意度，降低服务商的运作成本起到关键性的作用。

目前深圳供电局配送类型主要分为补仓配送、储备物资配送，其中，储备物资配送又分为紧急配送和一般需求配送。然而物资配送中需求汇总环节依然采用传统的电话预约、调度人员录入的形式进行需求汇总，并安排仓库进行相应的补仓及备货操作。配送路径选择班车调度形式，固定每周两次分别对各点进行物资配送。现阶段深圳供电局电力物资配送模式存在着几个不合理的方面，总结如下：

（1）电话预约物资需求，调度人员录入需求并汇总的方式存在较庞大的手工和信息不对称，极易丧失时效性；

（2）班车配送路径虽然稳定便于管理和责任分配，但存在着缺乏灵活性，容易造成资源浪费的问题。

4　路径寻优方法理论研究

求解路径最优的算法模型很多，车辆路径问题求解过程历经了精确式求解、启发式优化求解以及计算机仿真求解三个过程。鉴于车辆路径问题一直是一个公认的NP问题，而针对规模较大的车辆配送路径问题，其求解异常复杂。一般采用启发式优化算法和智能优化算法求其近似解。

现有的智能优化算法例如遗传算法大都是基于仿生学的角度寻求解的优化，它可以处理任何形式的目标函数和约束条件，无论是线性结构还是非线性结构，连续的还是离散的［3］。它具有强大的搜索特性，相比较精确式算法更容易找到最优解。但其主要是对问题参数的编码组进行计算，而不同的编码方式会对结果的判断产生较大的影响，另外算法对初始种群的选择有一定的依赖性。截至目前为止，还没有完整的适用于电力物资配送的编码设置，以及关于参数设置的成熟准则和方法，需要根据具体问题，依靠经验进行设置。针对目前深圳供电局现状，该智能算法并不具有实用性和普适性。

启发式算法是通过总结归纳过去的经验并进行推演，在实验室分析基础上来解决问题的方法。强调解决问题达到满意，不一味的寻求最优。启发式算法是一种简便、易行的方法，一方面体现于它快速高效地优化了整个运输过程，而精确式算法在求解大规模的车辆路径问题时，得到最优解所需要的时间复杂度和计算复杂度代价太大，然而现实决策出发，寻求较优解往往更具有实用性；另一方面，启发式算法思路简单清晰、便于执行，适合每个层级操作人员理解与应用。

现阶段，启发式算法主要分为三类：（1）构造启发式算法；（2）两阶段启发式算法；（3）改进启发式算法。

5　电力物资配送路径模型思路及系统设计

5.1启发式算法思路

在充分借鉴物资配送现有的智能配送算法的基础上，结合深圳供电局现状，本文主要通过引入交通指数的节约算法规划整体线路与实时路况导航推荐最终行车路线结合的方式，为电力物资配送完成全程行车路线规划，以达到配送过程效率最优，路径最优。

启发式算法要求分析人员必须运用自己的感知和洞察力，从与所研究的问题具有较大关联性又比较基础的模型和算法入手寻找其中的关联性，并从中获得启发，去发现解决该问题的思路与途径［4］。主要有节约法、扫描法等方法。

节约法的算法流程：（1）根据计算得到的节约里程表里节约里程大小依次由大到小排列，编制节约里程顺序表；（2）依次选择节约里程最多的点在满足车辆的载重和容积大小、车辆行驶里程等约束条件前提下组合线路；（3）循环第2步，直至所有客户全部分配完成，渐进绘出配送路径。

5.2交通运输指数

交通指数是对道路网交通总体运行情况进行量化评估的综合性指标，与传统的车速、流量等参数比较而言，具有更直观、简单的特点［5］，类似于体检时量体温，相比抽象派的说明，人们往往更能够理解数字化的概念，所以交通运行指数定义的目的主要是为了让人们在出行时由之前模糊的知道堵或者不堵转变为更加清晰直观的了解到道路现阶段堵到哪一种程度，从而对全市的整体交通，以及特定路段的交通状况有一个更直观量化的了解，为人们出行提供更有益的参考价值。

交通指数在全世界已有应用非常成功的案例，我国在不同城市，如：北京、上海等研究了不同的定义、不同算法的指数，并且其发布后对于市民日常出行以及政府管理部门优化交通取得了良好的效果。

深圳市目前发布的交通指数主要是采取出行时间的概念，经过大量实地考察及询标定参数据和试验分析，建立了拥堵程度不同层次划分标准和指数计算模型。主要是在0-10的范围内取值，划分为5个等级，其中0-2分为畅通，2-4分为基本畅通，4-6分为缓行，6-8分为较拥堵，8-10分则为拥堵。指数越大则说明一次出行相比较顺畅路况（如凌晨时刻）需要多花费的时间更长。

本文主要采用深圳市交通运输委员会官方网站发布的实时交通指数数据进行实证案例研究，数据来源公开且具有极大的公正性。

5.3基于交通运行指数的节约算法的电力物资配送路径寻优可行性分析

电力物资配送有不同其它行业的特点，配送模型大体总结如图1所示。

图1　电力物资配送模型

从物资配送仓库用车辆调配电力物资向多个目的地送货，每个需求点的位置、物资需求量一定，每台车的载重一定，要求合理安排线路，使得运输效率最高，配送路径最优，并满足如下约束前提条件［6］：

（1）对于每一条配送路径，目的地的需求之和不应该超过车辆的载重总量；

（2）电力物资配送过程的每个目的地的路况未知。

本文所用模型的研究思路如下：

第一步，利用节约算法的思路，针对电力物资配送完成整体线路优化。在算法运算过程中引入交通指数对节约法进行改进。

第二步，确定整体最优配送路径之后，结合实时路况导航推送以及大数据预测等方式给出各站点之间最佳行车路线推荐，渐进给出物资配送全程最优路线。

该模型分两阶段进行：

第一阶段，利用节约算法思路获得优化的整体配送路线推荐。由于实验室启发式算法在计算各点之间路线均以实际坐标为准，取直线距离。而实际线路可能存在多曲线甚至多折。并且该类算法是建立在车速一定、各点之间路况条件相同的情况下，路径最优，则效率最优的模型。但现实配送过程中存在多种不可控的因素，如：车祸等突发状况以及其它影响道路实际通行时间的因素，比如配送拥堵（早高峰、晚高峰）、天气导致的原因（暴雨、塌方、泥石流等）、交通方面（车祸、道路施工、临时封路等），去掉这些影响计算路径最优则效率最优对于实际的路径最优，推荐仍然存在不足。

故本模型针对该实验室算法的不足，引入了各点之间主干道路的交通指数，以此来增加算法选择路径的精

确性，具有很大的实用性以及创新性。

即目标优化函数为：

其中：i，j为各点，包括仓库及需求点；cij为第i点至第 j点之间的距离；ωij为第i点至第 j点之间的交通指数；xijk=1，第k辆车由第i点行驶至第 j个点；否则，xijk=0。

第二阶段，针对所取得的整体优化路线运用实时路况导航推送、大数据预测等方式，选取各需求点之间的实际行车线路推荐。由于启发式优化算法仅仅优化了整体路线，但针对各点之间实际行车线路，并未给出相应的路线推荐建议。本配送模型同时结合数据挖掘算法对大量路况历史数据进行大数据分析预测，针对由算法给出的配送线路各点之间实际行车线路推荐，同时根据地图APP（百度）路况导航信息对于各点之间实时路况进行推送，具有极大的完整性、实用性和创新性。

6　案例分析

6.1基础数据采集

本文选取了深圳局7个物资点与一个仓库的实证数据进行模型实证分析，若仓库有3t与16t载重车辆若干，如何合理安排行车路线以达到配送效率最优，路径最优。其中各点最短距离及需求如下（C0表示仓库，Xi表示物资点，Qi表示各物资点需求量）：

表1　各点之间最短距离及需求

路线中涉及到的主干道路的交通指数数据见表2。

表2　交通指数数据表

6.2最优路径计算

根据上述实际距离数据，结合交通指数利用节约法计算出各点之间的节约里程，并依次由大到小排列，编制节约里程顺序表［7］，见表3。

表3　节约里程顺序表

根据节约里程顺序，运用节约算法，结合仓库车辆情况得到较优配送线路如下：

首先选择最节约里程的路段（6—2），然后是（2—1），由于配送线路必须包含仓库，且每条循环路线上的运输重量之和要小于3t或者16t，此时载重达到2.8t，按照资源节约型思路，优先采用载重量小的车辆进行配送，第一回合采用3t车辆配送，具体路线如下：

路线1：仓库0-需求6-需求2-需求1-仓库0

依次方法类推，得到：

路线2：仓库0-需求4-需求5-仓库0

路线3：仓库0-需求3-需求7-仓库0

根据节约算法算得总路程为348km，共节约里程146km。

整体的行车路线图如图2所示。

6.3实时路况分析推荐

针对由节约算法计算获得的整体优化路线，根据百度地图实时路况地图对于各点之间实际行车线路进行分析，利用导航功能最终获得实际行车路线规划如图3所示。

综上利用节约算法及地图导航功能完成了全程最优路线推送。

图2　整体最优路线

图3　各点之间导航路线推荐

7　结语

本文提出一种引入交通指数的节约算法规划整体线路与实时路况导航推荐最终行车路线结合的方式完成电力物资配送最优路线模型。通过创新的引入交通指数，完成了需求点之间不同时段不同拥堵程度带来的效应影响估计，且数据来源于深圳市交通委员会官网，数据来源真实可靠。整个电力物资配送模型由两阶段构成，首先针对改进的节约算法获得整体最优线路，然后针对整体最优线路利用实时路况信息导航、大数据预测的方式完成各点之间实际行车路线推荐。并在此基础上开发了电力物资配送管理信息系统，通过多次应用结果表明，该系统能够较高程度地实现物资配送过程效率最优，路径最短，同时完成配送全程实时监控与记录分析，为电力物资配送的补仓、调度和优化提供了有力的支持，为监管层提供了较合理高效的决策。

［1］王君.不确定因素下物流配送车辆路径规划问题的建模及优化方法［M］.北京：中国财富出版社，2014.

［2］吴斌.物流配送车辆路径问题及其智能优化算法［M］.北京：经济管理出版社，2013.

［3］姜昌华，戴树贵，胡幼华.求解车辆路径问题的混合遗传算法［J］.计算机集成制造系统，2007，13（10）：2 047-2 052.

［4］黄敏镁.具有柔性资源约束的优化调度问题研究［D］.武汉：武汉理工大学，2007.

［5］乐华.如何借助拥堵指数平台提升道路通行效率［J］.道路交通管理，2014，（4）.

［6］苏鑫炜，梁丹钰.基于遗传算法的电力物资配送管理信息系统研究［J］.商，2015，（28）：220-220.

［7］陈远.物流配送车辆优化调度的研究［J］.广西轻工业，2011，（10）：70-71.

［8］刘晓阳.现代物流配送系统的研究与设计［D］.长沙：湖南大学，2013.

［9］谭文安.基于多目标物资调配优化模型的复杂应急系统并行计算方法［J］.系统工程理论与实践，2011，（S2）：31-32.

［10］黄永强.基于改进节约法的应急物资车辆调度问题研究［J］.物流技术，2013，32（17）：309-312.

［11］雷政.电力物资调度指挥信息系统的设计与实现［D］.成都：电子科技大学，2014.

［12］程相巍.智能交通系统中车辆路径优化问题的研究［J］.洛阳理工学院学报（自然科学版），2012，22（4）：51-54.

［13］李义华.基于多智能体的物流配送车辆调度决策方法研究［D］.上海：上海大学，2012.

［14］陈新建.浅析基建生产一体化信息建设的优势［J］.电力信息化，2008，6（3）：43-46.

［15］张红豆.基于蚁群算法的物流系统配送车辆路径优化问题研究［D］.昆明：昆明理工大学，2015.

［16］陈长魁.物流智能配送调度系统的设计与实现［D］.厦门：厦门大学，2013.

［17］Ma Wenjing，Xu Ying zhuo，Xie Hui.The Optimal Path Algorithm for Emergency Rescuefor Drilling Accidents［A］. IEEE International Conference on Network Infrastructureamp; Digital Content［C］.2009.

［18］吕新军.复杂多车辆物流调度问题的研究［D］.上海：上海交通大学，2003.

Optimization of Electric Power Material Distribution Process Using Saving Algorithm with Traffic Index

Zhang Yunxiang
（Shenzhen Electric Power Supply Bureau Co.， Ltd.， Shenzhen 518000， China）

In this paper， according to the empirical data of Shenzhen Power Supply Bureau， we used the saving algorithm with roadtraffic operation index to plan the general routing and at the same time finalized the route selection through a real-time navigation system.Then on such basis， we developed the electric power material distribution management information system and then through empirical dataverification， demonstrated the validity of the model.

traffic index； saving algorithm； electric power material； material distribution； route optimization

F426.61；F252

A

1005-152X（2016）08-0111-05

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

2016-07-11

张云翔（1981-），男，广西桂林人，硕士研究生，中级工程师，研究方向：应用系统建设。