货物作业车取送模型及算法研究
发布时间：2019-08-20 12:47:15
摘要：合理确定取送车作业顺序，有利于减少货车在站非生产停留时间，加速车辆周转，通过对取送车作业过程的分析，将其归纳为一个典型的旅行商问题，并建立了相应的数学模型，提出了求解最优调车作业过程的启发式节约算法，并结合实例进行了验算。此方法对优化车站各项技术作业过程有较好的实用价值。
货车在货物装卸作业站的停留时间，约占货车周转时间的1／3左右，压缩货车在站停留时间对加速车辆周转有重要意义。
货物作业车在站停留时间，是由技术作业时间、取送作业时间、装卸作业时间和待取送时间组成。在技术作业时间和取送、装卸等生产性时间一定的情况下，通过选择合理的取送车顺序，改进调车作业方法，可以实现压缩作业车待取、待送等非生产性时间，达到压缩货物作业车停时的目的。
以车站1台调车机车担当取送作业，探讨送车顺序的方法，以达到尽量压缩货物作业车停留时间的目的。至于取车顺序的确定，其方法是类似的。
传统的马密多夫取送车法在装卸作业点数量较少的情况下，能较好地压缩货物作业车非生产性停留时间，但装卸作业点较多时，其有效性会大大降低。为此建立铁路车站送车顺序模型，并给出一种更为有效的算法。
1 模型的建立
假设车站仅有1台调机提供取送车服务，调机1次向各专用线的各个装卸作业点送车，并且规定经过各作业点仅一次，最后调机返回车站。现在要解决的问题是如何安排调车线路，使调机总的走行时间最少。
为方便构造数学模型，将车站编号为0，需要送车的作业点编号为1，2，…，n。于是把问题构造成网络图，以g=[v，a，c]表示，其中：
v={0，1，…，n}——表示调机要经过的作业点，其中点0为源点；
a={(i，j)|i，j=o，1，…，n，i≠j}——表示调机可能走过的线路段集合；
c={cij(i，j)∈a}——cij表示调机经过对应弧段(i，j)所花的时间，包括调机在(i，j)纯走行时分及在i，j作业点进行摘挂、对货位等作业所花费时间。
因此，问题变为一个旅行商问题(tsp)，即在赋权无向图g中找到调机总走行时间最少的哈密尔顿(hamilton)回路。
设以下变量：
2 算法
从上述模型可以看出，这是一个典型的tsp问题。tsp问题属于np难题，目前无法求其精确解，只能求得近似解。以下采用启发式节约算法确定初始解，然后用线路改进法对初始解进行改进，求得最优解。
2．1 启发式节约算法步骤
(1)把赋权图g中各点单独与源点0相连，并计算节约值s(i，j)=ci0 c0j-cij，并排列成表格形式；
(2)在表格中选择最大元素s(i，j)，若有2个及以上元素都为最大，任取其中1个即可。考察对应的点i和j，检查是否满足下列条件：
①若点i和点j均不在已构成的线路上，则可连接点i和点j，得到线路段0→i→j→0，转步骤(3)；
②若点域点j在已构成的线路上，但连接后不是线路的内点(即不与源点0直接相连)，则可以连接，得到线路段0…→i→j→0或0→0i→j→…0，转步骤(3)；
③若点i口点j位于已构成的不同线路上，且连接后均不是内点，则可以连接，并得到线路段0→…i→j→…→0，转步骤(3)；
④若点i和点j在已构成的同一条线路上，则不能进行连接，转步骤(3)。
(3)若点i和点j相连接，则划去第i行和第j列，即i点不能到其他点，j点也不能由其他点到达；否则，只划去s(i，j)；
(4)若所有元素均被划去，则已找到——哈密尔顿回路，即得到了完整调车线路，算法结束；否则，转步骤(2)。
2．2 线路改进算法步骤
(1)在已求得哈密尔顿回路上任选定不含源点0的两弧(i，i 1)、(j，j 1)，然后用(i，j)、(i 1，j 1)代替之，交换后线路中的路径i 1→…→j被反向；
(2)若交换后哈密尔顿回路长度缩短，即：cij ci 1，j 1 (3)重复步骤(1)，直到不能再对线路进行改进时，得到一条最优哈密尔顿回路，算法终止。
3 算例
铁路某车站(编号0)连接专用线8条(分别编号1，2，…，8)，如图1所示。该站仅有一台调机担当取送作业，现有一批重车组(其车辆数量不超过调机所能附挂最大车辆数)要送往各专用线进行卸车作业，已知调车机车在站线与各作业点之间的走行时分cij如表1所示。要求确定一条最优调车线路，使一次送车作业过程中调机走行总时间最少。
根据表1中数据，构造以点0、1、…、8为顶点，cij为权的无向图，采用启发式节约算法，寻找一条最优哈密尔顿回路。
首先，计算节约值s(i，j)，例如，s(1，2)=c10 c02-c12=45 40-16=69，并把计算得到的所有节约值填入表2中。
然后，选择表2中最大元素s(1，2)=69，点1和点2可以连接，得到线路段0—1—2—0，划去表中第1行和第2列所有元素，再从表2中未被划去的元素中选择最大元素s(2，1)，由于点2和点1位于已构成的同一条线路上，故不连接，并划去s(2，1)。依此类推，经多次重复过程后，表2中所有元素都被划去，得到一条较优哈密尔顿回路：0→4→1→2→3→5→6→7→8→0，此时整个调车线路上调机花费总时间：30 31 16 19 38 18 27 21 25=225min。
再利用线路改进法对上述初始解进行优化。在初始解中，用(3，6)、(5，7)替换(3，5)、(6，7)，交换后线路中的路径5→6被反向为6→5，并发现c36 c57 此时调机花费总时间：
30 31 16 19 29 18 30 21 25=219 min。
到此为止，不能再对线路进行改进，所得调车线路0→4→1→2→3→6→5→7→8→0为最优。
4 结论
(1)采用优化取送作业方法，能较好地压缩调机一次取车或送车作业过程中的走行时间，从而减少货物作业车待送、待取等非生产性停留时间。
(2)调机往返于各货物作业点之间，所附挂车组数量和重量均会发生变化，对调机走行速度有一定影9向，要求司机严格掌握好行车速度，以保证在标准作业时间范围内完成取送车任务。
(3)对于取送作业连续进行的情况，即送车任务完成后，调机不返回车站，待装卸作业完毕后，再依次到各个作业点取回车辆，如何确定最优调车作业路线，有待于进一步研究。
参考文献：
[1]田毅．改进调车作业方法压缩货物作业车停时[j]．铁道运输与经济，2000，(4)：17-18．
[2]papadimitriou，c．h．，steiglitz k．conbinatorial optimization： algorithms and complexity．u．s．a．：prentice-hall，inc．
作者：中南大学交通运输学院 余少鹤 李夏苗 来源：《铁道运输与经济》2002年第12期
货车在货物装卸作业站的停留时间，约占货车周转时间的1／3左右，压缩货车在站停留时间对加速车辆周转有重要意义。
货物作业车在站停留时间，是由技术作业时间、取送作业时间、装卸作业时间和待取送时间组成。在技术作业时间和取送、装卸等生产性时间一定的情况下，通过选择合理的取送车顺序，改进调车作业方法，可以实现压缩作业车待取、待送等非生产性时间，达到压缩货物作业车停时的目的。
以车站1台调车机车担当取送作业，探讨送车顺序的方法，以达到尽量压缩货物作业车停留时间的目的。至于取车顺序的确定，其方法是类似的。
传统的马密多夫取送车法在装卸作业点数量较少的情况下，能较好地压缩货物作业车非生产性停留时间，但装卸作业点较多时，其有效性会大大降低。为此建立铁路车站送车顺序模型，并给出一种更为有效的算法。
1 模型的建立
假设车站仅有1台调机提供取送车服务，调机1次向各专用线的各个装卸作业点送车，并且规定经过各作业点仅一次，最后调机返回车站。现在要解决的问题是如何安排调车线路，使调机总的走行时间最少。
为方便构造数学模型，将车站编号为0，需要送车的作业点编号为1，2，…，n。于是把问题构造成网络图，以g=[v，a，c]表示，其中：
v={0，1，…，n}——表示调机要经过的作业点，其中点0为源点；
a={(i，j)|i，j=o，1，…，n，i≠j}——表示调机可能走过的线路段集合；
c={cij(i，j)∈a}——cij表示调机经过对应弧段(i，j)所花的时间，包括调机在(i，j)纯走行时分及在i，j作业点进行摘挂、对货位等作业所花费时间。
因此，问题变为一个旅行商问题(tsp)，即在赋权无向图g中找到调机总走行时间最少的哈密尔顿(hamilton)回路。
设以下变量：
2 算法
从上述模型可以看出，这是一个典型的tsp问题。tsp问题属于np难题，目前无法求其精确解，只能求得近似解。以下采用启发式节约算法确定初始解，然后用线路改进法对初始解进行改进，求得最优解。
2．1 启发式节约算法步骤
(1)把赋权图g中各点单独与源点0相连，并计算节约值s(i，j)=ci0 c0j-cij，并排列成表格形式；
(2)在表格中选择最大元素s(i，j)，若有2个及以上元素都为最大，任取其中1个即可。考察对应的点i和j，检查是否满足下列条件：
①若点i和点j均不在已构成的线路上，则可连接点i和点j，得到线路段0→i→j→0，转步骤(3)；
②若点域点j在已构成的线路上，但连接后不是线路的内点(即不与源点0直接相连)，则可以连接，得到线路段0…→i→j→0或0→0i→j→…0，转步骤(3)；
③若点i口点j位于已构成的不同线路上，且连接后均不是内点，则可以连接，并得到线路段0→…i→j→…→0，转步骤(3)；
④若点i和点j在已构成的同一条线路上，则不能进行连接，转步骤(3)。
(3)若点i和点j相连接，则划去第i行和第j列，即i点不能到其他点，j点也不能由其他点到达；否则，只划去s(i，j)；
(4)若所有元素均被划去，则已找到——哈密尔顿回路，即得到了完整调车线路，算法结束；否则，转步骤(2)。
2．2 线路改进算法步骤
(1)在已求得哈密尔顿回路上任选定不含源点0的两弧(i，i 1)、(j，j 1)，然后用(i，j)、(i 1，j 1)代替之，交换后线路中的路径i 1→…→j被反向；
(2)若交换后哈密尔顿回路长度缩短，即：cij ci 1，j 1
3 算例
铁路某车站(编号0)连接专用线8条(分别编号1，2，…，8)，如图1所示。该站仅有一台调机担当取送作业，现有一批重车组(其车辆数量不超过调机所能附挂最大车辆数)要送往各专用线进行卸车作业，已知调车机车在站线与各作业点之间的走行时分cij如表1所示。要求确定一条最优调车线路，使一次送车作业过程中调机走行总时间最少。
根据表1中数据，构造以点0、1、…、8为顶点，cij为权的无向图，采用启发式节约算法，寻找一条最优哈密尔顿回路。
首先，计算节约值s(i，j)，例如，s(1，2)=c10 c02-c12=45 40-16=69，并把计算得到的所有节约值填入表2中。
然后，选择表2中最大元素s(1，2)=69，点1和点2可以连接，得到线路段0—1—2—0，划去表中第1行和第2列所有元素，再从表2中未被划去的元素中选择最大元素s(2，1)，由于点2和点1位于已构成的同一条线路上，故不连接，并划去s(2，1)。依此类推，经多次重复过程后，表2中所有元素都被划去，得到一条较优哈密尔顿回路：0→4→1→2→3→5→6→7→8→0，此时整个调车线路上调机花费总时间：30 31 16 19 38 18 27 21 25=225min。
再利用线路改进法对上述初始解进行优化。在初始解中，用(3，6)、(5，7)替换(3，5)、(6，7)，交换后线路中的路径5→6被反向为6→5，并发现c36 c57
30 31 16 19 29 18 30 21 25=219 min。
到此为止，不能再对线路进行改进，所得调车线路0→4→1→2→3→6→5→7→8→0为最优。
4 结论
(1)采用优化取送作业方法，能较好地压缩调机一次取车或送车作业过程中的走行时间，从而减少货物作业车待送、待取等非生产性停留时间。
(2)调机往返于各货物作业点之间，所附挂车组数量和重量均会发生变化，对调机走行速度有一定影9向，要求司机严格掌握好行车速度，以保证在标准作业时间范围内完成取送车任务。
(3)对于取送作业连续进行的情况，即送车任务完成后，调机不返回车站，待装卸作业完毕后，再依次到各个作业点取回车辆，如何确定最优调车作业路线，有待于进一步研究。
参考文献：
[1]田毅．改进调车作业方法压缩货物作业车停时[j]．铁道运输与经济，2000，(4)：17-18．
[2]papadimitriou，c．h．，steiglitz k．conbinatorial optimization： algorithms and complexity．u．s．a．：prentice-hall，inc．
作者：中南大学交通运输学院 余少鹤 李夏苗 来源：《铁道运输与经济》2002年第12期
最新资讯
-
08-24 0
-
12-29 1
-
08-26 1
-
08-28 0
-
08-28 1
-
08-26 0