1、1考虑多作业路径的集装箱甩挂运输调度优化摘 要：在甩挂运输轴辐式网络中建立了考虑多作业路径的甩挂运输牵引车调度优化模型，并设计了基于启发式规则的模拟退火算法对模型进行求解。通过采用算例分析与实际调度规则进行比较，优化结果使执行任务所需时间减少了 19.37%，从而验证了模型与算法对于求解甩挂运输牵引车调度优化问题的有效性与实用性。 关键词：作业路径；甩挂运输；模拟退火算法 中图分类号：TB 文献标识码：A doi：10.19311/ki.1672-3198.2016.15.097 1 引言 甩挂运输利用并行工作的原理大大缩短了牵引车等待货物装卸及其在物流中心排队的时间，提高了牵引车的作业效率。
2、 国外关于甩挂作业调度的研究起步较早。Caris et al 提出了基于插入法的两阶段启发式算法，对具有时间窗约束的集装箱甩挂运输作业调度问题进行求解。Lin et al 应用模拟退火算法来求解甩挂作业调度问题，所获得的基准问题求解结果优于运用禁忌搜索的求解结果。Lin et al 构建了放松车辆数量约束的甩挂作业调度数学模型，以从更大的邻域内搜索是否存在可进一步减少运送距离的可行解，并设计了模拟退火算法对其进行求解。Derigs et al 对于具有时间窗约束的甩挂作业调度问题，2提出了由局部搜索、大规模邻域搜索和标准的泛启发式控制策略相结合的混合算法进行求解。相比国外众多研究成果，国内关于
3、甩挂运输调度优化方面的研究则刚刚起步，研究成果较少。胡志华等建立了在集装箱集散环境下空重箱循环甩挂的调度优化模型，并设计两阶段优化算法进行求解。胡志华等为甩挂运输带有子回路的新型路径优化问题建立了 0/1整数规划模型，采用混合进化算法进行求解。 基于以上研究成果，本文在轴辐式网络中的一点多线甩挂运输组织模式下，对任务的作业路径进行分类转换后建立了考虑多作业路径的集装箱甩挂运输牵引车调度优化模型，并设计了启发式算法的模拟退火算法求解。算例分析验证了模型与算法的有效性与实用性。 2 问题描述 2.1 运输网络描述 每个甩挂运输网络由若干个轴辐式子网络构成，每个轴辐式子网络的中心为甩挂运输中心，客户
4、点分布在甩挂中心周围。设轴辐式子网络结构图 G=（V，A） ，其中，V=0，1，n，顶点 0 表示甩挂中心，顶点 1，n 表示客户节点，A 表示顶点 0，1，n 之间距离弧的集合。图 1 表示的是一个轴辐式子网络图。 在图 1 中，0 表示甩挂中心，1 到 n 表示客户节点。牵引车每天从甩挂中心出发去执行取箱任务或送箱任务，待所有任务执行完之后返回甩挂中心。 2.2 任务路径描述 取箱任务是指若某客户点处有装卸完毕的挂车，牵引车到达该客户3点后立即挂上重箱后送回甩挂中心。送箱任务是指某客户点处有货物等待装箱，牵引车拖带一个空箱到达指定客户点后甩下空箱即可去完成其它任务，待该点集装箱装卸完毕后成
5、为一个新的取箱任务。在执行每个任务时，牵引车的来源是不确定的，若上一个任务为取箱任务则牵引车的来源为甩挂中心；若上一个任务为送箱任务，则牵引车的来源为上一个任务的客户点。在途牵引车经过的路径根据前后任务节点可以归为以下四类：（1）上一任务是取箱任务，下一任务是取箱任务；（2）上一任务是取箱任务，下一任务是送箱任务；（3）上一任务是送箱任务，下一任务是取箱任务；（4）上一任务是送箱任务，下一任务是送箱任务。这四类路径可由图 2 表示。 图 2 中顶点 0 代表甩挂中心，顶点 1、2 表示客户需求点。实线箭头表示执行当前任务行驶路线，虚线箭头表示执行上（下）一个任务行驶路线。为便于求解，本文将每个
6、任务的出发点和终到点结合成一点，则图 2 的四种车辆路径类型转变为图 3。 在图 3 中，1-0 表示从客户点 1 到甩挂中心的取箱任务，0-0 表示牵引车从甩挂中心到甩挂中心的虚拟行驶路径。从图 3 中的四种车辆路径类型可以看出，牵引车行驶路线如图 4 所示。与传统多重旅行商问题不同的是，任务节点是由出发点和终到点结合后形成的一点，且该牵引车行驶路线可能存在虚拟路径。 3 混合整数规划模型建立 3.1 假设条件 根据甩挂中心实际操作情况及解决实际问题的需要，做出如下假设：4（1）所有的任务在调度之前都已确定，中途不会增加其它任务； （2）所有牵引车和挂车都采用统一标准尺寸； （3）一辆牵引车
7、一次只拖挂一辆挂车； （4）牵引车拖挂重箱和拖挂空箱的速度相同； （5）牵引车拖上挂车以及取下挂车的时间不计； （6）牵引车每天从甩挂中心出发，最后返回到甩挂中心。 式（1）为目标函数，表示使牵引车的数量最少和总的行驶时间最短，C 为一个足够大的常数，故保证了减少牵引车数量的优先级高于总的行驶时间最短；式（2）表示从甩挂中心出发的牵引车数量不大于车辆总数；式（3）表示每辆牵引车每天从甩挂中心出发，执行完一天任务后回到甩挂中心；式（4）表示每个任务仅且只被执行一次；式（5）表示每辆牵引车的行驶时间不能超过其一天的工作时间；式（6）表示任务的被完成的先后顺序约束；式（7）表示任务的开始执行时间必须
8、在时间窗的范围之内；式（8）表示决策变量。 3.4 惩罚成本函数 本文的时间窗采用软时间窗。牵引车开始执行任务 i 的时间若在 ti1之前或 ti2 之后，将付出较高的惩罚成本固定值 M；若在ti3，ti4范围内，惩罚成本为 0；若在ti1，ti3范围内，单位时间的惩罚成本为 a；在ti4，ti2时间范围内到达，单位时间的惩罚成本为 b。图 5 为第 k 辆牵引车执行第 i 个任务所付出的惩罚成本函数图像。式（9）为相应的惩罚成本函数。 54 基于启发式规则的模拟退火算法求解 本文采用二维解矩阵的编码方式进行解的表示。在解的变换过程中，反复交换二维解矩阵中两个不等于 0 的值以得到新解，这种解
9、的反复变换过程类似于模拟退火算法的加温过程。图 6 为基于启发式规则的模拟退火算法流程图。 4.1 启发式规则生成初始解 将 n 个任务按照可接受时间窗上限从早到晚进行排序，形成任务集合 M=1，2，n，将所有牵引车形成集合 K=1，2，m。设计启发式规则生成初始解流程图如图 7，具体实现步骤如下： Step 1：设未完成任务集 L=M，任务 i=1（iM） ，牵引车j=1（jK） ，进入 step 2； Step 2：将任务集 L 按照时间窗顺序进行从小到大排序，进入 step 3； Step 3：依次判断任务 i 是否能加入到第 j 辆牵引车的任务集中，判断依据为，是否满足时间窗要求。若满
10、足，则 L=L/i，进入 step 4；否则，令 j=j+1，重复执行 step 3； Step 4：判断 L 是否为空集，若是，则输出初始解；否则令 i=i+1，转到 Step 3。 4.2 解的编码方式 二维解矩阵中的值为任务编号，每一行表示一辆牵引车的行驶路径。图 8 表示一个需使用 4 辆牵引车，完成 20 个任务的甩挂运输方案，其中这四辆牵引车的行驶路径分别为 5-6-8-16-15；7-9-14-17-18；2-4-10-13-20；1-3-11-12-19。 6但是，按照上述编码方式，运输方案中的牵引车数量和每辆牵引车所完成的任务数是固定的，不利于保证解变换时搜索到全部可行解。为
11、了扩大解的搜索空间，对解矩阵进行放大，每行每列增加足够的 0 位。0并无实际意义，仅起到扩大解的规模的作用。图 8 的解矩阵扩大规模后见图 9，此时该运输方案的牵引车数量由原来的 4 辆变为3，6范围内的任一整数值，每辆牵引车完成的任务数也由原来的 5 个变为2，7范围内的任一整数值，极大扩大了可行解规模。 4.3 解变换 采用产生随机数方法交换矩阵中的两个数，若生成的两个数对应在解矩阵中的值都是 0，则重新产生两个数，直到不都为 0 为止，生成新解。在图 10 中，解的规模是 42，在1，42范围内随机产生两个整数，确定两个位置，在当前解中将这两个位置的数值进行对换。假设产生的两个数是 9
12、和 18，则在解矩阵中，把第 9 个元素和第 18 个元素对调，其对应数值分别为 9 和 13，对调 9 和 13 的位置产生新的解矩阵。 5 算例分析 以某公司甩挂中心的运营数据为基础，对其每日的运输方案进行优化。为了保证算例分析的可重复性及其与实际分布规律的拟合程度，本文使用 matlab 中的 unidrnd 函数随机生成客户点的坐标，用 unidrnd 函数生成的随机数呈离散均匀分布。二维均匀分布的函数为 G=（x，y）|axb，cyd，x，y 为自变量。设甩挂中心的坐标为（b-a2，d-c2） 。表 1 为某次随机生成的客户点坐标，此时 a=c=0，b=d=30，甩挂中心的坐标为（1
13、5，15） 。 7每个客户点所包含的取箱任务量和送箱任务量为0，a内的任意随机整数，可用 matlab 中的 randpint 函数实现。表 2 为表 1 中所有客户随机生成的任务数量。本文取 a=2。 根据客户时间窗的特性，使用 unifrnd 函数随机生成每个任务的要求开始时间，然后使用 round 函数保证生成的随机数为整数。在每个任务的可接受时间窗等于要求的时间窗减去或加上一个固定的时间t0（t00） 。本文取 t0=30。表 3 为对表 2 中所有任务随机生成的时间窗。牵引车每天从甩挂中心开始发车的时刻为 6：00，平均以 40km/h 的速度行驶，甩挂中心与客户点之间和客户与客户之
14、间的欧氏距离等于坐标距离的两倍，牵引车早于任务的时间窗上限和晚于时间窗下限的惩罚系数为 50。 根据上述数据，设计结合启发式规则的模拟退火算法，对模型进行求解。初始温度 T0=1000，内循环次数 L=500-T/4（T 为当前温度） ，终止温度 Tend=1，降温速率 =0.8。求得最优解为：需要 4 辆牵引车，执行任务所需时间为 6968，目标函数的收敛情况如图 11。从图 11 可以看出，算法在 9000 次左右收敛到极值点 6986。收敛速度很快，而且算法比较稳定。 牵引车的最优行驶路线如表 4。 数据结果表明，提出的模型和算法能够为牵引车的调度提供最优方案。 另外，在甩挂运输的实际调
15、度规则用最多的是基于时间紧迫度的启8发式规则，即空的牵引车每次都去执行时间上最紧迫的任务。使用matlab 编程可得，实际调度规则得到的执行任务所需时间为 8642，牵引车的执行任务顺序如表 5。 与实际调度规则进行比较可知，本文的模型和算法从完成所有任务的时间最少上进行考虑，得到的执行任务时间比实际调度规则的执行任务时间减少了 19.37%。算例结果表明，本文的模型和求解算法对甩挂作业调度人员具有一定的实际指导意义。 6 结论 本文在轴辐式网络中的一点多线甩挂运输组织模式下，考虑了多作业路径并进行分类转换后建立集装箱甩挂运输牵引车调度优化模型，并设计了基于启发式规则的模拟退火算法对模型进行求
16、解，借助 matlab 编程得以实现。通过算例分析与实际调度规则进行比较，运算结果证明了模型和算法的有效性和实用性。进一步的研究将集中于甩挂运输任务集动态调度优化，即调度过程中可能增加其它任务。 参考文献 1Caris A.，Janssens G. K.A local search heuristic for the pre- and end-haulage of intermodal container terminalsJ.Computers & Operations Research，2009，36（10）. 2Lin Shih Wei，Yu Vincent F，Chou Shuo Ya
17、n. Solving the truck and trailer routing problem based on a simulated annealing heuristicJ.Computers & Operations Research，2009，36（5）. 93Lin Shih Wei，Yu Vincent F，Chou Shuo Yan.A note on the truck and trailer routing problemJ.Expert Systems with Applications，2010，37（1）. 4Lin Shih Wei，Yu Vincent F，Lu
18、 Chung Cheng.A simulated annealing heuristic for the truck and trailer routing problem with time windowsJ.Expert Systems With Applications，2011，38（12）. 5Derigs Ulrich，Pullmann Markus，Vogel Ulrich.Truck and trailer routing-Problems，heuristics and computational experienceJ.Computers & Operations Research，2013，40（2）. 6胡志华等.集装箱集散的空重箱循环甩挂调度方法J.武汉理工大学学报，2012， （10）. 7胡志华.集装箱码头间互拖的集卡甩挂运输调度问题J.重庆交通大学学报，2013，32（2）. 8胡志华等.基于混合进化算法的甩挂配送问题J.公路交通科技，2013，30（5）.
