问题标签 [vehicle-routing]

有许多商店s提供a不同价格的商品。商店可能不提供特定产品。商店可以相互连接（街道）。

任务是找到从（和返回）某个家庭位置的最佳路线（循环），以使总价格最小。总价是物品的价格和店铺之间的距离之和。

每个商店的物品价格都是已知的。无需访问商店即可获取此信息。

制约因素是：

• 买家/旅行者想要购买文章列表，可能是所有文章
• 每件商品至少在一家商店有售
• 商店之间的距离以成本表示，因此在计算一条路线的总成本时，可以简单地将其添加到购买物品的成本中
• 商店可以多次光顾，但这会增加旅行，因此会增加路线的总成本

我使用networkx进行了初始建模，将商店（和家庭）建模为有向图（距离/成本为权重），其中每个节点（商店）都包含其提供的产品的所有价格列表。

我的第一次尝试是创建一个蛮力解决方案，我通过迭代所有简单的循环成功了。然后，对于每个周期，我计算旅行成本和物品成本（即最低价格，因为它们出现在周期的商店中）。

现在上述工作，但不能扩展：枚举所有循环的时间复杂度是O((n+e)(c+1))n 个节点、e 个边和 c 个基本电路（查找有向图的所有基本电路。DB Johnson，SIAM Journal on Computing 4，否. 1, 77-84, 1975 )。并且周期（电路）的数量增长很快：

对于更具可扩展性的问题描述有什么建议吗？我正在考虑动态或线性编程解决方案，但我很想听听想法。

更新：找到关于该主题的完整博士论文：ftp: //tesis.bbtk.ull.es/ccppytec/cp181.pdf

我是 R 的新手。我正在尝试找出可用于物流优化问题的功能/包。例如，考虑到公司有 5 辆卡车，每辆卡车的最大运输量，我们如何才能最大化卡车运送货物的路线。容量为 500 盒，但无法达到最大限制。

请参阅下表，让您更清楚地了解我的示例问题。

表 1 显示卡车 1 和 2 达到了最大容量，但卡车 3、4 和 5 各只装了 300 个箱子。如您所见，总共有 600 个盒子占用了可用空间。我在想也许我们可以调整 3、4 和 5 号卡车的负载，以便我们可以最大限度地提高每辆卡车的容量并最大限度地减少要使用的卡车数量。

有没有人有使用 R 包或函数来解决这类问题的经验？R 提供了几个优化包，但我不知道如何开始编写脚本。谢谢你。

我已经为*在我的图表中访问 1000 个节点的最佳路线“设置了一个很好的求解器。

但我想解决“访问我的图中 1000 个给定节点中的任何 500 个的最短路径是什么”这个问题。

我想，我必须以某种方式向我的 python添加析取约束RoutingModel，但是如何？

这是我当前求解器的粗略草图：

我正在研究一个用例，其中我有多个车辆作为仓库、送货员和来自不同地点的一组客户来提供新鲜食物。客户从应用程序下订单，然后送货员收到订单并从 Van 获取食物，然后在承诺的交货时间（15 分钟）内交付。我想优化这个问题，以便降低旅行的运营成本并最大限度地缩短交货时间。只是想知道 Python 中是否有任何实现来解决 VRPTW 问题？请帮忙

我有一些不同的车辆路线优化问题变体。有不同的物品要在不同的商店被丢弃。每个商店需要 N 项金额 [a1, a2, ...., aN]。因为我们事先不知道一条路线上会有多少家商店。那么我们如何决定将多少特定物品放入车辆中呢？或者我应该先将随机数量的不同物品放入车辆中，然后使用容量限制。请提供任何指向解决此类问题的研究论文或博客的链接。

是否可以使用 OptaPlanner 或 jsprit 解决时间窗（具有实际道路距离）的不对称旅行推销员问题？

我的问题是对Capacitated Vehicle Routing Problem (CVRP)的修改，它最终也将包括时间窗口。

由于示例中已经内置了时间窗口，因此我应该不难弄清楚它们。但是，我需要更改CVRP示例的核心约束之一，而我对如何做到这一点有点迷茫。

