这是用户在 2025-2-28 11:09 为 https://app.immersivetranslate.com/pdf-pro/4c173304-0aa8-45cf-9b52-ab435acf9cca/ 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？


考虑托盘正向和反向流动的数学公式和启发式算法，用于优化汽车零件循环物流网络


Farivar Ranjbaran， Ali Husseinzadeh Kashan & Abolfazl Kazemi


引用本文：Farivar Ranjbaran， Ali Husseinzadeh Kashan & Abolfazl Kazemi （2020） 考虑到托盘的正向和反向流动，优化汽车部分牛奶运行物流网络的数学公式和启发式算法，国际生产研究杂志，58：6,1741-1775，DOI：10.1080/00207543.2019.1617449

要链接到这篇文章，请执行以下作：https://doi.org/10.1080/00207543.2019.1617449

在线发布：2019 年 5 月 28 日。

将您的文章投稿至本期刊
文章浏览量： 771
查看相关文章

查看 Crossmark 数据 △ △ /_\\triangle

施引文献： 11 查看施引文献


考虑托盘正向和反向流动的数学公式和启发式算法，用于优化汽车零件循环物流网络


Farivar Ranjbaran a a  ^("a "){ }^{\text {a }} 、Ali Husseinzadeh Kashan b* b*  ^("b* "){ }^{\text {b* }} 和 Abolfazl Kazemi a a  ^("a "){ }^{\text {a }}
a a ^(a){ }^{a} 伊朗加兹温伊斯兰阿扎德大学加兹温分校工业与机械工程学院工业工程系; b b ^(b){ }^{b} 伊朗德黑兰 Tarbiat Modares 大学工业与系统工程学院


（2018 年 10 月 17 日接收;2019 年 5 月 1 日接受）

抽象


汽车行业分销网络的运营规划很复杂，需要考虑许多条件，包括异构车队、强制将托盘 3D 包装到车辆中以解决车辆在重量和体积方面的容量、车辆中订单的兼容性、将空托盘从装配厂退回给供应商以及交货时间窗口。提出了一种数学模型 （MILP），该模型考虑了这些条件以最大限度地降低总运输成本。网络结构可以是直接装运和循环取货的组合，用于托盘的正向和反向流动。该模型针对小尺寸问题进行最佳求解。为了解决更大的问题，提出了一种启发式算法（有两个版本），该算法使用相似性度量来生成合理的订单列表。采用最佳/优先拟合策略，在拟议的 MILP 的宽松版本的帮助下生成可行的解决方案。还设计了改进启发式方法。与大多数现有的建设性启发式方法不同，我们开发启发式方法的目标是强制路由决策，并使其所有考虑因素都处于最佳状态。我们还在分组进化策略 （GES） 算法的主体中使用了所提出的最佳拟合策略，以获得有效的元启发式方法。在生成的实例上测试了启发式的有效性，这表明它们最适合小型问题。他们还根据从伊朗最大的汽车公司收集的每日汽车零部件发货数据进行了测试。结果表明，与直接运输策略相比，循环取货策略存在显著的成本节约潜力。


关键词：物流;循环取货;路由;混合整数线性公式;第一/最佳拟合策略;分组进化策略

1. 引言


商品运输是供应链管理的一个重要领域，这导致各个行业的物流成本约占三分之一到三分之二（Ghiani、Laporte 和 Musmanno 2004）。这使得运输成本的优化成为降低总物流成本的主要决定因素。实现这一目标的第一步是设计和实施一个高效和有效的分销网络。分销网络分为三类（Boysen 等人，2015 年）：（1） 直接运输网络，（2） 越库配送系统，（3） 和循环取货系统。

在直接发货网络中，货物直接从每个供应商运输到制造商。对于整车运输（TL 或 FTL）订单，将直接发货。对于零担 （LTL） 订单，直接发货并不经济，因为它会导致车辆半满，从而增加运输成本。在越库配送系统中，LTL 订单在中间节点合并，以使卡车装满。这些网络可能会导致交货时间增加，但也会导致库存和成本减少。在循环取货系统中，可以通过让车辆访问多个供应商来提取和积累订单，并将订单运送到一个或多个目的地，从而整合零担订单。实施循环取货系统还有其他几个优势，包括降低成本、库存和 CO 2 CO 2 CO_(2)\mathrm{CO}_{2} 排放。值得注意的是，该系统的名称来源于传统的牛奶配送系统，其中挤奶工访问多个客户的家庭，将牛奶瓶运送到配送中心并收集空瓶子（Sadjadi、Jafari 和 Amini，2009 年）。

循环取货系统已用于许多行业（Kilic、Durmusoglu 和 Baskak 2012）。一个显着的例子是，汽车行业因其供应链的广度和物流系统的复杂性而在伊朗和许多发展中国家被认为是一个非常重要的行业。具体来说，通常存在许多分散在不同地理位置的供应商，他们制造各种零件并将其发送到装配厂。这使得管理这个供应商、仓库和装配厂网络中的零件流变得复杂。入库中断

装配厂的物流可能会使装配线停止，从而给责任方带来成本。另一方面，网络的这一特性为从业者提供了在提高资源利用率时大规模降低成本的机会。当多个供应商关系密切且货物为零担 （LTL） 时，情况尤其如此。Nemoto 和 Rothengatter （2012） 研究了循环取货在绿色物流中的潜力，其中介绍了三家汽车公司的例子，即丰田、Webasto 和奥迪。另一项研究是 Gyulai et al. （2013），其中为车间物流中的循环取货问题提出了一种本地搜索算法。Boysen 等人（2015 年）还对汽车行业的零部件物流进行了回顾。

SAIPA Corp. 是伊朗最大的汽车制造商之一。在 SAIPA 中实施准时制 （JIT） 理念可以降低装配厂的库存水平，从而提高交货频率。因此，这给供应商带来了更高的运输成本，这些供应商应该根据直接发货的理由进行发货。此外，JIT 概念导致的批量较小和对供应商的递延债务加剧了这种情况。具体来说，这种情况增加了供应商的议价能力，他们拒绝将零件运送到遥远的目的地（他们可能会将货物运送到仓库）。在这里，使用循环取货物流运输的潜在好处及其由此产生的节省变得更加突出。这证明了设计一个网络的动机，在该网络中，小批量可以整合到车辆中并调度到装配厂。

除了从供应商到装配厂的零件交付的正向流动外，还有另一个同样重要的流动，它源自装配厂到供应商，即所谓的逆向流动。一般来说，零件是用木制或金属托盘运输的。虽然木制托盘在交付后被报废，但空的金属托盘应退回给下一个循环取货周期的供应商。因此，除了规划订单的正向交付外，规划空金属托盘的反向交付也具有挑战性。这里的挑战在于，并非所有从特定供应商交付给特定装配厂的金属托盘都必须在交付后送回给供应商。因此，供应商收到的空托拍数量可能多于或少于其发送的空托拍数量。事实上，就像具有起点和目的地的零件需求的远期订单（例如远期订单）一样，空托盘需求的倒向订单（例如倒序）也具有起点和目的地。因此，问题在于设计一个物流网络，以便使用循环取货概念有效和高效地处理前向和后向物流作。这就是为什么我们将这个问题命名为前向-后向循环-循环纸物流问题 （FB-MRLP） 的原因。

根据上述观察结果，本文的贡献是首先为汽车制造商公司面临的真实世界 FB-MRLP 开发一种数学建模方法。鉴于远期和后向订单的来源和目的地是已知的，我们的任务是找到最佳计划，从供应商/装配厂提取装满/空的托盘，并将其交付给装配厂/供应商，从而将分销的总成本降至最低。在优化分配系统时，这样的目标函数是常规的（Edokpia 和 Amiolemhen 2016）。因此，从数学建模的角度来看，根本问题（纯粹形式）是取货和送货问题 （PDP）。但是，为了处理我们的案例，我们有义务考虑远期订单兼容性、3D 托盘包装、不同类型节点之间的移动数量以及远期和后向订单的交货时间窗口，每个因素都强制执行一组约束。鉴于问题的性质，目标是将订单分组到卡车中并构成卡车的循环取货路线，我们的第二个贡献是开发启发式方法，即基于相似性的最佳拟合和基于相似性的第一拟合算法，并使其适应 FB-MRLP 并使用数值实验证明其有效性。FB-MRLP 的分组性质允许我们在分组进化策略 （GES） 算法的主体中使用提出的启发式方法。这使我们能够获得 FB-MRLP 进化算法提供的更有效的解决方案。 由于每个可行的 routing 都应该满足许多考虑因素（有关考虑因素列表，请参见 Section 2 和 Section 3 的结尾部分），我们开发启发式方法的目标是强制 routing 决策，同时将其所有考虑因素都变为最佳。因此，剩下的就是为车辆适当分配订单。

本文的组织结构如下。在对下一节的相关研究进行回顾后，FB-MRLP 将在第 3 节中陈述和制定。启发式算法在 Section 4 中介绍。第 5 节专门评估改编算法的效率。第 6 节介绍了对未来研究人员的结论和建议。

2. 文献综述


在本节中，我们首先简要回顾了与汽车行业零件物流相关的文献。Nemoto 和 Rothengatter （2012） 研究了循环取货在绿色物流中的潜力，其中介绍了三家汽车公司的例子，即丰田、Webasto 和奥迪。另一项研究是 Gyulai et al. （2013），其中提出了一种针对车间物流中的循环取货问题的本地搜索算法。Mei et al. （2017） 考虑了一家汽车零部件公司选择正确循环取货路线的问题。他们建立了一个数学模型，介绍如何根据时间窗口约束来优化循环取货路线。他们为解决问题编写的程序制定了八条接送路线方案。

Chuah 和 Yingling （2005） 研究了 JIT 供应概念，其中提出了一种基于时间窗的车辆路线问题的循环取货物流数学公式。为了解决这个问题，提出了一种列生成方法和禁忌搜索算法。Du， Wang， and Lu （2007） 分析了用于提供循环取货服务的实时车辆调度系统。它由 7 个模块组成，这些模块可以管理数据、对实时变化做出反应并高效创建解决方案。实验表明，最佳拟合算法和 2-exchange 算法分别是初始车辆调度和路线间改进的最佳算法。Güner、Murat 和 Chinnam （2017） 考虑在站点之间的动态路线中找到静态且稳健的重复循环牛奶线之旅。由于网络中经常出现拥塞，因此旅行时间是随机的并且与时间相关。作者使用随机动态规划 （SDP） 为每对站点生成动态路由策略 （DRP），以查找每对站点的行程时间分布。还提出了另一种 SDP 公式来构建稳健的旅行。他们表示，当使用历史流量数据在模拟网络中测试算法时，他们的结果是有希望的。Aragão、Novaes 和 Luna （2019） 评估了基于智能体的动态车辆路线公式中的协作策略，其中车辆被分配到 OEM 供应商那里取件和零件。他们使用车队的服务级别和平均每日运营成本标准来选择特定的协作策略。 他们的方法使我们能够了解分布式决策的功能，有助于采用运输运营的自主控制方法。提出了一个数学模型，目的是最大限度地降低伊朗汽车制造商的运输和库存成本（Sadjadi、Jafari 和 Amini，2009 年）。然后，比较了 15 个实例问题的精确解决方案、遗传算法 （GA） 和实际结果，其中 GA 提供的解决方案提供了介于 和 25 % 25 % 25%25 \% 之间的 15 % 15 % 15%15 \% 改进。此外，Jafari-Eskandari 等人（2009 年）为这个问题设计了一种稳健的优化方法。Nemoto、Hayashi 和 Hashimoto （2010） 调查了丰田在循环取货物流方面的零部件采购状况。据透露，循环取货物流的实施降低了泰国城市地区的运输成本并改善了交通状况。Hosseini、Shirazi 和 Ghomi （2014） 在直接发货和循环取货网络中提出了一种数学公式和一种和谐搜索算法。感兴趣的读者可以参考 Boysen 等人（2015 年），其中对汽车行业的零件物流进行了回顾。

循环取线物流的核心是通过物流网络取货和交付零件和产品的配送功能。因此，与运输和物流相关的一个有趣的研究领域是取货和送货问题 （PDP）。PDP 关注的是以满足运输请求的方式形成路线，其中每个请求都有起点和目的地，以及其他特征，例如大小和重量。另一方面，循环取货物流是一种将来自不同供应商的货物进行整合的方法。通过循环取货方法，将车辆送到多个供应商处取件。由于车辆利用率更高，这导致运输成本降低。

作为车辆路径问题的一种变体，有一些论文回顾了 PDP，它们是 Berbeglia 等人 （2007）、Berbeglia、Cordeeau 和 Laporte （2010） 以及 Parragh、Doerner 和 Hartl （2008a， 2008b）。研究人员还提出了精确和启发式算法。例如，Ropke 和 Cordeau （2009） 为具有时间窗口的 PDP 开发了一种 branch-and-cut-and-price 算法。在 Ropke、Cordeau 和 Laporte （2007） 中，一些有效不等式族被提出并用于分支和切割算法中，用于求解 PDPTW。Baldacci、Bartolini 和 Mingozzi （2011） 提出了一种基于集合分区公式的精确算法。为具有时间窗口和加载约束的 PDP 提出了数学公式和分支切割和价格算法。Veenstra 等人（2017 年）引入了具有时间窗口和处理作的 PDP。此外，还提出了一种 branch-price-and-cut 算法用于路由。Benavent 等人（2015 年）为具有 LIFO 约束的 PDP 提出了两种数学公式。此外，他们还设计了 branch-and-cut 算法和 Tabu 搜索，并分析了它们在测试实例上的性能。Cherkesly 等人（2015 年）引入了时间窗口和多个堆栈的取货和交付问题。提出了三种精确的算法，即非 LIFO、LIFO 和混合分支价格和削减算法。使用改编自 PDPTW 实例的实例测试了算法的性能，其中算法的混合版本可以更快地产生更好的结果。Soleimani、Chaharlang 和 Ghaderi （2018） 为退回再制造产品的取货和交付问题提出了一个数学公式，目的是最大限度地减少空气污染和燃料成本。 该模型使用报纸分发和收集的真实案例研究数据进行了验证。

对于无法有效求解至最优的大尺寸问题，还提出了元启发式算法。例如，Li 和 Lim （2003） 中的禁忌嵌入模拟退火 （SA） 算法，在多次迭代没有改进后，搜索从最佳解决方案重新开始。对于具有软时间窗口约束的多目标车辆路径问题，Yan 和 Zhang （2015） 提出了一种改进的遗传算法方法。他们还提出了一个数学模型，以最小化总运输成本（包括直接运输成本、早期的额外库存成本和延迟的罚款成本）和所需的车队规模。Wang 和 Chen （2012） 提出了一种具有各种交叉和突变运算符的遗传算法，用于解决具有时间窗的同时交付和拾取问题。与基本的遗传算法相比，所提出的遗传算法可以找到更好的解决方案。对于 PDPTW，比较了三种方法，即遗传算法、模拟退火算法

Hosny 和 Mumford （2010） 除了提出智能邻里移动外，还提出了爬山算法。Belmecheri 等人（2013 年）考虑了 VRP 中具有时间窗口的车辆异质性和混合回程，并提出了一种带有本地搜索的粒子群优化 （PSO） 算法来解决这个问题。将该算法应用于修改后的 VRPTW 测试实例，显示出其良好的性能。Cherkesly、Desaulniers 和 Laporte （2015） 提出了一种结合本地搜索（路线间、路线内和扰动运算符）的遗传算法，并研究了它在测试实例上的作用。Mahmoudi 和 周 （2016） 为具有取货和交付以及时间窗口的车辆路径问题提出了一种新的多商品网络流公式。他们提出了一种前向动态规划求解算法和一种基于拉格朗日松弛的方法。Abbasi-Pooya 和 Husseinzadeh Kashan （2017） 基于 PDP 对直升机路线问题进行了建模，并提出了一种分组进化策略算法来解决问题。Ting 等人（2017 年）研究了多车辆选择性取货和交付问题 （MVSPDP）。它们在公式中包括车辆容量和距离限制。提出了 GA 、 TS 和 SS 三种算法，并在解决容量 VRP 的问题实例中进行了比较。Männel 和 Bortfeldt （2017） 考虑了不允许重新加载的具有三维加载约束 （3L-PDP） 的 PDP。他们提出了一种由打包过程和大型邻域过程形成的混合算法来解决这个问题。Bettinelli et al. （2018） 研究了时间窗口和同步的 MultiTrip Pickup and Delivery 问题。 他们为该问题提出了一个整数线性规划公式和一个 branch-and-cut-and-price 算法。Reil、Bortfeldt 和 Mönch （2018） 考虑了车辆路径问题的不同变体，包括回程和时间窗口以及 3D 加载考虑因素。他们设计了一种基于打包先路由后方法的两阶段算法。该算法在基准测试实例和新生成实例上的应用证明了该算法的有效性。表 1 总结了一些回顾的研究。表 1 总结了诸如分割负载考虑、车辆的均匀性或异质性、时间窗口考虑和数学公式等特征。与商品相关的附带限制条件是指商品的包装、商品与车辆之间以及商品之间的兼容性等。

综上所述，从文献综述中，我们发现循环取货物流的规划和调度是车辆路径问题的主要应用之一。大多数调查循环线物流的审查研究都认为物流运营执行取货服务，在不同的供应商场所收集零部件，然后以准时制计划将它们运送到汽车制造商/装配厂;作我们将其称为 forward flow。然而，物流最重要的功能之一是包装管理，其中托盘的旋转（例如多次使用的金属托盘）至关重要，因此管理从汽车制造商/装配厂调度给供应商的空托盘的后向流动与管理装满的托盘的前进流同样重要。同时规划托盘的正向和反向流动，需要从 VRP 模型转向 VRPDP 模型。根据这些理由，我们对取货和送货模式进行了审查。文献中考虑的许多模型分类如下：

（1） 可分割配送和取货 （VRPDDP） 的车辆路线问题，其中每个客户可能都有取货和配送需求，必须由有容量的车辆来满足。如果有益，取件和配送数量可以分两次单独访问。

（2） 同时取货和送货的车辆路线问题 （VRPSPD），其中车辆不仅需要将货物运送给客户，还需要在客户地点提取一些货物。

（3） 集群回程 （VRPCB） 的车辆路径问题，其中每个客户要么是线路传输客户，要么是回程客户，并且在每条路由中，必须在任何回程客户之前访问所有线路传输客户。如果顺序是任意的，则存在混合 linehauls 和 backhauls （VRPMLB） 的车辆路径问题

本研究中考虑的取货和送货类型是上述类型的混合。供应商和汽车制造商/装配厂可以是长途或回程，也可以同时进行两者兼而有之。对于供应商节点，我们有 VRPCB 强制的假设。在将空托拍交付给供应商之前，必须在每条路线的供应商处提取已装满的托拍。对于汽车制造商/装配厂，我们有某种 VRPSPD 假设，其中交付装满的托盘并提取空托盘。但是，与典型的 VRPDP 不同，在我们的问题中，每个节点可以被不同的车辆多次访问。此外，在每个路由中，访问节点都有优先约束。参考上述理由，本文考虑的现实世界汽车零部件循环取货物流网络规划问题在其假设方面是独一无二的（更多假设和考虑见第 3 节）。因此，我们将提出一个详细的数学公式和合适的解决方案来解决这个问题。

现有广泛使用的构造性启发式方法，例如众所周知的 Saving 方法或 GAP 方法，无法考虑所有施加的约束（例如异构队列、订单兼容性、时间窗口、访问节点的优先约束等）。此外，元启发式算法中使用的约束处理方法在消除不可行性方面效率低下，因为有大量的约束，其数量随着问题大小的增加而增加。因此，这些算法的运算符的设计方式应使所有约束都由表示方案或

表 1.文献和当前研究摘要。
裁判。 问题 个案研究 # 仓库 分流负载 # 产品 Het.或 Hom。车辆 TW

与产品相关的约束
Constraint Related to Products| Constraint | | :--- | | Related to | | Products |
 配方 解决方法

Ropke、Cordeau 和 Laporte （2007）		 PDPTW - 单 不允许 单 磡。 ✓ ✓ ✓\checkmark - ✓ ✓ ✓\checkmark
分支和切割算法

Ai 和 Kachitvichyanukul （2009）		 VRPSPD - 单 不允许 单 磡。 ✓ ✓ ✓\checkmark - ✓ ✓ ✓\checkmark PSO
Hosny 和 Mumford （2010） PDPTW - 单 不允许 单 磡。 ✓ ✓ ✓\checkmark - ✓ ✓ ✓\checkmark GA、SA、HC

Baldacci、Bartolini 和 Mingozzi （2011）		 PDPTW - 单 不允许 单 磡。 ✓ ✓ ✓\checkmark - ✓ ✓ ✓\checkmark
一种基于集合分区的算法，通过割平面得到加强
Wang 和 Chen （2012） SDPPTW - 单 不允许 单 Het. ✓ ✓ ✓\checkmark - ✓ ✓ ✓\checkmark GA

Goksal、Karaoglan 和 Altiparmak （2013）		 VRPSPD - 单 不允许 单 Het. - - - 混合 PSO
Belmecheri 等人 （2013） HVRPMBTW - 单 不允许 单 Het. ✓ ✓ ✓\checkmark - ✓ ✓ ✓\checkmark PSO
Yu 和 Lin （2014） LRPSPD - 倍数 不允许 单 磡。 - - - 多启动 SA

Salhi、Imran 和 Wassan （2014）		 MDHFVRP - 倍数 不允许 单 Het. - - ✓ ✓ ✓\checkmark VNS

Chen， Li， and Liu （2014年）		 UPDPSL - 单 允许 倍数 磡。 ✓ ✓ ✓\checkmark - ✓ ✓ ✓\checkmark VNS
Cherkesly 等人（2015 年） PDPTWL - 单 不允许 单 Het. ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark
分支价格和切割算法

Cherkesly、Desaulniers 和 Laporte （2015）		 PDPTWL - 单 不允许 单 磡。 ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark - GA
Benavent 等人 （2015） PDPLT - 单 不允许 单 磡。 - ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark 分支和切割算法
马哈茂迪和周 （2016） VRPPDTW - 单 不允许 倍数 Het. ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark
拉格朗日弛豫程序
Ting 等人 （2017） MVSPDP - 单 不允许 单 磡。 - - ✓ ✓ ✓\checkmark TS、GA、SS

Männel 和 Bortfeldt （2017）		 3L-PDP - 单 不允许 单 磡。 ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark -
混合包装路由算法
Veenstra 等人 （2017） PDPTWHO - 单 不允许 单 磡。 ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark
分支价格和切割算法

Soleimani、Chaharlang 和 Ghaderi （2018）		 GVRP ✓ ✓ ✓\checkmark 倍数 不允许 倍数 Het. - - ✓ ✓ ✓\checkmark -
Bettinelli 等人 （2018） MT-PDTWS - 单 不允许 单 磡。 ✓ ✓ ✓\checkmark - ✓ ✓ ✓\checkmark
分支和切割和价格算法

Reil、Bortfeldt 和 Mönch （2018）		 3L-VRPBTW - 单 不允许 单 磡。 ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark -
先打包、先布线、后进货的方法
当前研究 循环取货问题 ✓ ✓ ✓\checkmark 虚拟 允许大订单 倍数 Het. ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark
基于相似性的 First-Fit/Best-Fit 和 GES 算法

3L-PDP：具有 3 维加载约束的取货和配送问题
PDPTW：时间窗口的取件和递送问题

3L-VRPBTW：回程和时间窗口的车辆路径问题
PDPTWL：时间窗口和加载约束的取件和交货问题

GVRP：绿色车辆路径问题
SDPPTW：时间窗口的同时送达和取件问题

HVRPMBTW：具有异构队列、混合回程和时间窗口的 VRP
UPDPSL：分担货物的未成对取货和送货问题

LRPSPD：同时取货和送货的位置路由问题
VRPPDTW：具有取件和配送以及时间窗口的 VRP

MT-PDTWS：时间窗口和同步的多程取货和配送问题
VRPSPD：同时取货和配送的车辆路径问题

MVSPDP：多车辆选择性取货和配送问题		 SA：模拟退火

PDPLT：具有 LIFO 约束和最长时间的多车取货和交付问题		 SS：分散搜索

ALNS：自适应大邻域搜索		 TS： 禁忌搜索
GA：遗传算法
VND：可变邻里血统

GES：分组进化策略
VNS：可变邻域搜索

GRASP：贪婪随机自适应搜索程序
PSO：粒子群优化算法

