基于改进节约算法的计量表计运送车辆调度

孙 勇，方彦军，肖 勇

SUN Yong1, FANG Yan-jun1, XIAO Yong2

（1.武汉大学 自动化系，武汉 430072；2.广东电网有限责任公司 电力科学研究院，广州 510080）

0 引言

省级电能计量中心的设立改变了原有的计量设备检定模式，新的业务流程下电能计量中心承担向地市级二级库进行设备配送的任务，因此有必要对计量表计运送车辆路径规划进行研究。

计量表计运送车辆的路径规划问题属于VRP问题[1～3]，相关研究较多，一般可分为启发式算法和智能优化算法，启发式算法中的节约算法[4,5]相对简单，便于理解，在具体问题中应用较为广泛[6]。文献[7]讨论了有时间窗约束的非满载车辆的调度问题，文献[8]讨论了目标函数总费用具有区间数特性的改进节约算法，文献[9]提出了允许订货量分割的改进节约算法。

本文结合电能计量中心业务流程特点，根据现有工作模式与时间安排方式，提出基于多目标优化、综合考虑配送回收策略的改进节约算法。该方法能够更好的实现计量车辆路径规划需求，实现路径规划的高效节能，通过相关实例进行对比分析，表明此方法确定的运送方案能够满足相关业务需求，最大限度节约时间、经济成本。

1 问题描述及模型建立

省级电能计量中心服务全省所有地市区二级库，需要根据各地市区业务需求的不同进行运送车辆调配。基于节约资源的原则，部分箱体需要进行回收再利用，因此运送车辆需要综合考虑箱体的回收操作。同时，由于每个阶段的配送方案即配送业务需求是变化的，最优配送路径也随之改变，这就需要根据当次业务需求来制定配送任务和车辆最优运送路径，进而确定回收任务，以此提高整个运送过程的效率。

在车辆实际运作中，影响目标优化的因素较多，需要考虑的情况较复杂，因此为了方便建模，需要对问题进行简化和假定，以便在一定的限制条件内进行运送路径优化问题研究。本文在遵循现有工作模式与时间安排制度的基础上，对计量表计运送车辆路径规划问题进行如下假设：

1）省级电能计量中心只有一个，负责向全省地市二级库进行配送，计量中心和二级库位置固定且两两之间行驶路径指定。

2）计量中心车辆单一，载重限制要求固定，不允许超载；运送车辆按照规划路线从计量中心出发，依次到达所负责的地市库，完成配送与回收任务后进行下一节点运送，最终返回计量中心。运送车辆需在12小时内完成整个运送作业并返回计量中心。

3）各个二级库配送物资可以混装，即可以同时装载于一辆运送车辆；同时某一二级库所需的计量表计允许分装，由不同运送车辆进行配送。

4）运送车辆以配送任务为主，先根据配送需求进行路径选择，再根据已定路径，进行回收方案制定，并保证在整个运送中任意时刻车辆不超载。

5）通过营销业务系统，计量中心可以实时获取各个二级库的相关数据，即表计需求量、待回收表箱数，其中需求量为刚性需求，待回收表箱数为区间数表示。

6）配送的计量表计和回收的周转箱可以混装，同时根据运送车辆的载重载容限制，满装周转箱与空周转箱的占据容积比为1∶1.2，即运送车辆相同空间可以放置更多的空周转箱。

7）路线规划是基于多目标优化，即从单纯考虑空间距离到考虑速度、成本、天气因素等多目标。

根据上述描述和相关假定，以综合优化指标最小为目标，建立以智能计量设备配送为主、兼顾空周转箱回收需求的车辆路径规划模型。

2 求解算法的设计

2.1 基本节约算法

节约算法是路径优化中的一种启发式算法，根据优化目标的不同有具体的表现形式。下面以空间距离为优化目标来说明节约算法的基本思想。设配送中心为M0，N个二级地市级配送库分别为已知任意两个节点之间的距离为则对于任意两个二级地市级配送库，计量中心配送方案可分为单独配送和合并配送两种模式，后者比前者的节约量为：此即为节约算法进行运算的基础。

