4

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

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

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

制约因素是：

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

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

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

现在上述工作，但不能扩展：枚举所有循环的时间复杂度是O((n+e)(c+1))n 个节点、e 个边和 c 个基本电路（查找有向图的所有基本电路。DB Johnson，SIAM Journal on Computing 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

4

2 回答 2

4

一分钟前这里有一条评论链接到维基百科条目，关于看起来像这个确切问题的内容：http ://en.wikipedia.org/wiki/Traveling_purchaser_problem

从该页面，有一些链接到描述各种解决方法的论文：

动态编程：http ://www.di.unipi.it/optimize/Events/proceedings/T/C/4/TC4-1.pdf

禁忌搜索——http : //infos2008.fci.cu.edu.eg/infos/DSS_04_P024-030.pdf （这可能只会找到一个“相当不错”的解决方案，不一定是绝对最好的，但它可能会更快）

编辑：谢谢你，@soulcheck——你的评论消失了一段时间，但现在又回来了。

于 2012-01-11T20:49:21.327 回答
0

我认为我们需要更多信息——如果总“成本”是旅行的距离加上花费的金额，那么我们会很挣扎，因为它们不是相同的单位——所以如果距离很便宜，那么这就是旅行推销员问题的一个例子- 确定每次成本最低的项目，然后计算获得所有项目的路线，如果与项目成本相比距离昂贵，那么我们就有不同的问题。

总结-我认为如果您添加约束，这个问题将是完整的-每行驶一英里花费$R$单位的钱，然后我们可以开始构建解决方案...

于 2012-01-11T20:51:05.753 回答