Ｌｏｇｉｓｔｉｃｓ Ｓｃｉ—Ｔｅｃｈ Ｎｏ．３，２０１７ 物流科技２０１７年第３期 ・交通运输・ 文章编号：１００２—３ １００ ｆ２０１７）０３—００７７—０４ 基于甩挂运输组织响车辆路径优化 Ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｂａｓｅｄ ｏｎ Ｔｒｕｃｋ－ｔｒａｉｌｅｒ Ｔｒａｎｓｐｏｒｔａｔｉｏｎ 李 维，成耀荣，吴百珂 ｕ ｗｅｉ，ＣＨＥＮＧ Ｙａｏ—ｒ（）ｎｇ，ＷＵ Ｂａｉ—ｋｅ （中南大学交通运输工程学院，湖南长沙４ １ ００７５） （Ｓｃｈｏｏｌ ｏｆ Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｅｎ 聊ｅ Ｃｅｎｔｒｏｌ Ｓｏｕｔｈ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ ４１００７５，Ｃｈｉｎａ） 摘要：传统大型制造业内部运输成本较高。文章针对运输任务对车辆具有独占性的特点及甩挂运输的组织特性，分析得 到总运输费用的大小取决于车辆的空车运行费用。在此基础上，将原有的甩挂运输任务问题转换为经典的１、ｓＰ问题。建立了相 应的数学模型，并设计了改进的自适应遗传。 关键词：甩挂运输；车辆路径；遗传算法 中图分类号：Ｕｌ１６．２ 文献标识码：Ａ Ａｂｓｔｒａｃｔ：Ｔｈｅ ｃｏｓｔ ｏｆ ｉｎｔｅｒｎａｌ ｔｒａｎｓｐｏｒｔ ｉｎ ｔｒａｄｉｉｔｏｎａｌ ｌａｒｇｅ ｍａｎｕｆａｃｔｕｒｉｎｇ ｉｓ ｖｅｒｙ ｈｉｇｈ Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｃｈａｒａｃｔｅｒ－ ｉｓｔｉｃｓ ｏｆ ｔｈｅ ｔｒａｎｓｐｏ￣ｔａｓｋ ｆｏｒ ｔｈｅ ｅｘｃｌｕｓｉｖｅ ｖｅｈｉｃｌｅ ａｎｄ ｔｈｅ ｏｒｇａｎｉｚａｔｉｏｎ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｃｏｓｔ ｉｓ ｄｅｔｅｒｍｉｎｅｄ ｂｙ ｔｈｅ ｅｍｐｔｙ ｒｕｎｎｉｎｇ ＣＯＳｌ ｏｆ ｖｅｈｉｃｌｅｓ，Ｏｎ ｔｈｉｓ ｂａｓｉｓ．， ｉｌｅｒ ｐｉｃｋ—ｕｐ ｔｒａｎｓｐｏｒｔ，ｔｈｅ ｔｏｔａｌ ｎｓｆｏｒｍ ｔｈｅ ｏｒｉｇｉｎａｌ ｔｓｋ ｏｆ ｔａｒａｉｌｅｒ ｐｉｃｋ－ ｕｐ ｔｒａｎｓｐｏｒｔ ｉｎｔｏ ａ ｃｌａｓｓｉｃ ＴＳＰ ｐｒｏｂｌｅｍ．Ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌ ｉｓ ｅｓｔａｂｌｉｓｈｅｄ ａｎｄ ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ｄｅｓｉｇｎｅｄ． Ｋｅｙ ｗｏｒｄｓ ：ｔｒａｉｌｅｒ ｐｉｃｋ—ｕｐ’ｔｒａｎｓｐｏｒｔ；ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｈｍ ｔ在制造业生产过程中，根据生产流程和工艺需要将分布在厂区不同地理位置上的原材料、再制晶与半成品、产成品以及【口】 收物料通过厂内车辆及时运送到各车间保证生产的正常进行。因此，在生产车间既需要将该车间生产完成的物料运送到下一Ｉ 序车间，同时也需要将本车间生产所需要的原材料及时送达。因为甩挂运输的特殊性，牵引车从某个车间挂上挂车出发后，甩 挂车辆进行组合运行的目的地必然是此挂车所在货物所对应的卸货点。在任务开始的最初时刻，所有牵引车辆都位于中心车 场，挂车已经分配在各客户点。大型生产企业场内甩挂运输组织问题，实际上是属于车辆调度（ＶＳＰ）范畴。因为各环节搭接 的时间有限，所以甩挂模式通常是大型制造业场内运输的主要模式。国内外学者在车辆调度（Ｖｅｈｉｃｌｅ Ｓｃｈｅｄｕｌｉｎｇ Ｐｒｏｂｌｅｍ， ＶＳＰ）方面取得了较多的理论和实际成果［１＿ 。在国外 丌ＲＰ（Ｔｒｕｃｋ ａｎｄ Ｔｒａｉｌ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ）定义为甩挂运输问题。这类问题 涉及到运输与生产计划的协调、挂车和牵引车在运输任务的组织、车辆的行驶路径规划与行驶时间的安排问题。此类问题的优 化目标：在满足运输要求下，如何有效组织牵引车和挂车的使用，使得总运输成本最小『圳。 ｌ问题描述 节点Ｎ（ ）为装货点，以ｉ为索引卸货地点为Ｎ（叶 ）。车库点为０。这样就区分了任务点、装卸货点以及其他的点。／、， ：ｌ０ １” …，２ｎ ｉ为所有运输节点的集合，Ｐ ＝¨，２，… ｝为装货点集合，Ｄ＝｛ｎ＋１，ｎ＋２，…，２ｎ ｌ为卸货点集合。值得注意的是，不 同的点可能带有相同的物理位置，也就是说有的点可能是虚拟的点。带时问窗的车辆路径问题在每个任务点有硬时间窗【ｅ』，ｚ。ｌ， 最早到达时间ｅｉ，最晚到达时间２ 。ｃ．．、ｔ ．为对应两点问的车辆行驶费用、时间。ｑ 为客户ｉ要求从节点Ｎ（ｉ）运到节点Ｎ（，ｌ ） 的运输基，中间过程不允许服务别的客户。埘于不能一次完成运输的任务，将视为不同的客户服务请求。ｄ． 为任意两点间距 离。基于甩挂运输的特性，本文不考虑装卸货时间。 ２概念和假设 （１）挂车装载能力相同且最大值为Ｑ ； （２）牵引车只能牵引一辆挂车； （３）有足够多的牵引车和挂车可用； （４）牵引车从车场出发完成一系列任务后最终返回车场； （５）行驶的费用和时间与距离成正比。 收稿日期：２０１６一ｌ２—３０ 作者简介：李 维（１９９２一），男，黑龙江哈尔滨人，中南大学交通运输工程学院硕士研究生，研究方向：车辆路径。 Ｉ．ｆ） ｉ Ｓ｛Ｉｊ一 ｉ“｝｛：ｆ｝ｌ？ ７７ 基于甩挂运输组织的车辆路径优化 ２．１策略和模型 根据甩挂运输的组织模式特性，当牵引车在某点挂上挂车后，那么牵引车和挂车运行的下一个点必然是该挂车的目的点。因 此，总运费的大小将取决于车辆的空车运行费用。对甩挂运输模型进行一定的变型，将节点Ｎ（ｉ）和其运输目的点Ｎ（ｎ＋ｉ）组合起 来看成一个甩挂运输任务点Ｎ（ ）。如图１各组合点间以运输任务的形式构建任务模型。转化后的问题就是典型的ＴＳＰ问题闭ｏ Ｎ（ ） ……… Ｎ ’ 、， 、 、， ，、 一Ｌ 二 Ｊ （ｂ）转换后 （ａ）转换前 ●装货点 。卸货点 转换后的虚拟任务点 图１甩挂运输节点转换图 车场 转化后车场 在一个有向图Ｇ＝｛Ⅳ ，Ｄ ｝中，Ｎ＝｛０，１ ，２ ，…， ），节点０表示甩挂运输车辆所在车场，其他节点为转化后的运输任务节点， Ｄ为连接任意两个任务间的距离。转化后的Ｎ（ ）状态参数变为［ｅｉ，ｌｉ】，ｅ ＝ｅ ；ｚ ＝ｚ ； ，州； 车辆．ｉ｝到达ｉ点的服务时问； ／＝ｄ 。综上所述可将甩挂运输模型描述为一个经典的 Ｐ模型，并便于求解。 ｃ Ｊ＝：ｃ州车辆在转化后的点停留时间Ｗｔ＂＝ｔｉ；ｄｉ决策变量：％ ：｛ 车辆 从 ： 驶到点 ；％＝｛ 点 的任 菏辆后完成 ｍｉ￣ｆ＝∑∑ｃ ∑￣ｉｊ＇ｋ＋Ａ∑‰ ｉ ＥⅣＪ ＥⅣ ｌ ｌ （１ （２） （３） （４） ∑ｙ ＾＝１ Ｖ ＥⅣ 、｛０】 ∑ 。 ＝∑ 。 ｉ ＥＮ Ｊ ｅＮ Ｖｉ∈Ｎ．Ｖｋ Ｅｒ≤ ／‘ ‘ｌ Ｊ ≤ Ｊ Ｖｉ，Ｊ∈Ｎ，ｋ∈Ｋ ∑ ＝∑ ＝１ ｋ ＥＫ ｉ Ｎ Ｊ ＥＮ （５） （６） （７） ∑∑％ ≤Ｉｓ Ｉ－ｘ，ＶＳＧＮ＼（ｏ】，Ｉｓ Ｉ＞－－２，Ｖｊｃ ｉ Ｅ ｓｊ ｅ ｓ ＾，Ｙｉ ＝ｏ或１，Ｖｉ ，ｋ 目标函数（１）总运输费用最小；约束条件（２）、 （３）表示每个客户点有且只能被访问一次；约束条件（４）牵引车服务 客户 的时间要满足＿『点的时间窗要求；约束条件（５）每辆牵引车从车场出发完成一系列任务后回到车场；约束条件（６）防 止客户间的子回路。 ３算法设计 因为将装货点ｉ和其卸货点ｉ＋ｎ整合成一个任务点来建立模型，所以需要对原来运输网络中节点距离做一些改变，变成甩 挂任务距离矩阵 。 ３．１任务距离矩阵生成算法 输入原始甩挂运输网络状态参数。 输出 改造后运输任务网络Ｇ＝｛Ⅳ ．Ｄ ｝。 开始 确定每个运输任务的装货点和卸货点，编制成运输任务属性表；将运输任务编号，创建一个空矩阵 。 开始１ 对每个运输任务，计算该任务的卸货点到其他所有运输任务装货点的距离，按编号将结果记录到矩阵 相应的行中。 返回１ 输出任务距离矩阵 。 ７８ ￣ｇｉｓｌｌｃｓ Ｓｃｉ一 Ｆｅｃｈ ２０ｔ ７．３ 基于甩挂运输组织的车辆路径优化 结束 获取甩挂运输任务距离矩阵后，选用遗传算法求解运输任务的最佳完成顺序。遗传算法是借助生物进化过程中自然选择和 自然遗传机制的随机搜索算法，对解决复杂和非线性优化问题比传统搜索算法有更强的适应能力。 ３．２运输任务最佳完成顺序生成算法 输入核载等。 任务距离矩阵 ，遗传算法控制因子ＭＡＸＧＥＮ、ＮＩＮＤ、ＧＧＡＰ、 、Ｐｍ等，其他计算系数如：车辆行驶成本、车辆 输出运输任务完成路径。 开始 确定编码方案， 生成初始种群。 当迭代次数ｇｅｎ＜ＭＡＸＧＥＮ时： 开始１ 当种群ｍ＜ＮＩＮＤ时： 开始２ 计算种群适应度值， 选择操作， 交叉操作， 变异操作， 进化逆转操作。 返回２ 算法终止判断。 返回１ 绘制迭代示意图、目标函数变化图以及路径图。 结束 ． ３．３算法关键参数设计 选择操作 选择操作是从原群体以一定的概率将优良个体选择出来，组成新的种群繁殖得到下一代个体。个体的适应度值越高，被选 择的概率越大。选择算子是计算适应度比例的选择策略，选择算子： ｐ ＝ Ｌ （８） ．●‘一 Ｆｉ 其中： 为个体ｉ的适应度值，Ⅳ为种群个体数目。 （１）交叉操作 交叉操作从种群中随机选择两个个体，通过两个染色体的交换组合，把父代的优良特性遗传给子代，从而产生新的优秀个 体。由于个体采用实物编码，所以交叉操作采用实数交叉法，第ｋ个染色体 和第ｚ个染色体 在 位的交叉变换为： ％＝ （１－ｂ） ６ （９） ＝ （１－ｂ） ％６ （１ｏ） 其中：ｂ是［０，１］区间的随机数。 （２）变异操作 变异操作主要是为了维持种群的多样性。进行变异操作，首先从种群中随机选取一个个体，选择该个体基因中的一点进行 变异以产生更优秀的个体。第 个个体的第Ｊ个基因 进行变异的操作： ＝ ； ５ … 其中： 是基因 的上界， 是基因 的下界，，（ｇ）＝ｒ２（１－ｇ，ｃ～）‘，ｒ：是一个随机数，ｇ是当前的迭代次数，Ｇ一是最 大进化次数，ｒ为［０，１］区间的随机数。 （３）进化逆转操作 在选择、交叉、变异之后，进行多次单方向的逆转操作来改善遗传算法的局部搜索能力，在逆转操作后，只有适应度值提 高的才接受该逆转，否则逆转无效。例如在［１，１０］随机产生两个数４和７，在一条染色体确定两个位置，将其位置调换。 ９ ５ １ Ｉ ７ ３ ８ Ｉ ６ １０ ４ ２ Ｌｏｇｉｓｔｉｃｓ Ｓｃｉ—Ｔｅｃｈ ２０１７．３ ７９ 基于甩挂运输组织的车辆路径优化 逆转操作之后成为： ９ ５ １ Ｉ ８ ３ ７ Ｉ ６ １０ ４ ２ （４）判断终止条件 因为遗传算法是随机搜索算法的特性，很难找到一个明确的终止条件。一般的解决办法要么是设置固定的进化迭代次数 Ｇ一（一般Ｇ一∈￣１ｏ０，１ ０００】），或者当前的优化解在连续进化若干代也没有变化作为算法的终止条件，本文选用设置固定的 迭代次数作为算法的终止条件。 ４结论 （１）运输任务对车辆具有独占性，分析得出总运输费用的大小将取决于车辆的空车运行费用。 （２）提出新的策略，将原有的甩挂运输任务模型变为经典的ＴＳＰ问题；并建立带时间窗的ＴＳＰ模型。 （３）本文设计了改进的遗传算法进行相应的优化求解；能够较为快速地计算出较优的牵引车行驶路径。 参考文献： ［１】刘云忠，宣慧玉．车辆路径问题的模型及算法研究综述［Ｊ］．管理工程学报，２００５，１９（１）：１２４—１３０． ［２］Ａｎｄｅｒｓｏｎ Ｅ，Ｐｈｉｌｌｉｐｓ Ｃ，Ｓｉｃｋｅｒ Ｄ，ｅｔ ａ１．Ａ ｓｉｍｐｌｅ ａｎｄ ｅｆｆｅｃｔｉｖｅ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ［Ｊ］． Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ，２００４，３１（１２）：１９８５—２００２． 【３】Ｓａｌｈｉ Ｓ，Ｎａｇｙ Ｇ．Ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｈｍｓｔ ｆｏｒ ｓｉｎｇｌｅ ａｎｄ ｍｕｌｔｉｐｌｅ ｄｅｐｏｔ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍｓ ｔｌｌ ｐｉｃｋｕｐｓ ａｎｄ ｄｅｌｉｖｅｒｉｅｓ［Ｊ］． Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｉｔｏｎａｌ Ｒｅｓｅａｒｃｈ，２００５，１６２（１）：１２６—１４１． ［４］Ｃｈｅｎｇ Ｙ Ｒ，Ｌｉｎｇａ Ｂ，Ｚｈｏｕ Ｍ Ｈ．Ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ｖｅｈｉｃｌｅ ｓｃｈｅｄｕｌｉｎｇ ｉｎ ｉｏｎ ａｎｄ ｓｒｔｅｅｌ ｗｏｒｋｓ ｂａｓｅｄ ｏｎ ｓｅｍｉ—ｔｒａｉｌｅｒ ｓｗａｐ ｔｒａｎｓｐｏｒｔ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｅｎｔｒｌａ Ｓｏｕｔｈ Ｕｎｉｖｅｒｓｉｔｙ，２０１０，１７（４）：８７３－８７９． 【５ 孙国华．带时间窗的开放式满载车辆路径问题建模及其求解算法［５］Ｊ］．系统工程理论与实践，２０１２，３２（８）：１８０１—１８０７． 【６】李建祥，唐立新．钢铁供应链生产计划与调度研究综述【Ｊ】．控制工程，２０１０，１７（１）：１２３—１２６． ［７】Ｔａｎｇ Ｌ＇Ｚｈａｏ Ｊ，Ｌｉｕ Ｊ．Ｍｏｄｅｌｉｎｇ ａｎｄ ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｊｏｉｎｔ ｑｕａｙ ｃｒａｎｅ ａｎｄ ｔｒｕｃｋ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ［Ｊ／．Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，２０１４（２３６）：９７８－９９０． 【８】辛曼玉．网络型甩挂运输模式下的车辆调度问题研究【Ｊ】．物流技术，２０１４，３３（１）：２５４—２５８． （上接第７３页） ｆ ０．５００ ０．３７５ ０．１２５ ０．０００ ０．０００ １ Ｒ ＝ｌ ０．３７５ ０．３７５ ０．２５０ ０．０００ ０．０００ Ｉ 【０．１２５ ０．３７５ ０．３７５ ０．１２５ ０．０００ Ｊ Ｓ１＝ （０．３６３ ０．３７５ ０．２３ ｌ Ｏ．０３ ｌ ０．０００） 计算站点对线路的影响设置公交站点的可行度： Ｏ．９ ０．７ ｒ ．ｓ３Ｅ＝（０．３６３ ０．３７５ Ｏ．２３１ ０．０３１ ０．０００） ０．５ ＝ｏ．７１４ ０Ｉ３ Ｏ．１ ＝即：根据乘客特性得知，柳州市３６路公交线路在广西科技大学西门设立站点的可行度为７６％。 对土地利用性质、站点及线路的影响和乘客特性得出的可行度按照第一层要素进行加权平均后得： ｆ ０．４５］ ０．２５ Ｊ ｆ ０．４］ 【０．３ Ｊ （ⅣＩⅣ２Ⅳ３）ｌ【 ０．３０ Ｉ＝（０．７００ ０．７０６ ０．７１４）ｌ ０．３ ｌ＝０．７０５ 由此可见，根据广西科技大学人口密度和公交需求的模糊分析，得出结论，３６路公交线路在广西科技大学西门处设立的 公交站点具有７０．５％的合理性。 ４结束语 城市公交站点的选址非常重要，是整个城市公交网络布局的关键组成部分。在城市公交网络规划中，要从每一个站点、每 一条线路开始进行考虑，还要统筹兼顾全局，做好公交线网的整体规划工作。 参考文献： 【ｌ】戴炳奎．快速公交站点布局设计优化研究［Ｄ】．成都：西南交通大学（硕士学位论文），２００９． 【２】 蒋文涛．公交站点选址与平面布置探讨叨．交通与运输，２ｏｏ６（ｓ０７）：８１—８４． ［３】卢小林，俞洁，邹难．公交专用道选址与公交线网组合优化模型【Ｊ】．交通运输工程学报，２０１６（２）：１３２—１４２． ［４］王琳，陈大鹏．公交站点选址的分析与模糊评判［Ｊ］．交通科技与经济，２００９（６）：４７ ９． ８０ Ｄｏｇｉｓｔｉｅｓ Ｓｃｉ—Ｔｅｃｈ ２０ ｌ ７．３
