树枝形

§3专用线取送车问题一、取送车概述二、树枝形专用线非直达车流取送车问题三、放射形专用线非直达车流取送车问题一、取送车概述（一）含义送车——将待卸重车（空车）由车站调车场（或到发线）送往货场、专用线等卸车地点卸车（装车地点装车）；取车——将装完重车（卸后空车）由装车地点（卸车地点）取回站内调车场集结（或到发线）。横列式区段站示意图货场调车场（二）取送车作业组成因素送车——挑选车组、去程走行、对货位、回程走行。取车——去程走行、收集车辆、回程走行、分解车组。送取结合（连送带取）——挑选车组、去程走行、对货位、收集车辆、回程走行、分解车组。作业类型（方式）：单送、单取、单机调移、连送带取、送兼调移、取兼调移、送调取结合。（三）取送车问题的分类1、按专用线布置形式分——放射形（也称“扇形”）专用线，树枝形专用线。2、按车流性质分——直达车流，非直达车流（零星车流）。3、按研究目的分——确定合理取送时机，确定合理取送次数，确定合理取送顺序。4、按车流到发方式分整列到，整列发整列到，非整列发非整列到，整列发非整列到，非整列发（四）树枝形与放射形的区别1、形状上的区别2、作业方式上的区别放射形树枝形区别1向一专用线送（取）完一批车组后必须返回车站才能再去另一线送（取）车在一批作业中间不必返回车站区别2各线车辆入线时刻不同，取回站内时刻也不同各线车辆入线时刻不同，但取回站内时刻是相同的1、设定条件（1）一台调车机车作业,连送带取；（2）每专用线至少有两条股道（见下图）；（3）各专用线待送、待取车数已定；（4）各段距离和走行时间已知。（一）问题的表述2、优化目标（1）使机车取送总时间最小；（2）在最小的基础上，使所有专用线总的入线车小时消耗最小。（3）在最小的基础上，使总的走行车辆公里数最小。1F1F1F2F3F二、树枝形专用线非直达车流取送车问题3、求合理的取送顺序，使目标实现。4、专用线树104.552.062.541.5123.092.0154.0102.582.071.5V0V1V2V3V4V5V6V7V8V9V10V1132412615578352.0图中顶点和边的意义：树根——车站；树枝——走行线；树叶——专用线；分枝点——道岔；共用枝——连接两个分枝点的边；-号代表送车，+号代表取车。1F（二）使取最小值的方法1、特殊的货郎担问题（1）目标1的另一表述——已知各顶点间的路程，欲寻一条从出发，遍历各点一次，最后回到的回路，使得总的路程最短。0v0v（2）特殊性——使所有共用枝都只往返经历一次的回路即为最优解，与最优解对应的取送顺序便是使取最小值的最佳方案。1F2、几个名词前进——机车顶车（或单机）向远离车站的方向运行。退行——机车牵引车辆（或单机）从专用线退出，向车站方向运行。访问树叶——机车在某专用线送车，或取车，或连送带取的调车作业。孪生兄弟——从同一分枝点分出去的两片树叶称为一对孪生兄弟。由于道岔为普通单开道岔，孪生兄弟必然成对出现。邻点——某分枝点的邻点就是与它相邻的分枝点。按照是前进还是退行，邻点又分为前方邻点和后方邻点。3、三条原则孪生兄弟优先原则——机车在访问了某片树叶之后，接着应访问它的孪生兄弟，如果有的话。前进方向优先原则——当机车处于某一分枝点，该点前后均有未被访问的树叶时，应先访问前进方向的树叶。退行邻点优先原则——机车在退行过程中，如果某分枝点的后方邻点和后方非邻点均衔接有未被访问的树叶，那么应优先访问邻点衔接的树叶。遵循上述三条原则，即可保证每条共用枝均只往返经历一次，使取最小值。1F练习：若规定首先送V4专用线，应如何排列顺序？（三）使取最小值的方法——比值法2F1、三个定义1、树叶的权——各专用线待送车数；2、树枝的权——各段走行时间；3、树枝的份量和的前进方向各树枝的权的权和的前进方向各树叶的权jijijiijvvvvvvW2、一个定理当机车处于分枝点需要前进时，优先沿着份量较大的树枝前进总是有利的。这里的“有利”，指的是入线车小时总消耗最小。（简单举例验证）3、比值法选优步骤（1）画出专用线树，计算各树枝的份量。（2）自树根开始前进，遇分枝点总是偏向份量较大的树枝，如此可到达一片树叶访问。（3）若该树叶有孪生兄弟，则紧接着访问它，之后转4，否则直接转4。（4）退行至最近的分枝点。（5）检查该点是否是树根。若是，算法结束；若不是，转6。（6）检查该分枝点前方是否有未被访问的树叶。若有，则前进，遇分枝点总是偏向份量较大的树枝，直至到达某片树叶访问，之后转3；若无，转4。专用线树如下图所示，各树枝的份量计算结果列于下表。4、例1104.552.062.541.5123.092.0154.0102.582.071.5V0V1V2V3V4V5V6V7V8V9V10V1132412615578352.00.420.780.480.400.390.430.250.100.360.13最优解树枝分枝点ijW7v8v9v10v11v87vv97vv58vv68vv19vv109vv410vv1110vv211vv311vv按照选优步骤，得出满足优化目标（1）和（2）的取送顺序为：05643210vvvvvvvv3F（四）使取最小值的方法优化目标（3）追求的是总的车公里数最小，这时就不仅与送车数有关，而且与取车数有关。把树枝的权定义为距离，树叶的权定义为待送车数减去待取车数所得的差。这样处理之后，比值法选优步骤仍是适用的。例2专用线树仍如图2.2所示，求满足优化目标（1）和（3）的取送方案。此时，各树枝的份量需重新计算，结果列于下表。1.331.00.921.00.77-3.33-0.5-1.20.3-0.62最优解树枝分枝点ijW7v8v9v10v11v87vv97vv58vv68vv19vv109vv410vv1110vv211vv311vv按照选优步骤，得出满足优化目标（1）和（3）的取送顺序为：05612340vvvvvvvv结语（1）比值法简单易懂，计算工作量不大，便于实际应用。（2）比值法适用于同一批取送的车组具有同等优先权的情况。如果它们有轻重缓急之别，则应本着急用先送，急用先取的原则安排计划，在挑车组时，把需优先入线的车组排在前面，对其余车组，仍应按比值法选优排序。（3）关于优化目标一般在单送时考虑目标1和2，单取时考虑目标1和3，连送带取时主要考虑目标1和2，但当专用线长大，且对装卸时间要求不高时应突出第3个优化目标。（4）若专用线只有一股道，计算时，若该线既有送车，又有取车，则对应树枝的权应当增加一倍。练习题1、专用线树如下图所示，每专用线均有两股道。(1)树枝上数字为走行时间，括弧内数字为送车数。试为单送作业安排最佳顺序。(2)树枝上数字为各段距离，括弧内数字为取车数。试为单取作业安排最佳顺序。从计算结果可得出什么结论？V0V1V2V3V412658437V5V6V7(20)(10)(12)(5)2、专用线树见下图，各段距离（单位：km）和各线货物作业车数均标于图上。试用比值法确定满足优化目标（1）和（3）的最佳取送方案，设所有专用线均至少有两股道。53272441221331v0v2v3v4v5v6v7v8v9v10v11v12v13v1570082239643153272441221331v0v2v3v4v5v6v7v8v9v10v11v12v13v15700822396431103122514340v1v2v3v4v5v6v7v8v9v）（8）（2）（7）（7）（4货场调车场区段站平面示意图