(郑州大学 管理工程学院,郑州 450001)

铁路枢纽是庞大而复杂的系统,是国家交通运输网的重要组成部分。在具有大量客货流发生、消失和中转作业的大城市、大工业区等都可能形成铁路枢纽。铁路枢纽是由若干专用车站和连接这些车站的联络线、迂回线等技术设备所构成的综合体。铁路枢纽的中心任务是合理使用各种技术设备,顺利完成车流交换和客货运输工作。因此,正确组织铁路枢纽工作对保证整个运输工作的均衡性、节奏性,以及加速货车周转、降低运输成本都具有重要的作用。

据我国几大枢纽统计,地方流的发送作业量均占该枢纽所在分局总发送作业量的50%左右,有的甚至更多。小运转货物作业系统担当了地方流的输送任务,同时还在枢纽内各专业车站间起着纽带作用,可以说小运转列车组织的好坏将直接影响到枢纽的畅通无阻。

关于货物运输组织优化调度是一项融合技术与管理的复杂系统工程,相关研究多集中在铁路调车作业优化、货车取送作业优化以及车队综合协调调度等方面。

(1)在铁路调车作业优化研究方面:郭瑞等[1]以所有车辆在站停留时间最短为目标,对单向单推单溜配流模型进行理论分析,构建以每列出发列车获得最大车流数最多为子目标的多阶段配流问题推理算法;王典等[2]考虑到达列车残存、出发列车停运和出发时刻调整等实际情况,以车辆在编组站总停留时间和车辆在前方站总额外中转时间最小为目标,为重载列车组合问题构建改进多目标混合整数线性规划模型;Li等[3]研究了铁路编组站的货物列车列检、解体和集结作业优化,构建基于多调机和列检组的一种排序模型,并利用商业软件对模型进行求解;Shi等[4]构建了一个多层网络流模型来描述铁路编组站的列车到达、解体、集结、编组和出发作业过程,进而构建多级作业过程的混合整数规划模型并给出启发式求解方法;Haahr等[5]研究了调车场调车线分配问题,并给出一个启发式方法解决解体调车和编组调车问题;Stephan等[6]研究了铁路集装箱堆场起重设备调度问题。

(2)在货车取送作业优化研究方面:Jaehn等[7]研究了铁路专用线取送调车优化问题,构建取送调车混合整数规划模型,并设计了具有一个多项式时间求解算法;张文晰等[8]针对路企直通列车组织过程中车流整列到发的取送问题,研究了装卸区呈树枝形布置成组装卸情形的取送方案;郭垂江[9]以铁路车站取送车作业为研究对象,建立树枝形货物作业点取送车作业方案的多目标优化模型,并设计了模拟退火算法对模型进行求解;牟峰等[10]以“先顺序、后批次”为构造取送车作业方案的总体思路,根据取送车作业问题的客观约束条件和实际生产经验,设计了取送车作业问题一般模型解的模块化构造方法;赵娟[11]针对装车地始发直达车流、时效要求较低的零散车流,以车流总的走行车公里最小为目标,以径路唯一性、树形径路及线路能力为约束,建立线性0～1规划模型;Wang等[12]研究了以碳排量最小化为目标的合作绿色取送问题,提出基于合作博弈理论的精确求解策略,完成合作方的薪酬和利润分配方案;Ghilas等[13]提出一种分支定界算法用来求解带时间窗货物取送问题;Haddad等[14]研究了货物分批取送问题,并设计了一个局部搜索启发式算法;Danloup等[15]研究了带转运的货物取送问题,设计了大规模邻域搜索算法和遗传算法对问题进行求解,并对两个求解算法进行比对分析;Wang等[16]研究了基于合作联盟企业共享车队的取送车优化问题,并提出了一种集成改进粒子群优化算法和蚁群优化算法的混合求解算法;Capelle等[17]研究了考虑货物取送作业的选址-路径问题,构建了问题的整数规划模型,提出了一种列生成求解算法;Zhu等[18]研究了带随机需求的货物同步取送问题,提出了新型货物取送策略,该策略允许车辆合作完成货物取送作业,但如果合作失败需要给予惩罚,并与不允许车辆合作取送策略进行了比较,验证了所提出的货物取送策略的优越性。

