基于节点换装时间不确定的多任务集装箱运输方案优化

王清斌，董 悦

（大连海事大学 交通运输工程学院，辽宁 大连 116026）

0 引言

为高效率、低成本地完成集装箱多式联运运输任务,集装箱多式联运在制订多任务的运输计划时,需要考虑运达时间限制、运输方式和运输路径的选择等因素,以及在中转站进行运输方式换装过程中的时间因素,这样才能确保多任务集装箱运输方案的合理性。在实际中,由于中转站进行换装作业的场地和设备等资源有限,而需要进行换装作业的集装箱量每天也不确定,使得这些资源被占用的情况无法确定。因此,集装箱多式联运在进行运输方式和运输路径的选择时,难以事先确定到达中转站后的换装时间,给集装箱多式联运的运输组织决策带来了难度。

国内外很多学者在集装箱多式联运方案优化研究方面已经进行了较为广泛和深入的研究。Wang等[1]在研究集装箱多式联运运输方式组合优化问题时考虑了箱型的选择和运输需求量为模糊的情况。Burak等[2]在进行集装箱多式联运运输任务最优路径的选择时,考虑海运服务是按照时间表运行的特点。Jae等[3]提出一种应用标签设置算法和修剪规则的动态规划算法,以解决进出口国际集装箱运输的加权约束最短路径问题。Li等[4]为解决动态的运输需求和动态交通状况,提出了一种滚动时域控制方法来解决深海码头与内陆货运港内陆码头之间的联运集装箱流量分配问题。胡星星等[5]重点考虑运输能力对集装箱运输方式选择的影响。吕学伟等[6]研究在实际运输过程中,混合时间窗对多式联运最优运输方案选择的重要影响。刘维林[7]针对集装箱国际多式联运网络路径的复杂性,通过设计动态蚁群算法提高模型的寻优能力,为多式联运最短路问题提供可靠的优化方法。蒋洋等[8]提出采用交叉熵算法来解决多式联运运输方案选择问题,通过实例验证了算法的有效性。李愈等[9]研究同时考虑固定运输费用和变动运输费用的具有时间窗和能力限制的最短路径问题。黄泽汉等[10]提出一种基于多蚁群并行优化的网络路径规划算法,按照一定的策略对关键网络资源进行调度分配,同时满足多个任务的运输需求。刘杰等[11]考虑实际中铁路、航空以及水运固定出发时间对多式联运运输任务路径选择的影响,并将运输费用细化为固定费用、路段运输费用、中转费用以及等待出发的费用。王伟伟[12]指出集装箱多式联运是铁路货运与现代物流融合发展的重要方向。

目前在集装箱多式联运方面的研究大多都假定在节点进行运输方式换装时间是某一固定值,而未考虑换装时间的变化对运输路线和运输方式选择的影响。在实际作业中,当集装箱在不同运输方式间进行换装时,常常因为等待或受其他不确定因素的影响,其换装时间带有一定的不确定性。另外,很多研究忽略了班轮具有固定出发时刻同时可用的箱位数存在限制等现实情况的影响。基于以上研究,还应综合研究在集装箱多式联运组织多个任务时,换装时间的不确定性、班轮的特性和不同任务优先级策略等因素对运输方案选择的影响。

1 基于节点换装时间不确定的多任务集装箱运输方案优化模型及算法

在集装箱多式联运网络中,将每2个节点间产生的集装箱运输需求看作一个任务,每个任务的产生时间、集装箱运量和运达期限已知,水运运段为按照固定船期表运行的班轮运输,并且每个班期可用箱位数已知,不同运输方式在节点上的换装作业时间不确定,需要以最低的成本在所有任务的规定期限内完成运输。可以看出,该问题是一个带有时间和容量约束的多源多汇最短路问题。基于多任务集装箱运输方案优化问题的特点,建立整数规划模型,采用蚁群并行算法求解。

1.1 模型构建

假设运量不可分割且使用单一箱型；集装箱只在节点处发生运输方式的转换,同时不考虑在节点的等待成本；公路和铁路运输不受运输能力和出发时刻的限制,在水运运段按照船期表运行且每个班次的可用箱位数已知。基于以上假设,多任务集装箱运输方案优化模型构建如下。

