作 者 姓 名 作 者 学 号 指导教师姓名 指导教师职称 完 成 时 间 年 月 北华航天工业学院教务处制 共 页 第 页 译文标题 卡车装载问题 原文标题 作 者 译 名 乌米特 国 籍 土耳其 原文出处 卡车装载问题 介绍 在相同的车舱内可以装载各种尺寸的货物产品， 车厢可能有相同或不同的 装配 能力。货车 带有 车厢 ，以 便于卸载和加载 满包装和空包装的产品到达 目的地。 空包装物的产品被作为循环再利用的资源， 这类型的运作要求 货车 向个繁忙闹市区 配送，使其始发地到目的地的距离最短。因此， 在繁忙的市中心区 ， 车厢 的 使用 使货车的装卸载更加 方便快捷 。 有 这样的个例子 是 关于 软饮料的包装 物 从 始发地到不同目的地的运输与配送的问题， 在欧洲的软饮料行业通常有六种类型 的 产品规格大小。这些是 和 。 同时 封装的大小取决于瓶口尺寸。 货车是 根据 给定路线上的目的地的 需求 来进行配载的 路线是由些地理区域目的地 来确定的。在这项研究中我们假定需求率，在目的地 没有存储 限制 ，每种产品都有足够的数量， 管理 策略是 需要目的地接受任何交货 计划， 只要 直满足 他们的要求。补货时间是 条路线上两个交货点之间的 时间时间间隔 。 有个关于 经营 的 问题是如何 以最大 限度的补货时间 来对车辆进行配载 。 我们叫这样的个问题叫车辆配载问题。 以最大限度的补货时间 所产生的重要结果是减少长期的潜在的运输成本。 问题的定义 不同的产品的卡车车厢运输和送货是在他们自己的包装的情况下从个始发地到的不同的目的的需求点的过程。大小的舱室的车辆可以不同。每种产品可以放置在任何舱室与他人在运输。这样的个例子是运输和传递从包装软饮料装瓶厂或仓库源到多个目的地，如餐馆，咖啡厅等在市区 这是非常重要的，在每个需求点提供正确数量的产品满足需求直到下次交货。任何产品短缺的意味着失 去了商业和 或现有车队配送车辆的配货，在增加运营成本。管理坚持目的地的路线上的每个车辆及时正确数额的货物送达到目的地。此外，这种政策只会随着季节反复变化。 共 页 第 页 连续两次内交付的时间间隔称为补货时间。其中个操作问题是在这样种方式最大限度的补充时间内，如何加载厢式车辆，满足给定的车辆舱容量的需求，直到下次指定的车辆路线的交付。 同时耗尽的产品是每个目的地的产品提供的正确的比例。 卡车装载问题模型 在建立模型之前，我们先介绍决策变量和相关参数，假定问题的参数不变。不同的目的地所有类型的产品共同补给时间表示 作为车厢的指数 作为目的地的参数。 来表示产品的参数。 可变 代表这次产品的数量整数  到目的地  的车厢装载的指数 ， 代表车厢的装载能力  代表产品  的包装尺寸 , 代表产品 的 需求率，目的地表示为  交货数量为 ，补给时间周期为所有的产品和目的地是最小的补货时间的每个产品在每个目的地。然后，为所有的产品和目的地补给时间周期是在每个目的地的每个产品最小的补货时间。    目标为，如何进行车辆配载使补货时间最大。   数学模型如下所示 服从        ，   取整数     这是个混合整数线性规划混合整数线性规划问题， 整数变量和连续变量 的约束。第个约束是能力的约束，配载车辆的车厢限制。装在车厢的包装产品的总体积不能超过车厢容量。第二个约束集 是需求约束。对在每个目的地的每个产品的需求必须满足，直到下次交货。换句话说，每个目的地的每个产品的交货数量至少应 。 在这个模型当中的  是送往目的地的产品的实际交货数量整数，这个模型是 年被乌米特 提出来。  代表产品的送货数量，表示已配车厢的配载能力的总和。因此，这两种模型在 结构上有微妙的差异。 这里有些关于卡车装载问题的可利用的方法。有这样个模型，定义 ， 共 页 第 页 设 ，所有 ，  ,如下 服从        ，   取整数     然而，设 ， ，  ，  ，使模型看起来简单，但也容易造成的结果。 服从       取整  ,  既然 是 个非负整数 在这个模型中 为整数， 也 是个整数， 可是，这个问题逆向的说法却 是不正确的。 如果，这个结果是 , 那么 就不是个整数。 在本文中，表达式 模型的形式 被保留下来，用来记录到达终点的产品 的数量。 对于经营管理和目标来说， 这信息是 很 重要的 解决方法 车辆装载问题 是个混合整数线性规划问题混合整数线性规划。商业软件包的使用，行话，延长使用，超长使用以及其它仅能解决规模较小的卡车装载问题。事实上，由于其特殊的结构和离散的问题，每个都需要如此多的计算时间找到个最佳的解决方案计算性能的术语在表 。因此，基于特殊结构的问题，本节会提出个有效的方法。调查的结构的问题表明，约束 和 的问题是为给定的补货时间 加权分配问题丹， 的限制。加权分配问题是基本上针对于产品体积特性的运输问题并对此提出进步详细的附录。这个问题对于个给定的 的数学表述如下             这个问题是个没有目标函数加权分配问题和变量的整数要求被忽略。解决这个问题 ， 和 的个整体可行的方法是可以通过个算法子算法 很容易的解决。从这点上，在这个文章中，这个问题被称为加权分配问题。 初步作业时，解 决卡车装载问题的方法，混合整数线性规划的提出建议如下。个主要的算法来确定补货时间 ，个子算法对于个给定的工作计划 共 页 第 页 找到整数可行解和另个子算法来测试最优性。主要的算法将最大限度的增加补充时间 分叉间隔不确定性。区间的不确定性之间的间隔是补货时间 的下限和上限可能值的间隔。在每次迭代的主要算法中，区间的不确定性将被分为二，同时迭代将继续重复，直到时间的不确定性变为足够小。对于卡车装载问题，整数解是个可行的解决方案，因此在每次迭代的主要算法中，这解决方案的表现形式是下限解的区间的不确 定性。最初的上限是 最优解的松弛问题，它可以通过所忽视的卡车车厢模型还有整数要求的问题来求解。显然， 是混合整数规划问题，因此，应选择相应的个合适的初始下界  。对于所有的实际目的，下界  可能被设置为 ，因为车辆的能力必须满足至少个时期的特定路线的需求。减少时间间隔不确定性的个方法是以 开端。如果有个可行的解决方案， 如果 则采用 ，然后不确定的初始区间是  , 若不是，则为 , 这种做法在开始使初始区间的不确定性降低些。下步，将会给出关于主要算法的运算的完整说明。 主要算法 步骤 初始化设  , 和  ，选择  ，然后到步骤 。 步骤   然后调用 子算法 ，进入步骤 步骤 如果 子算法 找到个可行的解决方案  ，则   ，否则  如 果   ，则直接进 入步骤 ，否则设  ，返回步骤 。 步骤 对于任何  和  ，计算  和 ,  ， 然后调用 子算法 做 最优试验和 或可能的改进。 加权分配问题层可以 用 个画面形式非常相似的运输表 来代替 。虚拟列可能被引入来弥补每个车厢 空载状况 。以 上 简单的算法获得的整数可行解的表达式层 和 个给定的时间 ，在 获得个整数解 方面， 它是类似于西北角法 的 些额外的功能 。 结论 本 文 研究的 是 卡车装载问题的数学模型 及 其结构与性能。有 很多 不同类型的产品 通过不同大小的厢式货车从来源地被运输和配送到不同的目的地。 运作上的问题是如何加载车辆 使其 补货时间 达到 最大化。产品 的尺寸是多种多样的， 每种产品都有不同的包装量 ，每种车厢 可以有不同的 装载 能力。产品可以 被 放置在同车厢 ， 这 就 提供了 车辆配载的 灵活性。混合整数线性规划 是 来描述这个问题的数学 模型。 它是个 问题。我们的经验表明，随着整数变量的