(3)在车队综合协调调度研究方面:王保华等[19]研究考虑车辆周转的铁路动态货运服务网络设计问题,构建了混合整数规划模型,并给出一种“分支-定价-切割”算法;李冰等[20-22]集中不同类型的随机动态车队调度问题,设计了基于参数诱导的逐段分解求解算法;柳毅等[23]研究了一类带时间窗可回程取货的车辆路径问题,通过将人工鱼群算法的仿生学原理与元胞自动机的邻域模型和状态迁移规则相结合,设计了元胞鱼群算法进行求解。

本文围绕服务铁路枢纽地方货物流,研究一类基于树枝形铁路专用线的小运转货物作业系统协调优化问题(Local Freight Trains Transship System on Branch-Shaped Sidings,LFTTS-BSS)。从小运转列车调配与作业车取送协同优化调度角度,以调机早到等待成本、调机晚到惩罚成本、铁路枢纽专用线调机和货车运营成本最小化为目标,构建问题模型。利用作业紧急度-编组定额-集结时间的送车-取车分步进行策略对小运转列车初始方案进行构造,进而设计伙伴-中心-变异取送车径路更新的异步循环求解策略,最后进行实验验证与数值分析。

1 问题分析与描述

1.1 小运转作业系统分析

树枝形专用线是铁路枢纽内常见的一种铁路联络线布置形式,其特点是小运转列车连挂本地车组到达装卸站并完成取送作业后可直接前往下一装卸站而不必返回编组站。树枝形专用线取送车作业中,各装卸站货车入线时刻不同,但取回编组站内时刻相同。

枢纽内编组站对到达列车解体和出发列车编组,完成“列流转变为车流”和“车流转变为列流”;装卸站对货物进行装车和卸车工作,完成“货流转变为车流”和“车流转变为货流”。根据装卸站取出车流的出发形式,主要分为可随就近列车挂走的车流和明确指定挂运车次的车流两种方式。在编组站,合理安排面向装卸站开行的小运转列车编组辆数和开行批次,从而完成小运转列车调配,实现列流向车流的转变;进而依据编组站小运转列车编排方案,给出合理取送车策略,完成装卸站间货车取送径路安排,实现车流向货流的转变。由此可见,这两个环节为一个整体,实现小运转列车调配-作业车取送一体化调度,就要做到前后作业计划同步化。基于编组站-装卸站的小运转列车调配-作业车取送一体化调度如图1所示。

图1 枢纽内小运转列车调配-作业车取送一体化综合协调

1.2 问题描述及研究条件

本文围绕服务铁路枢纽地方货物流,研究基于树枝形铁路专用线的小运转货物作业系统协调优化问题。该问题中,非直达列车陆续到达编组站,根据各车组到达编组站时分、车组目的装卸站位置、车组作业时间要求以及调机牵引定数等限制,以调机早到等待成本、调机晚到惩罚成本、铁路枢纽专用线调机和货车运营成本最小化为目标,构建问题模型。利用作业编号构造问题的解,将阶段时间段内的全部取送作业视为整体考虑,从而实现小运转列车调配-作业车取送一体化综合协调的目标。

LFTTS-BSS问题研究中考虑如下研究条件:

(1)铁路专用线的拓扑结构已知。

(2)单调机作业,调机最大牵引定数和最大走行时间已知。

(3)树枝形专用线网络中编组站、装卸站间的机车走行时间已知。

(4)非直达货物列车到达编组站的时刻已知。

(5)装卸站待送货车、待取货车已知。

(6)特定作业时间窗要求,即特定作业有固定时间窗限制,调机在规定时间外未将特定作业送达装卸站,会因为特定作业未能及时交货而产生额外成本。

(7)装卸站同步即时取送,即调机将货车送达目的装卸站后,若有装卸完毕的待取货车,则立即取回;若无装卸完毕的待取货车,则直接前往下一目的装卸站。

(8)随同一列车到达编组站,且目的装卸站一致的货车编为同一车组。车组取、送两种作业独立核算。

(9)调机在编组站和装卸站进行人员整备、货车甩挂时间不计。

