为多个旅行者寻找最适当位置折衷的算法

Question

很长一段时间以来，我一直在想，是否有一个已知的算法可以解决以下问题，或者至少是其中的一部分。

假设有一个有限的位置集(x，y)，每个位置也有一种类型(房子，餐馆，咖啡馆，cin……)和一个权重(用户评分，性价比...)。此外，存在比其他路径更快的路径子集(取决于运输类型和期望的到达时间)。

要回答的问题是:我们是一群位于n个不同地点的人，我们想在时间T相遇，找到t类型(电影院...)的最佳地点(最小化每个人的路径长度和旅行时间)。

这听起来像是任何已知的算法吗？

致以最好的问候，罗尔夫

Answer 1

有几种算法可以解决这个问题，这个问题被称为设施选址或k中心问题(k http://en.wikipedia.org/wiki/Facility_location problem )。这是一个NP困难问题，有一些算法可以近似求解，也可以搜索空间数据库中使用的“最佳交汇点”问题。