基于拉格朗日松弛的集装箱满载车辆路径启发式算法外文翻译资料

英语原文共 19 页，剩余内容已隐藏，支付完成后下载完整资料

基于拉格朗日松弛的集装箱满载车辆路径启发式算法

摘要：这篇文章我们解决了一个路径选择问题，这个问题产生于从/到一个多式联运终端，收集并运送集装箱货物。如果作业时间和集装箱货物的适用性允许，提货和交付任务之间的有效联系可以预期实现大量的成本和时间节省。由于这个问题是非确定性多项式困难问题，我们建立了一个基于拉格朗日松弛的子梯度启发式，它使我们能够确定一个近似的最优解。这个启发式由两个子问题组成：普通赋值问题和广义赋值问题。由于广义赋值问题也是存在非确定性多项式困难的，因此我们基于这个问题采用了一个有效的解决方案，代替了广义赋值问题。启发式在各种各样的问题示例上进行测试。测试结果表明，本文所开发的程序是能够有效地解决问题的大实例。

1.介绍

本文针对集装箱的提货和运输问题，提出了一种复杂的路径选择问题。多式联运系统由多种交通方式组成，如水运、铁路、公路等。集装箱的多式联运，通过卡车，从运输节点(或多式联运终端)，如港口和铁路码头，运送给客户。集装箱运输分为两类：装卸和配送。这些活动本质上是独立的。一辆拖车将集装箱从一个运输节点运送到收货人，卸货后将集装箱空载到码头。相反的是，在装货过程中，一辆拖车将一个空集装箱运输到托运人，并在装货(取车)后将一个装满集装箱的集装箱运回发货人。

大多数托运人和发货人都在附近的一个配送区附近，尤其在日本。因此，如果兼容性标准，如出货时间和适用性、集装箱到货物的类型和尺寸都是可以的，可以将空的集装箱从交付点直接转运到现场进行的装运，这样可以减少空运车的行程长度。这种被视为合并路线进行交付和接送可以有效利用空集装箱。

拖车由机车和拖车组成，它们通常可以分离（在日本，大多数专为国内集装箱配送而设计的拖车不能）。因此，当长时间的装载或卸载过程时，机车将拖车（或装载集装箱的的底盘）脱开，并将其留在客户现场，使得该卡车可以被分配到下一个货物。然而，这种情况不太可能发生在日本的集装箱多式联运中，主要原因是卡车作业的复杂性，以及上面提到的拖车卡车的物理特征。

一家公司通常可以选择购买自己的卡车或者租赁卡车来进行货物分配。由于资金和运营成本满足高峰需求的机队规模并不合适，所以公司投资于规模范围内估计的最高和最低需求之间的中等规模的船队，而在运营阶段公司包租额外的车队来满足超额需求。一旦拥有了所有的船队，包括司机的成本在内的资本成本被视为沉没成本，所花费的费用与卡车的寿命有关， 无论卡车工作量多少。然而，燃料成本通常是由于收入承担（包括空载运行）。从这个角度来看，自己与船队有关的费用（主要是燃料成本）低于租船费用，这些费用根据租船合约的时间长短而有所不同。在这方面，重要的是尽可能多地向自己的船队分配任务，以减少整个分配成本。然而，因为自己舰队可能会过度工作，因此这样一项高效的任务分配计划并不容易。如果包括自己和外部车队在内的任务分配计划不好，公司就需要雇佣更贵的外部卡车。

在集装箱货物运输自身的船队运营中，受到上述问题启发，我们认为这个问题称为全集装箱装载（VRPFC）的车辆路线问题，定义如下：假设具有不同牵引成本和工作时间长度的均匀集装箱类型和尺寸以及拥有和特许的船队，可以找到自己和特许船队对一组交货和捡拾点对（以下简称D-P对）的最佳配置，以尽量减少总分配成本。我们一天从一个运输节点处理集装箱配送。注意，当我们把注意力集中在国内的集装箱多式联运时，我们不会根据机车和拖车的单独使用来设想一个复杂而动态的操作。稍后将证明，VRPFC是一个非确定性多项式困难问题。因此，我们提出了一个基于拉格朗日的基于松弛的启发式方法。