2 模型构建

2.1 符号约定

为构建模型,引入如下参数与变量:

输入参量

N——铁路枢纽内专用车站集合,记为N={i|i=0,1,…,n},其中:i=0 表示编组站,i≠0表示装卸站;n为铁路枢纽内的装卸站总数

L——陆续到达铁路枢纽的货物列车序号集合,记为L={l|l=1,2,…,A},其中,A为到达的货物列车总数

R——从装卸站取回车组可挂运列车序号集合,即为R={r|r=1,2,…,},其中,为可挂运列车总数

l(i)——随货物列车L到达铁路枢纽且目的装卸站为i的本地作业车组,l∈L,i∈N

Ml(i)——车组l(i)的货车编组数,l∈L,i∈N

Ol(i)——本地作业车组l(i)在目的装卸站i处完成装卸作业所需时间,l∈L,i∈N

Z——作业性质集合,记为Z={z|z=1,2},其中:z=1表示送车作业;z=2表示取车作业

U——取送作业编号集合,记为U={u=l(i)z|i∈N,l∈L,z∈Z},其中:l(i)1表示将车组l(i)送往装卸站i的送车作业;l(i)2表示将车组l(i)由装卸站i取回编组站的取车作业

[ETu,LTu]——作业编号u允许的作业时间窗。ETu和LTu分别为作业编号u到达装卸站的最早作业时刻和最晚作业时刻,u∈U

T(r)——第r车次列车出发编组最晚时刻,r∈R

tij——从装卸站i到装卸站j的走行时间,其中i或j=0表示编组站到装卸站的走行时间,i,j∈N

e1——时间窗外单位分钟调机早到等待成本e2——时间窗外单位分钟调机晚到惩罚成本

cl——调机单位分钟运营成本

cw——货车单位分钟运营成本

D——调机最大牵引定数

P——调机的最大行驶时间

状态变量

K——调机取送批次集合,记为K={k|k=1,2,…,},其中,为小运转列车取送批次总数

Tu——作业编号u在目的装卸站的取送时刻,u∈U

sik——第k批次作业中,调机访问装卸站i时的累计行驶时间,k∈K,i∈N

yijk——第k批次作业中,调机途径装卸站(i,j)时所牵引的货车总编组数,k∈K,i,j∈N

决策变量

xijk——第k批次作业中,调机是否由装卸站i驶向装卸站j,如果调机途径装卸站(i,j),则xijk=1;否则,xijk=0,k∈K,i,j∈N

2.2 模型构建

考虑各车组到达编组站时分、车组目的装卸站位置、车组作业时间要求以及调机牵引定数等限制,以调机早到等待成本、调机晚到惩罚成本、铁路枢纽专用线调机和货车运营成本最小化为目标,构建如下问题模型:

式(2)～(11)为约束条件。其中:式(2)、(3)表示同一批次取送车作业中每个装卸站最多被访问1次,从而减少调机不必要走行时间;式(4)～(7)保证了调机在每个取送批次中的行驶时间不超过调机最大走行时间,即单批次取送过程中调机从编组站出发至回到编组站的总时间不大于调机最大走行时间;式(8)明确指定挂运r车次列车的车组l(i)取回编组站时刻小于第r车次出发列车编组最晚时刻;式(9)表示调机最大牵引定数限制,即调机每次牵引的最大货车数要小于调机最大牵引定数;式(10)、(11)表示各变量的取值约束。

3 求解策略

该模型为混合整数规划模型(Mixed Integer Programming Model,MIP),直接求解较为困难,故设计H H-GAP&AIP(Hybrid Heuristic Combining Greedy Assignment Procedure and Asynchronous Iteration Procedure)求解策略。该策略首先给出基于作业紧急度-编组定额-集结时间的小运转列车初始取送方案贪婪生成过程,进而提出三阶段异步循环启发式,利用伙伴-中心-变异取送车径路三阶段更新过程,完成装卸站间货物作业车取送径路方案优化。最后,利用所设计的终止规则完成循环迭代,得到作业车取送径路方案。

3.1 基于GAP的小运转列车初始方案生成