HC：Hill Climbing 启发式
Ref. Problem Case Study # of Depots Split Load # of Products Het. or Hom. Vehicles TW "Constraint Related to Products" Formulation Solution Method Ropke, Cordeau, and Laporte (2007) PDPTW - Single Not Allowed Single Hom. ✓ - ✓ Branch-and-cut algorithms Ai and Kachitvichyanukul (2009) VRPSPD - Single Not Allowed Single Hom. ✓ - ✓ PSO Hosny and Mumford (2010) PDPTW - Single Not Allowed Single Hom. ✓ - ✓ GA, SA, HC Baldacci, Bartolini, and Mingozzi (2011) PDPTW - Single Not Allowed Single Hom. ✓ - ✓ A set-partitioning-based algorithm strengthened by cuts Wang and Chen (2012) SDPPTW - Single Not Allowed Single Het. ✓ - ✓ GA Goksal, Karaoglan, and Altiparmak (2013) VRPSPD - Single Not Allowed Single Het. - - - Hybrid PSO Belmecheri et al. (2013) HVRPMBTW - Single Not Allowed Single Het. ✓ - ✓ PSO Yu and Lin (2014) LRPSPD - Multiple Not Allowed Single Hom. - - - Multi-start SA Salhi, Imran, and Wassan (2014) MDHFVRP - Multiple Not Allowed Single Het. - - ✓ VNS Chen, Li, and Liu (2014) UPDPSL - Single Allowed Multiple Hom. ✓ - ✓ VNS Cherkesly et al. (2015) PDPTWL - Single Not Allowed Single Het. ✓ ✓ ✓ Branch-price-and-cut algorithms Cherkesly, Desaulniers, and Laporte (2015) PDPTWL - Single Not Allowed Single Hom. ✓ ✓ - GA Benavent et al. (2015) PDPLT - Single Not Allowed Single Hom. - ✓ ✓ Branch-and-cut algorithm Mahmoudi and Zhou (2016) VRPPDTW - Single Not Allowed Multiple Het. ✓ ✓ ✓ A Lagrangian relaxation procedure Ting et al. (2017) MVSPDP - Single Not Allowed Single Hom. - - ✓ TS, GA, SS Männel and Bortfeldt (2017) 3L-PDP - Single Not Allowed Single Hom. ✓ ✓ - A hybrid packing-routing algorithm Veenstra et al. (2017) PDPTWHO - Single Not Allowed Single Hom. ✓ ✓ ✓ Branch-price-and-cut algorithms Soleimani, Chaharlang, and Ghaderi (2018) GVRP ✓ Multiple Not Allowed Multiple Het. - - ✓ - Bettinelli et al. (2018) MT-PDTWS - Single Not Allowed Single Hom. ✓ - ✓ Branch-and-cut-and-price algorithm Reil, Bortfeldt, and Mönch (2018) 3L-VRPBTW - Single Not Allowed Single Hom. ✓ ✓ - A packing-first-routing-second approach The current study Milk-run Problem ✓ Dummy Allowed for big orders Multiple Het. ✓ ✓ ✓ Similarity-Based First-Fit/Best-Fit and GES algorithms 3L-PDP: Pickup and Delivery Problem with 3-Dimensional Loading constraints PDPTW: Pickup and Delivery Problem with Time Windows 3L-VRPBTW: Vehicle Routing Problem with Backhauls and Time Windows PDPTWL: Pickup and Delivery Problem with Time Windows and Loading constraints GVRP: Green Vehicle Routing Problem SDPPTW: Simultaneous Delivery and Pickup Problem with Time Windows HVRPMBTW: VRP with Heterogeneous fleet, Mixed Backhauls, and Time Windows UPDPSL: Unpaired Pickup and Delivery Problem with Split Loads LRPSPD: Location Routing Problem with Simultaneous Pickup and Delivery VRPPDTW: VRP with Pickup and Delivery and Time Windows MT-PDTWS: Multi-Trip Pickup and Delivery problem with Time Windows and Synchronisation VRPSPD: Vehicle Routing Problem with Simultaneous Pickup and Delivery MVSPDP: Multi-Vehicle Selective Pickup and Delivery Problem SA: Simulated Annealing PDPLT: Multiple Vehicle Pickup and Delivery Problem with LIFO constraints and Maximum Time SS: Scatter Search ALNS: Adaptive Large Neighbourhood Search TS: Tabu Search GA: Genetic Algorithm VND: Variable Neighbourhood Descent GES: Grouping Evolution Strategy VNS: Variable Neighbourhood Search GRASP: Greedy Randomised Adaptive Search Procedure PSO: Particle Swarm Optimisation algorithm HC: Hill Climbing heuristic | Ref. | Problem | Case Study | # of Depots | Split Load | # of Products | Het. or Hom. Vehicles | TW | Constraint <br> Related to <br> Products | Formulation | Solution Method | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | Ropke, Cordeau, and Laporte (2007) | PDPTW | - | Single | Not Allowed | Single | Hom. | $\checkmark$ | - | $\checkmark$ | Branch-and-cut algorithms | | Ai and Kachitvichyanukul (2009) | VRPSPD | - | Single | Not Allowed | Single | Hom. | $\checkmark$ | - | $\checkmark$ | PSO | | Hosny and Mumford (2010) | PDPTW | - | Single | Not Allowed | Single | Hom. | $\checkmark$ | - | $\checkmark$ | GA, SA, HC | | Baldacci, Bartolini, and Mingozzi (2011) | PDPTW | - | Single | Not Allowed | Single | Hom. | $\checkmark$ | - | $\checkmark$ | A set-partitioning-based algorithm strengthened by cuts | | Wang and Chen (2012) | SDPPTW | - | Single | Not Allowed | Single | Het. | $\checkmark$ | - | $\checkmark$ | GA | | Goksal, Karaoglan, and Altiparmak (2013) | VRPSPD | - | Single | Not Allowed | Single | Het. | - | - | - | Hybrid PSO | | Belmecheri et al. (2013) | HVRPMBTW | - | Single | Not Allowed | Single | Het. | $\checkmark$ | - | $\checkmark$ | PSO | | Yu and Lin (2014) | LRPSPD | - | Multiple | Not Allowed | Single | Hom. | - | - | - | Multi-start SA | | Salhi, Imran, and Wassan (2014) | MDHFVRP | - | Multiple | Not Allowed | Single | Het. | - | - | $\checkmark$ | VNS | | Chen, Li, and Liu (2014) | UPDPSL | - | Single | Allowed | Multiple | Hom. | $\checkmark$ | - | $\checkmark$ | VNS | | Cherkesly et al. (2015) | PDPTWL | - | Single | Not Allowed | Single | Het. | $\checkmark$ | $\checkmark$ | $\checkmark$ | Branch-price-and-cut algorithms | | Cherkesly, Desaulniers, and Laporte (2015) | PDPTWL | - | Single | Not Allowed | Single | Hom. | $\checkmark$ | $\checkmark$ | - | GA | | Benavent et al. (2015) | PDPLT | - | Single | Not Allowed | Single | Hom. | - | $\checkmark$ | $\checkmark$ | Branch-and-cut algorithm | | Mahmoudi and Zhou (2016) | VRPPDTW | - | Single | Not Allowed | Multiple | Het. | $\checkmark$ | $\checkmark$ | $\checkmark$ | A Lagrangian relaxation procedure | | Ting et al. (2017) | MVSPDP | - | Single | Not Allowed | Single | Hom. | - | - | $\checkmark$ | TS, GA, SS | | Männel and Bortfeldt (2017) | 3L-PDP | - | Single | Not Allowed | Single | Hom. | $\checkmark$ | $\checkmark$ | - | A hybrid packing-routing algorithm | | Veenstra et al. (2017) | PDPTWHO | - | Single | Not Allowed | Single | Hom. | $\checkmark$ | $\checkmark$ | $\checkmark$ | Branch-price-and-cut algorithms | | Soleimani, Chaharlang, and Ghaderi (2018) | GVRP | $\checkmark$ | Multiple | Not Allowed | Multiple | Het. | - | - | $\checkmark$ | - | | Bettinelli et al. (2018) | MT-PDTWS | - | Single | Not Allowed | Single | Hom. | $\checkmark$ | - | $\checkmark$ | Branch-and-cut-and-price algorithm | | Reil, Bortfeldt, and Mönch (2018) | 3L-VRPBTW | - | Single | Not Allowed | Single | Hom. | $\checkmark$ | $\checkmark$ | - | A packing-first-routing-second approach | | The current study | Milk-run Problem | $\checkmark$ | Dummy | Allowed for big orders | Multiple | Het. | $\checkmark$ | $\checkmark$ | $\checkmark$ | Similarity-Based First-Fit/Best-Fit and GES algorithms | | 3L-PDP: Pickup and Delivery Problem with 3-Dimensional Loading constraints | | | | | | PDPTW: Pickup and Delivery Problem with Time Windows | | | | | | 3L-VRPBTW: Vehicle Routing Problem with Backhauls and Time Windows | | | | | | PDPTWL: Pickup and Delivery Problem with Time Windows and Loading constraints | | | | | | GVRP: Green Vehicle Routing Problem | | | | | | SDPPTW: Simultaneous Delivery and Pickup Problem with Time Windows | | | | | | HVRPMBTW: VRP with Heterogeneous fleet, Mixed Backhauls, and Time Windows | | | | | | UPDPSL: Unpaired Pickup and Delivery Problem with Split Loads | | | | | | LRPSPD: Location Routing Problem with Simultaneous Pickup and Delivery | | | | | | VRPPDTW: VRP with Pickup and Delivery and Time Windows | | | | | | MT-PDTWS: Multi-Trip Pickup and Delivery problem with Time Windows and Synchronisation | | | | | | VRPSPD: Vehicle Routing Problem with Simultaneous Pickup and Delivery | | | | | | MVSPDP: Multi-Vehicle Selective Pickup and Delivery Problem | | | | | | SA: Simulated Annealing | | | | | | PDPLT: Multiple Vehicle Pickup and Delivery Problem with LIFO constraints and Maximum Time | | | | | | SS: Scatter Search | | | | | | ALNS: Adaptive Large Neighbourhood Search | | | | | | TS: Tabu Search | | | | | | GA: Genetic Algorithm | | | | | | VND: Variable Neighbourhood Descent | | | | | | GES: Grouping Evolution Strategy | | | | | | VNS: Variable Neighbourhood Search | | | | | | GRASP: Greedy Randomised Adaptive Search Procedure | | | | | | PSO: Particle Swarm Optimisation algorithm | | | | | | HC: Hill Climbing heuristic | | | | | | | | | | |

修复/修改方法。我们引入所提出的启发式方法的理由是使用两阶段方法，该方法通过最佳求解与为第一阶段变量（即车辆的顺序分配）后剩余的子问题相关的 MILP 来部分决定最佳。通过这种方式，我们解决了路线决策的可行性和最优性，给定了对车辆内容的决定。此外，在分组进化策略 （GES） 算法中使用这种启发式原理使我们能够获得解决问题的有效进化方法。


3. 问题描述和制定


物流网络在前向和后向物流流程方面的整体配置如图 1 所示。车队负责在其路线上进行前向和后向物流作。具体来说，不同订单的装满托盘必须从供应商运输到装配厂，从供应商运输到中央仓库 （CW），从 CW 运输到装配厂。这些流动形成向前的物流运动。此外，空托盘必须从装配厂运输到供应商处，从而形成逆向物流运动。

每天开始时，应制定一个计划，将零件从供应节点运输到需求节点，将空托盘从其始发节点运送到目标节点。该计划包括每辆车的路线，以及车辆从起运地运送到目的地的订单及其数量（以托盘数量表示）。目标是制定一个将运输总成本降至最低的计划。FB-MRLP 的配方使循环取货和直接发货成为可能。应开发该模型，以便考虑图 2 中描述的可能 routing。在图 2（b） 中，路线上的卡车内容物仅由空托盘组成。在图 2© 中，内容物只是装满的托盘。在图 2（d） 中，对于路线的不同部分，内容物只有装满的托盘或空托盘，或两者兼而有之。这里的挑战在于，供应商节点可能会在整个路由中被访问两次。

在模型中应考虑以下条件：

  • 有足够数量的异构车辆可用。

  • 车辆的体积和重量是有限的。

  • 已装货和空托拍订单存在时间范围限制。

  • 应考虑每个托盘的装卸时间。

  • 有些订单彼此不兼容，即它们不能在同一辆车上发货。

  • 在某些节点（例如装配厂）可以同时进行取货和交付。但对于供应商来说，取货作应该在交货作（任何订单）之前完成。

  • 如果路线某一部分的车辆内容由空托盘和装满的托盘组成（不一定是同时进行的），则应在提取空托盘之前提取装满的托盘。

  • 对于装满的托拍，车辆可以从起始节点集移动到目标节点集一次。同样，对于空托盘的分配，车辆可以从其起始节点集移动到目标节点集一次。

  • 如果订单的尺寸小于最大车辆的重量和体积容量，则无法拆分。

  • 大于最大车辆容量的订单应拆分。所有被分配运送“大”订单的车辆都应满载，除了一辆可能进行循环取货的车辆。

图 1.订单流。


a） 直接运送已填妥的托拍订单和空托拍


c） 已装满托拍订单的车辆的循环取货行程实例

b） 车辆空托盘的循环取货行程实例


d） 车辆的循环取货行程实例，用于已装满的托盘订单和空托盘

图 2.可能的路由情况。

  • 托盘的长度与车辆的宽度平行，即托盘在车辆集装箱的宽度上排成一排。此外，不同订单的托拍不能在车辆集装箱的一排装载。如果同一订单的托拍是金属托拍，则可以相互堆叠。然后，可以通过将托盘行数乘以托盘宽度来计算订单占用的卡车长度。这样，每辆车的 3D 托盘包装子问题可以转换为 1 D 箱包装问题，其中每辆车的集装箱长度与其中一个箱子容量相关联。考虑到每个订单占用的长度在不同卡车上不同，我们面临着一个 1D 箱子包装问题，箱子尺寸可变，物品尺寸随箱子类型的变化而变化。

由于供应商节点可以是零件运输的起运地和空托盘运输的目的地，因此使用虚拟节点对从供应商节点到装配节点的一次性移动以及从装配节点到供应商节点的一次性移动进行建模。通过这种方式，我们可以处理在整个路线上两次访问供应商节点的建模挑战。图 3 显示了这个概念，其中左侧的节点是供应商节点，右侧的节点是对应于供应商的虚拟节点。但是应该防止不可能的路线（被划掉的路线）。

3.1. 符号


拟议的 MILP 公式中使用的集合、参数和决策变量如下：

设置和参数

集
K 车辆套装 ( k ) ( k ) (k)(k)
I
Node's set ( i , j ) ( i , j ) (i,j)(i, j) ，其中第一个节点是 dummy
M 订单设置 ( m , m ′ ) m , m ′ (m,m^('))\left(m, m^{\prime}\right)
M B ∈ M M B ∈ M MB in MM B \in M
大订单设定 ( m b ) ( m b ) (mb)(m b)
参数

B M 1 − B M 5 B M 1 − B M 5 BM1-BM5B M 1-B M 5 五个（相对）大数 epsilon 一个小数
BM1-BM5 Five (relatively) large numbers epsilon A small number| $B M 1-B M 5$ | Five (relatively) large numbers | | :--- | :--- | | epsilon | A small number |
K Vehicle's set (k) I Node's set (i,j), where the first node is dummy M Order's set (m,m^(')) MB in M Big order's set (mb) Parameters "BM1-BM5 Five (relatively) large numbers epsilon A small number" | K | Vehicle's set $(k)$ | | :--- | :--- | | I | Node's set $(i, j)$, where the first node is dummy | | M | Order's set $\left(m, m^{\prime}\right)$ | | $M B \in M$ | Big order's set $(m b)$ | | Parameters | | | $B M 1-B M 5$ Five (relatively) large numbers <br> epsilon A small number | |

