我正在进行一场政治活动,几十名志愿者将在未来几周内进行挨家挨户的促销活动。给定一个具有名称、地址和长/拉坐标的列表,可以使用什么算法来创建一个优化的步行列表。
发布于 2014-07-03 08:00:10
就像Steve所说的,这是一个TSP问题,并且有非常好的自由解来寻找近似解。
对于您正在寻找的东西来说,这可能是工作量太大了,但是您可以尝试使用其中一个与Google相结合的方法来找到您的坐标:https://developers.google.com/maps/documentation/directions/#DirectionsRequests的真正步行距离。
(我从未使用过这个API,所以我不知道它有多简单或有效)
发布于 2014-06-26 18:01:06
人们看到一些与旅行商问题密切相关的东西,认为它是无法解决的。
在这个主题上已经做了大量的工作,但并不是所有的工作都表明没有解决方案。根据参数和所需的解决方案,您可能会找到一些有用的东西。
您可能想看看OpenOpt python库。
另一个要查看的资源是TSP求解器与发电机。
如果您正在使用R,则有一个提供TSP包。
实际上,为您的问题实现一个解决方案有点过于复杂了,但是这应该是一个很好的起点。在这些包中,在我为您提供的链接中的文档中,您会发现有相当多的算法策略可用。您有一个小的地理区域和一小群“销售人员”,因此在合理的时间框架内计算策略所需的计算能力应该可以在桌面上使用。
实际上,您不需要找到绝对最优的策略。你只需要一个很好的。选择一个看起来最不压倒性的TSP包,然后试一试。
发布于 2014-06-30 04:00:35
这里有一个疯狂的想法:和那些熟悉社区的志愿者交谈,他们以前做过挨家挨户的工作。听听他们的建议和想法。他们可能会有任何算法都不会产生的洞察力,而这些修改对于任何计算机生成的路线列表都是有价值的。一个例子:避免在交通繁忙的街道上使用慢灯或没有灯。另一个例子是:一对志愿者在同一条街的对面工作,会比一个志愿者独自在这条街上工作更安全。
https://datascience.stackexchange.com/questions/600
复制相似问题