首先提出优先安排紧急和特殊车组,进而利用大车组优先原则安排一般车组,再基于编组定额与集结时间判别参数进行小运转列车批次调整,按照送车-取车分步进行,形成基于作业紧急度-编组定额-集结时间的小运转列车初始取送策略。基于贪婪指派的小运转列车初始取送方案生成过程(Greedy Assignment Procedure,GAP)如图2所示。

图2 基于GAP的小运转列车初始方案生成流程图

具体步骤:

阶段1初始本地车组作业编号的构造。

步骤1.1生成初始本地车组序列。统计到达编组站的列车数,根据列车到解时间先后顺序,将各列车中的本地车组编号,生成初始本地车组序列,记为={1(i1),…,A(im)},其中,m为本地车组数,im∈N。

步骤1.2生成初始本地车组作业编号。根据各本地车组在装卸站完成的作业类型,得到本地车组作业编号,记为={1(i1)1,1(i1)2,…,A(im)1,A(im)2},其中:A(im)1为本地车组A(im)的送车作业编号;A(im)2为本地车组A(im)的取车作业编号。

阶段2小运转列车开行批次构造。

步骤2.1设置小运转列车开行批次。设O为已编入特定批次小运转列车的作业编号,Ok为已编入第k批次小运转列车的作业编号。

步骤2.2参数初始化设置。初始已编入小运转列车的作业编号O为空集,初始小运转列车的批次编号k=1。

阶段3送车作业编号的小运转列车批次选取。

步骤3.1紧急和特殊送车作业安排。将紧急和特殊送车要求作业编号编入当前批次小运转列车Ok。

步骤3.2一般送车作业安排。对于没有紧急和特殊要求的作业,按大车组优先原则,依次编入小运转列车Ok,直至满足调机约束限制。

步骤3.3小运转列车是否继续集结的编组数判别参数Φ。将未编入任何批次小运转列车的送车作业编号依次编入集合Ok,若未满足调机约束限制,引入编组数判别参数Φ,若D-Ok＜Φ,则生成第k批次小运转列车送车作业;否则,转步骤3.4。

步骤3.4小运转列车是否继续集结的时间判别参数I。若距下次列车到解时间大于时间判别参数I,则生成第k批次小运转列车送车作业;否则,等待下次列车,重复步骤3.1～3.4至生成第k批次小运转列车送车作业。

阶段4取车作业编号的小运转列车批次选取。

步骤4.1紧急和特殊取车作业安排。将紧急和特殊取车要求作业编号编入当前批次小运转列车Ok。

步骤4.2一般取车作业安排。对于没有紧急和特殊要求的作业,按大车组优先原则,依次编入小运转列车Ok,直至满足调机约束限制。

阶段5小运转列车批次生成。

步骤5.1小运转列车单批次生成。第k批次送车作业、第k批次取车作业即为第k批次取送车作业。

步骤5.2生成所有取送车批次。令k=k+1,重复阶段3～5,生成所有取送车批次,即生成单个取送车径路。

阶段6初始取送车径路集合H生成。

步骤6.1重复上述步骤,产生w个初始取送车径路。

步骤6.2对重复取送车径路进行基于作业编号的调整,从而生成初始取送车径路集合H。令H=[h1,h2,…,hw]T,其中:hw为一个取送车径路的解;w为取送车径路集合H中所涵盖的初始取送车径路集合数量。

3.2 基于AIP的取送车集合更新过程

基于迭代寻优思路,设计异步循环迭代过程(Asynchronous Iteration Procedure,AIP)。该方法首先利用GAP策略生成的初始取送车方案进入循环迭代过程。在每次迭代中,执行基于伙伴取送车径路的解更新、基于中心取送车径路的解更新和基于变异取送车径路的解更新,为避免算法陷入局部最优及扩大解的搜索空间,给出基于检测-剔除-变换的取送车径路调整策略,从而完成迭代寻优。最后,利用所设计的终止规则完成循环迭代,得到作业车取送径路方案。AIP过程如图3所示。

图3 AIP算法流程

具体步骤:

阶段1基于作业编号的取送车方案表述。

