关于树枝形专用线取送车问题的探讨.docx

关于树枝形专用线取送车问题的探讨 (兰州交通大学 交通运输学院，甘肃 兰州 730070) 摘 要：为了科学合理地安排取送车作业，文章通过对 搜索操作和参数的合理设置，提出了求解该问题近似最优 解的模拟退火算法，利用计算机模拟证明了该算的有效性。 关键词：树枝形；取送车问题；模拟退火算法；智能 算法 中图分类号：U292.29 文献标识码：A 文章编号： 10076921(XX)06028802 取送车工作是较大的货运站和货物作业较多的技术站 的一项重要工作，它的效率高低直接关系到车辆周转和货 物送达的快慢及运输生产指标的完成。科学合理地安排取 送调车作业是车站调度指挥人员需要用心思考的问题之一。 专用线按其布置形式的不同通常分为放射形和树枝形 两大类。 按车流的性质不同，取送车问题有直达车流与非直达 车流之分。前者在组织装车地直达和空直达列车时经常遇 到，后者则是技术站和枢纽内货运站的常见类型。 无论是放射形专用线还是树枝形专用线，取送车问题 的核心内容是寻求最佳的取送顺序，而排序问题的难度颇 大，至今仍研究得不够充分。本论文主要对树枝形专用线 非直达车流连送带取这种情况进行讨论。 1 问题的表述 1.1 设定条件 所谓连送带取的作业方式就是：机车顶送一批车往各 专用线送车，与此同时将各线待取车辆取回站内。设定条 件如下：一台调车机车作业。每专用线至少有两条股 道，以便于连送带取时的调车作业。各专用线待送、待 取车数已定。车站至最近的分歧道岔、各专用线至最近 的分歧道岔及各道岔间的距离和走行时间已知。确定去专 用线的走行时间以货位中心线为准，且送车时间包含对货 位时间，取车时包含收集车辆时间在内。为简化计算，假 定往返走行时间相等。按现场标准化作业要求，入线前 各道岔处于定位状态，出线后道岔必须恢复定位。为了分 析问题的方便起见，将树枝形式专用线画成一棵树，称为 专用线树，如图 1 所示。 注：图中顶点的度数是指与该顶点关联的边数。 740)this.width=740“ border=undefined 图中，数根0 代表车站，树叶16 代表专用线， 分支点711 代表道岔。“-”表示送辆车， “+”表示取辆车，各段距离及走行时间均已标于图上。 1.2 优化目标 在取送车作业过程中，人们总是希望尽量缩短取送总 时间，即机车离开车站往各线送车取车后能尽快返回，特 别是一台机车既负责取送又承担其他任务时更是如此。在 满足上述要求的前提下，人们还希望机车能量消耗小，即 总的车公里数尽量少。由以上分析，可以产生两个优化目 标：使机车取送总时间 F1 最小。机车取送总时间是指自 机车从车站出发时经由各专用线至返回车站时止的总时间。 在 minF1 的基础上，使总的走行车辆公里数 F2 最小。 2 问题的求解 称图 1 中各段走行时间为各对应树枝的权，记作 tij(i,j=0,1，n-1,ij)。由设定条件、，可以算出 树根与树叶间，树叶与树叶间的“路程”各段树枝的 权和加上必要的扳道时间 t 扳，且有 tijtji，若令 t 板 1min，则 t05=t07+t78+t85+2t 板27(min) t50=t58+t87+t70+2t 板27(min) 于是，优化目标可以叙述如下： 已知顶点0，1，n-1 间的路程，欲寻一条 从0 出发，遍历1，2，n-1 各点一次，最后回 到 V0 的回路，使得总的路程最短。 根据上述求法，可得路程矩阵为： 740)this.width=740“ border=undefined 优化目标追求的是总的车公里数最小，这时就不仅与 送车数有关，而且与取车树有关。 假定刚开始机车不带任何车辆，送车视为减少车公里 数，取车视为增加车公里数。即把树枝的权定为距离，树 叶的权定义为待取车数减去待送车数所得的差。这样处理 后，可得车公里数消耗矩阵为： 740)this.width=740“ border=undefined 3 模拟退火算法 设计混合智能算法来求解上面的模型，具体地说是设 计模拟退火算法来搜寻模型的近似最优解。 模拟退火算法的基本思想来源于固体的退火算法，在 搜索策略上引入了适当的随机因素和物理系统退火过程的 自然机理，使得在迭代过程中出现可以接受使目标函数值 变“好”的试探点，也可以以一定的概率接受使目标函数 值变“差”的试探点。接受概率随温度的下降逐渐减小。 这样避免了搜索过程陷入局部最优解，有利于提高求得全 局最优解的可靠性。 用模拟退火算法求解不同的优化问题需要融入不同的 设计思想，下面将具体介绍树枝形专用线取送车问题中如 何应用和设计模拟退火算法。 31 解的形式和领域的结构 本文中假定问题的初始解为 01234560。即采用 n 条 专用线的一个排序表示问题的一个解。很直观可通过交换 任意两个专用线的取送车顺序来构造领域。这种领域表示 的主要特征是：每个领域所含的状态个树相同邻居； 每个邻居都是可行解；解空间中的任何两个状态可达。 由时齐算法的理论，只要接受概率满足一定的条件，一定 以概率 1 收敛到全局最优解。 32 温度参数的控制 本文采用时齐模拟退火算法，因此温度参数的控制包 括 3 部分内容：初始温度的选取；温度下降方法； 每一温度的迭代长度规则。 模拟退火算法的初始温度应选得足够高，才能不使算 法很快就落入局部最优值的陷阱很难跳出；但又不能选得 太高，以减少冗余的迭代。因此本文采取如下方法确定初 始温度 t0 为 t0=K0，K 是一个充分大的数，可以选取 K=10，20，100等试验值。 考虑本文中的实际情况，记对应的效益矩阵为(tij) nn 。 740)this.width=740“ border=undefined 33 算法终止条件 同时使用两个条件共同控制算法的停止： 零度法：给定一个较小的正数 ，如果当迭代温度 tk 时，表示已达到最低温度，算法就可以停止了。 基于不改进规则的控制法：如果当前最优解在连续 Q 步降温期间均不改变，则认为收敛，就停止运算。 以上两个终止条件，只要满足其中至少一个，该模拟 退火算法就可以终止了。 34 模拟退火算法的计算步骤 由上述决策，本文提出的一类指派问题的模拟退火算 法步骤归纳如下：指定初始可行解为 an =0，1，n-1，0，确定初始温度 t0，计算目标函数值 f1 的值，并令其为 now1，令最优解 best1=now1；并计算目 标函数 f2 的值，并令其为当前解 now, best=now；由当 前解 now1 通过迭代策略产生 f1 新解，令 k=k+1；若 k=s，转步骤；否则，转步骤；若 exp(FxFx) /tkrandom(0,1)或者 now1best1，则令 best1=now1， 并计算 now 的值，如果 nowbest，best=now；否则，不变。 返回步骤；若当前最优解已经在连续 Q 步降温期间均 不改变，则算法停止；否则，转步骤；温度进行降低 tk+1=tk；若 tk，则算法停止；否则，返回步骤 。其中 random(0,1)表示一个随即产生的(01)之间的实 数。 4 算例结果 一般来说，在实际工作中，F1、F2 的值是不用计算出 来的，只需确定取送车顺序即可。对于此问题，经过在计 算机上求解，得到如下表所示的结果。 740)this.width=740“ border=undefined 也就是满足优化目标和的取送顺序为： 04321650 5 结语 在分析树枝形专用线非直达车流取送车作业特点的基 础上，本文提出确定最佳取送顺序的智能算法模拟退 火算法。模拟退火算法适用于同一批取送的车组具有同等 优先权的情况。如果它们有轻重缓急之别，则应本着急用 先送，急用先取的原则安排计划，在挑选车组时，把需优 先入线的车组排在前面，对其余车组，仍应根据模拟退火 算法选优排序。在本文设定条件中曾假定每专用线至少有 两股道，便于送车取车一次完成。但实际上，有的专用线 只有一股道。这时，为了不延误入线时间，通常仍采用送 取结合的方式一次完成，即利用走行线或另一专用线进行 调车作业倒顺序，这使得该专用线多往返一次。因此，在 计算 时，对只有一股道的专用线，若该