VRP and related algorithms for logistics distribution综述的笔记

选了些自己感兴趣的。

        车辆路径问题（VRP）是当今物流公司面临的最关键挑战之一。自1959年丹齐格和兰姆泽（1959年）介绍了卡车调度问题以来，研究人员一直在研究车辆路由和交付调度。它被认为是车辆路径问题（VRP）的范例，并且涉及从中央仓库到地理分散的客户的货物配送。 自那时以来，已经引入了影响该问题的几个因素，例如车辆容量的变化，与时间相关的限制，即由客户设置的时间窗口，以及涉及分配的多个仓库的存在。这些以及其他特征和要求，都被转化为问题的约束条件或定义问题的变量。这一挑战导致了一个复杂的问题，需要同时考虑多个标准和限制，包括每个客户的要求。无论如何，源自物流公司实际情况的变量和约束，都被研究人员转化为VRP变体。

 因此，下面分析的VRP变体与实际情况相关联。在大多数情况下，无论是在实践中还是在理论上，目标都是相同的，即最小化总配送成本，同时保持配送服务水平高。 配送成本构成了产品最终销售价格的很大一部分，包括固定成本和变动成本。因此，公司需要减少这两种成本中的一种或两种，以实现更高的客户需求。固定成本主要源自司机的工资或车辆使用成本，不管是使用车辆还是服务的客户数量如何，都会给配送公司带来负担。另一方面，变动成本主要源自燃料成本或每条路线的行驶时间。因此，变动成本受到路线的长度和持续时间的影响。路线的长度和持续时间由路由实际问题中包含的限制和参数以及与不同VRP变体相关的决定。因此，首先需要定义一个实际情况的VRP变体，定义问题的公式，以及构成总成本的目标函数。所有这些因素将使得寻找最合适的优化方法成为可能，以最经济的方式解决问题。

 过去，车辆路由和调度的整个过程对于业务执行人员来说是困难的，因为几乎完全基于地图使用和负责人的经验知识。如今，随着计算机的使用，这一过程变得更加容易，使用车辆路由和调度软件，尽管主要挑战仍然存在，主要是由于需要管理的大量数据以及外部环境的不断增长的需求和要求。当然，这并不意味着对计划交付负责人的经验提出质疑。市场领导者的经验是每个计算机开发者依赖的基础，以便开发集成到路由软件中的高效算法。如今，物流公司面临的需求和挑战显然比以往任何时候都更加激烈，越来越需要使用先进的系统进行交付的路由和执行。

  在这个方向上，公司充分认识到不仅影响他们日常运营的许多变体和参数，而且算法也是至关重要的。基于这一前提，本文的主要目标首先是定义物流配送中最常见的VRP变体，然后介绍用于解决特定变体的算法。在今天充满挑战且不断变化的环境中，算法对于物流公司至关重要。客户数量及其需求和要求不断增加，使用优化算法是实现有效客户服务和高效运营的关键组成部分。 所提出的研究认识到了标志着VRP变体和所提出算法的趋势，以及它们之间的相关性。具体而言，不同的VRP变体被讨论并分类为十六（16）种类别，这代表了物流配送中最常见的实际情况。具有相似特征的一些变体被分类并一起讨论在16个类别中的一个。接下来，利用系统性文献回顾介绍解决VRP变体的算法，并讨论VRP变体与各种算法之间的关系。据我们所知，没有其他论文尝试在这个分析水平上找到VRP变体和算法之间的相关性。其他有关VRP算法的文献回顾仅将它们分类为图1中呈现的高级别：精确、启发式和元启发式。我们的贡献在于我们将分析扩展到算法的更低级别的分类。因此，本文对物流行业的研究人员和从业者的贡献是重大的。Marinakis和Migdalas（2007年）是首次对VRP变体及其解决算法进行定性研究的人，为当前研究提供了良好的起点。这些VRP变体由Eksioglu等人（2009年）、Lahyani等人（2015年）和Braekers等人（2016年）的出版物中提出的其他变体进一步增强，这些变体要么在过去几年提出，要么在VRP中被认为是重要的。

        1.配送物流的VRP变体

        在这一部分中，分析了物流和配送公司在日常运营中面临的车辆路由和交付调度方面的大多数变体，以及这些变体与实际情况的关系。首先，车辆的容量构成了车辆路径问题的关键因素，因为它是实际配送案例中最受研究的因素（Kim等，2015年；Mańdziuk和Nejman，2015年），也是研究人员和从业者最先考虑的因素。容量形成了VRP的两个变体：（1）容量限制的VRP（CVRP），在这种情况下，所有车辆都是相同的，具有相同的容量；（2）异构车队VRP（HFVRP），在这种情况下，存在多种类型的车辆，每种车辆由不同的容量、固定成本和变动成本定义（Prins，2009年）。在实际实践中，很少有公司拥有一致的车队。相反，为了有效地为客户服务，公司使用不同类型的车辆。小型车辆主要服务于城市中心的客户（最后一英里配送），而大型车辆主要服务于距离更远、需要更大订单量的客户和零售商。在制定问题时，在完成路线后假定车辆返回到中央仓库是常见的。（3）然而，合作运输公司的情况，特别是那些寻求减少固定成本的第三方物流（3PL）公司，他们会与拥有车队的运输公司合作。在这种情况下，合作伙伴的车辆在完成路线后不一定返回仓库。这种情况被研究界认为是开放式VRP（OVRP）（Zachariadis和Kiranoudis，2010年）。无论车队是异构的还是均匀的，过去十年来，一些研究人员考虑了二维（2D-VRP）或三维（3D-VRP）装载约束，以确保分配的物品能够合理地装载到车辆中（Zachariadis等，2016年）。在考虑这些约束时，研究人员最常将问题分解为不同的问题，其中一个是装载问题，另一个是路径问题。在本文中，我们将2D和3D装载约束视为问题的一个单一变体，即3D-VRP，并仅关注用于车辆路由的算法。此外，与装载容量相关的另一个变体是卡车和拖车VRP（TTVRP）。在特定情况下，一些客户可能由拉拖车的卡车服务，而其他客户仅由单个卡车服务（Lin等，2010年）。这主要与城市中心和农村地区的交付和收集有限制的情况有关（Usberti等，2013年）。 在其他情况下，城市中的交通拥堵、通行限制和环境法规迫使公司使用容量较低的车辆（Quak和de Koster，2009年；Sitek，2014年；Perboli和Rosano，2019年）。在这种情况下，车辆在行驶过程中只能访问少数客户。然而，他们可以在工作日内执行多次行程，导致多次行程VRP（MTVRP）（Brandão和Mercer，1998年）。为了优化程序并在驾驶员轮班期间执行最大数量的行程，通常使用卫星设施（VRPSF）来补充车辆。在这种情况下，应用了两级VRP，通过卫星设施将货物从仓库送到客户那里（G