对于GAP 策略生成的初始取送车径路集合H=[h1,h2,…,hw]T,为便于迭代更新,利用取送车作业编号构造问题的解,令每一个取送车径路为hw,则

其中:ψ(h(x))为所有取送车作业集合的排列组合,即为一个取送车径路的解;S为取送作业编号集合数。每个取送车径路hw在寻优过程中生成的取送车径路需要进行批次划分,从而计算目标函数值。当调机服务下一个作业编号h(x)时,根据调机最大牵引定数及最大走行时间等约束限制,从而完成批次划分。

该表述方式将一个时段内的全部取送作业视为整体考虑,进而根据调机牵引定数和最大行驶时间等合理安排面向装卸站的小运转列车开行批次和装卸站间货车取送径路顺序,从而实现小运转列车调配-作业车取送一体化综合协调的目标。

阶段2基于伙伴取送车径路集合的表述。

对于取送车径路集合H中取送车径路hi和hj,统计hi和hj之间对应位置相同作业编号的数量v(hi,hj),设定视野值V,对于取送车径路hi,若v(hi,hj)＜V,则称取送车径路hj为取送车径路hi的伙伴取送车径路,记做,如图4所示。

图4 伙伴取送车径路的生成过程

从取送车径路集合H中寻找取送车径路hi的所有伙伴取送车径路,从而形成伙伴取送车径路集合Hi,集合H中的取送车径路数为n(H),集合Hi中的伙伴取送车径路数为n(Hi)。

阶段3基于单次循环的三阶段异步更新过程。

步骤3.1基于伙伴取送车径路的解更新过程。

(1)最小伙伴取送车径路确定。从取送车径路集合H中选择一个取送车径路hℓ,生成伙伴取送车径路集合Hℓ,计算集合Hℓ中所有伙伴取送车径路的目标函数值,并寻找目标函数值最小的伙伴取送车径路,即。

(2)基于最小伙伴取送车径路的解更新过程。给出最大拥挤度负荷λ,利用取送车径路的伙伴取送车径路集合数除以取送车径路集合数n(H),计算最小伙伴取送车径路的拥挤度因子,记为。如果＜λ,且＜f(hℓ),则令替换hℓ,即;否则,保持当前取送车径路不变。

步骤3.2基于中心取送车径路的解更新过程。

(1)中心取送车径路确定。从取送车径路集合H中选择一个取送车径路hℓ,生成伙伴取送车径路集合Hℓ,对Hℓ中的每个伙伴取送车径路进行比较。将Hℓ中对应位置的作业编号出现次数最多的值作为中心取送车径路该位置的值,如果该位置的值在同一批次内已经出现过,则取对应作业编号出现次多的值作为该位置的值,如图5所示。

图5 中心取送车径路的生成过程

(2)基于中心取送车径路的解更新过程。给出最大拥挤度负荷λ,计算当前取送车径路hℓ目标函数值f(hℓ)和中心取送车径路目标函数值。利用中心取送车径路的伙伴取送车径路集合数除以取送车径路集合数n(H),计算的拥挤度因子,记为。如果＜λ,且,则令替换hℓ,即;否则,保持当前取送车径路不变。

步骤3.3基于变异取送车径路的解更新过程。

(1)变异取送车径路的确定。从取送车径路集合H中选择一个取送车径路hℓ,生成随机数rand,其中1＜rand≤V,随机选择rand个作业编号,将rand个作业编号进行基于次序的替换,从而生成一个新的变异取送车径路,如图6所示。

(2)基于变异取送车径路的解更新过程。计算当前取送车径路hℓ目标函数值f(hℓ)和变异取送车径路目标函数值,并对其进行比较:

情况1若变异取送车径路目标函数值小于当前取送车径路目标函数值f(hℓ),即＜f(hℓ),则令替换,即;否则,转下步。

图6 变异取送车径路的生成过程

情况2若变异取送车径路目标函数值大于当前取送车径路hℓ目标函数值f(hℓ),则重新生成变异取送车径路,并比较其目标函数值。若尝试次数超过最大尝试次数Rmax仍未找到满足要求的变异取送车径路,则保持当前取送车径路不变。

阶段4基于三阶段异步更新的取送车径路选取。

