购物路线优化算法？
有许多商店 s 提供不同价格的商品 a。商店可能不提供特定产品。商店可以相互连接（街道）。
任务是找到从（和返回）某个家庭位置的最佳路线（循环），以使总成本最小。总价是商品价格与店铺之间距离的总和。
每个商店的物品价格都是已知的。无需前往商店即可获取此信息。
限制是：
- 买家/旅行者想要购买一系列物品，可能是所有物品
- 每件物品至少在一个商店中可用
- 商店之间的距离表示为成本，因此可以简单地将其相加购买物品的成本，在计算路线的总成本时
- ，可以多次访问商店，但这会增加旅行，因此
我使用 networkx，将商店（和家庭）建模为有向图（以距离/成本为权重），其中每个节点（商店）都保存其产品的所有价格列表优惠。
我的第一次尝试是创建一个强力解决方案，并且通过迭代所有 简单循环。然后，对于每个周期，我计算旅行费用和物品成本（即，最低价格，因为它们出现在周期的商店中）。
现在上面的方法可以工作，但无法扩展：对于 n 个节点、e 个边和 c 个基本电路，枚举所有循环的时间复杂度为 O((n+e)(c+1))（ 查找有向图的所有基本电路，SIAM Journal。计算 4，第 1 期，77-84，1975）。而且周期（电路）的数量增长得相当快：
# random 'streetlike' shop-graphs
number of shops: 3, cycles: 2
number of shops: 4, cycles: 11
number of shops: 5, cycles: 11
number of shops: 6, cycles: 60
number of shops: 7, cycles: 229
number of shops: 8, cycles: 868
number of shops: 9, cycles: 1399
number of shops: 10, cycles: 61139
number of shops: 11, cycles: 60066
number of shops: 12, cycles: 1246579
number of shops: 13, cycles: 7993420
对于更具可扩展性的问题描述有什么建议吗？我正在考虑动态或线性编程解决方案，但我很想听听想法。
更新：找到了关于该主题的完整博士论文：ftp://tesis.bbtk.ull。 es/ccppytec/cp181.pdf
There are number of shops s which offer articles a for different prices. It is possible for a shop to not offer a specific product. Shops can be connected to each other (streets).
The task is to find an optimal route (cycle) from (and back to) some home location, so that the total price is minimal. The total prices is the sum of prices of the articles and the sum of the distances between the shops.
The prices of articles are known for each shop. A shop does not need to be visited for this information.
The constraits are:
- The buyer/traveller wants to purchase a list of articles, potentially all articles
- Every article is available at least in one shop
- The distances between shops are expressed as cost, so it may be simply added to the cost of the purchased articles, when calculating the total cost of a route
- Shops can be visited more than once, but that would increase the travelling an therefore the total cost of a route
I did the initial modeling with networkx, modeling the shops (and the home) as a directed graph (with the distance/cost as weight), where each node (shop) holds a list of all prices for the products it offers.
My first attempt was to create a brute-force solution, and I succeeded by iterating over all simple cycles. Then, for each cycle I calculate the travelling costs and the costs of the articles (that is, the minimum prices, as they appear in the shops of the cycle).
Now the above works, but doesn't scale: The time complexity for enumerating all cycles is O((n+e)(c+1)) for n nodes, e edges and c elementary circuits (Finding all the elementary circuits of a directed graph. D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975). And the number of cycles (circuits) grows quite rapidly:
# random 'streetlike' shop-graphs
number of shops: 3, cycles: 2
number of shops: 4, cycles: 11
number of shops: 5, cycles: 11
number of shops: 6, cycles: 60
number of shops: 7, cycles: 229
number of shops: 8, cycles: 868
number of shops: 9, cycles: 1399
number of shops: 10, cycles: 61139
number of shops: 11, cycles: 60066
number of shops: 12, cycles: 1246579
number of shops: 13, cycles: 7993420
Any suggestions for a more scalable problem description? I'm thinking about dynamic or linear programming solutions, but I'd love to hear ideas.
update: Found a whole PhD thesis on the topic: ftp://tesis.bbtk.ull.es/ccppytec/cp181.pdf
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为我们需要更多信息 - 如果总“成本”是行驶的距离加上花费的金额，那么我们会很困难，因为它们不是相同的单位 - 所以如果距离很便宜，那么这就成为旅行推销员问题的一个例子- 确定每次成本最低的物品，然后计算获取所有物品的路线，如果距离与物品的成本相比很昂贵，那么我们就会遇到不同的问题。
总结 - 我认为如果添加约束条件，这个问题就会完成 - 每行驶一英里花费 $R$ 单位的钱，然后我们可以开始构建解决方案......
I think we need more information - if the total 'cost' is the distance traveled plus the amount of money spent then we struggle because they arn't the same units - so if distance is cheap then this becomes an instance of the traveling salesman problem - identify the lowest cost item of each time and then compute the route to get them all, if distance is expensive compared to the cost of the item, then we have different problem.
Summary - I think this problem will be complete if you add the constaint - each mile traveled costs $R$ units of money, then we can start building solutions...