式中：V为节点集合；M为集合运输任务；K为运输方式集合,K= {1,2,3},其中1代表公路运输,2代表铁路运输；3代表水路运输；ta,m为任务m的产生时刻,m∈M；tf,m为任务m到终点的最晚允许到达时刻；qm为任务m的集装箱数量为任务m在节点i由运输方式k换装到s的时间,为任务m在节点i由k换装到s的等待时间为在节点i由k换装到s的单箱平均作业时间为运输方式k从节点i到j需要的时间；为运输方式k从节点i到j的单位运输成本；为在节点i由k换装到s的单箱换装成本；Ai,m为任务m到达中间节点i的时刻为从节点i到j的班次的数量为水路运输从节点i到j的第l个班次的出发时刻为节点i到j的第l个班次的可用箱位数为节点i的后向节点为节点i的前向节点；om为任务m的起点；dm为任务m的终点为任务m选择运输路径和方式的决策变量,当任务m从节点i到j选择运输方式k时,当任务m没有从节点i到j选择运输方式k时为任务m在节点i发生运输方式转换的决策变量,当任务m在节点i由运输方式k转换到s时当任务m没有在节点i由运输方式k转换到s时为任务m选择水路运输班次的决策变量,当任务m从节点i到j选择水路运输班次l时,当任务m没有从节点i到j选择水路运输班次l时,

公式 ⑴ 表示所有任务运输成本和换装成本最低；公式 ⑵ 至公式 ⑷ 表示每个任务从起点到终点有一条完整的路径；公式 ⑸ 表示节点最多发生一次中转；公式 ⑹ 表示节点前后运输方式的对应约束,如果在节点由运输方式由k变为s,则i的前向节点到i采用的是运输方式k,i到i的后向节点采用的是运输方式s；公式 ⑺ 表示每个任务在节点的换装时间；公式 ⑻ 表示任务m到节点i的时刻；公式 ⑼ 表示每个任务到达终点的时刻不超过最后期限；公式 ⑽ 表示采用水路运输且发生运输方式转换时可选班次的时间要求；公式 ⑾ 表示采用水路运输且没发生运输方式转换时可选班次的时间要求；公式 ⑿ 表示某班次所运输的所有任务不能超过其可用箱位数；公式 ⒀ 表示任务在某2个节点间选择水路运输时只能选择1个班次。

1.2 蚁群并行算法设计

蚁群并行算法的基本思想是将所有蚂蚁分为k个蚁群,每个蚁群包括m只蚂蚁,在一次迭代中一共有k×m只蚂蚁参与路径搜索。如果2只以上蚂蚁对同一个水路运段的同一个班次的班轮提出使用请求时,采用一定的策略决定该资源的分配方案。蚁群并行算法流程如图1所示。

在图1中按照一定规则选择1只蚂蚁,需要判断蚂蚁的当前节点i是否为目标节点dk,如果不是目的节点,找到该蚂蚁所处当前节点的邻接点,按照状态转移概率pk(i,j)选择下一节点,可以表示为

图1 蚁群并行算法流程图Fig.1 Flow chart of ant colony parallel algorithm

式中：τk(i,j)为节点间的信息素浓度；ηk(i,j)为节点间的预见度；α为残留信息的相对重要程度；β为预见值的相对重要程度。

当蚂蚁选择了水路运输时,更新该班次可用的箱位数。当k×m只蚂蚁都进行路径寻优之后,完成一次迭代,找到总成本最低的各个运输任务的方案,进行全局信息素更新,信息素浓度可表示为

式中：Q为决定信息素浓度的参数；Lbest为蚂蚁走行的最佳路线。

经过n次迭代的最优方案,可以作为模型的最优解。通过蚁群算法可以得到问题的最优解,由于节点换装时间存在随机性,问题的最优解不是集中在惟一一条路径上,因而要通过任务路径集中度和平均可用箱位利用率对问题的最优解进行统计分析。任务路径集中度可以表示为