如上所述，本研究假定集装箱类型和尺寸相同。在许多情况下，这种假设是存在的，原因如下：在日本的国内集装箱运输系统中，通常有三种类型的集装箱：12英尺，20英尺和30英尺的集装箱。如果货物需要一个12英尺的集装箱，那么货物可以用更大的集装箱来包装。容器尺寸兼容性也可以在国际集装箱运输系统中看到。然而，这样的大小替代可能适用于不同的运费率和其他运输相关协议。类型替换比大小替换更难。我们考虑的问题可以修改，这样就可以处理多种类型的集装箱，并在特定的客户站点中重用相同类型的集装箱。然而，这样的修改是未来的研究课题。

本文的组织结构如下。下一章将介绍问题的概要。第3章重新审视相关文献。问题公式及其拉格朗日松弛在第4章中有描述。第5章给出了一种子梯度方法来产生近似的最优解，突出了从解到松弛问题得到可行解的算法。第6章进行了广泛的数值实验，其次是本文的第7章，对本文研究的内容进行了总结。

2. 问题描述

VRPFC在图G =（V，A）上定义，其中V是表示终端的顶点集，接收点（或托运人）和交付点（或收货人），A是弧设置。有两种类型的行程，每一种都与传送点或拾取点相关。如果容器的兼容性和交货和提货的时间得到满足，送货行程和取件行程可以合并。问题是尽可能减少各种拖车（以下简称卡车）对集装箱运输行程进行维护的总分配成本，并允许相应的工作时间准则（以下称为本文剩余部分的时间容量）。用于集装箱配送的卡车分为自有和租赁，而这个区别对于问题来说并不是必不可少的。如第1章所述，如果忽略了自己的卡车的沉没成本，租赁卡车比自有卡车要贵。自有卡车的时间比包租的时间短，主要是由于公司的工会。合并后的运输由自己的卡车服务，只要它们的时间容量允许。此任务分配策略可以解释如下：如果包括沉没成本，自己的车队的总成本要高于租赁车队，因此公司限制了自有卡车的数量。公司将尽可能多的任务分配给自己的机队，因为拥有沉没成本的昂贵的机队应该有效地利用时间的能力。请注意，如果交货点的数量不等于取货点数量，则单独的行程仍然存在。不由自己的卡车服务的行程由特许的卡车覆盖。所有的行程都是应该被接受的，因为人们认为公司可以尽可能多地包租外面的卡车。

在后面的章节中描述的拉格朗日的基于松弛的解决方案过程中，交付点在每次迭代的第一个阶段都是成对的，并且在第二个阶段将卡车的车队分配给成对的客户站点(或合并的旅行)。在解决过程中，如第4章所述，通过迭代来改进解决方案。图2揭示了第一次迭代的可行解。仓库-客户和客户-客户距离如表1所示。请注意，由于交货点后面是合并行程中的起点，因此表1中仅提供了从交货点到收货点的距离。在表2中给出了[货运站 - 运输点 - 仓库]的合并旅行时间，其中拖运时间涵盖可能的合并行程，假设一辆卡车以15公里/小时的速度运行。请注意，为简单起见，拖运时间不包括客户的装货/卸货时间。卡车数量，相关成本和时间容量如表3所示。共计20分配对组成10次合并旅行A-J。有两个不同的卡车车队：一个是自己的车队，另一个是特许车队。自己拥有的卡车有较短的时间容量。图2的右侧部分是甘特图，显示了卡车到合并行程A-J的任务。这两辆租来的卡车中，有一辆根本没有使用。请注意，在问题设置中，尽管卡车的时间容量不高，但成本与旅行时间成比例。这意味着对于特许车队，卡车在一天内完成分配任务后，就会被派往租赁公司。例如，在完成行程F之后，卡车3将返回其公司，同时保持5小时的时间。

表1 客户点之间的距离（公里）

表2点i点j的合并运输时间（小时）

您可能感兴趣的文章

• 基于换乘网络的公交接驳线网优化外文翻译资料
• 公路综合运输系统设计与开发研究外文翻译资料
• 然而，由于问题的复杂性，他们的模型只能由启发式解决方法，得到次优解。外文翻译资料
• 安吉川达集装箱码头后方堆场布局仿真优化设计外文翻译资料
• 3.1 基于EPQ模型无缺货延迟策略分析外文翻译资料
• 三峡库区船舶交通流分析及预测外文翻译资料
• O.R.运输规划在货运代理公司的创新应用tabu搜索算法的综合业务运输规划问题外文翻译资料
• 应急物流规划的稳定优化:人道主义救援供应链中的风险缓解外文翻译资料
• 一种预测和估计城市网络交通需求的组合方法外文翻译资料
• 基于GIS和数据包络分析的考虑社会优先级的城市公交路线运输系统效率评估的多模态数据建模外文翻译资料