通过计算任意两个地市区二级库的节约量，可以构造出所有配送点的节约量表，按照节约量从大到小的顺序进行配送路径的确定。先选取节约量最大的两个配送点作为某条配送线路的两个端点，同时检查两个配送点的货运量之和是否超过车辆限制条件；再从节约量表中选择包含这两个配送端点之一的最大节约量，将有关二级库点加入配送路线，计算是否超过限制条件并确定配送端点；依次进行这种操作，直至配送线路载货量超过车辆限制条件，再寻找节约量表中包含两个配送端点之一的较小节约量，看是否不超过限制条件。直到所有可能的连接都连接完成，则得到一条配送路线。

依次循环上述操作，可确定计量中心配送方案。

2.2 改进节约算法

改进节约算法是在节约算法的基础上，进行必要的改进，使之更加适应具体问题和应用实例。相关研究提出了基于货物分割、单位距离载重的选择性满载等思想的改进节约算法，较好的解决了相关实际问题。

本文结合实际运行情况，提出改进的节约算法，首先以综合指标系数作为节约算法的优化目标，而不再是单一的空间距离。综合指标系数根据城市间实际路程公里数、汽车实际行驶速度概率、行驶经济费用、突发事件等情况进行综合得出，最终反映到节点运行时间，节点运行时间是动态调整变化的。以空间距离为优化目标的基本节约算法是假定空间距离为唯一决定车辆运行状况的因素，而实际情况下，相关因素对运行状况影响也较大，如局部地区天气状况、路面维修及突发事故交通受阻状况、运送车性能状态、车辆行驶正常速度与非正常速度概率，这些因素都会影响优化结果，因此改进节约算法对基本节约算法的第一个改进即为引进综合指标系数，系数构成如下式：

式中：S为综合指标系数；

N为天气状况指数；

P为路面维修、突发事故指数；

Q为运送车车体状况指数；

T为速度概率；

a、b、c、d为权重系数。

建立科学可行的综合性能指数模型对于真实反映优化目标，以及优化结果的真实性和可操作性有很大帮助。而综合性能指数最终以节点运行时间作为衡量参考，节点运行时间与简单的用空间距离除以车辆行驶速度有很大区别，综合性能指数是在综合相关因素的基础上得到的节点运行时间，更能真实反映运行中的各种因素，优化结果更具真实性。

改进节约算法在采用综合指标系数为优化目标后，其运算流程如图1所示，可以看出和基本节约算法相似，同样是得出节约量表，依次寻找节约量最大的节点进行线路规划。本文提出的改进节约算法并不对运送车辆满载作进一步要求，主要是考虑回收策略的制定。实际操作过程中，二级库需要回收的空周转箱数并不是一个定数，而是在一定范围内变化，因此采用区间数的表达方式，回收策略的回收量必须在区间数表达的范围内，这样更符合业务需求。

改进节约算法和传统的节约算法在综合指标系数、回收策略制定方面有所不同，整个算法的优化目标为在节约量最大的前提下，尽可能实现回收量的最大化。

3 算例分析

3.1 基本情况

根据第1节对运送车辆路径规划问题做的分析，选取广东中东部地区11个地级城市作为假定算例进行分析。表1列出了省级计量中心（配送中心）、各地市区二级库之间的距离，其中城市序号1代表计量中心。表中数值为指定行驶线路下的空间距离。同时假定计量中心运送车能够载重300个满载计量箱体，则根据第1节假设6，运送车可装360个空箱体。某次运送策略制定前，根据相关业务系统获取各二级库有关信息，并依照运送车载货情况进行归一化处理，则各二级库箱体需求量及回收量如表2所示。

图1 改进节约算法的计算流程图

表1 配送中心与各二级库之间的空间距离

表2 各配送点需求量及回收量

根据改进节约算法对综合指标系数的定义，将二级库之间的空间距离转换为二级库之间的节点运行时间，如表3所示。改进方法的配送方案采用综合指标系数，可以大幅度综合实际运行中可能出现的影响运送的因素。

