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