计算第q次迭代得到的取送车径路集合Hq=中各条取送车径路的目标函数值,并记录q次迭代最优取送车径路,即

从而得到q+1次迭代取送车径路可行集合Hq+1=,同时记录q+1次更新后的最优取送车径路,即

依次执行上述过程,直至迭代次数达到Q为止。从最优取送车径路序列中选取目标函数值最小的取送车径路,即为取送车作业的最优取送车径路。

阶段5基于检测-剔除-变换的取送车径路调整。

步骤5.1最优取送车径路检测调整。

为防止陷入局部最优,设置检测因子α,每进行u次迭代检测当前最优取送车径路的目标函数值与u代以前的最优目标函数值,并比较大小,若,表明算法陷入局部最优。为跳出循环,重新生成取送车径路集合。若,则当前取送车径路集合保持不变。

步骤5.2较差取送车径路的剔除调整。

为加快算法迭代收敛,设置加速次数m,对于每进行Q/m次迭代的取送车径路集合,给出剔除因子β,将wβ个目标函数值较大的取送车径路剔除,即剔除较差的取送车径路,从而减少取送车径路集合数,以提高算法运行能力。

步骤5.3重复取送车径路变换调整。

为扩大解的搜索空间,对于每次迭代的取送车径路集合,筛选找出相同的取送车径路,设计3点换位原则,将重复取送车径路更新为相似取送车径路,具体过程如图7所示。

图7 重复取送车径路变换调整

3.3 基于HH-GAP&AIP求解策略的复杂性分析

由上述算法描述可以看出,HH-GAP&AIP求解策略本质上是利用最小伙伴取送车径路、中心取送车径路以及变异取送车径路进行迭代更新,探索当前阶段的最优解,从而利用局部最优解找到全局最优解,H H-GAP&AIP在解的编码上有了一定改进,将阶段时间内取送车作业编号视为一个整体,增加了解的全局信息,从而保证了解更新的多样性。同时,还可以看出,参数视野值V、拥挤度负荷λ以及尝试次数Rmax作为主要循环体参数,对算法收敛速度和精度有着重要影响,特别是参数视野值V的设置,决定了伙伴取送车径路集合的数量,从而在很大程度上决定了算法的复杂性。HH-GAP&AIP求解策略的计算复杂性除了受主循环体参数的影响之外,取送车径路集合的数量也决定了算法的复杂性和收敛速度,取送车径路集合数较多,在一定程度上增加了算法的计算时间,同时也增加了伙伴取送车集合的储存空间,剔除较差取送车径路能够降低算法复杂性,提高算法运行速度。检测和变换策略在一定程度上增加了解变换的多样性,从而能够更好地找到全局最优解。

4 实验验证及结果分析

4.1 实验场景

设计由12个装卸站组成的树枝形小运转作业网络(见图8)。树枝形专用线网络中各装卸站及编组站间的调机走行时间数据如表1 所示,其中0表示编组站。本地作业车取送信息数据如表2所示,出发列车最晚编组时分如表3所示。

图8 枢纽地方货物流小运转作业网络示意图

表1 装卸站间调机走行时间表 min

4.2 HH-GAP&AIP主要循环体参数调试

算法利用Matlab R2014a 对H H-GAP&AIP求解策略进行编程,在Intel(R)Core(TM)i5-3337U CPU(1.80 GHz)微机上运行。鉴于铁路实际作业环境和以往参考文献,将已知参数进行如下设置:调机单位分钟运营成本cl=16,货车单位分钟运营成本cw=16,单位分钟等待成本e1=2,单位分钟惩罚成本e2=2。调机最大行驶时间为300 min,调机牵引定数D=40,编组数判别参数Φ=8辆,时间判别参数I=30 min,最大迭代次数Q=100。

对于取送车径路集合的取送车径路调整阶段所涉及的参数,做出如下处理:取u=Q/10,检测因子α=10,表明目标函数在更新,算法就继续迭代寻优;加速次数m=5,剔除因子β=0.2,从而降低算法计算复杂度,提高算法运行速度。