表3 配送中心与二级库之间的综合指标系数

3.2 配送路线的确定

根据表1和表3中的数据，进行节约算法及改进节约算法的运算，可以得到配送路线如表4、表5所示。两种方法得出的配送方案有所不同，路线1和路线2相同，路线3和4的结果不同。对比路线3和路线4的总耗时和总行驶路程，改进节约算法的结果更加省时，同时总路程也较短。更有利的是以综合指标系数为优化目标的方法得出的配载率也相对均衡，这样为后续回收方案的制定提供了更大的可操作空间。

表4 配送方案-空间距离

表5 配送方案-综合指标系数

3.3 回收方案的确定

根据确定的运送路线和回收需求，可以制定每条配送线路的回收策略。本方法不要求分割订单实现满载，主要是考虑回收任务，其相关空间可以最大限度满足各二级库对空周转箱回收的需求。回收时必须首先满足各二级库回收区间的下限要求，同时尽可能满足优先级较高的二级库的上限需求。

以第1条配送线路为例说明回收方案的制定，如果三个城市没有优先级的区别，只是根据行驶路线上的顺序按照最大的可能性进行操作，则序号9、11、10这三个二级库的回收量依次为0.5、0.4、0.15，即二级库11不能实现最大量的回收，其余两个二级库可以实现最大回收量；如果二级库11优先级高于线路上其他二级库，则回收策略变化为0.4、0.6、0.15，即为保证序号11的二级库的回收需求，在9号二级库时预留空间为11号做准备；如果序号9、11的优先级相同，则回收策略变化为0.45、0.55、0.15，即两者同时受到了影响。一般情况下，优先级的设置是为了保证二级库库存管理的灵活性，结合相关业务系统的优化调度，一般不会存在一条线路上多个高优先级二级库的情况，因此高优先级二级库的需求都能得到满足。

因此，以综合指标系数为优化目标制定的配送方案下，不考虑二级库优先级区分的最终回收方案结果为，除二级库3、11之外，其余二级库均可实现需求量上限的回收，而二级库3、11只能回收需求量中的0.4。整体回收方案基本满足需求。

4 结束语

本文提出的改进节约算法能够根据实际情况进行改善，更加符合配送需求。依照空间距离的方式，并不能直接将相关因素考虑在内，而通过综合指标系数，可以将道路信息进行整合，更加完善的反映相关情况。通过算例分析，得出两者的规划路径不同，对比配载率、时间消耗、总行驶路程等指标，可以看出本文的配送策略更为有效。同时，在更加可靠的配送任务解决后，再进行回收路径规划，完成配送-回收任务，实现业务需求。

[1] 刘家利,马祖军.存在车辆租赁及共享且有时间窗的多配送中心开环V R P[J].系统工程理论与实践,2013,33(3)∶666-675.

[2] Yiyo Kuo. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem[J].Computers & Industrial Engineering, 2010,59(2010)∶157-165.

[3] 谢桂芩,杨玉华,涂井先.带有时间窗的虚拟场站接驳补货车辆路径问题[J].广东工业大学学报,2013,30(1)∶61-67,72.

[4] 张建勇,郭耀煌,李军.一种具有模糊费用系数的VSP的修正C-W节约算法[J].西南交通大学学报,2004,39(3)∶281-284,310.

[5] 付连宁,崔文,曾华.并行节约算法的自适应邻域选择策略[J]. 山东大学学报（工学版）,2012,42(1)∶72-80.

[6] 张学志,陈功玉.车辆路线安排的改进节约算法[J].系统工程,2008,26(11)∶67-70.

[7] 宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的节约算法[J].东北大学学报（自然科学版）,2006,27(1)∶65-68.

[8] 刘诚,顾坤坤.具有区间参数的VRP及其改进的C-W节约算法[J].武汉理工大学学报（信息与管理工程版）,2010,32(2)∶182-185.

[9] 范洁,曹俊琴.改进节约算法在电表配送路线选择中的应用[J].物流工程与管理,2012,34(4)∶102-105.