基于Matlab融合回溯算法在光电缆配盘中的应用

王彦博



基于Matlab融合回溯算法在光电缆配盘中的应用

王彦博

结合南宁市轨道交通一号线信号系统光电缆配盘情况，介绍了通过Matlab模块化编程进行配盘算法优化。结果表明采取回溯算法进行深度优化搜索，可减少接头，节约成本，提高运营稳定性，降低维护难度，且通过Matlab进行模块化编程解决该一维装箱问题，操作性和移植性强、时间短、易优化。

光电缆配盘；Matlab；回溯算法

0 引言

在城市轨道交通工程中，光电缆敷设作为其主要工程内容之一，良好的配盘既可以提升光电缆敷设效率，又可以削减光电缆接头数量，节约成本，提高运营稳定性，降低维护难度，在项目管控中具有重要意义。

基于城市轨道交通建设中各站、各处采用光电缆的长度和型号不同，厂家生产的光电缆每盘长度有上限阈值，光电缆配盘作为一种一维装箱问题在工程实施中具有重要的研究价值。国内外对于一维装箱问题以及算法做了大量的研究，文献[1]探讨并研究了贪心算法的思想及实现过程，通过实例分析了贪心算法的具体应用，指出了贪心算法的特点及存在问题；文献[2]就如何给出材料利用率最高的切割方案提出了优化算法；文献[3]提出了一种近似算法来解决一维装箱问题；文献[4]通过研究搜索树的平均节点数，分析了回溯算法求解随机模型的平均复杂性；文献[5]基于回溯算法建立了飞机离场排序问题的数学模型，证明了回溯算法解决该类问题的高效性；文献[6]在回溯算法中引入了拟人策略和遗传算法，建立了排课系统的数学模型。

传统光电缆配盘方法即为简单的贪心算法，该算法没有从整体最优加以考虑，仅从局部最优加以求解[1]，即只考虑满足即将配盘的这一根电缆的条件，不考虑整体情况以及对后续剩余电缆的影响，从而增加了整个光电缆工程的接头量，产生了额外成本，以及带来其他维护问题。本文利用回溯算法，对南宁市轨道交通一号线信号系统光电缆数据进行了配盘，减少了光电缆接头量，且采用Matlab进行模块化编程，移植性和操作性强，方便快捷，为城市轨道交通光电缆配盘提供了一种新方法。

1 数学模型建立与分析

在运筹学领域有一类所谓最优化问题，即一维装箱问题，其一般形式是：在满足约束条件的前提下，给出自变量值，使目标函数值最优（通常是使得目标函数值最小或最大），学者们已经证明该经典组合优化问题是一个NP难度问题[7]，意味着不存在时间复杂度为多项式的完整算法，完整算法对于优化问题就意味着是可保证找到最优解的算法，而对于判定问题就是可保证正确判定的算法。

以南宁市轨道交通一号线信号系统电缆为例，可以分为信号电缆（DWZR-PTYA23）、计轴电缆（DWZR-PJYL23）、信标电缆（ET-2PI795）以及电力电缆（WDZC-YJY23），部分类型电缆还要区分不同芯数。结合厂家生产能力，设有根长度不均的光电缆，记为1、2、3...n；假如1光电缆大于预定的阈值而产生的差值记为1，依次类推分别记为2、3...n；每根光电缆的接头量记为1、2、3...n；为所有光电缆接头量总和，列出如下模型（以电缆阈值为例）。

min

s.t. 2000＜i+j＜2300 （1）

i= 1 (0＜j＜2300) （2）

i= 2 (j＞2300) （3）

＞0；＞0

式（1）中的受限条件即为任意根光电缆进行组合配盘，不能超过厂家生产能力阈值，若一根光电缆超过预定的阈值，剩余的差值继续与其他光电缆进行组合配盘；式（2）、式（3）是根据差值计算出的接头量；总函数即为求所有光电缆组合接头量最小。在现场施工中，配盘时如果考虑了地铁施工左右线的影响因素，将明显提升光电缆敷设的效率，所以该受限条件不加入模型中，在Matlab中由程序进行筛选与处理。

2 回溯算法的设计

本文选取回溯算法进行配盘。回溯算法实际上是一个类似枚举的搜索尝试过程[9]，在搜索尝试过程中寻找问题的解，当发现已不满足求解条件或原先选择并非最优解时，就回溯返回尝试其他路径（满足回溯条件的某个状态的点称为回溯点）[10]，按照选优条件依次搜索，以达到目标。结合南宁市轨道交通一号线实际情况，靠近站台中心的设备光电缆用量较小（几百米不等），而远离站台中心以及位于区间的设备光电缆用量较大，所以在搜寻节点和约束条件设立的过程中应避免类似于贪心策略的选择而导致的浪费。回溯算法流程如图1所示。

图1 回溯算法流程图

3 Matlab模块化配盘

3.1 数据处理

Matlab是一套功能强大的工程计算软件，被广泛应用于自动控制、机械设计、流体力学和数理统计等工程领域，可高效求解复杂的工程问题，并可对系统进行动态仿真，在此选取Matlab解决该一维装箱问题。在初始数据中有7个关键字段，分别为规格型号、芯数、定测长度、起点、终点、作用、设备里标。在前文中提到，配盘时考虑左右线的影响将明显提升光电缆敷设效率，首先将设备里标划分出左线、右线，再按照型号、芯数、长度依次排列存入矩阵。由于部分光电缆长度已经超过了厂家预定的阈值，对该部分光电缆进行拆分处理并加以标记，超过阈值的部分作为新的光电缆存入矩阵（除长度以外的其他字段信息与原光电缆一致），以东段南湖联锁区信号电缆为例生成143×8的矩阵，见图2。