考虑到参数视野值V、拥挤度负荷λ以及尝试次数Rmax作为HH-GAP&AIP 求解策略的主要循环体参数,故对参数不同取值进行多次实验,分析参数对解质量的影响。采用固定其他参数,观察某一参数对解分布情况的影响。设置3组实验,即视野值参数测试实验、最大尝试次数参数测试实验和拥挤度负荷参数测试实验,对于3组实验各测试参数取值均运行10次取其平均值,从而更准确地进行测试对比。

表2 枢纽内本地作业车取送信息表

表3 出发列车最晚编组时分

(1)视野值参数测试实验。在初始取送车径路集合数w=30,w=10下,固定拥挤度负荷λ=0.6,最大尝试次数Rmax=3,观察视野值V对调运成本和计算机运行时间的变化关系,具体结果如图9所示。

图9 视野值参数调试

由图9可见,当初始取送车径路集合数分别为w=30和w=10时,视野值V对于调运成本的影响规律都不明显,但总体而言,两者在较小视野值求得的解优于较大视野值求得的解;随着视野值V不断增加,CPU 运行时间也越来越长。当初始取送车径路集合数为30时,求得解的质量较好;当初始取送车径路集合数为10时,求得解的质量较差。当初始取送车径路集合数增加为30时,CPU 运行时间明显提高,说明提高初始取送车径路集合数虽提高了解的质量,但也消耗了一定的CPU 运行时间。

(2)最大尝试次数参数测试实验。在初始取送车径路集合数w=30,w=10下,固定视野值V=5,拥挤度负荷λ=0.6,观察最大尝试次数Rmax对调运成本和计算机运行时间的变化关系,具体结果如图10所示。

图10 最大尝试次数参数调试

由图10可见,当初始取送车径路集合数分别为w=30和w=10时,最大尝试次数Rmax对于调运成本和CPU 运行时间的影响呈现出一定的规律性,即随着Rmax的不断增加,求得解的质量越来越好,但CPU 运行时间也随之增加,说明增加最大尝试次数Rmax虽能提高解的质量,但也消耗了一定的CPU 运行时间。同样,当初始取送车径路集合数为30时,求得解的质量较好;当初始取送车径路集合数为10时,求得解的质量较差。当初始取送车径路集合数增加为30时,CPU 运行时间明显提高。

(3)拥挤度负荷参数测试实验。在初始取送车径路集合数w=30,w=10下,固定视野值V=5,最大尝试次数Rmax=3,观察拥挤度负荷λ对调运成本和计算机运行时间的变化关系,具体结果如图11所示。

由图11可见,当初始取送车径路集合数分别为w=30和w=10时,拥挤度负荷λ对于调运成本和CPU 运行时间的影响没有呈现出一定的规律性,说明在此实验条件下,拥挤度负荷λ对解的影响具有随机性。当初始取送车径路集合数为30时,求得解的质量较好;当初始取送车径路集合数为10时,求得解的质量较差。当初始取送车径路集合数增加为30时,CPU 运行时间明显提高。

4.3 过程验证

图11 拥挤度负荷参数调试

根据循环体参数调试,在合理运行时间范围内为实现目标函数值最优化,对H H-GAP&AIP算法参数设置如下:拥挤度负荷λ=0.8,取送车径路视野V=4,最大尝试次数Rmax=10,HH-GAP&AIP算法初始取送车径路集合数w=30,迭代次数Q=100代。在解决优化排序问题上,遗传算法和模拟退火算法能够很好地解决此类问题,参考文献[21,24],引入参数自适应遗传算法(IGA)和模拟退火算法(SA)作为对比,IGA 算法初始种群规模与H HGAP&AIP求解算法保持一致,交叉概率为[0.5,0.99],变异概率为[0.1,0.5]。SA 算法所涉及的参数多次尝试取较优结果设置如下:初始温度控制参数为1 000,温度停止控制参数为0.01,温度衰减因子为0.99,初始马尔科夫链长度为500。为公平比较算法,设置IGA 和SA 算法的停止时间与H HGAP&AIP求解算法迭代到100 代的运行时间相同,算法运行结果如表4所示。