图 3.在供应商集、装配厂和虚拟供应商节点之间发货的可能性。
L k L k L_(k)L_{k}
整车 k k kk 的集装箱长度
W C k W C k WC_(k)W C_{k}
车辆 k k kk 载重量
w m w m w_(m)w_{m}
订单 m m mm 的托盘重量
N w m , k N w m , k Nw_(m,k)N w_{m, k}
可以放置在车辆 k k kk 宽度上的订单 m m mm 托盘数量
N h m , k N h m , k Nh_(m,k)N h_{m, k}
可在车辆 k k kk 中相互堆叠的订单 m m mm 托盘数量
p w m p w m pw_(m)p w_{m}
订单 m m mm 的托盘宽度
L T m L T m LT_(m)L T_{m}
订单 m m mm 的托盘装载时间
U T m U T m UT_(m)U T_{m}
订单 m m mm 的托盘卸货时间
f m f m f_(m)f_{m}
订单 m m mm 流程（托盘数量）
O m O m O_(m)O_{m}
订单 m m mm 的由来
D m D m D_(m)D_{m}
订单 m m mm 的目的地
O i ′ O i ′ O_(i)^(')O_{i}^{\prime}
来源为 node i i ii 的订单
D i ′ D i ′ D_(i)^(')D_{i}^{\prime}
目的地为 node i i ii 的订单
c o m p m , m ′ c o m p m , m ′ comp_(m,m^('))c o m p_{m, m^{\prime}}
一个参数，显示订单 m m mm 的兼容性 （=1） 或不兼容性 （=0），以及 m ′ m ′ m^(')m^{\prime}
l b m l b m lb_(m)l b_{m}
时间窗的订单取 m m mm 货下限
u b m u b m ub_(m)u b_{m}
订单 m m mm 交付的时间窗口上限
c i , j , k c i , j , k c_(i,j,k)c_{i, j, k}
车辆从节点 i i ii 到节点 j j jj 的 k k kk 运输成本
t i , j , k t i , j , k t_(i,j,k)t_{i, j, k}
车辆从节点 i i ii 到节点 j j jj 的 k k kk 运输时间
n s n s nsn s 供应商数量
n a n a nan a
装配厂数量
n k n k nkn k
车辆数量的上限
决策变量
X i , j , k X i , j , k X_(i,j,k)X_{i, j, k}
如果车辆 k k kk 从一个节点 i i ii 移动到另一个节点 j j jj ，则等于 1 的变量，否则等于 0（二进制）
Y i , k Y i , k Y_(i,k)Y_{i, k}
如果 vehicle k k kk 访问节点 i i ii ，则等于 1 的变量，否则等于 0（二进制）
Δ m , k Δ m , k Delta_(m,k)\Delta_{m, k}
如果 order m m mm 由 vehicle k k kk 拾取，则等于 1 的变量，否则等于 0（二进制）
σ m b , k σ m b , k sigma_(mb,k)\sigma_{m b, k}
如果大订单 m b m b mbm b （被拆分）由 vehicle k k kk 直接发货，则等于 1 的变量，否则为 0
P m , k P m , k P_(m,k)P_{m, k} （二进制）
D m , k D m , k D_(m,k)D_{m, k}
显示车辆 k k kk 提取的订单 m m mm 托拍数量的变量 （整数）
U i , k U i , k U_(i,k)U_{i, k}
一个变量，显示车辆 k k kk 交付的订单 m m mm 托拍数量 （整数）
W i , k W i , k W_(i,k)W_{i, k}
一个变量，显示车辆 k k kk 容器离开节点 i i ii 时占用的长度（非负）
T i , k T i , k T_(i,k)T_{i, k}
一个变量，显示车辆 k k kk 离开节点 i i ii 时车辆中托盘的总重量（非负）

显示车辆 k k kk 到达节点 i i ii 的时间的变量（非负）
L_(k) The container length of vehicle k WC_(k) Weight capacity of vehicle k w_(m) Pallet weight of order m Nw_(m,k) Number of pallets of order m that can be put on the width of vehicle k Nh_(m,k) Number of pallets of order m that can be stacked on top of each other in vehicle k pw_(m) Pallet width of order m LT_(m) Pallet loading time of order m UT_(m) Pallet unloading time of order m f_(m) The flow of order m (number of pallets) O_(m) The origin of order m D_(m) The destination of order m O_(i)^(') Orders with the origin of node i D_(i)^(') Orders with the destination of node i comp_(m,m^(')) A parameter showing the compatibility (=1) or incompatibility (=0) of orders m and m^(') lb_(m) Time window's lower bound for the pickup of order m ub_(m) Time window's upper bound for the delivery of order m c_(i,j,k) Transportation cost from node i to node j by vehicle k t_(i,j,k) Transportation time from node i to node j by vehicle k ns Number of suppliers na Number of assembly plants nk An upper bound on the number of vehicles Decision variables X_(i,j,k) A variable that equals 1 if the vehicle k moves from node i to node j, and 0 otherwise (binary) Y_(i,k) A variable that equals 1 if node i is visited by vehicle k, and 0 otherwise (binary) Delta_(m,k) A variable that equals 1 if order m is picked up by vehicle k, and 0 otherwise (binary) sigma_(mb,k) A variable that equals 1 if the big order mb (which is split) is directly shipped by vehicle k, and 0 otherwise P_(m,k) (binary) D_(m,k) A variable showing the number of pallets of order m that is picked up by vehicle k (integer) U_(i,k) A variable showing the number of pallets of order m that is delivered by vehicle k (integer) W_(i,k) A variable showing the occupied length of the container of vehicle k, when it leaves node i (nonnegative) T_(i,k) A variable showing the total weight of pallets in vehicle k when it leaves node i (nonnegative) A variable showing the time vehicle k arrives at node i (nonnegative) | $L_{k}$ | The container length of vehicle $k$ | | :--- | :--- | | $W C_{k}$ | Weight capacity of vehicle $k$ | | $w_{m}$ | Pallet weight of order $m$ | | $N w_{m, k}$ | Number of pallets of order $m$ that can be put on the width of vehicle $k$ | | $N h_{m, k}$ | Number of pallets of order $m$ that can be stacked on top of each other in vehicle $k$ | | $p w_{m}$ | Pallet width of order $m$ | | $L T_{m}$ | Pallet loading time of order $m$ | | $U T_{m}$ | Pallet unloading time of order $m$ | | $f_{m}$ | The flow of order $m$ (number of pallets) | | $O_{m}$ | The origin of order $m$ | | $D_{m}$ | The destination of order $m$ | | $O_{i}^{\prime}$ | Orders with the origin of node $i$ | | $D_{i}^{\prime}$ | Orders with the destination of node $i$ | | $c o m p_{m, m^{\prime}}$ | A parameter showing the compatibility (=1) or incompatibility (=0) of orders $m$ and $m^{\prime}$ | | $l b_{m}$ | Time window's lower bound for the pickup of order $m$ | | $u b_{m}$ | Time window's upper bound for the delivery of order $m$ | | $c_{i, j, k}$ | Transportation cost from node $i$ to node $j$ by vehicle $k$ | | $t_{i, j, k}$ | Transportation time from node $i$ to node $j$ by vehicle $k$ | | $n s$ | Number of suppliers | | $n a$ | Number of assembly plants | | $n k$ | An upper bound on the number of vehicles | | Decision variables | | | $X_{i, j, k}$ | A variable that equals 1 if the vehicle $k$ moves from node $i$ to node $j$, and 0 otherwise (binary) | | $Y_{i, k}$ | A variable that equals 1 if node $i$ is visited by vehicle $k$, and 0 otherwise (binary) | | $\Delta_{m, k}$ | A variable that equals 1 if order $m$ is picked up by vehicle $k$, and 0 otherwise (binary) | | $\sigma_{m b, k}$ | A variable that equals 1 if the big order $m b$ (which is split) is directly shipped by vehicle $k$, and 0 otherwise | | $P_{m, k}$ | (binary) | | $D_{m, k}$ | A variable showing the number of pallets of order $m$ that is picked up by vehicle $k$ (integer) | | $U_{i, k}$ | A variable showing the number of pallets of order $m$ that is delivered by vehicle $k$ (integer) | | $W_{i, k}$ | A variable showing the occupied length of the container of vehicle $k$, when it leaves node $i$ (nonnegative) | | $T_{i, k}$ | A variable showing the total weight of pallets in vehicle $k$ when it leaves node $i$ (nonnegative) | | A variable showing the time vehicle $k$ arrives at node $i$ (nonnegative) | |

表 2.逻辑依赖关系。
排 逻辑依赖关系 约束
1 1 1\mathbf{1} 如果 comp m m , m ′ = 0 → Δ m , k + Δ m ′ , k ≤ 1 comp m m , m ′ = 0 → Δ m , k + Δ m ′ , k ≤ 1 compm_(m,m^('))=0rarrDelta_(m,k)+Delta_(m^('),k) <= 1\operatorname{comp} m_{m, m^{\prime}}=0 \rightarrow \Delta_{m, k}+\Delta_{m^{\prime}, k} \leq 1 Δ m , k + Δ m ′ , k ≤ c o m p m , m ′ + 1 Δ m , k + Δ m ′ , k ≤ c o m p m , m ′ + 1 Delta_(m,k)+Delta_(m^('),k) <= comp_(m,m^('))+1\Delta_{m, k}+\Delta_{m^{\prime}, k} \leq c o m p_{m, m^{\prime}}+1
2 2 2\mathbf{2} 如果 σ m b , k = 1 → Δ m b , k = 1 σ m b , k = 1 → Δ m b , k = 1 sigma_(mb,k)=1rarrDelta_(mb,k)=1\sigma_{m b, k}=1 \rightarrow \Delta_{m b, k}=1 Δ m , k ≤ ( 1 − Δ m b , k ) + ( 1 − σ m b , k ) Δ m , k ≤ 1 − Δ m b , k + 1 − σ m b , k Delta_(m,k) <= (1-Delta_(mb,k))+(1-sigma_(mb,k))\Delta_{m, k} \leq\left(1-\Delta_{m b, k}\right)+\left(1-\sigma_{m b, k}\right)

（所有包含 mb 命令的车辆都会执行其

直接发货，除了 LTL 除外）		 σ m b , k ≤ Δ m b , k σ m b , k ≤ Δ m b , k sigma_(mb,k) <= Delta_(mb,k)\sigma_{m b, k} \leq \Delta_{m b, k}
∑ k ∈ K σ m b , k = ∑ k ∈ K Δ m b , k − 1 ∑ k ∈ K   σ m b , k = ∑ k ∈ K   Δ m b , k − 1 sum_(k in K)sigma_(mb,k)=sum_(k in K)Delta_(mb,k)-1\sum_{k \in K} \sigma_{m b, k}=\sum_{k \in K} \Delta_{m b, k}-1
Row Logical dependency Constraints 1 if compm_(m,m^('))=0rarrDelta_(m,k)+Delta_(m^('),k) <= 1 Delta_(m,k)+Delta_(m^('),k) <= comp_(m,m^('))+1 2 if sigma_(mb,k)=1rarrDelta_(mb,k)=1 Delta_(m,k) <= (1-Delta_(mb,k))+(1-sigma_(mb,k)) (All vehicles containing the pllets of order mb do their shippment directly except one that is LTL) sigma_(mb,k) <= Delta_(mb,k) sum_(k in K)sigma_(mb,k)=sum_(k in K)Delta_(mb,k)-1| Row | Logical dependency | Constraints | | :--- | :--- | :--- | | $\mathbf{1}$ | if $\operatorname{comp} m_{m, m^{\prime}}=0 \rightarrow \Delta_{m, k}+\Delta_{m^{\prime}, k} \leq 1$ | $\Delta_{m, k}+\Delta_{m^{\prime}, k} \leq c o m p_{m, m^{\prime}}+1$ | | $\mathbf{2}$ | if $\sigma_{m b, k}=1 \rightarrow \Delta_{m b, k}=1$ | $\Delta_{m, k} \leq\left(1-\Delta_{m b, k}\right)+\left(1-\sigma_{m b, k}\right)$ | | | (All vehicles containing the pllets of order mb do their | | | shippment directly except one that is LTL) | $\sigma_{m b, k} \leq \Delta_{m b, k}$ | | | | | $\sum_{k \in K} \sigma_{m b, k}=\sum_{k \in K} \Delta_{m b, k}-1$ |

在模型中应考虑一些作条件。条件可以以逻辑格式编写，并转换为要包含在公式中的约束。它们与订单托盘的兼容性和大订单的拆分有关：

  1. 如果两个订单的托拍不兼容，则它们不能位于同一辆车中（表 2 的第 1 行）。

  2. 拆分大小大于最大车辆容量的订单。这些“大”订单由整车 （FTL） 直接发货，但一辆卡车是零担运输，包含相关大订单的一些托盘，并且可以在循环取货行程中（表 2 第 2 行）。


3.3. 数学模型


使用上述符号，MILP 公式为：
Minimize ObjF = ∑ i ∈ I ∑ j ∈ I ∑ k ∈ K c i , j , k ∗ X i , j , k  Minimize ObjF  = ∑ i ∈ I   ∑ j ∈ I   ∑ k ∈ K   c i , j , k ∗ X i , j , k " Minimize ObjF "=sum_(i in I)sum_(j in I)sum_(k in K)c_(i,j,k)**X_(i,j,k)\text { Minimize ObjF }=\sum_{i \in I} \sum_{j \in I} \sum_{k \in K} c_{i, j, k} * X_{i, j, k}
s.t.

路由约束

∑ j ∈ I X 1 , j , k ≤ 1 ∀ k ∈ K ∑ i ∈ I X i , 1 , k ≤ 1 ∀ k ∈ K ∑ j ∈ I ∑ k ∈ K X 1 , j , k ≤ n k ∑ i ∈ I X i , j , k = ∑ i ∈ I X j , i , k ∀ j ∈ I , k ∈ K ∑ j ∈ I X i , j , k = Y i , k ∀ i ∈ I , k ∈ K ∑ k ∈ K Y i , k ≥ 1 ∀ i ∈ I ∑ k ∈ K X i , i , k = 0 ∀ i ∈ I X i , j , k + X j , i , k ≤ 1 ∀ i ∈ I , j ∈ I , k ∈ K ∑ ∑ ∑ i , k X i , j , k ≤ 1 ∀ k ∈ K i ≤ I , i ≠ 1 , j ∈ I , j ≥ n s + 2 i ≤ n s + 1 , j ≤ n s + n a + 1 ∑ j ∈ I   X 1 , j , k ≤ 1 ∀ k ∈ K ∑ i ∈ I   X i , 1 , k ≤ 1 ∀ k ∈ K ∑ j ∈ I   ∑ k ∈ K   X 1 , j , k ≤ n k ∑ i ∈ I   X i , j , k = ∑ i ∈ I   X j , i , k ∀ j ∈ I , k ∈ K ∑ j ∈ I   X i , j , k = Y i , k ∀ i ∈ I , k ∈ K ∑ k ∈ K   Y i , k ≥ 1 ∀ i ∈ I ∑ k ∈ K   X i , i , k = 0 ∀ i ∈ I X i , j , k + X j , i , k ≤ 1 ∀ i ∈ I , j ∈ I , k ∈ K ∑ ∑ ∑ i , k   X i , j , k ≤ 1 ∀ k ∈ K i ≤ I , i ≠ 1 , j ∈ I , j ≥ n s + 2 i ≤ n s + 1 , j ≤ n s + n a + 1 {:[sum_(j in I)X_(1,j,k) <= 1quad AA k in K],[sum_(i in I)X_(i,1,k) <= 1quad AA k in K],[sum_(j in I)sum_(k in K)X_(1,j,k) <= nk],[sum_(i in I)X_(i,j,k)=sum_(i in I)X_(j,i,k)quad AA j in I","k in K],[sum_(j in I)X_(i,j,k)=Y_(i,k)quad AA i in I","k in K],[sum_(k in K)Y_(i,k) >= 1quad AA i in I],[sum_(k in K)X_(i,i,k)=0quad AA i in I],[X_(i,j,k)+X_(j,i,k) <= 1quad AA i in I","j in I","k in K],[ sum sumquadsum_(i,k)quadX_(i,j,k) <= 1quad AA k in K],[i <= I","i!=1","quad j in I","j >= ns+2],[i <= ns+1quad","j <= ns+na+1]:}\begin{aligned} & \sum_{j \in I} X_{1, j, k} \leq 1 \quad \forall k \in K \\ & \sum_{i \in I} X_{i, 1, k} \leq 1 \quad \forall k \in K \\ & \sum_{j \in I} \sum_{k \in K} X_{1, j, k} \leq n k \\ & \sum_{i \in I} X_{i, j, k}=\sum_{i \in I} X_{j, i, k} \quad \forall j \in I, k \in K \\ & \sum_{j \in I} X_{i, j, k}=Y_{i, k} \quad \forall i \in I, k \in K \\ & \sum_{k \in K} Y_{i, k} \geq 1 \quad \forall i \in I \\ & \sum_{k \in K} X_{i, i, k}=0 \quad \forall i \in I \\ & X_{i, j, k}+X_{j, i, k} \leq 1 \quad \forall i \in I, j \in I, k \in K \\ & \sum \sum \quad \sum_{i, k} \quad X_{i, j, k} \leq 1 \quad \forall k \in K \\ & i \leq I, i \neq 1, \quad j \in I, j \geq n s+2 \\ & i \leq n s+1 \quad, j \leq n s+n a+1 \end{aligned}
∑ X i , j , k ≤ 1 ∀ k ∈ K i ∈ I , i ≥ n s + 2 , j ∈ I , i ≤ n s + n a + 1 j ≥ n s + n a + 2 ∑ i ∈ I , ∑ j ∈ I , j ≠ 1 , X i , j , k = 0 ∀ k ∈ K i ≥ n s + n a + 2 j ≤ n s + 1 ∑ i ∈ I , i ≠ 1 , ∑ j ∈ I , X i , j , k = 0 ∀ k ∈ K i ≤ n s + 1 j ≥ n s + n a + 2 ∑ X i , j , k = 0 ∀ k ∈ K i ∈ I , i ≥ n s + 2 , j ∈ I , j ≠ 1 , i ≤ n s + n a + 1 j ≤ n s + 1 ∑ i ∈ I , ∑ j ∈ I , j ≥ n s + 2 , X i , j , k = 0 ∀ k ∈ K i ≥ n s + n a + 2 j ≤ n s + n a + 1 ∑ X i , j , k ≤ 1 ∀ k ∈ K i ∈ I , i ≥ n s + 2 , j ∈ I , i ≤ n s + n a + 1 j ≥ n s + n a + 2 ∑ i ∈ I ,   ∑ j ∈ I , j ≠ 1 ,   X i , j , k = 0 ∀ k ∈ K i ≥ n s + n a + 2 j ≤ n s + 1 ∑ i ∈ I , i ≠ 1 ,   ∑ j ∈ I ,   X i , j , k = 0 ∀ k ∈ K i ≤ n s + 1 j ≥ n s + n a + 2 ∑ X i , j , k = 0 ∀ k ∈ K i ∈ I , i ≥ n s + 2 , j ∈ I , j ≠ 1 , i ≤ n s + n a + 1 j ≤ n s + 1 ∑ i ∈ I ,   ∑ j ∈ I , j ≥ n s + 2 ,   X i , j , k = 0 ∀ k ∈ K i ≥ n s + n a + 2 j ≤ n s + n a + 1 {:[ sumquadX_(i,j,k) <= 1quad AA k in K],[i in I","i >= ns+2","quad j in I","],[i <= ns+na+1quad j >= ns+na+2],[sum_(i in I,)sum_(j in I,j!=1,)X_(i,j,k)=0quad AA k in K],[i >= ns+na+2quad j <= ns+1],[sum_(i in I,i!=1,)sum_(j in I,)X_(i,j,k)=0quad AA k in K],[i <= ns+1quad j >= ns+na+2],[ sumquadX_(i,j,k)=0quad AA k in K],[i in I","i >= ns+2","quad j in I","j!=1","],[i <= ns+na+1quad j <= ns+1],[sum_(i in I,)sum_(j in I,j >= ns+2,)X_(i,j,k)=0quad AA k in K],[i >= ns+na+2quad j <= ns+na+1]:}\begin{aligned} & \sum \quad X_{i, j, k} \leq 1 \quad \forall k \in K \\ & i \in I, i \geq n s+2, \quad j \in I, \\ & i \leq n s+n a+1 \quad j \geq n s+n a+2 \\ & \sum_{i \in I,} \sum_{j \in I, j \neq 1,} X_{i, j, k}=0 \quad \forall k \in K \\ & i \geq n s+n a+2 \quad j \leq n s+1 \\ & \sum_{i \in I, i \neq 1,} \sum_{j \in I,} X_{i, j, k}=0 \quad \forall k \in K \\ & i \leq n s+1 \quad j \geq n s+n a+2 \\ & \sum \quad X_{i, j, k}=0 \quad \forall k \in K \\ & i \in I, i \geq n s+2, \quad j \in I, j \neq 1, \\ & i \leq n s+n a+1 \quad j \leq n s+1 \\ & \sum_{i \in I,} \sum_{j \in I, j \geq n s+2,} X_{i, j, k}=0 \quad \forall k \in K \\ & i \geq n s+n a+2 \quad j \leq n s+n a+1 \end{aligned}


取货和交货约束

P m , k ≤ f m ∗ Y i , k ∀ i ∈ I , i ≠ 1 , k ∈ K , m ∈ O i ′ ∑ k ∈ K P m , k = f m ∀ m ∈ M D m , k ≤ f m ∗ Y i , k ∀ i ∈ I , i ≠ 1 , k ∈ K , m ∈ D i ′ P m , k = D m , k ∀ k ∈ K , m ∈ M ∑ m ∈ O i ′ P m , k + ∑ m ∈ D i ′ D m , k ≥ Y i , k ∀ i ∈ I , i ≠ 1 , k ∈ K P m , k ≤ f m ∗ Y i , k ∀ i ∈ I , i ≠ 1 , k ∈ K , m ∈ O i ′ ∑ k ∈ K   P m , k = f m ∀ m ∈ M D m , k ≤ f m ∗ Y i , k ∀ i ∈ I , i ≠ 1 , k ∈ K , m ∈ D i ′ P m , k = D m , k ∀ k ∈ K , m ∈ M ∑ m ∈ O i ′   P m , k + ∑ m ∈ D i ′   D m , k ≥ Y i , k ∀ i ∈ I , i ≠ 1 , k ∈ K {:[P_(m,k) <= f_(m)**Y_(i,k)quad AA i in I","i!=1","k in K","m inO_(i)^(')],[sum_(k in K)P_(m,k)=f_(m)quad AA m in M],[D_(m,k) <= f_(m)**Y_(i,k)quad AA i in I","i!=1","k in K","m inD_(i)^(')],[P_(m,k)=D_(m,k)quad AA k in K","m in M],[sum_(m inO_(i)^('))P_(m,k)+sum_(m inD_(i)^('))D_(m,k) >= Y_(i,k)quad AA i in I","i!=1","k in K]:}\begin{aligned} P_{m, k} & \leq f_{m} * Y_{i, k} \quad \forall i \in I, i \neq 1, k \in K, m \in O_{i}^{\prime} \\ \sum_{k \in K} P_{m, k} & =f_{m} \quad \forall m \in M \\ D_{m, k} & \leq f_{m} * Y_{i, k} \quad \forall i \in I, i \neq 1, k \in K, m \in D_{i}^{\prime} \\ P_{m, k} & =D_{m, k} \quad \forall k \in K, m \in M \\ \sum_{m \in O_{i}^{\prime}} P_{m, k}+\sum_{m \in D_{i}^{\prime}} D_{m, k} & \geq Y_{i, k} \quad \forall i \in I, i \neq 1, k \in K \end{aligned}
U i , k + ∑ m ∈ O j ′ ⌈ P m , k N w m , k ∗ N h m , k ⌉ p w m − ∑ m ∈ D j ′ ⌈ D m , k N w m , k ∗ N h m , k ⌉ p w m ≤ U j , k + ( 1 − X i , j , k ) ∗ B M 1 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j , k ∈ K U i , k + ∑ m ∈ O j ′   P m , k N w m , k ∗ N h m , k p w m − ∑ m ∈ D j ′   D m , k N w m , k ∗ N h m , k p w m ≤ U j , k + 1 − X i , j , k ∗ B M 1 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j , k ∈ K {:[U_(i,k)+sum_(m inO_(j)^('))|~(P_(m,k))/(Nw_(m,k)**Nh_(m,k))~|pw_(m)-sum_(m inD_(j)^('))|~(D_(m,k))/(Nw_(m,k)**Nh_(m,k))~|pw_(m) <= U_(j,k)+(1-X_(i,j,k))^(**)BM1],[AA i in I","j in I","j!=1","i!=j","k in K]:}\begin{aligned} & U_{i, k}+\sum_{m \in O_{j}^{\prime}}\left\lceil\frac{P_{m, k}}{N w_{m, k} * N h_{m, k}}\right\rceil p w_{m}-\sum_{m \in D_{j}^{\prime}}\left\lceil\frac{D_{m, k}}{N w_{m, k} * N h_{m, k}}\right\rceil p w_{m} \leq U_{j, k}+\left(1-X_{i, j, k}\right)^{*} B M 1 \\ & \forall i \in I, j \in I, j \neq 1, i \neq j, k \in K \end{aligned}
U i , k ≤ L k ∀ i ∈ I , k ∈ K U i , k ≤ L k ∀ i ∈ I , k ∈ K U_(i,k) <= L_(k)quad AA i in I,k in KU_{i, k} \leq L_{k} \quad \forall i \in I, k \in K
W i , k + ∑ m ∈ O j ′ w m P m , k − ∑ m ∈ D j ′ w m D m , k ≤ W j , k + ( 1 − X i , j , k ) ∗ B M 2 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j , k ∈ K W i , k ≤ W C k ∀ i ∈ I , k ∈ K W i , k + ∑ m ∈ O j ′   w m P m , k − ∑ m ∈ D j ′   w m D m , k ≤ W j , k + 1 − X i , j , k ∗ B M 2 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j , k ∈ K W i , k ≤ W C k ∀ i ∈ I , k ∈ K {:[W_(i,k)+sum_(m inO_(j)^('))w_(m)P_(m,k)-sum_(m inD_(j)^('))w_(m)D_(m,k) <= W_(j,k)+(1-X_(i,j,k))^(**)BM2],[AA i in I","j in I","j!=1","i!=j","k in K],[quadW_(i,k) <= WC_(k)quad AA i in I","k in K]:}\begin{gathered} W_{i, k}+\sum_{m \in O_{j}^{\prime}} w_{m} P_{m, k}-\sum_{m \in D_{j}^{\prime}} w_{m} D_{m, k} \leq W_{j, k}+\left(1-X_{i, j, k}\right)^{*} B M 2 \\ \forall i \in I, j \in I, j \neq 1, i \neq j, k \in K \\ \quad W_{i, k} \leq W C_{k} \quad \forall i \in I, k \in K \end{gathered}


Pallet 兼容性约束

Δ m , k + Δ m ′ , k ≤ comp m , m ′ + 1 ∀ m ∈ M , m ′ ∈ M , k ∈ K Δ m , k + Δ m ′ , k ≤ comp m , m ′ + 1 ∀ m ∈ M , m ′ ∈ M , k ∈ K Delta_(m,k)+Delta_(m^('),k) <= comp_(m,m^('))+1quad AA m in M,m^(')in M,k in K\Delta_{m, k}+\Delta_{m^{\prime}, k} \leq \operatorname{comp}_{m, m^{\prime}}+1 \quad \forall m \in M, m^{\prime} \in M, k \in K
⌈ P m , k N w m , k ∗ N h m , k ⌉ p w m ≤ L k ∗ Δ m , k ∀ m ∈ M , k ∈ K P m , k ≥ Δ m , k ∀ m ∈ M , k ∈ K P m , k N w m , k ∗ N h m , k p w m ≤ L k ∗ Δ m , k ∀ m ∈ M , k ∈ K P m , k ≥ Δ m , k ∀ m ∈ M , k ∈ K {:[|~(P_(m,k))/(Nw_(m,k)**Nh_(m,k))~|pw_(m) <= L_(k)**Delta_(m,k)quad AA m in M","k in K],[P_(m,k) >= Delta_(m,k)quad AA m in M","k in K]:}\begin{gathered} \left\lceil\frac{P_{m, k}}{N w_{m, k} * N h_{m, k}}\right\rceil p w_{m} \leq L_{k} * \Delta_{m, k} \quad \forall m \in M, k \in K \\ P_{m, k} \geq \Delta_{m, k} \quad \forall m \in M, k \in K \end{gathered}


LTL 的 No-split 约束

∑ k ∈ K Δ m , k = 1 m ∈ M − M B ∑ k ∈ K   Δ m , k = 1 m ∈ M − M B sum_(k in K)Delta_(m,k)=1quad m in M-MB\sum_{k \in K} \Delta_{m, k}=1 \quad m \in M-M B


FTL 的拆分约束

Δ m , k ≤ ( 1 − Δ m b , k ) + ( 1 − σ m b , k ) ∀ m ∈ M , m b ∈ M B , m ≠ m b , k ∈ K σ m b , k ≤ Δ m b , k m b ∈ M B , k ∈ K ∑ k ∈ K σ m b , k = ∑ k ∈ K Δ m b , k − 1 m b ∈ M B Δ m , k ≤ 1 − Δ m b , k + 1 − σ m b , k ∀ m ∈ M , m b ∈ M B , m ≠ m b , k ∈ K σ m b , k ≤ Δ m b , k m b ∈ M B , k ∈ K ∑ k ∈ K   σ m b , k = ∑ k ∈ K   Δ m b , k − 1 m b ∈ M B {:[Delta_(m,k) <= (1-Delta_(mb,k))+(1-sigma_(mb,k))quad AA m in M","mb in MB","m!=mb","k in K],[sigma_(mb,k) <= Delta_(mb,k)quad mb in MB","k in K],[sum_(k in K)sigma_(mb,k)=sum_(k in K)Delta_(mb,k)-1quad mb in MB]:}\begin{gathered} \Delta_{m, k} \leq\left(1-\Delta_{m b, k}\right)+\left(1-\sigma_{m b, k}\right) \quad \forall m \in M, m b \in M B, m \neq m b, k \in K \\ \sigma_{m b, k} \leq \Delta_{m b, k} \quad m b \in M B, k \in K \\ \sum_{k \in K} \sigma_{m b, k}=\sum_{k \in K} \Delta_{m b, k}-1 \quad m b \in M B \end{gathered}
T i , k + ∑ m ∈ O i ′ L T m P m , k + ∑ m ∈ D i ′ U T m D m , k + t i , j , k ≤ T j , k + ( 1 − X i , j , k ) ∗ B M 3 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j , k ∈ K T j , k ≥ T i , k − ( 1 − Δ m , k ) ∗ B M 4 ∀ k ∈ K , m ∈ M , i = O m , j = D m T i , k ≥ l b m Δ m , k ∀ m ∈ M , i = O m , k ∈ K T i , k ≤ u b m + ( 1 − Δ m , k ) ∗ B M 5 ∀ m ∈ M , i = D m , k ∈ K T i , k + ∑ m ∈ O i ′   L T m P m , k + ∑ m ∈ D i ′   U T m D m , k + t i , j , k ≤ T j , k + 1 − X i , j , k ∗ B M 3 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j , k ∈ K T j , k ≥ T i , k − 1 − Δ m , k ∗ B M 4 ∀ k ∈ K , m ∈ M , i = O m , j = D m T i , k ≥ l b m Δ m , k ∀ m ∈ M , i = O m , k ∈ K T i , k ≤ u b m + 1 − Δ m , k ∗ B M 5 ∀ m ∈ M , i = D m , k ∈ K {:[T_(i,k)+sum_(m inO_(i)^('))LT_(m)P_(m,k)+sum_(m inD_(i)^('))UT_(m)D_(m,k)+t_(i,j,k) <= T_(j,k)+(1-X_(i,j,k))^(**)BM3],[AA i in I","j in I","j!=1","i!=j","k in K],[T_(j,k) >= T_(i,k)-(1-Delta_(m,k))**BM4quad AA k in K","m in M","i=O_(m)","j=D_(m)],[quadT_(i,k) >= lb_(m)Delta_(m,k)quad AA m in M","i=O_(m)","k in K],[quadT_(i,k) <= ub_(m)+(1-Delta_(m,k))**BM5quad AA m in M","i=D_(m)","k in K]:}\begin{aligned} & T_{i, k}+\sum_{m \in O_{i}^{\prime}} L T_{m} P_{m, k}+\sum_{m \in D_{i}^{\prime}} U T_{m} D_{m, k}+t_{i, j, k} \leq T_{j, k}+\left(1-X_{i, j, k}\right)^{*} B M 3 \\ & \forall i \in I, j \in I, j \neq 1, i \neq j, k \in K \\ & T_{j, k} \geq T_{i, k}-\left(1-\Delta_{m, k}\right) * B M 4 \quad \forall k \in K, m \in M, i=O_{m}, j=D_{m} \\ & \quad T_{i, k} \geq l b_{m} \Delta_{m, k} \quad \forall m \in M, i=O_{m}, k \in K \\ & \quad T_{i, k} \leq u b_{m}+\left(1-\Delta_{m, k}\right) * B M 5 \quad \forall m \in M, i=D_{m}, k \in K \end{aligned}

变量

X i , j , k , Y i , k , γ k , Δ m , k , z i , j , k , σ m b , k ∈ { 0 , 1 } ; P m , k , D m , k ∈ Z U i , k , W i , k , T i , k ≥ 0 X i , j , k , Y i , k , γ k , Δ m , k , z i , j , k , σ m b , k ∈ { 0 , 1 } ; P m , k , D m , k ∈ Z U i , k , W i , k , T i , k ≥ 0 {:[X_(i,j,k)","Y_(i,k)","gamma_(k)","Delta_(m,k)","z_(i,j,k)","sigma_(mb,k)in{0","1};P_(m,k)","D_(m,k)in Z],[quadU_(i,k)","W_(i,k)","T_(i,k) >= 0]:}\begin{aligned} & X_{i, j, k}, Y_{i, k}, \gamma_{k}, \Delta_{m, k}, z_{i, j, k}, \sigma_{m b, k} \in\{0,1\} ; P_{m, k}, D_{m, k} \in Z \\ & \quad U_{i, k}, W_{i, k}, T_{i, k} \geq 0 \end{aligned}

（1） 中的目标函数是要最小化的总运输成本。约束集 （2）-（3） 是度约束。约束集 （4） 限制车辆的数量。约束 （5） 确保路由连续性。约束 （6） 确保如果卡车访问某个节点，它应该只从该节点退出一次。约束 （7） 确保每个节点至少访问一次。约束集 （8） 和 （9） 分别防止循环和向后移动。约束集 （10） 保证车辆最多可以从供应商集移动到装配厂集一次。约束 （11） 确保车辆最多可以从装配厂移动到供应商的虚拟节点一次。约束 （12） 和 （13） 保证车辆不能分别从供应商的虚拟节点移动到供应商节点，并按相反的顺序移动。约束集 （14） 确保车辆不能从装配厂到供应商。约束 （15） 保证车辆不能从供应商的虚拟节点转到装配厂节点。约束 （16） 保证如果车辆访问某个节点并且它是订单的起点，它可以选取该订单。约束 （17） 确保拣选订单的所有托盘。约束 （18） 与 （16） 类似，但用于订单的交付。约束条件 （19） 规定，每辆车捡起的托盘数量应等于其交付的托盘数量。约束集 （20） 规定，如果车辆访问某个节点，则应从该节点提取或交付至少一个托盘。车辆容器离开每个节点时的占用长度由 （21） 计算。约束 （22） 确保车辆中占用的总长度不超过车辆集装箱的长度。 约束 （23） 和 （24） 对车辆的重量施加了与 （21） 和 （22） 类似的条件。约束集 （25） 保证车辆中不存在不兼容的停靠点。约束 （26） - （27） 分别控制最小值

以及车辆可提取的最大托拍数量。约束 （28） 确保 LTL 订单不被拆分。约束集 （29）-（31） 确保拆分那些超过最大车辆容量的订单，使它们成为 FTL，但可能是 LTL 的订单除外。约束集 （32） 计算每辆车到达节点的时间。约束 （33） 确保在其相应的交付节点之前访问每个 pickup 节点。约束 （34）-（35） 是订单的时间窗口约束。最后，变量及其类型的声明在 （36） 中给出。


3.4. 对 ceiling 函数进行划线


约束 （21） 和 （26） 中的上限函数导致模型的非线性。但是这些非线性项可以通过更改变量和向模型添加约束来线性化。为了线性化约束，变量的变化可以用作 Q m , k = ⌈ P m , k / N w m , k ∗ N h m , k ⌉ Q m , k = P m , k / N w m , k ∗ N h m , k Q_(m,k)=|~P_(m,k)//Nw_(m,k)**Nh_(m,k)~|Q_{m, k}=\left\lceil P_{m, k} / N w_{m, k} * N h_{m, k}\right\rceil 和 E m , k = ⌈ D m , k / N w m , k ∗ N h m , k ⌉ E m , k = D m , k / N w m , k ∗ N h m , k E_(m,k)=|~D_(m,k)//Nw_(m,k)**Nh_(m,k)~|E_{m, k}=\left\lceil D_{m, k} / N w_{m, k} * N h_{m, k}\right\rceil ，其中 Q m , k Q m , k Q_(m,k)Q_{m, k} 和 E m , k E m , k E_(m,k)E_{m, k} 是两个整数变量。根据性质 a ≤ ⌈ a ⌉ < a + 1 a ≤ ⌈ a ⌉ < a + 1 a <= |~a~| < a+1a \leq\lceil a\rceil<a+1 ，可以写成 （37）-（40）。输入 Q m , k Q m , k Q_(m,k)Q_{m, k} E m , k E m , k E_(m,k)E_{m, k} （21） 和 （26） 代替了天花板功能，产生了 （41） 和 （42）。因此，约束 （37）-（42） 将替换 （21） 和 （26） 以线性化模型：
P m , k N w m , k ∗ N h m , k ≤ Q m , k m ∈ M , k ∈ K Q m , k ≤ P m , k N w m , k ∗ N h m , k + 1 − ε m ∈ M , k ∈ K D m , k N w m , k ∗ N h m , k ≤ E m , k m ∈ M , k ∈ K E m , k ≤ D m , k N w m , k ∗ N h m , k + 1 − ε m ∈ M , k ∈ K U i , k + ∑ m ∈ O j ′ Q m , k ∗ p w m − ∑ m ∈ D j ′ E m , k ∗ p w m ≤ U j , k + ( 1 − X i , j , k ) ∗ B M 1 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j , k ∈ K Q m , k ∗ p w m ≤ L k ∗ Δ m , k ∀ m ∈ M , k ∈ K P m , k N w m , k ∗ N h m , k ≤ Q m , k m ∈ M , k ∈ K Q m , k ≤ P m , k N w m , k ∗ N h m , k + 1 − ε m ∈ M , k ∈ K D m , k N w m , k ∗ N h m , k ≤ E m , k m ∈ M , k ∈ K E m , k ≤ D m , k N w m , k ∗ N h m , k + 1 − ε m ∈ M , k ∈ K U i , k + ∑ m ∈ O j ′   Q m , k ∗ p w m − ∑ m ∈ D j ′   E m , k ∗ p w m ≤ U j , k + 1 − X i , j , k ∗ B M 1 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j , k ∈ K Q m , k ∗ p w m ≤ L k ∗ Δ m , k ∀ m ∈ M , k ∈ K {:[(P_(m,k))/(Nw_(m,k)**Nh_(m,k)) <= Q_(m,k)quad m in M","k in K],[Q_(m,k) <= (P_(m,k))/(Nw_(m,k)**Nh_(m,k))+1-epsiquad m in M","k in K],[(D_(m,k))/(Nw_(m,k)**Nh_(m,k)) <= E_(m,k)quad m in M","k in K],[E_(m,k) <= (D_(m,k))/(Nw_(m,k)**Nh_(m,k))+1-epsiquad m in M","k in K],[U_(i,k)+sum_(m inO_(j)^('))Q_(m,k)**pw_(m)-sum_(m inD_(j)^('))E_(m,k)**pw_(m) <= U_(j,k)+(1-X_(i,j,k))**BM1],[AA i in I","j in I","j!=1","i!=j","k in K],[Q_(m,k)**pw_(m) <= L_(k)**Delta_(m,k)quad AA m in M","k in K]:}\begin{aligned} & \frac{P_{m, k}}{N w_{m, k} * N h_{m, k}} \leq Q_{m, k} \quad m \in M, k \in K \\ & Q_{m, k} \leq \frac{P_{m, k}}{N w_{m, k} * N h_{m, k}}+1-\varepsilon \quad m \in M, k \in K \\ & \frac{D_{m, k}}{N w_{m, k} * N h_{m, k}} \leq E_{m, k} \quad m \in M, k \in K \\ & E_{m, k} \leq \frac{D_{m, k}}{N w_{m, k} * N h_{m, k}}+1-\varepsilon \quad m \in M, k \in K \\ & U_{i, k}+\sum_{m \in O_{j}^{\prime}} Q_{m, k} * p w_{m}-\sum_{m \in D_{j}^{\prime}} E_{m, k} * p w_{m} \leq U_{j, k}+\left(1-X_{i, j, k}\right) * B M 1 \\ & \forall i \in I, j \in I, j \neq 1, i \neq j, k \in K \\ & Q_{m, k} * p w_{m} \leq L_{k} * \Delta_{m, k} \quad \forall m \in M, k \in K \end{aligned}

3.5. 大 M 系数


在建议的公式中为（相对）较大的数字赋予的值非常重要。这些值不应太大或太小，以便分别防止舍入误差或不可行性。因此，应计算这些大数字值的下限。计算完成 B M 2 B M 2 BM2B M 2 ;其他值可以采用类似的方式计算。

当 X i , j , k = 0 X i , j , k = 0 X_(i,j,k)=0X_{i, j, k}=0 ， 从 （23） 中，我们有
B M 2 ≥ ( W i , k − W j , k ) + ( ∑ m ∈ O j ′ w m P m , k − ∑ m ∈ D j ′ w m D m , k ) B M 2 ≥ W i , k − W j , k + ∑ m ∈ O j ′   w m P m , k − ∑ m ∈ D j ′   w m D m , k BM2 >= (W_(i,k)-W_(j,k))+(sum_(m inO_(j)^('))w_(m)P_(m,k)-sum_(m inD_(j)^('))w_(m)D_(m,k))B M 2 \geq\left(W_{i, k}-W_{j, k}\right)+\left(\sum_{m \in O_{j}^{\prime}} w_{m} P_{m, k}-\sum_{m \in D_{j}^{\prime}} w_{m} D_{m, k}\right)

如果我们能推导出括号的最大值，我们就可以获得 的 B M 2 B M 2 BM2B M 2 下限。对于 ( W i , k − W j , k ) W i , k − W j , k (W_(i,k)-W_(j,k))\left(W_{i, k}-W_{j, k}\right) ，从 （24） 到 （36），我们可以写 0 ≤ W i , k ≤ W C k 0 ≤ W i , k ≤ W C k 0 <= W_(i,k) <= WC_(k)0 \leq W_{i, k} \leq W C_{k} 和 − W C k ≤ − W j , k ≤ 0 − W C k ≤ − W j , k ≤ 0 -WC_(k) <= -W_(j,k) <= 0-W C_{k} \leq-W_{j, k} \leq 0 。加上这两个，我们得到了
− W C k ≤ W i , k − W j , k ≤ W C k − W C k ≤ W i , k − W j , k ≤ W C k -WC_(k) <= W_(i,k)-W_(j,k) <= WC_(k)-W C_{k} \leq W_{i, k}-W_{j, k} \leq W C_{k}

另一方面， ∑ m ∈ O j ′ w m P m , k − ∑ m ∈ D j ′ w m D m , k ∑ m ∈ O j ′   w m P m , k − ∑ m ∈ D j ′   w m D m , k sum_(m inO_(j)^('))w_(m)P_(m,k)-sum_(m inD_(j)^('))w_(m)D_(m,k)\sum_{m \in O_{j}^{\prime}} w_{m} P_{m, k}-\sum_{m \in D_{j}^{\prime}} w_{m} D_{m, k} 如果所有订单的所有托盘都由车辆拾取，并且它们具有最大重量（第一个求和项），则取其最大值，第二个求和项取其最小值，即零。因此，我们可以编写
( ∑ m ∈ O j ′ w m P m , k − ∑ m ∈ D j ′ w m D m , k ) ≤ n m ∗ max ( f m ) ∗ max ( w m ) ∑ m ∈ O j ′   w m P m , k − ∑ m ∈ D j ′   w m D m , k ≤ n m ∗ max f m ∗ max w m (sum_(m inO_(j)^('))w_(m)P_(m,k)-sum_(m inD_(j)^('))w_(m)D_(m,k)) <= nm**max(f_(m))**max(w_(m))\left(\sum_{m \in O_{j}^{\prime}} w_{m} P_{m, k}-\sum_{m \in D_{j}^{\prime}} w_{m} D_{m, k}\right) \leq n m * \max \left(f_{m}\right) * \max \left(w_{m}\right)

（ n m n m nmn m 是订单数量）。从 （44） 中设置的最大值 （45） 到 （43） 中，获得 BM2 的下限。其他 Big M 值的计算和总结如下：
B M 1 = max ( L k ) + n m ∗ max ( f m ) ∗ max ( p w m ) / ( min ( N h k , m ) ∗ min ( N w k , m ) ) B M 2 = max ( W C k ) + n m ∗ max ( f m ) ∗ max ( w m ) B M 3 = max ( u b m − l b m ) + n m ∗ max ( f m ) ∗ ( max ( L T m ) + max ( U T m ) ) + max ( t i , j , k ) B M 4 = max ( u b m − l b m ) B M 5 = max ( u b m ) B M 1 = max L k + n m ∗ max f m ∗ max p w m / min N h k , m ∗ min N w k , m B M 2 = max W C k + n m ∗ max f m ∗ max w m B M 3 = max u b m − l b m + n m ∗ max f m ∗ max L T m + max U T m + max t i , j , k B M 4 = max u b m − l b m B M 5 = max u b m {:[BM1=max(L_(k))+nm**max(f_(m))**max(pw_(m))//(min(Nh_(k,m))**min(Nw_(k,m)))],[BM2=max(WC_(k))+nm**max(f_(m))**max(w_(m))],[BM3=max(ub_(m)-lb_(m))+nm**max(f_(m))**(max(LT_(m))+max(UT_(m)))+max(t_(i,j,k))],[BM4=max(ub_(m)-lb_(m))],[BM5=max(ub_(m))]:}\begin{aligned} & B M 1=\max \left(L_{k}\right)+n m * \max \left(f_{m}\right) * \max \left(p w_{m}\right) /\left(\min \left(N h_{k, m}\right) * \min \left(N w_{k, m}\right)\right) \\ & B M 2=\max \left(W C_{k}\right)+n m * \max \left(f_{m}\right) * \max \left(w_{m}\right) \\ & B M 3=\max \left(u b_{m}-l b_{m}\right)+n m * \max \left(f_{m}\right) *\left(\max \left(L T_{m}\right)+\max \left(U T_{m}\right)\right)+\max \left(t_{i, j, k}\right) \\ & B M 4=\max \left(u b_{m}-l b_{m}\right) \\ & B M 5=\max \left(u b_{m}\right) \end{aligned}

4. 解决方法


使用所提出的数学模型只能有效地求解小尺寸的 FB-MRLP 实例。对于实际问题，需要一种高效的算法。FB-MRLP 类似于分组问题，因为订单托盘将被分组到车辆中。分组问题可以定义为将多个项目划分为多个组。组中项的顺序在某些问题中是相关的，而在另一些问题中则无关紧要。分组问题的一些示例包括装箱问题、取货和交货问题以及并行机器调度 （PMS） 问题。还可以根据组数是恒定的还是可变的来对分组问题进行分类。在恒定分组问题（如 PMS 问题）中，组数（用于 PMS 问题的计算机）是恒定的。另一方面，对于变量分组问题，例如 bin 打包问题，组 （bin） 的数量是事先不知道的（Husseinzadeh Kashan、Akbari 和 Ostadi 2015）。

因此，可以采用分组启发式方法来解决 FB-MRLP。这里提出了一种启发式方法，分为两个版本，基于首次拟合和最佳拟合策略。对于大多数分组问题，最佳拟合策略和首次拟合策略通常是最简单且有效的建设性启发式方法之一。first-fit 策略始终查找可以满足当前项要求的第一个组。最佳拟合策略与最佳拟合策略的不同之处在于，它查找最适合当前项目要求的组。一旦第一拟合和最佳拟合策略都找到了合适的组，它们就会将项目分配给该组（Husseinzadeh Kashan、Akbari 和 Ostadi 2015）。

提出的建设性方法定义了一个相似性矩阵，用于解决最大权重二分匹配以确定订单序列。然后，以满足所有条件的方式将订单分配给车辆。创建可行的解决方案后，将应用两种改进启发式方法，即 Reduce 和 Merge 启发式方法。前者尝试在较小的车辆上下订单，而后者试图将两辆车的订单合并为一辆车。该算法的伪代码如下。
解决方案过程
初始化参数;
开始

（创建可行的解决方案）

确定大订单，拆分它们，并将它们分配给车辆直接发货;

使用 SBO 算法对剩余订单进行排序 （根据 4.2.1）;

应用 best-fit/first-fit 算法（根据 4.2.2/4.2.3）;

（应用改进启发式）

Apply Reduce 启发式（根据 44.3.1）;

Apply Merge 启发式（根据 4.3.2）;
结束
The solution procedure Initialise parameters; Begin (Create a feasible solution) Determine big orders, split them, and assign them to vehicles for direct shipment; Make an ordering of the remaining orders using the SBO algorithm (according to 4.2.1); Apply the best-fit/first-fit algorithm (according to 4.2.2/4.2.3); (Apply improvement heuristics) Apply Reduce heuristic (according to 44.3.1); Apply Merge heuristic (according to 4.3.2); End| The solution procedure | | :--- | | Initialise parameters; | | Begin | | (Create a feasible solution) | | Determine big orders, split them, and assign them to vehicles for direct shipment; | | Make an ordering of the remaining orders using the SBO algorithm (according to 4.2.1); | | Apply the best-fit/first-fit algorithm (according to 4.2.2/4.2.3); | | (Apply improvement heuristics) | | Apply Reduce heuristic (according to 44.3.1); | | Apply Merge heuristic (according to 4.3.2); | | End |

上述为 FB-MRLP 生成解决方案的方法是建设性的，并生成单个解决方案。我们可以在搜索方法（例如进化算法）的主体中使用此过程的某些部分来生成和评估问题的许多解决方案。遵循这样的策略，我们在第 4-4 节中开发了一个分组进化策略算法，并在第 5 节中广泛分析了它的性能。

4.1. 解决方案编码


解决方案表示有两个部分（图 4）：第一部分是分配部分，它显示了打开的车辆和分配给每辆车的订单。此外，第二部分包括每辆车的路线，这与车辆包含的前进（和/或后退）顺序一致。
分配部分

车辆 A：node4 node5 node8 node9

车辆 B：node2 node3 node6
车辆 C：node4 node7

步路部分


图 4.问题的解决方案表示形式。


4.2. 基于相似性的最佳拟合算法 （SBBF） 和首次拟合算法 （SBFF）


已使用最佳拟合/首次拟合算法来构建解决方案。它有两个主要阶段，一个用于处理大订单，另一个用于处理 LTL 订单。第一阶段，大订单被拆分直接发送。然后，使用基于相似性的订购 （SBO） 算法对大订单和其他 LTL 订单的剩余托盘进行订购，并使用最佳拟合/首次拟合算法分配给车辆。


4.2.1. 基于相似性的排序 （SBO） 算法


订单应按特定顺序分配给车辆。根据订单的起点和目的地的距离，根据订单的相似性进行排序。基本原理是，如果两个订单的起点 （目的地） 很近，则它们更相似，并且更有可能放在一起。为此，构建了一个以 orders 为节点的二分图。然后，节点通过具有相似性系数权重的边连接起来，该系数由原始相似性（方程 46）和目标相似性（方程 47）系数的平均值计算得出。相似系数值介于 0 和 1 之间，其中 0 表示最远的起点（或目的地），1 表示具有相同起点（或目的地）的停靠点。
SimOrig ( m , m ′ ) = 1 − dist ( Orig m , Orig m ′ ) max ( dist ′ SimDest ( m , m ′ ) = 1 − dist ( Dest m , Dest m ′ ) max ( dist ) SimOrig m , m ′ = 1 − dist  Orig  m ,  Orig  m ′ max  dist  ′ SimDest m , m ′ = 1 − dist  Dest  m ,  Dest  m ′ max ( dist ) {:[SimOrig(m,m^('))=1-(dist(" Orig "_(m)," Orig "_(m^('))))/(max(" dist "^('))],[SimDest(m,m^('))=1-(dist(" Dest "_(m)," Dest "_(m^('))))/(max(dist))]:}\begin{aligned} & \operatorname{SimOrig}\left(m, m^{\prime}\right)=1-\frac{\operatorname{dist}\left(\text { Orig }_{m}, \text { Orig }_{m^{\prime}}\right)}{\max \left(\text { dist }^{\prime}\right.} \\ & \operatorname{SimDest}\left(m, m^{\prime}\right)=1-\frac{\operatorname{dist}\left(\text { Dest }_{m}, \text { Dest }_{m^{\prime}}\right)}{\max (\operatorname{dist})} \end{aligned}

最大权重二分匹配问题以贪婪方式解决。换句话说，找到相似度的最大值，匹配行和列，并删除行和列。此过程将迭代完成，直到没有找到不匹配的订单。图 5 中具有 8 个订单的实例的程序示意性地显示。八个订单匹配形成四对。这些订单将匹配成四个订单的组。在这个阶段，要计算相似性矩阵的元素，例如 ， SimOrig ( a c , d e ) SimOrig ( a c , d e ) SimOrig(ac,de)\operatorname{SimOrig}(a c, d e) 我们有 SimOrig ( a c , d e ) = SimOrig ( a , d ) + SimOrig ( a c , d e ) = SimOrig ( a , d ) + SimOrig(ac,de)=SimOrig(a,d)+\operatorname{SimOrig}(a c, d e)=\operatorname{SimOrig}(a, d)+ SimOrig ( a , e ) + SimOrig ( c , d ) + SimOrig ( c , e ) SimOrig ( a , e ) + SimOrig ( c , d ) + SimOrig ( c , e ) SimOrig(a,e)+SimOrig(c,d)+SimOrig(c,e)\operatorname{SimOrig}(a, e)+\operatorname{SimOrig}(c, d)+\operatorname{SimOrig}(c, e) 。计算可以扩展到当前和后续相似性矩阵的其他元素。最后，它们被匹配以形成一个 Sequences，以输入到 best-fit 和 first-fit 算法。


4.2.2. 最佳拟合算法


以下伪代码演示了适用于 FB-MRLP 的最佳拟合算法。它只是将订单分配给车辆。如果完成分配后，容量、兼容性和时间窗口约束仍然可行，则结果将是一个可行的解决方案。在继续进行最佳拟合算法之前，应处理两个条件。首先，拆分大订单，直到剩余托盘的尺寸小于最大的车辆。拆分订单将随机分配给直接发货的车辆。剩余的托盘和其他订单不能拆分，可以在循环取货系统中进行。其次，托盘在集装箱中按排排列，使托盘的长度与车辆的宽度平行。因此，每辆车的占用长度是托盘排数与托盘宽度的乘积，即 ⌈ P m , k / N w m , k × N h m , k ⌉ p w m P m , k / N w m , k × N h m , k p w m |~P_(m,k)//Nw_(m,k)xx Nh_(m,k)~|pw_(m)\left\lceil P_{m, k} / N w_{m, k} \times N h_{m, k}\right\rceil p w_{m} 。

图 5.应用于 8 阶样本实例的 SBO 算法。

最佳拟合算法

开始


将 SBO 算法生成的订单排序作为输入。
对于每个订单

为所有打开的车辆和新的空车分配顺序并检查可行性（根据 4.2.4 节的截断模型）;

计算所有可行战车的花费增加量;

选择成本增幅最小的车辆，并将订单分配给该车辆;
End For
结束


4.2.3. 首次拟合算法


首次拟合算法与上述最佳拟合算法类似，但顺序将分配给第一个可行的车辆。first-fit 算法的伪代码如下：


4.2.4. 路由和保留策略


如前所述，如果通过 best-fit/first-fit 算法将 orders 分配给车辆的方式是考虑到问题的约束并保持可行性，那么整个输出解决方案将是可行的。因此，最佳拟合和首次拟合算法的输出保证了重量和长度方面的可行性

首次拟合算法

开始


将 SBO 算法生成的订单排序作为输入。
对于每个订单

对于每个开放的车辆和一辆新车辆：将订单分配给车辆并检查可行性（根据第 4.2.4 节的截断模型）;如果可行

将订单分配给车辆;
破;

结束条件

End For
结束

车辆容量和订单兼容性。为了考虑到时间窗口的可行性，还应做好每辆车的路线规划。每次将停靠点分配给车辆时，都会使用截断模型确定分配的可行性。这是 Section 3.3 中提出的模型的简化版本，其中我们假设只有一个车辆，并且车辆的内容也是已知的，并且是迄今为止通过最佳拟合/首次拟合算法分配给车辆的顺序。因此，此模型用于规划车辆路线和检查可行性。参数和变量的定义类似于 3.1 表示法中定义的定义，但删除了与车辆 ( k ) ( k ) (k)(k) 相关的索引（因为只有一辆车）。因此，该问题成为具有 side constraints 的 Travelling Salesman Problem （TSP） 的一个版本。可以看出，约束 （49）-（52） 是 TSP 中常用的约束，约束 （53）-（66） 是所谓的 side constraints，用于执行与重量和体积容量、节点访问顺序、时间窗口等相关的约束。此外，集和参数是在应该访问的节点上定义的，以便提取和交付当前订单到车辆中。附加变量和参数以及截断的模型如下所示。通过与第 3.3 节的 MILP 模型中的对应项进行比较，可以感知目标函数和每个约束的解释。
变量 定义
u i u i u_(i)u_{i}
为子绕线抵销约束定义的变量（非负）
参数 定义
n n nn
截断模型中的节点数
o l m o l m ol_(m)o l_{m}
订单 m m mm 的托盘所占用的车辆的长度
Variable Definition u_(i) A variable defined for the subtour elimination constraints (nonnegative) Parameter Definition n The number of nodes in the truncated model ol_(m) The length of the vehicle that is occupied by the pallets of order m| Variable | Definition | | :--- | :--- | | $u_{i}$ | A variable defined for the subtour elimination constraints (nonnegative) | | Parameter | Definition | | $n$ | The number of nodes in the truncated model | | $o l_{m}$ | The length of the vehicle that is occupied by the pallets of order $m$ |

截断模型

Minimize O b j F = ∑ i ∈ I ∑ j ∈ I c i , j ∗ X i , j  Minimize  O b j F = ∑ i ∈ I   ∑ j ∈ I   c i , j ∗ X i , j " Minimize "ObjF=sum_(i in I)sum_(j in I)c_(i,j)**X_(i,j)\text { Minimize } O b j F=\sum_{i \in I} \sum_{j \in I} c_{i, j} * X_{i, j}
s.t.

路由约束

∑ j ∈ I X i , j = 1 ∀ i ∈ I ∑ i ∈ I X i , j = 1 ∀ j ∈ I u i − u j + n X i j ≤ n − 1 ∀ j ∈ I , ∀ j ∈ I , i , j ≥ 2 , i ≠ j X i , i = 0 ∀ i ∈ I ∑ i ∈ I , i ≠ 1 , j ∈ I , j ≥ n s + 2 i ≤ n s + 1 ∑ i , j ≤ 1 , j ≤ n s + n a + 1 ∑ j ∈ I   X i , j = 1 ∀ i ∈ I ∑ i ∈ I   X i , j = 1 ∀ j ∈ I u i − u j + n X i j ≤ n − 1 ∀ j ∈ I , ∀ j ∈ I , i , j ≥ 2 , i ≠ j X i , i = 0 ∀ i ∈ I ∑ i ∈ I , i ≠ 1 , j ∈ I , j ≥ n s + 2 i ≤ n s + 1 ∑ i , j   ≤ 1 , j ≤ n s + n a + 1   {:[sum_(j in I)X_(i,j)=1quad AA i in I],[sum_(i in I)X_(i,j)=1quad AA j in I],[u_(i)-u_(j)+nX_(ij) <= n-1quad AA j in I","AA j in I","i","j >= 2","i!=j],[X_(i,i)=0quad AA i in I],[sum_({:[],[i in I","i!=1","quad j in I","j >= ns+2],[i <= ns+1],[sum_(i,j) <= 1],[","j <= ns+na+1]:})]:}\begin{gathered} \sum_{j \in I} X_{i, j}=1 \quad \forall i \in I \\ \sum_{i \in I} X_{i, j}=1 \quad \forall j \in I \\ u_{i}-u_{j}+n X_{i j} \leq n-1 \quad \forall j \in I, \forall j \in I, i, j \geq 2, i \neq j \\ X_{i, i}=0 \quad \forall i \in I \\ \sum_{\substack{ \\ i \in I, i \neq 1, \quad j \in I, j \geq n s+2 \\ i \leq n s+1 \\ \sum_{i, j} \leq 1 \\ , j \leq n s+n a+1}} \end{gathered}
∑ i ∈ I , i ≥ n s + 2 , i ≤ n s + n a + 1 ∑ j ∈ I , j ≥ n s + n a + 2 X i , j ≤ 1 ∑ i ∈ I , i ≥ n s + 2 , i ≤ n s + n a + 1   ∑ j ∈ I , j ≥ n s + n a + 2   X i , j ≤ 1 sum_({:i in I","i >= ns+2","i <= ns+na+1:})sum_({:j in I","j >= ns+na+2:})X_(i,j) <= 1\sum_{\substack{i \in I, i \geq n s+2, i \leq n s+n a+1}} \sum_{\substack{j \in I, j \geq n s+n a+2}} X_{i, j} \leq 1
∑ i ∈ I , i ≥ n s + n a + 2 ∑ j ∈ I , j ≠ 1 j ≤ n s + 1 X i , j = 0 ∑ i ∈ I , i ≥ n s + n a + 2   ∑ j ∈ I , j ≠ 1 j ≤ n s + 1   X i , j = 0 sum_({:i in I","i >= ns+na+2:})sum_({:[j in I","j!=1],[j <= ns+1]:})X_(i,j)=0\sum_{\substack{i \in I, i \geq n s+n a+2}} \sum_{\substack{j \in I, j \neq 1 \\ j \leq n s+1}} X_{i, j}=0
∑ i ∈ I , i ≠ 1 i ≤ n s + 1 ∑ j ∈ I , j ≥ n s + n a + 2 X i , j = 0 ∑ i ∈ I , i ≠ 1 i ≤ n s + 1   ∑ j ∈ I , j ≥ n s + n a + 2   X i , j = 0 sum_({:[i in I","i!=1],[i <= ns+1]:})sum_({:j in I","j >= ns+na+2:})X_(i,j)=0\sum_{\substack{i \in I, i \neq 1 \\ i \leq n s+1}} \sum_{\substack{j \in I, j \geq n s+n a+2}} X_{i, j}=0
∑ i ∈ I , i ≥ n s + 2 , i ≤ n s + n a + 1 ∑ j ∈ I , i ≠ 1 , j ≤ n s + 1 X i , j = 0 ∑ i ∈ I , i ≥ n s + n a + 2 ∑ j ∈ I , j ≥ n s + 2 , j ≤ n s + n a + 1 X i , j = 0 ∑ i ∈ I , i ≥ n s + 2 , i ≤ n s + n a + 1   ∑ j ∈ I , i ≠ 1 , j ≤ n s + 1   X i , j = 0 ∑ i ∈ I , i ≥ n s + n a + 2   ∑ j ∈ I , j ≥ n s + 2 , j ≤ n s + n a + 1   X i , j = 0 {:[sum_({:i in I","i >= ns+2","i <= ns+na+1:})sum_({:j in I","i!=1","j <= ns+1:})X_(i,j)=0],[sum_({:i in I","i >= ns+na+2:})sum_({:j in I","j >= ns+2","j <= ns+na+1:})X_(i,j)=0]:}\begin{gathered} \sum_{\substack{i \in I, i \geq n s+2, i \leq n s+n a+1}} \sum_{\substack{j \in I, i \neq 1, j \leq n s+1}} X_{i, j}=0 \\ \sum_{\substack{i \in I, i \geq n s+n a+2}} \sum_{\substack{j \in I, j \geq n s+2, j \leq n s+n a+1}} X_{i, j}=0 \end{gathered}
U i + ∑ m ∈ O j ′ o l m − ∑ m ∈ D j ′ o l m ≤ U j + ( 1 − X i , j ) ∗ B M 1 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j U i ≤ L ∀ i ∈ I U i + ∑ m ∈ O j ′   o l m − ∑ m ∈ D j ′   o l m ≤ U j + 1 − X i , j ∗ B M 1 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j U i ≤ L ∀ i ∈ I {:[U_(i)+sum_(m inO_(j)^('))ol_(m)-sum_(m inD_(j)^('))ol_(m) <= U_(j)+(1-X_(i,j))**BM1quad AA i in I","j in I","j!=1","i!=j],[U_(i) <= L quad AA i in I]:}\begin{gathered} U_{i}+\sum_{m \in O_{j}^{\prime}} o l_{m}-\sum_{m \in D_{j}^{\prime}} o l_{m} \leq U_{j}+\left(1-X_{i, j}\right) * B M 1 \quad \forall i \in I, j \in I, j \neq 1, i \neq j \\ U_{i} \leq L \quad \forall i \in I \end{gathered}
W i + ∑ m ∈ O j ′ w m f m − ∑ m ∈ D j ′ w m f m ≤ W j + ( 1 − X i , j ) ∗ B M 2 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j W i ≤ W C ∀ i ∈ I W i + ∑ m ∈ O j ′   w m f m − ∑ m ∈ D j ′   w m f m ≤ W j + 1 − X i , j ∗ B M 2 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j W i ≤ W C ∀ i ∈ I {:[W_(i)+sum_(m inO_(j)^('))w_(m)f_(m)-sum_(m inD_(j)^('))w_(m)f_(m) <= W_(j)+(1-X_(i,j))**BM2quad AA i in I","j in I","j!=1","i!=j],[W_(i) <= WC quad AA i in I]:}\begin{gathered} W_{i}+\sum_{m \in O_{j}^{\prime}} w_{m} f_{m}-\sum_{m \in D_{j}^{\prime}} w_{m} f_{m} \leq W_{j}+\left(1-X_{i, j}\right) * B M 2 \quad \forall i \in I, j \in I, j \neq 1, i \neq j \\ W_{i} \leq W C \quad \forall i \in I \end{gathered}
T i + ∑ m ∈ O i ′ L T m f m + ∑ m ∈ D i ′ U T m f m + time i j ≤ T j + ( 1 − X i , j ) ∗ BM3 ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j T j ≥ T i m ∈ M , i = Orig m , j = Dest m T i ≥ l b m ∀ m ∈ M , i = Orig m T i ≤ u b m ∀ m ∈ M , i = Dest m , T i + ∑ m ∈ O i ′   L T m f m + ∑ m ∈ D i ′   U T m f m +  time  i j ≤ T j + 1 − X i , j ∗  BM3  ∀ i ∈ I , j ∈ I , j ≠ 1 , i ≠ j T j ≥ T i m ∈ M , i =  Orig  m , j =  Dest  m T i ≥ l b m ∀ m ∈ M , i =  Orig  m T i ≤ u b m ∀ m ∈ M , i =  Dest  m , {:[T_(i)+sum_(m inO_(i)^('))LT_(m)f_(m)+sum_(m inD_(i)^('))UT_(m)f_(m)+" time "_(ij) <= T_(j)+(1-X_(i,j))**" BM3 "quad AA i in I","j in I","j!=1","i!=j],[T_(j) >= T_(i)quad m in M","i=" Orig "_(m)","j=" Dest "_(m)],[T_(i) >= lb_(m)quad AA m in M","i=" Orig "_(m)],[T_(i) <= ub_(m)quad AA m in M","i=" Dest "_(m)","]:}\begin{aligned} T_{i} & +\sum_{m \in O_{i}^{\prime}} L T_{m} f_{m}+\sum_{m \in D_{i}^{\prime}} U T_{m} f_{m}+\text { time }_{i j} \leq T_{j}+\left(1-X_{i, j}\right) * \text { BM3 } \quad \forall i \in I, j \in I, j \neq 1, i \neq j \\ T_{j} & \geq T_{i} \quad m \in M, i=\text { Orig }_{m}, j=\text { Dest }_{m} \\ T_{i} & \geq l b_{m} \quad \forall m \in M, i=\text { Orig }_{m} \\ T_{i} & \leq u b_{m} \quad \forall m \in M, i=\text { Dest }_{m}, \end{aligned}

变量

X i , j ∈ { 0 , 1 } ; U i , W i , T i , u i ≥ 0 X i , j ∈ { 0 , 1 } ; U i , W i , T i , u i ≥ 0 X_(i,j)in{0,1};U_(i),W_(i),T_(i),u_(i) >= 0X_{i, j} \in\{0,1\} ; U_{i}, W_{i}, T_{i}, u_{i} \geq 0

当卡车内的订单数量（具有不同的起点-目的地）在实践中不是太多（例如少于 10 个）时，我们可以使用 CPLEX 求解器在几秒钟内以最佳方式求解建议的截断模型。如果此数字变大，

然后，CPLEX 的使用变得无关紧要，因为获取最佳解可能需要太多时间。幸运的是，汽车零部件分销系统使得卡车可以放入的订单数量和在合理时间限制内可以访问的供应商/汽车制造商节点数量都很小，我们可以通过像 CPLEX 这样的强大求解器更快地获得最佳解决方案。由于所提出的模型应该多次求解，我们可以开发一种快速的建设性启发式方法或元启发式方法，或者以最佳方式求解它。我们更喜欢以最佳方式解决它，因为建设性启发式方法（如果可用）可能性能不佳，而元启发式方法需要约束处理技术并且可能需要很多时间。


4.3. 改进启发式


在通过最佳拟合或首次拟合算法创建可行解决方案后，应用两种改进启发式方法。添加这些启发式方法是为了提高这些算法生成的解决方案的质量。

4.3.1. 减少


的 Reduce 启发式检查车辆中的订单集是否可以使用较小的车辆进行运输。这是基于小型车辆比大型车辆成本更低的假设。Reduce 启发式的伪代码如下：
Reduce Heuristic
Begin
Set \(V_{o}\) as the vehicles in the solution;
For each vehicle \(v_{o}\) in \(V_{o}\)
    Set \(V_{p}\) as the set of smaller vehicles than \(v_{o}\) (sorted in increasing order of size);
    For each vehicle \(v_{p}\) in \(V_{p}\)
        Assign orders of \(v_{o}\) to \(v_{p}\) and check feasibility by solving the truncated model of Section 4.2.4;
        If feasible
            Permanently assign orders of \(v_{o}\) to \(v_{p}\) in the solution;
            Continue;
        End If
    End For
End For
End

4.3.2. 合并


Merge 启发式方法将两辆车的订单合并到两辆车中最大的或更大的一辆中。这可能会导致车辆数量减少。值得注意的是，在合并之前会检查两辆车的订单兼容性。Merge 启发式的伪代码如下（我们设置 ξ = 10 ξ = 10 xi=10\xi=10 ）：

随机运算用于算法的不同步骤。由于车队是异构的，因此在最佳拟合/首次拟合步骤中，每当我们需要一辆新车辆时，我们都应该选择一辆车辆并为其分配顺序。更准确地说，在拖车、卡车和皮卡车（我们的案例研究中可用的三种类型的车辆）中，应该选择一种。在没有任何关于特殊类型车辆适用性的先验知识的情况下，我们随机选择一个。此外，不同的车辆是随机选择和合并的。因此，输出可能会因卡车的选择方式而异。但是，对于同构队列，每次运行中的输出都是相同的。

为了说明所提出的方法的机制，我们在附录中定义了一个小问题，并用数字描述了它的不同步骤。


4.4. 分组进化策略


分组进化策略 （GES） 于 2009 年首次引入用于分组问题，并于 2017 年由 Abbasi-Pooya 和 Husseinzadeh Kashan （2017） 成功应用于路由问题。在本节中，我们将 GES 应用于 FB-MRLP 问题。借助最佳拟合/首次拟合算法，可以以最佳方式完成适应。在 GES 中生成新解决方案的过程包括继承和重新插入阶段。继承包括确定父解的每个车辆中的哪些订单应转移到后代解决方案中的同一车辆。重新插入
Merge Heuristic
Initialise parameter \(\xi\);
Begin
Set \(V_{o}\) as the vehicles in the solution;
While counter \(<=\xi\);
    Select two vehicles \(v_{1}\) and \(v_{2}\) from \(V_{o}\);
    Set \(V_{p}\) as the set of vehicles that are larger than or similar to the largest of \(v_{1}\) and \(v_{2}\) (in increasing order);
    For each vehicle \(v_{p}\) in \(V_{p}\)
        Assign orders of \(v_{1}\) and \(v_{2}\) to \(v_{p}\) and check feasibility by solving the truncated model of Section 4.2.4;
        If compatible and feasible
            Permanently assign orders of \(v_{1}\) and \(v_{2}\) to \(v_{p}\);
            Set \(V_{0}=V_{0}-\left\{v_{1}, v_{2}\right\} \cup\left\{v_{p}\right\}\);
            Break;
        End If
    End For
    counter \(=\) counter +1 ;
End While
End

阶段包括将未分配的订单（在继承阶段中未选择的订单）重新分配给当前可用的车辆或新车辆。最佳拟合/首次拟合算法的采用处于重新插入阶段，此时存在部分解决方案，其中许多等待分配的订单根据给定顺序通过最佳/首次拟合分配给车辆。回想一下，这里 GES 被认为是一种基于单一解决方案的进化算法。

在 GES 的继承阶段，必须确定父解和后代解的每组（车辆）之间的共享项（订单）数量。设 n k t n k t n_(k)^(t)n_{k}^{t} 为 迭代中 vehicle k k kk 的共享订单数 t t tt 。设 v k t v k t v_(k)^(t)v_{k}^{t} 是迭代中分配给父解决方案中 vehicle k k kk 的订单集 t t tt 。设 Beta k ( α t , β ) Beta k α t , β Beta_(k)(alpha^(t),beta)\operatorname{Beta}_{k}\left(\alpha^{t}, \beta\right) 为带参数 α t α t alpha^(t)\alpha^{t} 的 beta 随机数， β . n k t β . n k t beta.n_(k)^(t)\beta . n_{k}^{t} 计算如下：
n k t = ⌊ 1 − Beta k ( α t , β ) | v k t | ⌋ n k t = 1 − Beta k α t , β v k t n_(k)^(t)=|__1-Beta_(k)(alpha^(t),beta)|v_(k)^(t)|__|n_{k}^{t}=\left\lfloor 1-\operatorname{Beta}_{k}\left(\alpha^{t}, \beta\right)\left|v_{k}^{t}\right|\right\rfloor

有关 GES 机制的更多详细信息，读者可以参考 Abbasi-Pooya 和 Husseinzadeh Kashan （2017） 以及 Husseinzadeh Kashan、Akbari 和 Ostadi （2015）。GES 生成适用于 FB-MLRP 的新解决方案的过程由新解决方案生成 （NSG） 算法执行，如下所示：
New Solution Generation (NSG) Algorithm
Begin
Set \(V^{t}\) as the vehicles in the parent solution;
Step 1 (inheritance phase)
For each vehicle \(k=1\) to \(\left|V^{t}\right|\)
    Compute \(n_{k}^{t}=\left\lfloor 1-\operatorname{Beta}_{k}\left(\alpha^{t}, \beta\right)\left|v_{k}^{t}\right|\right\rfloor\);
    Select \(n_{k}^{t}\) orders from \(v_{k}^{t}\) and assign them to set \(u_{k}^{t}\);
    \(U^{t}=U^{t} \cup\left\{u_{k}^{t}\right\} ;\)
End
Set \(U^{t}\) as the vehicles in the offspring solution;
Step 2 (the post-assignment phase)
List the orders that has not been selected during Step 1 in an arbitrary order. Starting from the head
    of the list, employ the best-fit/first-fit algorithm to assign the orders to currently available vehicles
    in \(U^{t}\) or newly added vehicles to \(U^{t}\);
结束

适应 FB-MRLP 的 GES 整个伪代码如下：


5. 实验和结果


本节致力于使用从 SAIPA 伊朗汽车制造商面临的实际日常问题和一些生成的实例中获得的数据来测试所提出的数学公式和算法。以下各节给出了生成的实例的描述、案例研究和结果。
Grouping Evolution Strategy (GES) Algorithm
Initialise \(\alpha^{0}, \beta, a\)
Begin
\(t \leftarrow 0 ; \alpha \leftarrow \alpha^{0}\);
Create an initial solution \(V^{t}\) using the best-fit/first-fit algorithm;
While stopping criteria are not true
    Given the parent solution \(V^{t}\), apply the NSG algorithm to obtain the offspring solution \(U^{t}\);
    Apply Reduce improvement heuristic on \(U^{t}\);
    If \(\operatorname{Obj}\left(U^{t}\right)<\operatorname{Obj}\left(V^{t}\right)\)
        \(V^{t+1} \leftarrow U^{t} ;\)
        \(\alpha \leftarrow \alpha / a ;\)
    Else
        \(V^{t+1} \leftarrow V^{t} ;\)
        \(\alpha \leftarrow \alpha \times a ;\)
    End if
    \(t \leftarrow t+1\);
    \(\alpha^{t} \leftarrow \alpha ;\)
End While
End

5.1. 生成的实例


问题实例的生成方式是它们代表每日订单。每日订单包括向前（装满托拍）和向后（空托拍）订单。对于远期订单，根据要生成的订单数量，随机生成库存代码列表和零件数量。这些信息足以确定供应商、托拍类型以及其他与包装相关的数据。然后，将随机生成其他相关数据，例如订单的目的地和时间窗的边界。对于反向订单，托盘类型、托盘数量、它们的出发地和目的地以及时间窗口的上限和下限也是随机生成的。实例大小由订单数量（前向和后向）决定，订单数量在 6 到 122 个订单之间变化（表 3 中的第二列）。少于 10 个订单的实例被视为小型实例。车辆分为三种类型，例如拖车、卡车和皮卡车。所以队列是异构的。对于同质车队，车辆类型仅为 Truck。

5.2. 案例研究问题


SAIPA 的日常汽车零部件物流问题可以定义如下。在每天开始时，供应商、每个供应商提供的每个订单中的零件数量、订单时间窗口和每个订单的目的地都是已知的。托盘的尺寸、类型、重量及其兼容性也是已知的。此外，还有空托盘的订单，应该从装配厂运送到供应商。问题是分配所有正向和反向订单。更详细地说，问题的解决方案将是一组车辆及其路线以及它们的取货和送货时间表，以一种将总成本降至最低并满足约束条件（如前所述）的方式。

表 4 提供了每日数据的示例。每天的远期订单包括以下内容：从每个供应商运输到其各自交货点（装配厂）的零件的库存代码。其他信息是可以放置在托拍中的零件数量。根据零件和空托盘的重量，可以确定一个满托盘的重量。将装满的托盘数量乘以满托盘的重量，得到订单的重量。与托拍相关的其他参数是托拍的长度、宽度和高度。此外，空托拍的倒行订单也有类似的数据。根据这些数据，可以确定托盘类型（金属/木制）、订单兼容性、每辆车宽度上可以排列的托盘数量、每辆车可以堆叠的托盘数量、每辆车的旅行时间和成本等信息。案例研究的 FB-MRLP 将被求解，并将使用不同的求解程序比较结果。

值得一提的是，SAIPA 目前的运输策略是直接运输，其中每个供应商都负责通过单独的车辆将其订单直接发送到需求点并返回空托盘。因此，在目前的配送系统形式下，两个供应商不能共享同一辆车，即使他们知道他们正在调度半载车辆。

目前，SAIPA 的供应链由分布在伊朗各地的 480 家活跃供应商组成。根据 SAIPA 的物流政策，该地图已划分为 60 个区域，每个供应商都被分配到其中一个区域。这些区域是计算运输成本的基础。

表 3.实例特征。
问题参数
实例 不。订单数量 不。远期订单 不。的反向订单
小型实例 01 6 4 2
02 6 4 2
03 6 3 3
04 6 3 3
05 7 4 3
06 7 4 3
07 8 4 4
08 8 4 4
09 8 5 3
10 8 5 3

相对较小的实例到大型实例		 11 10 6 4
12 11 7 4
13 12 8 4
14 14 9 5
15 18 10 8
16 19 11 8
17 22 11 11
18 30 15 15
19 36 20 16
20 42 25 17
21 54 30 24
22 74 40 34
23 83 45 38
24 93 50 43
25 103 55 48
26 112 60 52
27 122 65 57
Problem Parameters Instance No. of orders No. of forward orders No. of backward orders Small instances 01 6 4 2 02 6 4 2 03 6 3 3 04 6 3 3 05 7 4 3 06 7 4 3 07 8 4 4 08 8 4 4 09 8 5 3 10 8 5 3 Relatively small to large instances 11 10 6 4 12 11 7 4 13 12 8 4 14 14 9 5 15 18 10 8 16 19 11 8 17 22 11 11 18 30 15 15 19 36 20 16 20 42 25 17 21 54 30 24 22 74 40 34 23 83 45 38 24 93 50 43 25 103 55 48 26 112 60 52 27 122 65 57| | Problem Parameters | | | | | :---: | :---: | :---: | :---: | :---: | | | Instance | No. of orders | No. of forward orders | No. of backward orders | | Small instances | 01 | 6 | 4 | 2 | | | 02 | 6 | 4 | 2 | | | 03 | 6 | 3 | 3 | | | 04 | 6 | 3 | 3 | | | 05 | 7 | 4 | 3 | | | 06 | 7 | 4 | 3 | | | 07 | 8 | 4 | 4 | | | 08 | 8 | 4 | 4 | | | 09 | 8 | 5 | 3 | | | 10 | 8 | 5 | 3 | | Relatively small to large instances | 11 | 10 | 6 | 4 | | | 12 | 11 | 7 | 4 | | | 13 | 12 | 8 | 4 | | | 14 | 14 | 9 | 5 | | | 15 | 18 | 10 | 8 | | | 16 | 19 | 11 | 8 | | | 17 | 22 | 11 | 11 | | | 18 | 30 | 15 | 15 | | | 19 | 36 | 20 | 16 | | | 20 | 42 | 25 | 17 | | | 21 | 54 | 30 | 24 | | | 22 | 74 | 40 | 34 | | | 23 | 83 | 45 | 38 | | | 24 | 93 | 50 | 43 | | | 25 | 103 | 55 | 48 | | | 26 | 112 | 60 | 52 | | | 27 | 122 | 65 | 57 |

从 SAIPA 收集的数据显示，直接运输的货物中不 92 % 92 % 92%92 \% 止一部分，因此通过开发最佳的循环取货物流系统存在巨大的节省潜力。此外，通过网络分销的零件中，超过一 41 % 41 % 41%41 \% 类 B B BB 是非大型零件，从组装端具有相对稳定的需求。这些零件适合与循环取货物流系统一起分销。

我们的进一步分析表明，帕累托 80 − 20 80 − 20 80-2080-20 规则也是可观察的。也就是说，超过 80 % 80 % 80%80 \% 3 件货物来自位于 60 个地区中 12 个主要地区的供应商。此外，大多数货物被送到德黑兰、萨维赫和卡尚市的 3 个组装厂，其中 12 个目的地（即 75 % 75 % 75%75 \% ）。因此，该公司可以只关注位于前 12 个地理区域的主要供应商以及其 3 个主要装配厂，因此可以减少物流网络的范围。

5.3. 结果


5.3.1. 求解生成的实例


使用生成的测试实例评估算法的性能。基于相似性的最佳拟合 （SBBF） 和基于相似性的首次拟合 （SBFF） 算法和 GES 的代码是用 MATLAB 编写的，并在具有 8 GB RAM 和 Core i5 处理器 ( 2.60 GHz ) ( 2.60 GHz ) (2.60GHz)(2.60 \mathrm{GHz}) 的笔记本电脑上运行。SBBF 和 SBFF 的结果是使用 Reduce 和 Merge 算法改进后报告的。使用 SBBF、Reduce 和 Merge 算法初始化 GES 会产生 GES-SBBF 算法。如果 GES 以没有 SBO 算法的最佳拟合算法开始，并且仅借助随机订单列表，我们得到 GES-RAND 算法。在这里，在初始化阶段没有使用 Merge 或 Reduce作。NSG 算法的输出始终作为 Reduce 算法的输入。最后，在我们的 GES 实验中，我们设置了 α 0 = 5 , β = 1 α 0 = 5 , β = 1 alpha^(0)=5,beta=1\alpha^{0}=5, \beta=1 ， a = 0.9 a = 0.9 a=0.9a=0.9 。每个算法在每个测试问题实例上测试 10 次，并报告 Min、Average 和 Max 统计数据。将算法的性能与通过 GAMS/CPLEX 求解所提出的模型获得的结果进行了比较。GAMS 执行的时间限制为 3600 s ，对于找到可行解决方案但无法保证最优性的情况，将报告找到的最佳解决方案。

表 5-7 显示了按 GAMS/CPLEX、SBBF、SBFF 和 GES 求解实例的结果。报告获得的目标函数 （总成本） 和求解每个实例的 CPU 时间。对于时间限制是

表 4.一天的正向和反向订单数据。
远期订单数据
Ftock 代码 不。零件数 供应商代码
交货目的地代码		 托盘名称 托盘中的零件 年级 部件重量 （g）
零件的净重（以托盘为单位） （g）
空托盘重量 （Kg）		 整托盘重量 长度 宽度 高度
DN12053650A 800 13285 1175 GP5 160 B 1800 288 150 438 1200 1080 765
DN12054650A 800 13285 1175 GP5 160 B 1800 288 150 438 1200 1080 765
DP13070231 480 11293 9909 GP5 480 B 470 226 150 376 1200 1080 765
… … dots\ldots … … dots\ldots . … … dots\ldots … … dots\ldots … … dots\ldots … … dots\ldots … … dots\ldots … … dots\ldots … … dots\ldots … … dots\ldots … … dots\ldots … … dots\ldots … … dots\ldots
Forward orders data Ftock code No. of parts Supplier code Delivery destination code Pallet name Parts in pallet Grade Part weight (g) Part's net weight in pallet (g) Weight of empty pallet (Kg) Weight of full pallet Length Width Height DN12053650A 800 13285 1175 GP5 160 B 1800 288 150 438 1200 1080 765 DN12054650A 800 13285 1175 GP5 160 B 1800 288 150 438 1200 1080 765 DP13070231 480 11293 9909 GP5 480 B 470 226 150 376 1200 1080 765 dots dots . dots dots dots dots dots dots dots dots dots dots dots| Forward orders data | | | | | | | | | | | | | | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | Ftock code | No. of parts | Supplier code | Delivery destination code | Pallet name | Parts in pallet | Grade | Part weight (g) | Part's net weight in pallet (g) | Weight of empty pallet (Kg) | Weight of full pallet | Length | Width | Height | | DN12053650A | 800 | 13285 | 1175 | GP5 | 160 | B | 1800 | 288 | 150 | 438 | 1200 | 1080 | 765 | | DN12054650A | 800 | 13285 | 1175 | GP5 | 160 | B | 1800 | 288 | 150 | 438 | 1200 | 1080 | 765 | | DP13070231 | 480 | 11293 | 9909 | GP5 | 480 | B | 470 | 226 | 150 | 376 | 1200 | 1080 | 765 | | $\ldots$ | $\ldots$ | . | $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ | $\ldots$ |
倒序数据
Weight of empty pallet )  Weight of   empty pallet  {:[,,,,," Weight of "],[" empty pallet "])\left.\begin{array}{lcccccccc}\hline & & & & & \text { Weight of } \\ \text { empty pallet }\end{array}\right)

表 5.小型实例上的结果。
实例 Optimal/best solution ―  Optimal/best solution  _ " Optimal/best solution "_\underline{\text { Optimal/best solution }} SBBF SBFF GES-RAND
Obj. func. ( × 10 6 ) × 10 6 (xx10^(6))\left(\times 10^{6}\right)
平均时间 （s）
Avg. time (s)| Avg. time | | :--- | | (s) |
 Obj. func. ( × 10 6 ) × 10 6 (xx10^(6))\left(\times 10^{6}\right)
平均时间 （s）
Avg. time (s)| Avg. time | | :--- | | (s) |
 差距 （%） Obj. func. ( × 10 6 ) × 10 6 (xx10^(6))\left(\times 10^{6}\right)
平均时间 （s）
Avg. time (s)| Avg. time | | :--- | | (s) |
 差距 （%）
func. ( × 10 6 )  func.  × 10 6 {:[" func. "],[(xx10^(6))]:}\begin{aligned} & \text { func. } \\ & \left(\times 10^{6}\right) \end{aligned} 时间 （s） 最小 平均。 麦克斯。 差距 （%） 最小 平均。 麦克斯。 最小 平均。 麦克斯。
01 7.388 9.3 7.388 7.521 7.7 13.75 0.0 7.388 7.575 7.7 14.35 0.0 7.388 7.388 7.388 15.35 0.0
02 7.9 7.6 7.9 7.9 7.9 4.7 0.0 7.9 7.9 7.9 4.2 0.0 7.9 7.9 7.9 8.95 0.0
03 8.6 2.7 8.6 9.26 10.8 6.4 0.0 8.6 9.92 10.8 4.15 0.0 8.6 8.6 8.6 8.95 0.0
04 10.8 1.7 10.8 11.16 12 4.4 0.0 10.8 11.04 12 3.35 0.0 10.8 10.8 10.8 6.7 0.0
05 6.2 3600* 6.3 6.96 7.4 9.15 1.6 7.2 7.32 7.6 6.05 16.1 6.2 6.28 6.3 64 0.0
06 6.6 2617.7 6.6 6.71 7.7 6.7 0.0 6.6 7 8.6 5.35 0.0 6.6 6.6 6.6 18.5 0.0
07 10.9 3600* 10.9 11.99 12.8 7.37 0.0 10.9 11.72 14.1 6.63 0.0 10.9 10.9 10.9 116.05 0.0
08 6.4 3600* 6.4 7.349 8.698 6.9 0.0 6.4 7.349 8.698 7.05 0.0 6.4 6.4 6.4 155.9 0.0
09 10 3089 10 10.54 11.5 8.585 0.0 10 11.68 14.4 6.55 0.0 10 10 10 47.865 0.0
10 10.3 2538.5 10.3 11.27 12.7 9.9 0.0 10.3 13.06 15.4 8.95 0.0 10.3 10.36 10.9 53.9 0.0
Instance " Optimal/best solution "_ SBBF SBFF GES-RAND Obj. func. (xx10^(6)) "Avg. time (s)" Obj. func. (xx10^(6)) "Avg. time (s)" GAP (%) Obj. func. (xx10^(6)) "Avg. time (s)" GAP (%) " func. (xx10^(6))" Time (s) min. avg. max. GAP (%) min. avg. max. min. avg. max. 01 7.388 9.3 7.388 7.521 7.7 13.75 0.0 7.388 7.575 7.7 14.35 0.0 7.388 7.388 7.388 15.35 0.0 02 7.9 7.6 7.9 7.9 7.9 4.7 0.0 7.9 7.9 7.9 4.2 0.0 7.9 7.9 7.9 8.95 0.0 03 8.6 2.7 8.6 9.26 10.8 6.4 0.0 8.6 9.92 10.8 4.15 0.0 8.6 8.6 8.6 8.95 0.0 04 10.8 1.7 10.8 11.16 12 4.4 0.0 10.8 11.04 12 3.35 0.0 10.8 10.8 10.8 6.7 0.0 05 6.2 3600* 6.3 6.96 7.4 9.15 1.6 7.2 7.32 7.6 6.05 16.1 6.2 6.28 6.3 64 0.0 06 6.6 2617.7 6.6 6.71 7.7 6.7 0.0 6.6 7 8.6 5.35 0.0 6.6 6.6 6.6 18.5 0.0 07 10.9 3600* 10.9 11.99 12.8 7.37 0.0 10.9 11.72 14.1 6.63 0.0 10.9 10.9 10.9 116.05 0.0 08 6.4 3600* 6.4 7.349 8.698 6.9 0.0 6.4 7.349 8.698 7.05 0.0 6.4 6.4 6.4 155.9 0.0 09 10 3089 10 10.54 11.5 8.585 0.0 10 11.68 14.4 6.55 0.0 10 10 10 47.865 0.0 10 10.3 2538.5 10.3 11.27 12.7 9.9 0.0 10.3 13.06 15.4 8.95 0.0 10.3 10.36 10.9 53.9 0.0| Instance | $\underline{\text { Optimal/best solution }}$ | | SBBF | | | | | SBFF | | | | | GES-RAND | | | | | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | Obj. func. $\left(\times 10^{6}\right)$ | | | Avg. time <br> (s) | | Obj. func. $\left(\times 10^{6}\right)$ | | | Avg. time <br> (s) | GAP (%) | Obj. func. $\left(\times 10^{6}\right)$ | | | Avg. time <br> (s) | GAP (%) | | | $\begin{aligned} & \text { func. } \\ & \left(\times 10^{6}\right) \end{aligned}$ | Time (s) | min. | avg. | max. | | GAP (%) | min. | avg. | max. | | | min. | avg. | max. | | | | 01 | 7.388 | 9.3 | 7.388 | 7.521 | 7.7 | 13.75 | 0.0 | 7.388 | 7.575 | 7.7 | 14.35 | 0.0 | 7.388 | 7.388 | 7.388 | 15.35 | 0.0 | | 02 | 7.9 | 7.6 | 7.9 | 7.9 | 7.9 | 4.7 | 0.0 | 7.9 | 7.9 | 7.9 | 4.2 | 0.0 | 7.9 | 7.9 | 7.9 | 8.95 | 0.0 | | 03 | 8.6 | 2.7 | 8.6 | 9.26 | 10.8 | 6.4 | 0.0 | 8.6 | 9.92 | 10.8 | 4.15 | 0.0 | 8.6 | 8.6 | 8.6 | 8.95 | 0.0 | | 04 | 10.8 | 1.7 | 10.8 | 11.16 | 12 | 4.4 | 0.0 | 10.8 | 11.04 | 12 | 3.35 | 0.0 | 10.8 | 10.8 | 10.8 | 6.7 | 0.0 | | 05 | 6.2 | 3600* | 6.3 | 6.96 | 7.4 | 9.15 | 1.6 | 7.2 | 7.32 | 7.6 | 6.05 | 16.1 | 6.2 | 6.28 | 6.3 | 64 | 0.0 | | 06 | 6.6 | 2617.7 | 6.6 | 6.71 | 7.7 | 6.7 | 0.0 | 6.6 | 7 | 8.6 | 5.35 | 0.0 | 6.6 | 6.6 | 6.6 | 18.5 | 0.0 | | 07 | 10.9 | 3600* | 10.9 | 11.99 | 12.8 | 7.37 | 0.0 | 10.9 | 11.72 | 14.1 | 6.63 | 0.0 | 10.9 | 10.9 | 10.9 | 116.05 | 0.0 | | 08 | 6.4 | 3600* | 6.4 | 7.349 | 8.698 | 6.9 | 0.0 | 6.4 | 7.349 | 8.698 | 7.05 | 0.0 | 6.4 | 6.4 | 6.4 | 155.9 | 0.0 | | 09 | 10 | 3089 | 10 | 10.54 | 11.5 | 8.585 | 0.0 | 10 | 11.68 | 14.4 | 6.55 | 0.0 | 10 | 10 | 10 | 47.865 | 0.0 | | 10 | 10.3 | 2538.5 | 10.3 | 11.27 | 12.7 | 9.9 | 0.0 | 10.3 | 13.06 | 15.4 | 8.95 | 0.0 | 10.3 | 10.36 | 10.9 | 53.9 | 0.0 |

表 6.小型实例 （同类队列） 上的结果。
最佳/最佳 溶液 SBBF SBFF GES-RAND
数控。( × 10 6 × 10 6 xx10^(6)\times 10^{6} )
Obj. func. ( × 10 6 ) × 10 6 (xx10^(6))\left(\times 10^{6}\right) 时间 （s） Obj. func. ( × 10 6 ) × 10 6 (xx10^(6))\left(\times 10^{6}\right) 平均时间 （s） 差距 （%） Obj. func. ( × 10 6 ) × 10 6 (xx10^(6))\left(\times 10^{6}\right) 平均时间 （s） 差距 （%） 最小 平均。 麦克斯。 平均时间 （s） 差距 （%）
7.9 3.9 7.9 8.7 0.0 7.9 8.7 0.0 7.9 7.9 7.9 6.4 0.0
7.9 2.8 7.9 3.1 0.0 7.9 2.95 0.0 7.9 7.9 7.9 6.55 0.0
8.6 1.6 8.6 2.15 0.0 8.6 2.1 0.0 8.6 8.6 8.6 2.95 0.0
12 1.3 12 1.3 0.0 12 1.2 0.0 12 12 12 1.35 0.0
6.9 276.9 7.2 5.7 4.3 7.2 4.85 4.3 6.9 6.9 6.9 28.65 0.0
6.6 394.7 6.6 5.45 0.0 6.6 4.8 0.0 6.6 6.6 6.6 23.7 0.0
10.9 1490.8 10.9 4.3 0.0 10.9 3.05 0.0 10.9 10.9 10.9 6.9 0.0
7 1234.3 7 6.1 0.0 7 5.6 0.0 7 7 7 26.9 0.0
10.6 2332.3 10.6 5.05 0.0 10.6 4.05 0.0 10.6 10.6 10.6 7.6 0.0
10.9 756.2 10.9 4.55 0.0 10.9 2.95 0.0 10.9 10.9 10.9 4.95 0.0
Optimal/best Solution SBBF SBFF GES-RAND nc. ( xx10^(6) ) Obj. func. (xx10^(6)) Time (s) Obj. func. (xx10^(6)) Avg. time (s) GAP (%) Obj. func. (xx10^(6)) Avg. time (s) GAP (%) min. avg. max. Avg. time (s) GAP (%) 7.9 3.9 7.9 8.7 0.0 7.9 8.7 0.0 7.9 7.9 7.9 6.4 0.0 7.9 2.8 7.9 3.1 0.0 7.9 2.95 0.0 7.9 7.9 7.9 6.55 0.0 8.6 1.6 8.6 2.15 0.0 8.6 2.1 0.0 8.6 8.6 8.6 2.95 0.0 12 1.3 12 1.3 0.0 12 1.2 0.0 12 12 12 1.35 0.0 6.9 276.9 7.2 5.7 4.3 7.2 4.85 4.3 6.9 6.9 6.9 28.65 0.0 6.6 394.7 6.6 5.45 0.0 6.6 4.8 0.0 6.6 6.6 6.6 23.7 0.0 10.9 1490.8 10.9 4.3 0.0 10.9 3.05 0.0 10.9 10.9 10.9 6.9 0.0 7 1234.3 7 6.1 0.0 7 5.6 0.0 7 7 7 26.9 0.0 10.6 2332.3 10.6 5.05 0.0 10.6 4.05 0.0 10.6 10.6 10.6 7.6 0.0 10.9 756.2 10.9 4.55 0.0 10.9 2.95 0.0 10.9 10.9 10.9 4.95 0.0| Optimal/best | Solution | SBBF | | | SBFF | | | GES-RAND | | | | | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | | | | | | | nc. ( | $\times 10^{6}$ ) | | | | Obj. func. $\left(\times 10^{6}\right)$ | Time (s) | Obj. func. $\left(\times 10^{6}\right)$ | Avg. time (s) | GAP (%) | Obj. func. $\left(\times 10^{6}\right)$ | Avg. time (s) | GAP (%) | min. | avg. | max. | Avg. time (s) | GAP (%) | | 7.9 | 3.9 | 7.9 | 8.7 | 0.0 | 7.9 | 8.7 | 0.0 | 7.9 | 7.9 | 7.9 | 6.4 | 0.0 | | 7.9 | 2.8 | 7.9 | 3.1 | 0.0 | 7.9 | 2.95 | 0.0 | 7.9 | 7.9 | 7.9 | 6.55 | 0.0 | | 8.6 | 1.6 | 8.6 | 2.15 | 0.0 | 8.6 | 2.1 | 0.0 | 8.6 | 8.6 | 8.6 | 2.95 | 0.0 | | 12 | 1.3 | 12 | 1.3 | 0.0 | 12 | 1.2 | 0.0 | 12 | 12 | 12 | 1.35 | 0.0 | | 6.9 | 276.9 | 7.2 | 5.7 | 4.3 | 7.2 | 4.85 | 4.3 | 6.9 | 6.9 | 6.9 | 28.65 | 0.0 | | 6.6 | 394.7 | 6.6 | 5.45 | 0.0 | 6.6 | 4.8 | 0.0 | 6.6 | 6.6 | 6.6 | 23.7 | 0.0 | | 10.9 | 1490.8 | 10.9 | 4.3 | 0.0 | 10.9 | 3.05 | 0.0 | 10.9 | 10.9 | 10.9 | 6.9 | 0.0 | | 7 | 1234.3 | 7 | 6.1 | 0.0 | 7 | 5.6 | 0.0 | 7 | 7 | 7 | 26.9 | 0.0 | | 10.6 | 2332.3 | 10.6 | 5.05 | 0.0 | 10.6 | 4.05 | 0.0 | 10.6 | 10.6 | 10.6 | 7.6 | 0.0 | | 10.9 | 756.2 | 10.9 | 4.55 | 0.0 | 10.9 | 2.95 | 0.0 | 10.9 | 10.9 | 10.9 | 4.95 | 0.0 |

表 7.实验结果。
实例 GAMS/CPLEX SBBF SBFF GES-SBBF GES-RAND
Obj. func.
( × 10 3 ) × 10 3 (xx10^(3))\left(\times 10^{3}\right)		 时间 （s）
Obj. func.（ × 10 6 × 10 6 xx10^(6)\times 10^{6} ）		 Avg. time (s)  Avg.   time (s)  {:[" Avg. "],[" time (s) "]:}\begin{aligned} & \text { Avg. } \\ & \text { time (s) } \end{aligned} 差距 （%）
Obj. func.（ × 10 6 × 10 6 xx10^(6)\times 10^{6} ）		 平均时间 （s） Gap ( % )  Gap  ( % ) {:[" Gap "],[(%)]:}\begin{aligned} & \text { Gap } \\ & (\%) \end{aligned} 签名。
Obj. func.（ × 10 6 × 10 6 xx10^(6)\times 10^{6} ）		 平均时间 （s） Gap ( % )  Gap  ( % ) {:[" Gap "],[(%)]:}\begin{aligned} & \text { Gap } \\ & (\%) \end{aligned}
Obj. func.（ × 10 6 × 10 6 xx10^(6)\times 10^{6} ）		 平均时间 （s） 签名。 Gap ( % )  Gap  ( % ) {:[" Gap "],[(%)]:}\begin{aligned} & \text { Gap } \\ & (\%) \end{aligned}
最小 平均。 麦克斯。 最小 平均。 麦克斯。 最小 平均。 麦克斯。 最小 平均。 麦克斯。
11 10.9 3600* 12.316 14.532 18.1 9.4 12.9 12.5 15.06 18.3 9.4 14.6 ∼ ∼ ∼\sim 8 10.85 12.6 85.8 - 26.6 10 11.773 15.416 87.8 ∼ ∼ ∼\sim − 8.2 − 8.2 -8.2-8.2
12 12.5 3600* 13.5 15.41 17.7 13.0 8.0 15.2 17.15 19.4 10.9 21.6 - 12.5 13.21 14.7 124.1 0.0 12.5 12.94 14 105.5 ∼ ∼ ∼\sim 0.0
13 11.8 3600* 18.9 23.282 27.4 12.2 60.1 28.066 28.161 28.224 9.1 137.8 - 11.8 13.13 15.3 126.9 0.0 11.8 14.18 17 107.2 ∼ ∼ ∼\sim 0.0
14 21.3 3600* 22.37 27.945 33.614 13.1 5.0 29.014 32.609 40.022 12.3 36.2 - 21.1 23.727 27.24 113.1 -0.9 22.1 25.028 27.36 88.5 ∼ ∼ ∼\sim 3.7
15 23.3 3600* 27.8 31.74 35.6 26.6 19.3 34.4 37.539 42.8 21.1 47.6 - 23.8 25.76 27.8 258.2 2.1 24 26.51 29.5 183.95 ∼ ∼ ∼\sim 3.0
16 20.3 3600* 23.314 28.188 31.058 21.5 14.8 28.516 36.398 45.788 16.2 40.4 - 14.9 20.556 23 170.1 - 26.6 16.6 22.245 25.05 175.2 ∼ ∼ ∼\sim - 18.2
17 24.8 3600* 24.7 28.71 32.6 42.6 -0.4 27.3 32.14 40.3 34.9 10.1 - 20.5 22.86 25.8 313.3 - 17.3 20.3 22.56 24.6 265.1 ∼ ∼ ∼\sim - 18.1
18 † † †\dagger 3600* 36.8 40.705 46.66 50.0 不适用 39.784 45.758 57.962 52.3 不适用 - 33.7 35.022 37.2 403.5 不适用 31.5 35.742 46.1 319.6 ∼ ∼ ∼\sim 不适用
19 87.9 3600* 35.8 42.61 47.6 65.5 - 59.2 43.2 48.65 55.2 50.3 -50.8 - 33.3 35.23 39.1 484.2 − 62.1 − 62.1 -62.1-62.1 32.6 34.483 38 430.8 ∼ ∼ ∼\sim -62.9
20 † † †\dagger 3600* 49.314 55.523 62.728 82.8 不适用 59.384 66.198 74.742 61.0 不适用 - 41.4 45.334 49.072 2598.9 不适用 43.6 46.977 50.712 495.1 ∼ ∼ ∼\sim 不适用
21 162.05 3600* 54.8 63.447 69.228 120.9 -66.1 58.114 66.601 76.128 104.1 -64.1 ∼ ∼ ∼\sim 51.2 53.88 56.7 702.3 -68.4 52.2 54.06 57.9 603.0 ∼ ∼ ∼\sim -67.7
22 † † †\dagger 3600* 86.028 93.482 99.752 179.7 不适用 96.828 106.073 116.576 166.0 不适用 - 73.1 77.706 81.4 972.2 不适用 78.514 85.124 94.006 881.1 - 不适用
23 † † †\dagger 3600* 88.5 98.495 111.628 250.9 不适用 105.824 111.651 121.918 205.1 不适用 - 81.1 84.66 88.5 1309.5 不适用 85.7 92.009 99.5721 1092.8 - 不适用
24 † † †\dagger 3600* 95.528 104.45 112.042 311.7 不适用 112.77 121.744 130.57 288.0 不适用 - 87.314 94.252 98.614 41477.0 不适用 87.3 97.16 104 1204.4 ∼ ∼ ∼\sim 不适用
25 † † †\dagger 3600* 101.914 109.653 119.128 418.3 不适用 108.224 118.921 130.386 312.9 不适用 - 100.5 104.203 107.862 21607.8 不适用 112.2 114.642 116.77 1461.2 - 不适用
26 † † †\dagger 3600* 134.814 139.454 145.256 436.9 不适用 147.012 154.7 164.26 301.8 不适用 - 120.214 125.717 132.6 1775.3 不适用 140.884 147.054 152.7141 1299.5 - 不适用
27 † † †\dagger 3600* 121.838 126.912 132.008 459.85 不适用 133.234 138.996 147.68 431.7 不适用 - 111.614 114.759 118.322 21894.5 不适用 130.672 134.609 137.4 1889 - 不适用
Instance GAMS/CPLEX SBBF SBFF GES-SBBF GES-RAND Obj. func.(xx10^(3)) Time (s) Obj. func. ( xx10^(6) ) " Avg. time (s) " Gap (%) Obj. func. ( xx10^(6) ) Avg. time (s) " Gap (%)" Sig. Obj. func. ( xx10^(6) ) Avg. time (s) " Gap (%)" Obj. func. ( xx10^(6) ) Avg. time (s) Sig. " Gap (%)" min. avg. max. min. avg. max. min. avg. max. min. avg. max. 11 10.9 3600* 12.316 14.532 18.1 9.4 12.9 12.5 15.06 18.3 9.4 14.6 ∼ 8 10.85 12.6 85.8 - 26.6 10 11.773 15.416 87.8 ∼ -8.2 12 12.5 3600* 13.5 15.41 17.7 13.0 8.0 15.2 17.15 19.4 10.9 21.6 - 12.5 13.21 14.7 124.1 0.0 12.5 12.94 14 105.5 ∼ 0.0 13 11.8 3600* 18.9 23.282 27.4 12.2 60.1 28.066 28.161 28.224 9.1 137.8 - 11.8 13.13 15.3 126.9 0.0 11.8 14.18 17 107.2 ∼ 0.0 14 21.3 3600* 22.37 27.945 33.614 13.1 5.0 29.014 32.609 40.022 12.3 36.2 - 21.1 23.727 27.24 113.1 -0.9 22.1 25.028 27.36 88.5 ∼ 3.7 15 23.3 3600* 27.8 31.74 35.6 26.6 19.3 34.4 37.539 42.8 21.1 47.6 - 23.8 25.76 27.8 258.2 2.1 24 26.51 29.5 183.95 ∼ 3.0 16 20.3 3600* 23.314 28.188 31.058 21.5 14.8 28.516 36.398 45.788 16.2 40.4 - 14.9 20.556 23 170.1 - 26.6 16.6 22.245 25.05 175.2 ∼ - 18.2 17 24.8 3600* 24.7 28.71 32.6 42.6 -0.4 27.3 32.14 40.3 34.9 10.1 - 20.5 22.86 25.8 313.3 - 17.3 20.3 22.56 24.6 265.1 ∼ - 18.1 18 † 3600* 36.8 40.705 46.66 50.0 N/A 39.784 45.758 57.962 52.3 N/A - 33.7 35.022 37.2 403.5 N/A 31.5 35.742 46.1 319.6 ∼ N/A 19 87.9 3600* 35.8 42.61 47.6 65.5 - 59.2 43.2 48.65 55.2 50.3 -50.8 - 33.3 35.23 39.1 484.2 -62.1 32.6 34.483 38 430.8 ∼ -62.9 20 † 3600* 49.314 55.523 62.728 82.8 N/A 59.384 66.198 74.742 61.0 N/A - 41.4 45.334 49.072 2598.9 N/A 43.6 46.977 50.712 495.1 ∼ N/A 21 162.05 3600* 54.8 63.447 69.228 120.9 -66.1 58.114 66.601 76.128 104.1 -64.1 ∼ 51.2 53.88 56.7 702.3 -68.4 52.2 54.06 57.9 603.0 ∼ -67.7 22 † 3600* 86.028 93.482 99.752 179.7 N/A 96.828 106.073 116.576 166.0 N/A - 73.1 77.706 81.4 972.2 N/A 78.514 85.124 94.006 881.1 - N/A 23 † 3600* 88.5 98.495 111.628 250.9 N/A 105.824 111.651 121.918 205.1 N/A - 81.1 84.66 88.5 1309.5 N/A 85.7 92.009 99.5721 1092.8 - N/A 24 † 3600* 95.528 104.45 112.042 311.7 N/A 112.77 121.744 130.57 288.0 N/A - 87.314 94.252 98.614 41477.0 N/A 87.3 97.16 104 1204.4 ∼ N/A 25 † 3600* 101.914 109.653 119.128 418.3 N/A 108.224 118.921 130.386 312.9 N/A - 100.5 104.203 107.862 21607.8 N/A 112.2 114.642 116.77 1461.2 - N/A 26 † 3600* 134.814 139.454 145.256 436.9 N/A 147.012 154.7 164.26 301.8 N/A - 120.214 125.717 132.6 1775.3 N/A 140.884 147.054 152.7141 1299.5 - N/A 27 † 3600* 121.838 126.912 132.008 459.85 N/A 133.234 138.996 147.68 431.7 N/A - 111.614 114.759 118.322 21894.5 N/A 130.672 134.609 137.4 1889 - N/A| Instance | GAMS/CPLEX | | SBBF | | | | | SBFF | | | | | | GES-SBBF | | | | | GES-RAND | | | | | | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | Obj. func.$\left(\times 10^{3}\right)$ | Time (s) | Obj. func. ( $\times 10^{6}$ ) | | | $\begin{aligned} & \text { Avg. } \\ & \text { time (s) } \end{aligned}$ | Gap (%) | Obj. func. ( $\times 10^{6}$ ) | | | Avg. time (s) | $\begin{aligned} & \text { Gap } \\ & (\%) \end{aligned}$ | Sig. | Obj. func. ( $\times 10^{6}$ ) | | | Avg. time (s) | $\begin{aligned} & \text { Gap } \\ & (\%) \end{aligned}$ | Obj. func. ( $\times 10^{6}$ ) | | | Avg. time (s) | Sig. | $\begin{aligned} & \text { Gap } \\ & (\%) \end{aligned}$ | | | | | min. | avg. | max. | | | min. | avg. | max. | | | | min. | avg. | max. | | | min. | avg. | max. | | | | | 11 | 10.9 | 3600* | 12.316 | 14.532 | 18.1 | 9.4 | 12.9 | 12.5 | 15.06 | 18.3 | 9.4 | 14.6 | $\sim$ | 8 | 10.85 | 12.6 | 85.8 | - 26.6 | 10 | 11.773 | 15.416 | 87.8 | $\sim$ | $-8.2$ | | 12 | 12.5 | 3600* | 13.5 | 15.41 | 17.7 | 13.0 | 8.0 | 15.2 | 17.15 | 19.4 | 10.9 | 21.6 | - | 12.5 | 13.21 | 14.7 | 124.1 | 0.0 | 12.5 | 12.94 | 14 | 105.5 | $\sim$ | 0.0 | | 13 | 11.8 | 3600* | 18.9 | 23.282 | 27.4 | 12.2 | 60.1 | 28.066 | 28.161 | 28.224 | 9.1 | 137.8 | - | 11.8 | 13.13 | 15.3 | 126.9 | 0.0 | 11.8 | 14.18 | 17 | 107.2 | $\sim$ | 0.0 | | 14 | 21.3 | 3600* | 22.37 | 27.945 | 33.614 | 13.1 | 5.0 | 29.014 | 32.609 | 40.022 | 12.3 | 36.2 | - | 21.1 | 23.727 | 27.24 | 113.1 | -0.9 | 22.1 | 25.028 | 27.36 | 88.5 | $\sim$ | 3.7 | | 15 | 23.3 | 3600* | 27.8 | 31.74 | 35.6 | 26.6 | 19.3 | 34.4 | 37.539 | 42.8 | 21.1 | 47.6 | - | 23.8 | 25.76 | 27.8 | 258.2 | 2.1 | 24 | 26.51 | 29.5 | 183.95 | $\sim$ | 3.0 | | 16 | 20.3 | 3600* | 23.314 | 28.188 | 31.058 | 21.5 | 14.8 | 28.516 | 36.398 | 45.788 | 16.2 | 40.4 | - | 14.9 | 20.556 | 23 | 170.1 | - 26.6 | 16.6 | 22.245 | 25.05 | 175.2 | $\sim$ | - 18.2 | | 17 | 24.8 | 3600* | 24.7 | 28.71 | 32.6 | 42.6 | -0.4 | 27.3 | 32.14 | 40.3 | 34.9 | 10.1 | - | 20.5 | 22.86 | 25.8 | 313.3 | - 17.3 | 20.3 | 22.56 | 24.6 | 265.1 | $\sim$ | - 18.1 | | 18 | $\dagger$ | 3600* | 36.8 | 40.705 | 46.66 | 50.0 | N/A | 39.784 | 45.758 | 57.962 | 52.3 | N/A | - | 33.7 | 35.022 | 37.2 | 403.5 | N/A | 31.5 | 35.742 | 46.1 | 319.6 | $\sim$ | N/A | | 19 | 87.9 | 3600* | 35.8 | 42.61 | 47.6 | 65.5 | - 59.2 | 43.2 | 48.65 | 55.2 | 50.3 | -50.8 | - | 33.3 | 35.23 | 39.1 | 484.2 | $-62.1$ | 32.6 | 34.483 | 38 | 430.8 | $\sim$ | -62.9 | | 20 | $\dagger$ | 3600* | 49.314 | 55.523 | 62.728 | 82.8 | N/A | 59.384 | 66.198 | 74.742 | 61.0 | N/A | - | 41.4 | 45.334 | 49.072 | 2598.9 | N/A | 43.6 | 46.977 | 50.712 | 495.1 | $\sim$ | N/A | | 21 | 162.05 | 3600* | 54.8 | 63.447 | 69.228 | 120.9 | -66.1 | 58.114 | 66.601 | 76.128 | 104.1 | -64.1 | $\sim$ | 51.2 | 53.88 | 56.7 | 702.3 | -68.4 | 52.2 | 54.06 | 57.9 | 603.0 | $\sim$ | -67.7 | | 22 | $\dagger$ | 3600* | 86.028 | 93.482 | 99.752 | 179.7 | N/A | 96.828 | 106.073 | 116.576 | 166.0 | N/A | - | 73.1 | 77.706 | 81.4 | 972.2 | N/A | 78.514 | 85.124 | 94.006 | 881.1 | - | N/A | | 23 | $\dagger$ | 3600* | 88.5 | 98.495 | 111.628 | 250.9 | N/A | 105.824 | 111.651 | 121.918 | 205.1 | N/A | - | 81.1 | 84.66 | 88.5 | 1309.5 | N/A | 85.7 | 92.009 | 99.5721 | 1092.8 | - | N/A | | 24 | $\dagger$ | 3600* | 95.528 | 104.45 | 112.042 | 311.7 | N/A | 112.77 | 121.744 | 130.57 | 288.0 | N/A | - | 87.314 | 94.252 | 98.614 | 41477.0 | N/A | 87.3 | 97.16 | 104 | 1204.4 | $\sim$ | N/A | | 25 | $\dagger$ | 3600* | 101.914 | 109.653 | 119.128 | 418.3 | N/A | 108.224 | 118.921 | 130.386 | 312.9 | N/A | - | 100.5 | 104.203 | 107.862 | 21607.8 | N/A | 112.2 | 114.642 | 116.77 | 1461.2 | - | N/A | | 26 | $\dagger$ | 3600* | 134.814 | 139.454 | 145.256 | 436.9 | N/A | 147.012 | 154.7 | 164.26 | 301.8 | N/A | - | 120.214 | 125.717 | 132.6 | 1775.3 | N/A | 140.884 | 147.054 | 152.7141 | 1299.5 | - | N/A | | 27 | $\dagger$ | 3600* | 121.838 | 126.912 | 132.008 | 459.85 | N/A | 133.234 | 138.996 | 147.68 | 431.7 | N/A | - | 111.614 | 114.759 | 118.322 | 21894.5 | N/A | 130.672 | 134.609 | 137.4 | 1889 | - | N/A |

终止（用 表示）， ∗ ∗ *** 报告了找到的最佳解决方案。从表 5 中可以看出，10 个实例中只有 7 个可以在 3600 秒内通过 GAMS/CPLEX 进行最佳求解。对于其余 3 个问题实例，它以可行的解决方案终止，但没有证明最优性（但是，结果很可能是最优的）。可以看出，SBBF 和 SBFF 的性能是可以接受的，因为这两种算法都可以为 10 个问题实例中的 9 个实现最佳（最佳找到）总成本。随着问题大小的增加，最差 （max） 值与最佳 （min） 值的偏差平均增加。SBBF 报告的统计数据价值优于 SBFF 报告的对应物的案件数量相对较高，这表明 SBBF 的表现优于 SBFF。对于 GES，情况有所不同。GES 在所有实例上持续执行。除了问题实例 5 和 10 之外，在其余 8 个实例上，GES 在每个问题的 10 次运行中始终产生相同的结果。最差结果和最佳结果之间的偏差，例如，05 是 1.6 % 1.6 % 1.6%1.6 \% ，例如 10 是 5.8 % 5.8 % 5.8%5.8 \% ，其余 8 个实例是 0 % 0 % 0%0 \% ，这是一个相当可接受的性能。但是，GES 的良好性能是以牺牲更多计算时间为代价的。GES 的执行时间大于 SBBF 和 SBFF。但这是合理的，因为 GES 是一种进化算法，而 SBBF 和 SBFF 是一次性建设性启发式算法。

表 5 的结果适用于异构队列的问题。为了更深入地了解算法的性能，表 6 报告了同构队列情况的结果。在此表中，问题数据与表 5 中的相应问题相同，只有车辆均为 Truck 类型。可以看出，GES 的性能是稳定的，最好和最差的性能之间没有偏差。它总能找到最优或最佳找到的解决方案。在这里，SBBF 和 SBFF 的性能是可以接受的，因为它们都找到了 10 个实例中 9 个实例的最佳解决方案。这意味着 SBO 算法执行可接受，并提供良好的订单排列以将它们连续分配给车辆。作为另一个观察结果，虽然表 6 中的所有测试问题实例都可以在不到一小时的时间内以最佳方式解决，但当队列变得异构时，无法解决三个实例。因此，异构的车队使牛奶线配送系统的优化变得更加困难。

表 7 总结了较大问题实例的结果。可以看出，没有问题实例我们可以保证结果的最优性，因为 GAMS/CPLEX 在 3600 s 内没有获得最优解。对于实例 11-17、19 和 21，获得的解决方案可能不是最优的。对于较小的问题（例如实例 11-17），GAMS/CPLEX 的性能相对可接受，尽管它被 GES 击败（实例 15 除外）。但是，对于较大的问题，其性能会急剧下降（请参阅实例 19 和 21）。比较 SBBF 和 SBFF 结果表明，SBBF 在所有统计数据上的表现都优于 SBFF。哪个 SBFF 可以报告比 SBBF 报告的统计数据更有价值的统计数据没有问题。根据 Husseinzadeh Kashan （2015） 的说法，通过近似双样本 t t tt 检验，对 SBBF 与 SBFF 和 GES-SBBF 与 GES-RAND 的性能进行了统计分析。在 17 个实例中有 15 个实例中，差异很大（请参阅标题为“Sig”的左起第一列）。这里的符号 ' - ' 和 ' ∼ ∼ ∼\sim ' 分别表示 SBFF 的性能更差，并且与 SBBF 的性能相似。另一方面，SBFF 在平均 CPU 时间方面效率更高。因此，可以得出结论，SBBF 获得了更好的目标函数，而 SBFF 的效率更高（如图 6 所示）。

将 GES-SBBF 与 GES-RAND 进行比较，发现在 17 个问题中有 11 个问题上，GES-SBBF 的最小值优于 GES-RAND，而在 4 个问题上更差。在 2 个问题上，两种算法执行相同的作。就 Avg 或 Max 性能而言，在 17 个问题中的 14 个问题上，GES-SBBF 表现出更好的性能，而在 3 个问题上，情况正好相反。在 17 个实例中，有 5 个实例存在 GES-SBBF 和 GES-RAND 之间的差异很大。也就是说，GES-SBBF 更好

图 6.不同算法的目标函数 （a） 和 CPU 时间 （b）。

表 8.解决案例研究问题的结果。
箱 GAMS/CPLEX SBBF SBFF GES-SBBF GES-RAND

Obj. func.（ × 10 6 × 10 6 xx10^(6)\times 10^{6} ）		 时间 （s） Obj. func. ( × 10 6 ) × 10 6 (xx10^(6))\left(\times 10^{6}\right) 平均时间 （s）
Obj. func.（ × 10 6 × 10 6 xx10^(6)\times 10^{6} ）		 平均时间 （s）
Obj. func.（ × 10 6 × 10 6 xx10^(6)\times 10^{6} ）		 平均时间 （s）
Obj. func.（ × 10 6 × 10 6 xx10^(6)\times 10^{6} ）		 平均时间 （s）
最小 平均。 麦克斯。 最小 平均。 麦克斯。 最小 平均。 麦克斯。 最小 平均。 麦克斯。
A † † †\dagger 3600* 63.897 70.7259 76.429 495.1 68.294 76.237 89.369 354.39 59.314 65.56 71.284 1396.2 60.15 67.381 73.38 1289.6
B † † †\dagger 3600* 68.6 74.638 81.1 196.8 74.76 81.377 88 146.3 65.7 71.398 75.7 967.2 65.3 69.26 73.7 977.5
C † † †\dagger 3600* 91.8 101.708 109.814 361.5 101.498 109.911 117.854 296.1 88.2 93.68 101.1 1583.5 93.216 99.118 106.6 1613.7
Case GAMS/CPLEX SBBF SBFF GES-SBBF GES-RAND Obj. func. ( xx10^(6) ) Time (s) Obj. func. (xx10^(6)) Avg. time (s) Obj. func. ( xx10^(6) ) Avg. time (s) Obj. func. ( xx10^(6) ) Avg. time (s) Obj. func. ( xx10^(6) ) Avg. time (s) min. avg. max. min. avg. max. min. avg. max. min. avg. max. A † 3600* 63.897 70.7259 76.429 495.1 68.294 76.237 89.369 354.39 59.314 65.56 71.284 1396.2 60.15 67.381 73.38 1289.6 B † 3600* 68.6 74.638 81.1 196.8 74.76 81.377 88 146.3 65.7 71.398 75.7 967.2 65.3 69.26 73.7 977.5 C † 3600* 91.8 101.708 109.814 361.5 101.498 109.911 117.854 296.1 88.2 93.68 101.1 1583.5 93.216 99.118 106.6 1613.7| Case | GAMS/CPLEX | | SBBF | | | | SBFF | | | | GES-SBBF | | | | GES-RAND | | | | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | Obj. func. ( $\times 10^{6}$ ) | Time (s) | Obj. func. $\left(\times 10^{6}\right)$ | | | Avg. time (s) | Obj. func. ( $\times 10^{6}$ ) | | | Avg. time (s) | Obj. func. ( $\times 10^{6}$ ) | | | Avg. time (s) | Obj. func. ( $\times 10^{6}$ ) | | | Avg. time (s) | | | | | min. | avg. | max. | | min. | avg. | max. | | min. | avg. | max. | | min. | avg. | max. | | | A | $\dagger$ | 3600* | 63.897 | 70.7259 | 76.429 | 495.1 | 68.294 | 76.237 | 89.369 | 354.39 | 59.314 | 65.56 | 71.284 | 1396.2 | 60.15 | 67.381 | 73.38 | 1289.6 | | B | $\dagger$ | 3600* | 68.6 | 74.638 | 81.1 | 196.8 | 74.76 | 81.377 | 88 | 146.3 | 65.7 | 71.398 | 75.7 | 967.2 | 65.3 | 69.26 | 73.7 | 977.5 | | C | $\dagger$ | 3600* | 91.8 | 101.708 | 109.814 | 361.5 | 101.498 | 109.911 | 117.854 | 296.1 | 88.2 | 93.68 | 101.1 | 1583.5 | 93.216 | 99.118 | 106.6 | 1613.7 |

比 GES-RAND 多（参见左起第二列中带有符号 ' - ' 的行，标题为 'Sig.'）。对于其余问题，差异在统计上不显著。但是，GES-SBBF 的一般性能优于 GES-RAND，对于较大的问题尤其如此。这表明，从 SBBF 生成的更高效的解决方案启动 GES 会影响 GES 的最终输出。

在标题 i ¨ j i ¨ Å j G a p ( % ) i ¨ j i ¨ Å j G a p ( % ) i^(¨)_(j)i^(¨)"Å"_(j)Gap(%)\ddot{i}_{j} \ddot{i} \AA_{j} G a p(\%)Å 为 ' 的列中，使用间隙百分比将算法与 GAMS/CPLEX 提供的最佳/最佳找到的解决方案进行比较。gap 的值由 （69） 计算。
G a p o b j = O b j a l g − O b j o p t O b j o p t G a p o b j = O b j a l g − O b j o p t O b j o p t Gap_(obj)=(Obj_(alg)-Obj_(opt))/(Obj_(opt))G a p_{o b j}=\frac{O b j_{a l g}-O b j_{o p t}}{O b j_{o p t}}

其中 O b j alg O b j alg  Obj_("alg ")O b j_{\text {alg }} 是 SBBF 或 SBFF 或 GES-SBBF 或 GES-RAND 的客观值，并且 O b j opt O b j opt  Obj_("opt ")O b j_{\text {opt }} 是最优或最佳找到的解决方案的客观值。在表 7 的 'Gap （%）' 列下，正值表示精确解决方案给出了更好的目标，而负值和零值表明算法获得的结果比模型找到的最佳解决方案或类似结果更好。对于 SBBF，差距在 6 个实例中为正，而在 3 个实例中可能会找到更好的结果。SBFF 的情况几乎相同。但是，对于基于 GES 的算法，情况有所不同。在这里，除了一两种情况外，GES 的性能要么相同（在实例 12 和 13 上），要么优于 GAMS/CPLEX。SBBF （GES-SBBF） 和 SBFF （GES-RAND） 的整体性能表明，与 SBBF （GES-SBBF） 相比，SBFF （GES-RAND） 的最小值和最大值之间的差异更大，这表明性能不太稳定。


5.3.2. 解决案例研究问题


针对一个真实数据问题，该问题由 GAMS/CPLEX 的 65 个已装满的托盘的正向订单和 57 个空托盘的向后订单（案例 A）、49 个已装满的托盘的正向订单和 34 个空托盘的反向订单（案例 B）和 57 个已装满的托盘的正向订单和 50 个空托盘的向后订单（案例 C）组成， SBBF、SBFF 和 GES 及其结果如表 8 所示。GAMS/CPLEX 在时间限制内找不到可行的整数解（ † † †\dagger 表 8 中）。算法之间在目标函数值方面的差异很大，并且

图 7.案例研究问题的循环取货路线（案例 A）。

图 8.范宁为每辆卡车提出了案例研究问题（案例 A）。
图 8.继续。

SBBF 在案例 A、B 和 C 上的表现（平均）差不 7.7 % , 9.0 % 7.7 % , 9.0 % 7.7%,9.0%7.7 \%, 9.0 \% 多或 8.0 % 8.0 % 8.0%8.0 \% 优于 SBFF。该指数 5.8 % 5.8 % 5.8%5.8 \% 介于 2.7 % , − 3 % 2.7 % , − 3 % 2.7%,-3%2.7 \%,-3 \% GES-SBBF 和 GES-RAND 之间。仅从案例 B 中可以看出，GES-RAND 的表现优于 GES-SBBF。为了解释这种行为，我们调查了这种情况的数据结构，并观察到与其他两种情况相比，应该交付/提取的托盘数量更少。因此，我们面临着相对较小尺寸物品的包装问题，其中局部最优的数量明显大于相对大尺寸物品的包装情况。因此，以良好的初始种子开始的 GES-SBBF 可能会更有可能陷入这种局部最优值。另一方面，GES-RAND 有机会逐步改进随机的初始种子，并以更好的质量获得最终输出。

图 7 显示了 SBBF 针对情况 A 问题提出的路由。该解决方案显示了不同类型的装运，即循环取货（例如拖车 02）和直接装运（例如卡车 04）。此外，该算法还确定了每辆车的装箱情况，如图 8 所示。在装箱时会考虑现实世界的条件，例如托盘的兼容性、可堆叠性和托盘的大小。解决案例研究问题的结果也证明了所提出的算法在寻找可接受解决方案方面的有效性和效率。例如，对于案例 A，与直接发货 89 , 821 , 000 89 , 821 , 000 89,821,00089,821,000 的 IRR 订单成本相比，SBBF （GES-SBBF） 的循环取货物流平均可以产生约 26.9 % 26.9 % 26.9%26.9 \% （ 37 % 37 % 37%37 \% ） 的改进。SBBF （GES-SBBF） 获得的最大节省是 40.5 % 40.5 % 40.5%40.5 \% （） 51.4 % 51.4 % 51.4%51.4 \% ），这是相当大的。解决方案的实施将导致成本降低，同时考虑现实世界中面临的条件。拟议的循环取线物流规划方法已作为决策支持系统 （DSS） 实施，目前已在 SAIPA 公司的物流部门使用。


6. 结束语和未来的研究方向


在本文中，研究了一种前向-后向分配系统，该系统基于将零件托盘从供应商分配到装配厂，以及将空托盘从装配厂运输到供应商的实际问题。提出了一个混合整数规划公式，该公式考虑了异构车队的路线、托盘的正向分布、空托盘的反向分布和订单的兼容性。此外，应在特定时间窗口内执行前向和后向分发。为了解决使用数学公式无法有效解决的现实世界问题，提出了一种两个版本的启发式算法。这些算法混合了最大加权二分匹配算法、最佳拟合/首次拟合算法和两种改进启发式算法。此外，我们在分组进化策略 （GES） 算法的主体中使用了所提出的最佳拟合策略，以获得有效的元启发式方法。将算法在小型实例上的性能与通过将数学模型求解到最优性而获得的结果进行了比较。结果表明，最佳拟合策略会产生更好的结果，但第一个拟合策略在解决手头的问题方面更有效。此外，还发现基于 GES 的算法比建设性启发式算法有效得多。然后，将算法应用于解决一个案例研究问题，结果表明，所提出的算法可以高效且有效地为问题提供解决方案，并可以考虑所有现实世界的条件。对于未来的研究方向，可以考虑设计和比较问题的确切方法。 另一个需要考虑的条件可能是订单的动态需求，其中可以将新订单添加到列表中，并且应该修改解决方案。还可以考虑其他目标，例如不同车辆的总排放量。

披露声明


作者未报告潜在的利益冲突。

引用


Abbasi-Pooya， A. 和 A. Husseinzadeh Kashan。2017. “用于最佳直升机路线和机组人员接送的新数学模型和混合分组进化策略算法。”计算机与工业工程 112：35-56。doi：10.1016/j.cie.2017.08.007.

Ai， TJ 和 V. Kachitvichyanukul。2009. “同时取货和投递的车辆路径问题的粒子群优化。”计算机与运筹学 36 （5）： 1693-1702。doi：10.1016/j.cor.2008.04.003.

阿拉冈，DP，Jr.，AGN Novaes 和 MMM Luna。2019. “一种基于代理的方法，用于评估循环播放 OEM 运营中的协作策略。”计算机与工业工程129：545-555。doi：10.1016/j.cie.2019.01.026.

Baldacci， R.、E. Bartolini 和 A. Mingozzi。2011. “时间窗口取货和送货问题的精确算法。”运筹学 59 （2）：414-426。doi：10.1287/opre.1100.0881.

Belmecheri， F.、C. Prins、F. Yalaoui 和 L. Amodeo。2013. “具有异构车队、混合回程和时间窗的车辆路径问题的粒子群优化算法。”智能制造杂志 24 （4）： 775-789。doi：10.1007/s10845-012-0627-8.

Benavent， E.、M. Landete、E. Mota 和 G. Tirado。2015. “具有 LIFO 约束的多辆车取货和交付问题。”欧洲运筹学杂志 243 （3）：752-762。doi：10.1016/j.ejor.2014.12.029.

Berbeglia， G.， J.-F.科尔多、I. Gribkovskaia 和 G. Laporte。2007. “静态取货和送货问题：分类方案和调查。”前 15 名 （1）：1-31。doi：10.1007/s11750-007-0009-0.

Berbeglia， G.， J. F. Cordeau 和 G. Laporte。2010. “动态取货和送货问题。”欧洲运筹学杂志 202 （1）： 8-15。doi：10.1016/j.ejor.2009.04.024.

Bettinelli， A.、V. Chacchiani、TG Crainic 和 D. Vigo。2018. 具有时间窗口和同步的多程取货和配送问题的 Branch-and-Cut-and-Price：具有时间窗口和同步的多行程取货和配送问题的 Branch-and-Cut-and-Price，（1 月）。

博伊森，N.，S. Emde，M. Hoeck 和 M. Kauderer。2015. “汽车行业的零件物流：决策问题、文献综述和研究议程。”欧洲运筹学杂志 242 （1）： 107-120。doi：10.1016/j.ejor.2014.09.065 .

Chen， Q.， K. Li， 和 Z. Liu.2014. “具有拆分负载的未成对取货和送货车辆路径问题的模型和算法。”运输研究 E 部分：物流与运输评论 69：218-235。doi：10.1016/j.tre.2014.06.010.

Cherkesly， M.、G. Desaulniers、S. Irnich 和 G. Laporte。2015. “时间窗口和多个堆栈的取货和配送问题的 Branch-price-and-cut 算法。”欧洲运筹学杂志， doi：10.1016/j.ejor.2015.10.046.

Cherkesly， M.、G. Desaulniers 和 G. Laporte。2015. “基于群体的元启发式方法，用于时间窗口和 LIFO 加载的取货和交付问题。”计算机与运筹学 62：23-35。doi：10.1016/j.cor.2015.04.002.

Chuah， KH 和 JC Yingling。2005. “Routing for a Just-in-Time Supply Pickup and Delivery System”（即时供应取货和交付系统的路由）。运输科学 39 （3）： 328-339。doi：10.1287/trsc.1040.0092.

Du， T.， F. K. Wang， 和 P. Y. Lu.2007. “用于整合循环取货的实时车辆调度系统。”运输研究 E 部分：物流与运输评论 43 （5）： 565-577。doi：10.1016/j.tre.2006.03.001.

Edokpia， RO 和 PE Amiolemhen。2016. “使用遗传算法方法实现制造公司的运输成本最小化。”尼日利亚技术杂志 35：866-873。doi：10.4314/njt.v35i4.22.

Ghiani， G.、G. Laporte 和 R. Musmanno。2004. 物流系统规划与控制导论.艾加斯 2014 年。约翰·威利父子。doi：10.1007/s13398-014-0173-7.2.

Goksal， F. P.， I. Karaoglan 和 F. Altiparmak。2013. “同时取货和投递的车辆路径问题的混合离散粒子群优化。”计算机与工业工程 65 （1）： 39-53。doi：10.1016/j.cie.2012.01.005.

Güner， A. R.， A. Murat 和 RB Chinnam。2017. “随机瞬态网络中具有时间窗口的循环取线之旅的动态路由。”运输研究 E 部分：物流与运输评论 97：251-267。doi：10.1016/j.tre.2016.10.014.

Gyulai， D.、A. Pfeiffer、T. Sobottka 和 J. Váncza。2013. “车间物流的循环取货车辆路线方法。”Procedia CIRP 7：127-132。

Hosny， M. I. 和 CL Mumford。2010. “时间窗的单车取货和交付问题：启发式和元启发式算法的智能运算符。”启发式杂志16（3）：417-439。doi：10.1007/s10732-008-9083-1.

Hosseini， S. D.， M. A. Shirazi 和 S. M. T. F. Ghomi。2014. “整合网络中新型运输问题的 Harmony 搜索优化算法。”工程优化 46 （11）：1538-1552。doi：10.1080/0305215X.2013.854350.

侯赛因扎德·卡尚，A. 2015 年。“一种基于 Optics Inspired Optimization （OIO） 的约束优化的有效算法。”计算机辅助设计 63：52-71。doi：10.1016/j.cad.2014.12.007.

侯赛因扎德·卡尚，A.，A. A. A. Akbari 和 B. Ostadi。2015. “分组进化策略：对问题进行分组的有效方法。”应用数学建模 39 （9）：2703-2720。doi：10.1016/j.apm.2014.11.001.

Jafari-Eskandari， M.， S. J. Sadjadi， MS Jabalameli， 和 A. Bozorgi-Amiri。2009. “牛奶线问题的稳健优化方法（汽车行业供应链案例研究）”。计算机与工业工程国际会议，CIE 2009,1076-1081。doi：10.1109/ICCIE.2009.5223541.

Kilic， HS、MB Durmusoglu 和 M. Baskak。2012. “厂内循环取货配送系统的分类和建模。”国际先进制造技术杂志 62 （9-12）：1135-1146。doi：10.1007/s00170-011-3875-4.

Li， H. 和 A. Lim. 2003 年。“时间窗口取货和送货问题的元启发式方法。”国际人工智能工具杂志 12 （2）：173-186。http://www.worldscientific.com/doi/abs/10.1142/S0218213003001186。

马哈茂迪，M.和X. 周。2016. “使用时间窗口的取货和送货服务寻找车辆路径问题的最佳解决方案：一种基于状态-时空-时间网络表示的动态规划方法。”交通研究 B 部分：方法论 89：19-42。doi：10.1016/j.trb.2016.03.009.

Männel， D. 和 A. Bortfeldt。2017. “解决具有三维加载约束和重新加载禁令的取货和交付问题，生产。”制造与物流解决 264 （1）：1-19。doi：10.1016/j.ejor.2017.05.034.

Mei， H.， Y. Jingshuai， M. Teng， L. Xiuli， 和 W. Ting.2017. “基于加入时间窗口的改进 C-W 算法的循环取车路径问题建模。”交通研究程序 25：716-728。doi：10.1016/j.trpro.2017.05.453.

Nemoto， T.、K. Hayashi 和 M. Hashimoto。2010. “泰国日本汽车制造商的循环线物流”。Procedia - 社会和行为科学 2 （3）：5980-5989。doi：10.1016/j.sbspro.2010.04.012.

Nemoto， T. 和 W. Rothengatter。2012. “城市地区的高效绿色物流：汽车行业的循环取货物流。”中国城市可持续交通，第 3 卷，319-337。doi：10.1108/S2044-9941（2012）0000003017.

Parragh， SN、KF Doerner 和 RF. Hartl。2008a. “取货和送货问题调查：第一部分：客户和仓库之间的运输。”Journal für Betriebswirtschaft 58 （1）： 21-51.doi：10.1007/s11301-008-0036-4.

Parragh， SN、KF Doerner 和 RF. Hartl。2008b. “取货和送货问题调查：第二部分：取货和送货地点之间的运输。”Journal für Betriebswirtschaft 58 （2）： 81-117.doi：10.1007/s11301-008-0036-4.

Reil， S.、A. Bortfeldt 和 L. Mönch。2018. “具有回程、时间窗口和 3D 加载约束的车辆路径问题的启发式方法。”欧洲运筹学杂志 266 （3）：877-894。doi：10.1016/j.ejor.2017.10.029.

Ropke， S. 和 J.-F.科尔多。2009. “时间窗口取货和交货问题的分支和切割和价格。”交通科学 43 （3）： 267-286。doi：10.1287/trsc.1090.0272.

Ropke， S.、J. F. Cordeeau 和 G. Laporte。2007. “时间窗取货和配送问题的模型和分支和切割算法。”网络49 （4）：258-272。

萨贾迪，SJ，M. Jafari 和 T. Amini。2009. “牛奶线问题的新数学建模和遗传算法搜索（汽车行业供应链案例研究）”。国际先进制造技术杂志 44 （1-2）：194-200。doi：10.1007/s00170-008-1648-5.

Salhi， S.、A. Imran 和 NA Wassan。2014. “异构车队的多站点车辆路径问题：公式和可变邻域搜索实现。”计算机与运筹学 52：315-325。doi：10.1016/j.cor.2013.05.011.

Soleimani， H.、Y. Chaharlang 和 H. Ghaderi。2018. “考虑到可持续和绿色标准的取货和配送车辆路线问题中退货再制造产品的收集和配送。”清洁生产杂志 172：960-970。doi：10.1016/J.JCLEPRO.2017.10.124.

丁，CK，XL廖 Y.-H.Huang 和 R.-T.廖。2017. “使用元启发式算法的多车辆选择性取货和交付。”信息科学 406-407（增刊 C）：146-169。doi：10.1016/j.ins.2017.04.001.

Veenstra， M.、M. Cherkesly、G. Desaulniers 和 G. Laporte。2017. “时间窗口和处理作的取货和交货问题。”计算机与运筹学 77：127-140。doi：10.1016/j.cor.2016.07.014.

Wang， H. F. 和 Y. Y. Chen。2012. “时间窗口同时交付和取货问题的遗传算法。”计算机与工业工程 62 （1）： 84-95。doi：10.1016/j.cie.2011.08.018.

Yan， Q. 和 Q. Zhang。2015. “具有时间窗口约束的物流企业运输成本优化。”自然与社会中的离散动力学 文章 ID 365367.doi：10.1155/2015/365367.

Yu， VF 和 S.-W.林. 2014.“针对同时取货和交货的位置路由问题的多起点模拟退火启发式。”应用软计算杂志 24：284-290。doi：10.1016/j.asoc.2014.06.024.

附录


示例：让我们考虑一个有 6 个订单和以下数据的问题。前 4 条记录用于正向流，后 2 条记录用于向后流。
远期订单
订单记录 股票代码
源码
Origin code| Origin | | :---: | | code |
目的地代码
Destination code| Destination | | :---: | | code |
 不。零件数
就绪时间
Ready time| Ready | | :---: | | time |
 死线
托盘类型
Pallet type| Pallet | | :---: | | type |

订单 ( kg ) ( kg ) (kg)(\mathrm{kg}) 重量
Weight of the order (kg)| Weight of the | | :---: | | order $(\mathrm{kg})$ |
托盘数量
Number of pallets| Number of | | :---: | | pallets |
O1 DN1205365A 23028 2 664 08 : 00 08 : 00 08:0008: 00 17 : 00 17 : 00 17:0017: 00 GP5 1950 5
O2 DN1205465A 13285 1175 433 08 : 00 08 : 00 08:0008: 00 17 : 00 17 : 00 17:0017: 00 GP5 1230 3
O3 DP1307123A 12809 14 793 08 : 00 08 : 00 08:0008: 00 17 : 00 17 : 00 17:0017: 00 GP5 672.71 2
O4 DN03067125 11293 2 727 08 : 00 08 : 00 08:0008: 00 17 : 00 17 : 00 17:0017: 00 GP7 176.872 1
Forward orders Order record Stock code "Origin code" "Destination code" No. of parts "Ready time" Dead line "Pallet type" "Weight of the order (kg)" "Number of pallets" O1 DN1205365A 23028 2 664 08:00 17:00 GP5 1950 5 O2 DN1205465A 13285 1175 433 08:00 17:00 GP5 1230 3 O3 DP1307123A 12809 14 793 08:00 17:00 GP5 672.71 2 O4 DN03067125 11293 2 727 08:00 17:00 GP7 176.872 1| Forward orders | | | | | | | | | | | :--- | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | Order record | Stock code | Origin <br> code | Destination <br> code | No. of parts | Ready <br> time | Dead line | Pallet <br> type | Weight of the <br> order $(\mathrm{kg})$ | Number of <br> pallets | | O1 | DN1205365A | 23028 | 2 | 664 | $08: 00$ | $17: 00$ | GP5 | 1950 | 5 | | O2 | DN1205465A | 13285 | 1175 | 433 | $08: 00$ | $17: 00$ | GP5 | 1230 | 3 | | O3 | DP1307123A | 12809 | 14 | 793 | $08: 00$ | $17: 00$ | GP5 | 672.71 | 2 | | O4 | DN03067125 | 11293 | 2 | 727 | $08: 00$ | $17: 00$ | GP7 | 176.872 | 1 |
反向订单
订单记录 股票代码 源码 目的地代码 就绪时间 死线 托盘类型
订单重量 （kg）		 托盘数量
O5 EP01 2 23028 08:00 21:00 GP5 750 5
O6 EP02 1175 13285 08:00 21:00 GP5 450 3
Order record Stock code Origin code Destination code Ready time Dead line Pallet type Weight of the order (kg) Number of pallets O5 EP01 2 23028 08:00 21:00 GP5 750 5 O6 EP02 1175 13285 08:00 21:00 GP5 450 3| Order record | Stock code | Origin code | Destination code | Ready time | Dead line | Pallet type | Weight of the order (kg) | Number of pallets | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | O5 | EP01 | 2 | 23028 | 08:00 | 21:00 | GP5 | 750 | 5 | | O6 | EP02 | 1175 | 13285 | 08:00 | 21:00 | GP5 | 450 | 3 |

节点之间的距离如下：
Distance = [ 23028 13285 12809 11293 2 1175 23028 0 21 21 32 233 417 13285 0 65 79 178 452 12809 0 43 193 382 11293 0 184 442 2 0 359 1175 0 ]  Distance  = 23028 13285 12809 11293 2 1175 23028 0 21 21 32 233 417 13285 0 65 79 178 452 12809 0 43 193 382 11293 0 184 442 2 0 359 1175 0 " Distance "=[[,23028,13285,12809,11293,2,1175],[23028,0,21,21,32,233,417],[13285,,0,65,79,178,452],[12809,,,0,43,193,382],[11293,,,,0,184,442],[2,,,,,0,359],[1175,,,,,,0]]\text { Distance }=\left[\begin{array}{ccccccc} & 23028 & 13285 & 12809 & 11293 & 2 & 1175 \\ 23028 & 0 & 21 & 21 & 32 & 233 & 417 \\ 13285 & & 0 & 65 & 79 & 178 & 452 \\ 12809 & & & 0 & 43 & 193 & 382 \\ 11293 & & & & 0 & 184 & 442 \\ 2 & & & & & 0 & 359 \\ 1175 & & & & & & 0 \end{array}\right]

我们假设节点之间运输的成本和时间矩阵是根据车辆的类型提供的。可用的车辆类型及其功能如下：
车辆

承重能力 ( kg ) ( kg ) (kg)(\mathrm{kg})
Weight capacity (kg)| Weight capacity | | :---: | | $(\mathrm{kg})$ |

车辆装载长度 ( m ) ( m ) (m)(\mathrm{m})
Vehicle loading length (m)| Vehicle loading | | :---: | | length $(\mathrm{m})$ |

车辆装载宽度 ( m ) ( m ) (m)(\mathrm{m})
Vehicle loading width (m)| Vehicle loading | | :---: | | width $(\mathrm{m})$ |

车辆装载高度 ( m ) ( m ) (m)(\mathrm{m})
Vehicle loading height (m)| Vehicle loading | | :---: | | height $(\mathrm{m})$ |
拖车 22000 12.5 2.6 2.5
卡车 6000 6 2.2 2.4
皮卡车 1800 2.3 1.7 1.8
Vehicle "Weight capacity (kg)" "Vehicle loading length (m)" "Vehicle loading width (m)" "Vehicle loading height (m)" Trailer 22000 12.5 2.6 2.5 Truck 6000 6 2.2 2.4 Pickup truck 1800 2.3 1.7 1.8| Vehicle | Weight capacity <br> $(\mathrm{kg})$ | Vehicle loading <br> length $(\mathrm{m})$ | Vehicle loading <br> width $(\mathrm{m})$ | Vehicle loading <br> height $(\mathrm{m})$ | | :--- | :---: | :---: | :---: | :---: | | Trailer | 22000 | 12.5 | 2.6 | 2.5 | | Truck | 6000 | 6 | 2.2 | 2.4 | | Pickup truck | 1800 | 2.3 | 1.7 | 1.8 |

Pallet 的相关数据如下：
托盘类型
空托拍 ( kg ) ( kg ) (kg)(\mathrm{kg}) 的重量		 长度 （ mm ） 宽度 （ mm ） 高度 （ mm ）
GP5 150 1200 1080 765
GP7 78 800 700 690
Pallet type Weight of an empty pallet (kg) length ( mm ) width ( mm ) height ( mm ) GP5 150 1200 1080 765 GP7 78 800 700 690| Pallet type | Weight of an empty pallet $(\mathrm{kg})$ | length ( mm ) | width ( mm ) | height ( mm ) | | :--- | :---: | :---: | :---: | :---: | | GP5 | 150 | 1200 | 1080 | 765 | | GP7 | 78 | 800 | 700 | 690 |

SBBF 算法的执行如下：

步骤 1.基于相似性的排序 （SBO） 算法

根据 （46），我们有：
SimOrig = [ O 1 O 2 O 3 O 4 O 5 O 6 O 1 0 0.9535 0.9535 0.9292 0.4845 0.0774 O2 0 0.8562 0.8252 0.6062 0 O3 0 0.9049 0.5730 0.1549 O4 0 0.5929 0.0221 O5 0 0.2058 O6 0 ]  SimOrig  = O 1 O 2 O 3 O 4 O 5 O 6 O 1 0 0.9535 0.9535 0.9292 0.4845 0.0774  O2  0 0.8562 0.8252 0.6062 0  O3  0 0.9049 0.5730 0.1549  O4  0 0.5929 0.0221  O5  0 0.2058  O6  0 " SimOrig "=[[,O1,O2,O3,O4,O5,O6],[O1,0,0.9535,0.9535,0.9292,0.4845,0.0774],[" O2 ",,0,0.8562,0.8252,0.6062,0],[" O3 ",,,0,0.9049,0.5730,0.1549],[" O4 ",,,,0,0.5929,0.0221],[" O5 ",,,,,0,0.2058],[" O6 ",,,,,,0]]\text { SimOrig }=\left[\begin{array}{ccccccc} & O 1 & O 2 & O 3 & O 4 & O 5 & O 6 \\ O 1 & 0 & 0.9535 & 0.9535 & 0.9292 & 0.4845 & 0.0774 \\ \text { O2 } & & 0 & 0.8562 & 0.8252 & 0.6062 & 0 \\ \text { O3 } & & & 0 & 0.9049 & 0.5730 & 0.1549 \\ \text { O4 } & & & & 0 & 0.5929 & 0.0221 \\ \text { O5 } & & & & & 0 & 0.2058 \\ \text { O6 } & & & & & & 0 \end{array}\right]

根据 （47），我们有：
SimDest = [ O 1 O 2 O 3 O 4 O 5 O 6 O 1 0 0.2058 0.9226 1 0.4845 0.6062 O 2 0 0.1881 0.2058 0.0774 0 O 3 0 0.9226 0.5044 0.5398 O 4 0 0.4845 0.6062 O5 0 0.9535 O6 0 ]  SimDest  = O 1 O 2 O 3 O 4 O 5 O 6 O 1 0 0.2058 0.9226 1 0.4845 0.6062 O 2 0 0.1881 0.2058 0.0774 0 O 3 0 0.9226 0.5044 0.5398 O 4 0 0.4845 0.6062  O5  0 0.9535  O6  0 " SimDest "=[[,O1,O2,O3,O4,O5,O6],[O1,0,0.2058,0.9226,1,0.4845,0.6062],[O2,,0,0.1881,0.2058,0.0774,0],[O3,,,0,0.9226,0.5044,0.5398],[O4,,,,0,0.4845,0.6062],[" O5 ",,,,,0,0.9535],[" O6 ",,,,,0]]\text { SimDest }=\left[\begin{array}{ccccccc} & O 1 & O 2 & O 3 & O 4 & O 5 & O 6 \\ O 1 & 0 & 0.2058 & 0.9226 & 1 & 0.4845 & 0.6062 \\ O 2 & & 0 & 0.1881 & 0.2058 & 0.0774 & 0 \\ O 3 & & & 0 & 0.9226 & 0.5044 & 0.5398 \\ O 4 & & & & 0 & 0.4845 & 0.6062 \\ \text { O5 } & & & & & 0 & 0.9535 \\ \text { O6 } & & & & & 0 \end{array}\right]

对两个矩阵求平均值得到顶级相似性矩阵，如下所示：
SimMat = [ O 1 O 2 O 3 O 4 O 5 O 6 O 1 0 0.5796 0.9381 0.9646 0.4845 0.3418 O 2 0 0.5221 0.5155 0.3418 0 O 3 0 0.9137 0.5387 0.3473 O 4 0 0.5387 0.3142 O 5 0 0.5796 O 6 0 ]  SimMat  = O 1 O 2 O 3 O 4 O 5 O 6 O 1 0 0.5796 0.9381 0.9646 0.4845 0.3418 O 2 0 0.5221 0.5155 0.3418 0 O 3 0 0.9137 0.5387 0.3473 O 4 0 0.5387 0.3142 O 5 0 0.5796 O 6 0 " SimMat "=[[,O1,O2,O3,O4,O5,O6],[O1,0,0.5796,0.9381,0.9646,0.4845,0.3418],[O2,,0,0.5221,0.5155,0.3418,0],[O3,,,0,0.9137,0.5387,0.3473],[O4,,,,0,0.5387,0.3142],[O5,,,,,0,0.5796],[O6,,,,,,0]]\text { SimMat }=\left[\begin{array}{ccccccc} & O 1 & O 2 & O 3 & O 4 & O 5 & O 6 \\ O 1 & 0 & 0.5796 & 0.9381 & 0.9646 & 0.4845 & 0.3418 \\ O 2 & & 0 & 0.5221 & 0.5155 & 0.3418 & 0 \\ O 3 & & & 0 & 0.9137 & 0.5387 & 0.3473 \\ O 4 & & & & 0 & 0.5387 & 0.3142 \\ O 5 & & & & & 0 & 0.5796 \\ O 6 & & & & & & 0 \end{array}\right]

通过解决最大权重匹配问题的实例，根据相似度值对订单进行配对，将产生以下匹配项：

  • O4 与 O1 匹配，产生 O4-O1 对

  • O6 与 O5 匹配，得到 O6-O5 对

  • O3 与 O2 匹配，产生 O3-O2 对

现在我们计算由 O4-O1、O6-O5 和 O3-O2 组成的对之间的相似性。例如： SimOrig ( O 4 − O 1 , O 6 − O 5 ) = SimOrig ( O 4 − O 1 , O 6 − O 5 ) = SimOrig(O4-O1,O6-O5)=\operatorname{SimOrig}(O 4-O 1, O 6-O 5)= SimOrig ( O 4 , O 6 ) + SimOrig ( O 4 , O 5 ) + SimOrig ( O 1 , O 6 ) + SimOrig ( O 1 , O 5 ) = 0.3142 + 0.5387 + 0.3418 + 0.4845 = 1.6792 SimOrig ( O 4 , O 6 ) + SimOrig ( O 4 , O 5 ) + SimOrig ( O 1 , O 6 ) + SimOrig ( O 1 , O 5 ) = 0.3142 + 0.5387 + 0.3418 + 0.4845 = 1.6792 SimOrig(O4,O6)+SimOrig(O4,O5)+SimOrig(O1,O6)+SimOrig(O1,O5)=0.3142+0.5387+0.3418+0.4845=1.6792\operatorname{SimOrig}(O 4, O 6)+\operatorname{SimOrig}(O 4, O 5)+\operatorname{SimOrig}(O 1, O 6)+\operatorname{SimOrig}(O 1, O 5)=0.3142+0.5387+0.3418+0.4845=1.6792 .此步骤的整个相似性矩阵如下所示：
SimMat 1 = [ O 4 − O 1 O 6 − O 5 O 3 − O 2 O 4 − O 1 0 1.6792 2.9469 O 6 − O 5 0 1.2279 O 3 − O 2 0 ]  SimMat  1 = O 4 − O 1 O 6 − O 5 O 3 − O 2 O 4 − O 1 0 1.6792 2.9469 O 6 − O 5 0 1.2279 O 3 − O 2 0 " SimMat "1=[[,O4-O1,O6-O5,O3-O2],[O4-O1,0,1.6792,2.9469],[O6-O5,,0,1.2279],[O3-O2,,,0]]\text { SimMat } 1=\left[\begin{array}{cccc} & O 4-O 1 & O 6-O 5 & O 3-O 2 \\ O 4-O 1 & 0 & 1.6792 & 2.9469 \\ O 6-O 5 & & 0 & 1.2279 \\ O 3-O 2 & & & 0 \end{array}\right]

通过解决最大权重匹配问题的实例，根据其相似性值配对成对的订单，将产生以下匹配：

  • O3-O2 与 O4-O1 匹配，产生对 O3O2-O4O1

  • O6-05 与自身匹配，产生对 O605-0605，本质上是 O6O5。

现在我们计算由 O3O2-04O1、O6O5-O6O5 组成的对之间的相似性，如下所示：
SimOrig ( O 3 O 2 − O 4 O 1 , O 6 O 5 − O 605 ) = SimOrig ( O 3 O 2 , O 6 O 5 ) + SimOrig ( O 3 O 2 , O 6 O 5 ) + SimOrig ( O 4 O 1 , O 605 ) SimOrig ( O 3 O 2 − O 4 O 1 , O 6 O 5 − O 605 ) = SimOrig ( O 3 O 2 , O 6 O 5 ) + SimOrig ( O 3 O 2 , O 6 O 5 ) + SimOrig ( O 4 O 1 , O 605 ) SimOrig(O3O2-O4O1,O6O5-O 605)=SimOrig(O3O2,O6O5)+SimOrig(O3O2,O6O5)+SimOrig(O4O1,O 605)\operatorname{SimOrig}(O 3 O 2-O 4 O 1, O 6 O 5-O 605)=\operatorname{SimOrig}(O 3 O 2, O 6 O 5)+\operatorname{SimOrig}(O 3 O 2, O 6 O 5)+\operatorname{SimOrig}(O 4 O 1, O 605) + SimOrig ( O 4 O 1 , O 6 O 5 ) = 1.2279 + 1.2279 + 1.6792 + 1.6792 = 5.8142 + SimOrig ( O 4 O 1 , O 6 O 5 ) = 1.2279 + 1.2279 + 1.6792 + 1.6792 = 5.8142 +SimOrig(O4O1,O6O5)=1.2279+1.2279+1.6792+1.6792=5.8142+\operatorname{SimOrig}(O 4 O 1, O 6 O 5)=1.2279+1.2279+1.6792+1.6792=5.8142.
SimMat 2 = [ O 3 O 2 − O 4 O 1 O 6 O 5 − O 6 O 5 O 3 O 2 − O 4 O 1 0 5.8142 O 6 O 5 − O 6 O 5 0 ]  SimMat  2 = O 3 O 2 − O 4 O 1 O 6 O 5 − O 6 O 5 O 3 O 2 − O 4 O 1 0 5.8142 O 6 O 5 − O 6 O 5 0 " SimMat "2=[[,O3O2-O4O1,O6O5-O6O5],[O3O2-O4O1,0,5.8142],[O6O5-O6O5,,0]]\text { SimMat } 2=\left[\begin{array}{ccc} & O 3 O 2-O 4 O 1 & O 6 O 5-O 6 O 5 \\ O 3 O 2-O 4 O 1 & 0 & 5.8142 \\ O 6 O 5-O 6 O 5 & & 0 \end{array}\right]

配对成对的订单会产生以下匹配项：

  • O3O2-O4O1 与 O6O5 匹配，产生 O3O2O4O1-O6O5 对

因此 SBO 算法的排序结果是 3-2-4-1-6-5。


步骤 2。最佳拟合算法


第一个顺序是 O3。

  • 我们将 O3 分配给第一辆可用的战车。第一辆车在拖车、卡车和皮卡车之间随机选择。下表中的刻度表示可以容纳订单的车辆类型。由于重量和长度限制，O1 和 O5 不能分别被容纳在皮卡车上。
次序 拖车 卡车 皮卡车
O1 ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark × × xx\times
O2 ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark
O3 ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark
O4 ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark
O5 ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark × × xx\times
O6 ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark ✓ ✓ ✓\checkmark
Order Trailer Truck Pickup truck O1 ✓ ✓ xx O2 ✓ ✓ ✓ O3 ✓ ✓ ✓ O4 ✓ ✓ ✓ O5 ✓ ✓ xx O6 ✓ ✓ ✓| Order | Trailer | Truck | Pickup truck | | :--- | :---: | :---: | :---: | | O1 | $\checkmark$ | $\checkmark$ | $\times$ | | O2 | $\checkmark$ | $\checkmark$ | $\checkmark$ | | O3 | $\checkmark$ | $\checkmark$ | $\checkmark$ | | O4 | $\checkmark$ | $\checkmark$ | $\checkmark$ | | O5 | $\checkmark$ | $\checkmark$ | $\times$ | | O6 | $\checkmark$ | $\checkmark$ | $\checkmark$ |

  • 让我们假设选择了一辆卡车并为其分配了 O3。
车辆 1

总成本 = 2000000 = 2000000 =2000000=2000000 ;最佳路线： 12809 → 14 12809 → 14 12809 rarr1412809 \rightarrow 14 .

下一个顺序是 O 2 O 2 O2\mathrm{O2} 。

  • 案例 1：就时间窗口、重量和长度约束而言，将 O2 分配给车辆 1 是可行的
车辆 1

总费用 = 4660000 ; = 4660000 ; =4660000;=4660000 ; 最佳路线： 12809 → 13285 → 1 4 → 1175 12809 → 13285 → 1 4 → 1175 12809 rarr13285 rarr14rarr117512809 \rightarrow 13285 \boldsymbol{\rightarrow} \boldsymbol{1 4} \boldsymbol{\rightarrow} 1175 .

  • 案例 2：将 O2 分配给拖车类型的新车辆（随机选择）
车辆 1
总成本 = 2000000;
最佳路线： 12809 → 14 12809 → 14 12809 rarr1412809 \rightarrow 14
车辆 2
总成本 = 7800000;

最佳路线： 13285 > 1175 13285 > 1175 13285 > 117513285 \boldsymbol{>} 1175 .

接受 Case 1 并丢弃 Case 2。

下一个订单是 04。

  • 情况 1：对于所有约束，将 04 分配给车辆 1 是可行的
车辆 1

总成本 = 4716000 = 4716000 =4716000=4716000 ;最佳路线： 11293 → 12809 → 13285 → 14 →→ 1175 11293 → 12809 → 13285 → 14 →→ 1175 11293 rarr12809 rarr13285 rarr14 rarr rarr117511293 \boldsymbol{\rightarrow} 12809 \rightarrow 13285 \boldsymbol{\rightarrow} 14 \boldsymbol{\rightarrow} \boldsymbol{\rightarrow} 1175 .

  • 案例 2：将 O4 分配给卡车类型的新车辆（随机选择）
车辆 1
总成本 = 4660000;

最佳路线： 12809 → 13285 → 14 → 1175 12809 → 13285 → 14 → 1175 12809 rarr13285 rarr14 rarr117512809 \rightarrow 13285 \rightarrow 14 \rightarrow 1175 .
车辆 2

总成本 = 2000000;最佳路线： 11293 > 11293 > 11293 >11293 \boldsymbol{>} 2.

由于 4716000 < 4660000 + 2000000 4716000 < 4660000 + 2000000 4716000 < 4660000+20000004716000<4660000+2000000 接受 Case 1 并丢弃 Case 2。

下一个订单是 O1。

  • 情况 1：将 O1 分配给车辆 1 是不可行的。

  • 案例 2：将 O1 分配给拖车类型的新车辆（随机选择）
车辆 1
总成本 = 4716000;

车辆 2
总成本 = 4900000;

最佳路线： 23028 > 23028 > 23028 >23028 \boldsymbol{>} 2.
案例 2 被接受。

下一个顺序是 O 6 O 6 O6O 6 。

  • 情况 1：将 O6 分配给车辆 1 是不可行的。

  • 情况 2：对于所有约束，分配给 O 6 O 6 O6O 6 车辆 2 都是可行的
车辆 1
总成本 = 4716000 = 4716000 =4716000=4716000 ;
车辆 2
总成本 = 16358000;

最佳路线： 23028 →→ 1 1 7 5 → 13285 23028 →→ 1 1 7 5 → 13285 23028 rarr rarr1175rarr1328523028 \boldsymbol{\rightarrow} \boldsymbol{\rightarrow} \boldsymbol{1 1 7 5} \boldsymbol{\rightarrow} 13285 .

最佳路线： 11293 → 12809 → 13285 → 14 → 2 → 1175 11293 → 12809 → 13285 → 14 → 2 → 1175 11293 rarr12809 rarr13285 rarr14 rarr2rarr117511293 \rightarrow 12809 \rightarrow 13285 \rightarrow 14 \rightarrow 2 \rightarrow 1175 .最佳的

案例 3：将 O6 分配给一辆 trailer 类型的新车（随机选择）
车辆 1
总成本 = 4716000;
最佳路线：
车辆 2
总成本 = 4900000 = 4900000 =4900000=4900000 ;

最佳路线： 23028 → 23028 → 23028 rarr23028 \boldsymbol{\rightarrow} .
车辆 3
总成本 = 7800000;

最佳路线： 1175 → 13285 1175 → 13285 1175 rarr132851175 \boldsymbol{\rightarrow} 13285 .
11293 → 12809 → 13285 → 14 → 2 → 1175 11293 → 12809 → 13285 → 14 → 2 → 1175 11293 rarr12809 rarr13285 rarr14 rarr2rarr117511293 \rightarrow 12809 \rightarrow 13285 \rightarrow 14 \rightarrow 2 \rightarrow 1175.

由于 4716000 + 16358000 > 4716000 + 4900000 + 7800000 4716000 + 16358000 > 4716000 + 4900000 + 7800000 4716000+16358000 > 4716000+4900000+78000004716000+16358000>4716000+4900000+7800000 情况 3 被接受。

最后一个顺序是 O 5 O 5 O5\mathrm{O5} 。

  • 情况 1：将 O5 分配给车辆 1 是不可行的。

  • 情况 2：对于所有约束，分配给 O 5 O 5 O5O 5 车辆 2 都是可行的
车辆 1
总成本 = 4716000;
最佳路线：
11293 → 12809 → 13285 → 14 11293 → 12809 → 13285 → 14 11293 rarr12809 rarr13285 rarr1411293 \rightarrow 12809 \rightarrow 13285 \rightarrow 14
→ 2 → 1 175 → 2 → 1 175 rarr2rarr1175\rightarrow 2 \boldsymbol{\rightarrow 1} 175.

  • 案例 3：对于所有约束，将 O5 分配给车辆 3 是可行的
车辆 1
总成本 = 4716000;
最佳路线：
车辆 2
总成本 = 4900000;

最佳路线： 23028 → 2 23028 → 2 23028 rarr223028 \rightarrow 2 .
11293 → 12809 → 13285 → 14 11293 → 12809 → 13285 → 14 11293 rarr12809 rarr13285 rarr1411293 \rightarrow 12809 \rightarrow 13285 \rightarrow 14 ⇒ 2 > 1 1 7 5 ⇒ 2 > 1 1 7 5 =>2 > 1175\Rightarrow 2 \boldsymbol{> 1 1 7 5}.

  • 案例 4：将 O5 分配给一辆 trailer 类型的新战车（随机选择）
车辆 1
总成本 = 4716000;
最佳路线：
11293 → 12809 → 13285 → 14 → 2 → 1175 . 11293 → 12809 → 13285 → 14 → 2 → 1175 . {:[11293 rarr12809 rarr13285 rarr14],[ rarr2rarr1175.]:}\begin{aligned} & 11293 \rightarrow 12809 \rightarrow 13285 \rightarrow 14 \\ & \rightarrow 2 \rightarrow 1175 . \end{aligned}
车辆 2
总成本 = 4900000;

最佳路线： 23028 → 2 23028 → 2 23028 rarr223028 \rightarrow 2 .
车辆 3
总成本 = 7800000;

最佳路线： 1175 > 13285 1175 > 13285 1175 > 132851175 \boldsymbol{>} 13285 .

车辆 3

总成本 = 9058000;
最佳路线： 1175 →→→ 1175 →→→ 1175 rarr rarr rarr1175 \boldsymbol{\rightarrow} \boldsymbol{\rightarrow} \boldsymbol{\rightarrow}
13285 → 23028 13285 → 23028 13285 rarr2302813285 \rightarrow 23028.
车辆 3
总成本 = 7800000;

最佳路线： 1175 > 13285 1175 > 13285 1175 > 132851175 \boldsymbol{>} 13285 .

案例 3 的成本最低。最适合的输出是情况 3 的路由方案，总成本为 18674000 。

步骤 3。Reduce 算法


在此步骤中，我们尝试用具有相同内容的较小车辆替换较大的车辆，以降低成本。拖车最大，卡车在中间，皮卡车最小。在任何路线段上，较小的价格都更便宜。

考虑更换车辆 3。

  • 情况 1： 无法将此车辆的内容物装入皮卡车。

  • 情况 2：求解截断模型的实例，可以用卡车替换 Trailer

车辆 3

总成本 = 9058000;

最佳路线： 1175 →→ 1 3 2 8 5 → 23028 1175 →→ 1 3 2 8 5 → 23028 1175 rarr rarr13285rarr230281175 \boldsymbol{\rightarrow} \boldsymbol{\rightarrow} \boldsymbol{1 3 2 8 5} \boldsymbol{\rightarrow} 23028 .

最佳路线： 1175 → 2 → 13285 23028 1175 → 2 → 13285 23028 1175 rarr2rarr13285230281175 \boldsymbol{\rightarrow} \boldsymbol{2} \boldsymbol{\rightarrow} 13285 \boldsymbol{\boldsymbol { \boldsymbol { ~ } }} 23028 .

案例 2 被接受。


考虑更换车辆 2。

  • 情况 1： 无法将此车辆的内容物装入皮卡车。

  • 情况 2：求解截断模型的实例，可以用卡车替换 Trailer


车辆 2 总成本 = 4900000; 最佳路线： 23028 > 23028 > 23028 >23028 \boldsymbol{>} .


考虑更换车辆 1。

  • 情况 1： 无法将此车辆的内容物容纳在较小的皮卡车中。

Reduce 算法的输出是以下路由方案，总成本为 10432000。可以看出，成本显著降低。
车辆 1
总成本 = 4716000;
最佳路线：
车辆 2
总成本 = 2000000;

最佳路线： 23028 → 2 23028 → 2 23028 rarr223028 \rightarrow 2 .
车辆 3
总成本 = 3716000;
最佳路线：
1175 → 2 → 1 3 2 8 5 → 1175 → 2 → 1 3 2 8 5 → 1175 rarr2rarr13285rarr1175 \rightarrow 2 \boldsymbol{\rightarrow} \boldsymbol{1 3 2 8 5} \boldsymbol{\rightarrow} 23028.
⇒ 2 > 1175 ⇒ 2 > 1175 =>2 > 1175\Rightarrow 2 \boldsymbol{>} 1175.
步骤 3。合并算法

随机选择两辆车，例如车辆 1 和车辆 3。两者都是卡车类型。合并这两辆车的内容只能放在类似或更大的车辆中，即卡车或拖车

  • 情况 1：用拖车替换车辆 1 和车辆 3 不会为订单 O 2 O 2 O2O 2 生成到 06 的可行路径。

  • 情况 2：将车辆 1 和车辆 3 替换为卡车，无法为停靠点 O2 到 O6 生成可行的路径。

对任何一对车辆（或通常预定义的一对）继续这种机制是没有可行性的。因此我们停止了。

  1. *通讯作者。电子邮件： a.kashan@ modares.ac.ir

  2. *超出资源限制。

    † † ^(†){ }^{\dagger} 未找到整数解。