Google 地图 - 发现较低路线的点顺序

Question

我需要一种方法来使用 Google 地图 API。

找出点之间的最佳路线

假设我有 A、B、C 和 D 四个点，我将从 A 点出发，需要找出我应该访问的最佳顺序，并在地图上绘制这些点到此的最小路线顺序。

根据我在 API 文档中的研究，很容易找到多个点之间的最低路线，但 API 需要点的顺序。就我而言，我需要 API 到 return 我最好的顺序。

我想到的解决方案是找到所有可能的路径，然后找到所有路径的最短路径，然后显示这条路径。但是这个解决方案不会有很好的性能，Google API 限制了一天可以绘制的路线数量。

Answer 1

you may pass optimizeWaypoints: true within the DirectionsRequest to allow the
Directions service to optimize the provided route by rearranging the waypoints
in a more efficient order. (This optimization is an application of the 
Travelling Salesman Problem.) All waypoints must be stopovers for 
theDirections service to optimize their route.

fiddle with {optimizeWaypoints: false}

var start = "New York, NY";
var end = "New York, NY";
var waypts = [];
var wayptsIn = ["Montreal, QBC", "Toronto, ONT", "Chicago,IL", "Winnipeg,MB", "Fargo,ND", "Calgary,AB", "Spokane,WA"];

for (var i = 0; i < wayptsIn.length; i++) {
    waypts.push({
        location: wayptsIn[i],
        stopover: true
    });
}

var request = {
    origin: start,
    destination: end,
    waypoints: waypts,
    optimizeWaypoints: false,
    travelMode: google.maps.TravelMode.DRIVING
};

same fiddle with optimizeWaypoints: true}

var start = "New York, NY";
var end = "New York, NY";
var waypts = [];
var wayptsIn = ["Montreal, QBC", "Toronto, ONT", "Chicago,IL", "Winnipeg,MB", "Fargo,ND", "Calgary,AB", "Spokane,WA"];
for (var i = 0; i < wayptsIn.length; i++) {
    waypts.push({
        location: wayptsIn[i],
        stopover: true
    });
}

var request = {
    origin: start,
    destination: end,
    waypoints: waypts,
    optimizeWaypoints: true,
    travelMode: google.maps.TravelMode.DRIVING
};

Answer 2

研究您的数据以寻找线索... 这个问题被称为 'Travelling Salesman Problem' 并且没有比您提到的强力穷举搜索方法更好的已知方法 [查找计算机科学方面的 'NP-complete']。只有使用 'extra' 有关路线的知识（例如 Google 期望的顺序），您才能击败系统，您可能可以从 'insider' 应用程序知识中获得.只有这样，您才有机会减少搜索次数。祝你好运！

Answer 3

使用这个optimizeWaypoints: true

https://developers.google.com/maps/documentation/javascript/directions#Waypoints

Google 地图 - 发现较低路线的点顺序

Google Maps - Discover order of points for the lower route

javascript

google-maps

google-maps-api-3