由上述算例仿真对比结果可以看出,H HGAP&AIP求解算法调机被划分为8个批次,最优路径为0-4-6-5-0-12-8-7-0-10-1-0-3-9-1-0-2-11-10-0-12-8-5-4-0-3-2-11-0-9-6-7-0,调机总花费时间为988 min(包含调机早到等待时间),总调运成本为19 249.6元;用IGA 求解算法调机被划分为9个批次,最优路径为0-5-4-11-12-0-6-5-8-0-9-0-1-10-0-3-2-1-0-7-8-4-0-2-6-7-0-10-9-0-3-12-11-0,调机总花费时间为1 132 min(包含调机早到等待时间),总调运成本为24 469.2元;用SA 求解算法调机被划分为9个批次,最优路径为0-11-5-12-4-0-6-7-0-10-9-2-0-8-1-3-0-6-7-5-0-1-12-9-0-4-2-11-0-3-10-0-8-0,调机总花费时间为1 241 min(包含调机早到等待时间),总调运成本为24 719.6 元。可以看出,HHGAP&AIP求解算法比IGA、SA 求解算法得到更好质量的解。

图12给出了H H-GAP&AIP、IGA 和SA 算法的迭代次数与目标函数值的演进关系,限定3种算法迭代次数为100代。由图12可见,IGA 和SA 求解算法收敛较早,容易陷入局部最优,HHGAP&AIP求解算法收敛较晚,迭代后期能够扩大搜索范围,得到更好质量的解。

4.4 实验测试对比与性能评估

为对算法进行性能测试与评估,将本地作业车取送信息根据经验数据进行适当增减,设定不同规模作业数量,分别利用HH-GAP&AIP、IGA 和SA算法进行求解,从而更全方位地进行算法对比。引入调运成本偏差比RAT(C1)和RAT(C2)对实验结果进行比对分析,RAT(C1) 表示 H HGAP&AIP目标函数值相对于IGA 算法的改进率,RAT(C2)表示H H-GAP&AIP目标函数值相对于SA 算法的改进率,令HH-GAP&AIPC、IGAC和SAC分别表示HH-GAP&AIP、IGA 和SA 算法求得的模型目标函数值,即调运成本,则:

对于HH-GAP&AIP、IGA 和SA 算法所涉及的参数与上阶段保持一致,H H-GAP&AIP算法迭代次数为100代,设置IGA 和SA 算法的停止时间与HH-GAP&AIP 求解算法迭代到100 代的运行时间相同,具体求解信息如表5所示。

由表5可见,对于不同作业数量规模问题,3种算法都能在合理的时间内得到较好的解,其中,H H-GAP&AIP求解结果较好,SA 算法求解较差。图13给出了作业数量规模与调运成本偏差比关系,由图13 可见,随着作业数量规模的增加,RAT(C1)和RAT(C2)呈现逐渐扩大趋势,说明随着作业数量规模的不断增加,H H-GAP&AIP 算法相对于IGA 和SA 算法优势更加明显。

表4 计算时间限定条件下HH-GAP&AIP、IGA和SA算法计算结果

图12 HH-GAP&AIP、IGA 和SA 算法调运成本随迭代次数收敛曲线图

表5 HH-GAP&AIP、IGA和SA算法不同作业规模下求解质量对比

图13 作业数量规模与调运成本偏差比关系

5 结语

本文研究了一类基于树枝形专用线网络的小运转货物作业系统优化问题。首先剖析了铁路枢纽小运转货物作业机理,进而根据各车组到达编组站时分、车组目的装卸站位置、车组取送作业时间要求以及调机牵引定数等限制,以调机早到等待成本、调机晚到惩罚成本、铁路枢纽专用线调机和货车运营成本最小化为目标,构建问题模型。鉴于模型复杂,直接求解较为困难,故设计HH-GAP&AIP 求解策略,该方法首先基于作业紧急度-编组定额-集结时间的送车-取车分步进行策略对小运转列车初始取送方案进行贪婪过程构造,进而设计异步循环启发式完成解的迭代寻优,同时,为避免算法陷入局部最优及扩大解的搜索空间,给出检测-剔除-变换的取送车径路调整策略。最后,设计实验场景,对本文所提出的方法进行过程验证,并设计不同规模问题,对算法进行测试对比及性能评估。