图2 南湖站信号电缆数据处理示意图

3.2 回溯算法配盘

在包含所有问题解的解空间树中，按照深度优先搜索策略，从根节点出发深度搜索解空间树，当探索到某一节点时，要先判断该节点是否包含问题的解，如果包含，则从该节点继续探索下去，如果不包含，则逐层向其祖先节点回溯，分为3步：（1）确定解空间；（2）确定节点的扩展搜索规则；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索，提高程序运行速度。

上述数据处理分别生成3个联锁区对应的5个矩阵（信号电缆、计轴电缆、信标电缆、电力电缆、光缆），按照芯数、长度由高到低排序后，由于长度远低于阈值的光电缆配盘灵活性较高，相反长度位于阈值附近的光电缆灵活性较低，所以在配盘时，优先组合处理灵活性低的光电缆。在某节点有多种可行解时记录下该节点，并顺着第一种路径继续配盘，组合所有候选对象后，剩下的未被选择的对象强行配盘，计算接头数量，之后再回溯到该节点，计算该点其余旁支结果，对比选取最小接头数的解，保证所有的可行旁支都被搜索后才结束，依此类推得到最终配盘结果，以东段南湖联锁区信号电缆为例生成40×10的矩阵，见图3。

图3 南湖站信号电缆配盘结果示意图

3.3 比较分析

在新的教学标准背景下，新修订的高中英语课程标准增加了对英语词汇和词汇难度的需求。面对现状下的英语教学标准，对比旧的英语教学方式，应在教学方式上作出改变才能满足政策标准，让英语词汇记忆教学的有效性有所提高。如何使学生高效、优质地记忆英语词汇已成为英语教学的首要任务。

南宁市轨道交通一号线石埠、西乡塘、广西大学、新民路、南湖、百花岭、火车东站7个联锁区光电缆原配盘接续共325处，经回溯算法进行深度搜索优化后，共产生接续256处。对比分析结果如表1。在关键节点上回溯算法和贪心策略所做出的组合配盘不同，由于回溯算法考虑到每个对象的后效性，回溯过程相当于一个自动纠错的过程，而贪心算法的贪心策略只考虑了当下局部的最优解，从而导致最后接头数量有较大差异。

表1 对比分析结果表

4 结语

结合南宁市轨道交通一号线信号系统正线施工情况，通过数学模型的建立、回溯算法的选取、Matlab模块化处理对7个联锁区的光电缆进行了配盘，得出如下结论：

（1）通过对配盘算法的改进，特别是利用回溯算法，避免了以往贪心算法导致的只能解出局部最优解的情况，合理组合优化了南宁市轨道交通一号线正线光电缆，共减少接头69处，节约成本 82 264.82元，为项目成本管控提供了技术支持。

（2）配盘方法的改进，减少了光电缆的接头量，提高了施工效率，增强了运行的稳定性，降低了维护的难度和工作量，为施工、运营、维护各方面带来了一定的经济效益和工作效益。

（3）利用Matlab对城市轨道交通光电缆配盘一维装箱问题进行模块化编程处理，与人工手动配盘相比，避免了人工失误，操作性强，时间短，可复制，准确性高，适用于各地城市轨道交通工程。

[1] 肖衡. 浅析贪心算法[J]. 办公自动化：综合版，2009（18）：25-26.

[2] 曹晶，郑巍，许旻鸿. 有约束的一维装箱问题的新型算法设计[J]. 计算机应用与软件，2008，25（5）：234-236.

[3] Coffman E J, Garey M, Johnson D. Approximation algorithms for bin-packing[J]. Algorithm Design for Computer System Design, 1984.

[4] 许可，李未. 随机约束满足问题的回溯算法分析[J]. 软件学报，2000，11（11）：1467-1471.

[5] 李楠，刘来永，徐肖豪. 融合回溯算法在离场航班排序问题中的应用[J]. 计算机仿真，2012，（6）：88-92.

[6] 车明，秦存秀，刘凯. 基于改进回溯算法的计算机排课系统[J]. 沈阳工业大学学报，2006，28（6）：667-670.

[7] 孙春玲，陈智斌，李建平. 装箱问题的一种新的近似算法[J]. 云南大学学报：自然科学版，2004，26（5）：392-396.

[8] 应莉. 0-1背包问题及其算法分析[J]. 计算机与现代化，2009，（6）：24-26.

[9] 王岩冰，郑明春，刘弘. 回溯算法的形式模型[J]. 计算机研究与发展，2001，38（9）：1066-1079.

[10] 赵群英. 回溯算法及其改进型的分析与比较[J]. 电脑知识与技术，2011，7（8）：5436-5438.

With connection of situations for allocation of optical cable drums for signal system of line 1 of Nanning Urban Mass Transit, the paper introduces the allocation and optimization of cable drums by means of Matlab modularized programming. The results show that profound optimization and searching conducted by application of back-fitting algorithm may cut the number of joints, improve the operation stability and lower the difficulty of maintenance; and one dimensional packing problem may be solved by Matlab modularized programming, which is easy for operation, transplanting and optimization.

Allocation of drums of optical cables; Matlab; back-fitting algorithm

U231.7

B

1007-936X(2017)03-0028-03

2016-08-27

王彦博.中铁电气化局集团有限公司电气化公司，助理工程师，电话：18817598843。