我的模特

在我试图建模的系统中，aVehicle可以离开它Depot，去几个不同Customers的，然后加载材料。但是，我的模型与示例的不同之处在于它Vehicle可以访问任何Depot中间链来存放其当前负载。

问题

我一直在阅读文档试图弄清楚如何做到这一点，到目前为止我的基本理解是我必须改变Depot（也许通过实施Standstill）的定义才能成为地方链的一部分车辆访问，和/或可能只是Depot与Customer某种特殊规则相结合，即访问Depot清空车辆而不是增加需求。

我也一直在研究shadow variables和variable listeners，但我不知道这是否是正确的方法。这有点令人困惑。

任何人都可以提供一些提示或建议，或者在我把自己挖得太深之前指出正确的方向吗？

我正在为我的初创公司解决一个问题，我必须根据配送中心的最佳路线为送货卡车分配位置。

我现在正在使用ortools但我正在使用 gps 坐标，这与使用网格结构的给定示例不同。

现在我已经找到了一种计算坐标之间距离的方法并修改了他们的演示 python 代码，但据我所知，没有办法将 gps 坐标定义为 home depot，我正在努力从我的 home depot 获得最佳路线.

任何帮助，将不胜感激。
谢谢你

车辆路线问题的线性规划需要帮助。在车辆路径问题 (VRP) 中，车辆将服务于一组节点，从而使总行驶成本最小化。如果在节点 i 之后访问节点 j，我的决策变量是：Xij=1。参数 dij 是节点 i 和 j 之间的距离。所以，模型如下：

请注意，车辆从仓库（节点号 0）开始旅行，最后返回仓库（约束 11 和 12）。应该访问所有节点（约束 13），当进入一个节点时，它应该离开那个节点（约束 14）。但是，当我在 cplex 中为大量节点解决这个问题时，有时解决方案是无效的，因为像这样的循环：

在此解决方案的情况下，所有约束都得到满足，但此解决方案无效，因为路径未连接。现在，我的问题是我应该添加什么约束来完成模型。

我发现阅读了一个作业的所有值，从

时间窗口的路由问题非常棘手。首先，有节点和索引。我通过以下方式获得车辆（路线）的索引

对应的节点由下式获得

对于具有 5 个停靠点的特定路由问题，depot=0求解器找到具有以下索引和节点的分配：

所以索引比节点多三个，因为每辆车都在仓库开始和结束。我为每次运输定义了 1 的成本，并通过以下方式读取成本值

似乎工作：

但是当我添加时间限制时，我遇到了问题。我们先来看定义问题的代码。时间单位是分钟。

因此，每次行程需要 30 分钟，车辆可能会在停靠站闲置 40 分钟 ( slack_max=40)，并且每个停靠站应在上午 9 点至上午 10 点之间提供服务。通过实施的范围限制time_windows[0]旨在定义早上每次旅行的开始时间。但由于站点是每条路线的第一站和最后一站，因此也可以将其解释为晚上的到达时间。

所以这是我使用时间窗口的第一个困难：站点在每条路线上出现两次，但范围约束是在节点上定义的。我假设路由模型的设计不是为仓库占用两个窗口？

让我继续讨论我的问题的第二部分。我设置fix_start_cumul_to_zero = False了路线可以随时开始。另请注意，这routing.AddToAssignment(time_dimension.SlackVar(node))应该让我稍后可以访问松弛变量。现在，当我检查每个索引的时间值时，通过

用日期时间格式化，我得到合理的结果：

求解器显然倾向于提前出发时间。给定 40 分钟的最大松弛时间，每辆车也可能会晚一点启动，例如早上 8 点。

当我尝试通过以下方式读取松弛变量时，麻烦就开始了

程序崩溃并显示以下消息：

SystemError：返回 NULL 而不设置错误

这表明time_dimension每个索引都没有松弛变量。那正确吗？为什么不？

感谢您阅读这篇过多​​的帖子。这里有两个问题：

1. 是否可以定义站点的到达和离开时间窗口？
2. 如何正确读取所有节点（包括 depo）的时间窗口的松弛？