传送旅行者,随着时间的推移最佳利润问题

Question

我是整个旅行商问题以及stackoverflow的新手,所以如果我说一些不太正确的话,请告诉我.

介绍:

我正在尝试为涉及多个国家(地区)内的多个城市(节点)的游戏编写利润/时间优化的多重交易算法,其中:

• 在两个相连的城市之间旅行所需的物理时间总是相同的;
• 城市没有线性联系(你可以同时在一些城市之间传送);
• 一些国家(地区)拥有传送路线,通过其他国家提供最短路径.
• 旅行者(或交易者)对他的钱包,货物的重量以及在某个贸易路线中可交易的数量有限制.贸易路线可以跨越多个城市.

---

问题参数:

内存中已存在一个数据库(python:sqlite),它根据源城市和目的地城市进行交易,中间的最短路径城市作为数组和金额,以及限制因素及其总资本回报率(或在没有任何因素限制的情况下,那么只是给出总资本回报最高的方法).

• 我试图找到某个预设大块时间(即30分钟)的最佳利润
• 穿越新城市的行为实际上是同步的
• 在城市地图上旅行通常需要相同的时间(即2分钟)
• 启动第一个或任何新交易的行为与穿越一个城市地图(即2分钟)的时间相同
• 我的起点可能实际上没有有效的交易(我必须前往第一个/最近/最好的一个)

---

迄今为止的伪解决方案

优化

首先,我意识到因为我对时间有限制,并且我知道每一跳需要多长时间(包括-1用于启动交易),我可以将图形限制为跳数低于或等于的所有交易max_hops=int(max_time/route_time) -1.我删除了不属于这个时间限制的交易数据库的元素,修剪最短路径长度大于的城市max_hops.

我再次进入交易数据库,其中包括我当前城市与所有现有交易的起始城市之间的最短路径,而不是我当前的城市,并给予他们0%的回报.我会将这些限制在城市啤酒花的数量小于的地方max_hops,我还会计算当前城市到起始城市加上交易最短路径的啤酒花是否会超出max_hops并删除那些超出此限制的城市.

然后我采取其余的交易,(current_city->starting_city)并在所有目的地和起始城市之间添加0%的交易路线,因为啤酒花不会超过max_hops

然后,我为所有不在交易数据库中的城市做最后一次修剪,作为起始城市,目的地城市或最短路径城市阵列的一部分.

图搜索 我留下了一个(多)较小的交易图表,在时限内(即30分钟)可行.

因为所有连接的节点都是相邻的,所以连接默认都是加权1.我将%return除以交易中的跳数然后取倒数并加上+ 1(这意味着一个权重为1.01) 100%回程路线).在收益率为0%的情况下,我加上...... 2？

它应该返回最有利可图的路线......

---

问题:

大多,

1. 当我遗留金钱或空间并通过路径离散到单一贸易路线时,如何添加获取多条路线的能力？由于在城市内以多种价格和数量出售货物的性质,将会有很多重叠的路线.

2. 我如何惩罚启动新的贸易路线？

3. 图搜索在这种情况下是否有用？

在旁注,

3. 我应该(或者我不应该)对图表进行哪些修剪/优化？
4. 我的加权方法是否正确？我觉得它会给我不成​​比例的重量.我应该使用实际回报而不是百分比回报吗？
5. 如果我在python中编码的是python-graph这样的库适合我的需求？或者它会为我节省很多开销(据我所知,图搜索算法可能是计算密集型的)来编写一个专门的函数？
6. 我最好使用A*搜索吗？
7. 我应该预先计算交易数据库中的最短路径点并进行最大化优化,还是应该将其全部留给图搜索？
8. 你能注意到我可以提高的一切吗？

Answer 1

我认为您已经定义了一些适合称为库存路由问题的问题。我认为既然你既有商品又有硬币，旅行者就会沿着所选路线进行买卖。我们首先假设一切都是确定性的——所有商品的需求量、可用供应量、买卖价格等都是预先知道的。随机版本变得更加困难（显然）。

目标之一是在钱包和商品受到限制的情况下实现利润最大化。如果旅行者必须回家，它看起来就像一次旅行，如果不是，它看起来就像一条路。由于您没有要求旅行者访问每个节点，因此它不是 TSP。这很好——最短路径问题通常比 TSP 更容易解决。

由于侧面的限制和每个节点后续步骤的选择有限 - 我会考虑使用动态编程作为解决方案技术的第一次尝试。它将帮助您枚举您在每个阶段购买和出售的商品，并且阶段数量有限。此外，由于您对决策施加了时间限制，因此限制了选择的状态空间。

对于那些建议 Djikstra 算法的人来说——你可能是对的——标签约定需要包括时间、硬币、商品以及相应的利润。由于利润的复杂性增加，Djikstra 的假设可能不适用于此。还没有想清楚。

这是资本预算中类似问题的链接。

祝你好运 ！