式中：γ为任务路径集中度,是衡量在多次模拟计算的结果中,各任务走行相同路径的程度；πm为任务m最优路径的条数；LC表示总任务数。平均可用箱位利用率可以表示为

式中：θ为平均可用箱位利用率,衡量在多次模拟计算的结果中班轮可用箱位的利用率的平均值；bs为第s次模拟利用的箱位数；gs为第s次模拟可利用的箱位数。

2 算例分析

2.1 换装时间的确定

在一个包含公路、铁路和水路3种运输方式的网络中,有A,B,C,D,E,F,G7个节点,各个节点间产生的集装箱运输需求的时间、数量和运达期限已知,运输任务在节点换装作业时间不确定。 在集装箱多式联运网络的水运运段为班轮运输,每个班次的可用箱位数已知。水路运段最早班次出发时间为0点,每隔11 h发一班。集装箱多式联运网络如图2所示。

图2 集装箱多式联运网络Fig.2 Multimodal container transport network

在集装箱多式联运网络中,换装时间包括集装箱换装作业时间和作业期间发生的换装等待时间。节点的集装箱换装作业时间取决于进行换装作业的机械效率及操作的集装箱量,单位换装作业时间相对稳定,集装箱换装作业时间=集装箱量×单位平均换装作业时间。研究取各节点的单位平均换装作业时间均为2 min。节点的换装等待时间具有不确定性,通过统计可知各集装箱中转站的换装等待时间大致服从正态分布X～N (μ,σ2),分布如表1所示。

2.2 求解结果及其分析

为比较不同的运输任务特征对求解运输方案的影响,根据运输任务数、运输规模的不同,即根据运输任务数量的多少和运输批量的大小设计9种不同类型的算例。发生多运输任务争夺水路运输有限可用箱位时,分别采用大批量先服务、小批量先服务和先到先服务3种服务策略进行资源分配。为模拟换装时间的不确定性,每个算例在每种服务策略下计算100次,算法中的换装等待时间在每次运行时按照表1随机生成。按照公式⒁计算任务路径集中度,按照公式⒂计算平均可用箱位利用率。各种算例在3种服务策略下运行100次的结果如表2所示。

表1 各集装箱中转站的换装等待时间分布Tab.1 Distribution of waiting time for replacement of container depots

由表2的结果进一步分析3种服务策略对各种类型算例的影响,9个算例在3种服务策略下的特征如表3所示。

表2 各种算例在3种服务策略下运行100次的结果Tab.2 Results of various examples running 100 times under three service strategies

由表2和表3可知,在任务数较少时,小批量先服务的服务策略成本最高,大批量先服务和先到先服务无明显差异。随着任务数的增加,大批量先服务的策略使得班轮利用率逐渐提高,成本优势也越来越明显。当任务数量较少时,任务路径的集中度较高,这是因为任务数量少,相互间基本没有影响；而随着任务数的增加,任务间的影响开始明显,导致任务路径的集中度开始分散。由此可见,集装箱多式联运在多个运输任务对班轮的箱位数产生资源争夺时,采用大批量先服务的策略,可以有效减少运输总成本。另外,影响总成本的主要因素是水路运输的资源,如能争取到更多的可用水路运输资源,则可以为进一步降低运输总成本带来空间。

表3 9个算例在3种服务策略下的特征Tab.3 Features of 9 examples under 3 service strategies

3 结束语

单一的集装箱运输模式已经不能满足当今的货物运输需求,以顾客为中心的、快速、高效、安全、低成本的集装箱多式联运已成为发展趋势。实现集装箱多式联运模式的高效发展已经成为国家经济可持续发展的关键之一,加快推进我国多式联运集装箱运输的发展也成为国家交通运输业的重要发展战略。近年来国家大力促进多式联运的发展,多式联运越来越受到重视,铁水联运、公铁联运等运输方式也因其结合了各种运输方式的优点而受到青睐,在交通运输领域发挥着越来越大的作用。基于节点换装时间不确定的多任务集装箱运输方案优化研究,有助于提高多式联运经营人组织运输的效率,促进多式联运系统高效运转和物流行业的蓬勃发展。