这个优化算法的正式名称?

对我来说,这很可能是 Integer Linear programming problem (ILP) ,即它的0或1变量,其中整数变量限制为集合{0,1}。这是一个NP难问题(相应的决策问题是NP完全问题)。

给定矩阵 ,约束向量 乙 c类 ,找到向量 {0,1} ^N个 所有的限制 很满意,而且成本 是最小的。

一个 和 乙

这些不平等表明你的订单是满意的:你至少可以在访问过的商店里购买每件商品的数量。请注意 乙 以及两者的列数 c类 和 . 点积 国泰

因为你要尽量减少旅行次数,所以每次旅行的费用都是一样的,所以 c类 ,和 一个 每个项目有一行,每个存储有一列,以及 乙

当然,通过尝试所有可能的2 ^N个 的值 .

由于NP-hard问题没有单一的解决方法,请考虑问题的大小,以及您希望达到的最优值的接近程度。当“库存”很大时,贪婪的方法会很有效(当你下一个要去的商店的商品总数最多时)。如果预先知道预期的最小行程数,可以将搜索光束修剪为某个值,使行程数超过某个乘系数。当搜索时间受限时,这是最好的方法(我经常进行束搜索,与本文提到的分支和切割方法密切相关,在图中,束宽达10000的每个勘探步骤占用的内存略快于30毫秒的限制)。如果搜索环境不太粗糙,模拟退火也可以工作。

search on cs.SE ;这可能是回答此类问题的更好地方。