Nano Hash - криптовалюты, майнинг, программирование

Сервисы направления карты Google более 50 путевых точек

В документации указано, что ограничение по путевым точкам составляет 8 точек. Но мне нужно найти лучший список путевых точек из более чем 50 путевых точек. Как это сделать?

Я могу найти порядок путевых точек, используя Start + Destination + 8 Waypoints, но мне нужна помощь для более чем 50 Waypoints


  • В настоящее время, в 2016 году, в документации указано, что максимальное количество путевых точек в веб-сервисе Directions API равно 23. 30.10.2016

Ответы:


1

function initMap() {
    var service = new google.maps.DirectionsService;
    var map = new google.maps.Map(document.getElementById('map'));

    // list of points
    var stations = [
        {lat: 48.9812840, lng: 21.2171920, name: 'Station 1'},
        {lat: 48.9832841, lng: 21.2176398, name: 'Station 2'},
        {lat: 48.9856443, lng: 21.2209088, name: 'Station 3'},
        {lat: 48.9861461, lng: 21.2261563, name: 'Station 4'},
        {lat: 48.9874682, lng: 21.2294855, name: 'Station 5'},
        {lat: 48.9909244, lng: 21.2295512, name: 'Station 6'},
        {lat: 48.9928871, lng: 21.2292352, name: 'Station 7'},
        {lat: 48.9921334, lng: 21.2246742, name: 'Station 8'},
        {lat: 48.9943196, lng: 21.2234792, name: 'Station 9'},
        {lat: 48.9966345, lng: 21.2221262, name: 'Station 10'},
        {lat: 48.9981191, lng: 21.2271386, name: 'Station 11'},
        {lat: 49.0009168, lng: 21.2359527, name: 'Station 12'},
        {lat: 49.0017950, lng: 21.2392890, name: 'Station 13'},
        {lat: 48.9991912, lng: 21.2398272, name: 'Station 14'},
        {lat: 48.9959850, lng: 21.2418410, name: 'Station 15'},
        {lat: 48.9931772, lng: 21.2453901, name: 'Station 16'},
        {lat: 48.9963512, lng: 21.2525850, name: 'Station 17'},
        {lat: 48.9985134, lng: 21.2508423, name: 'Station 18'},
        {lat: 49.0085000, lng: 21.2508000, name: 'Station 19'},
        {lat: 49.0093000, lng: 21.2528000, name: 'Station 20'},
        {lat: 49.0103000, lng: 21.2560000, name: 'Station 21'},
        {lat: 49.0112000, lng: 21.2590000, name: 'Station 22'},
        {lat: 49.0124000, lng: 21.2620000, name: 'Station 23'},
        {lat: 49.0135000, lng: 21.2650000, name: 'Station 24'},
        {lat: 49.0149000, lng: 21.2680000, name: 'Station 25'},
        {lat: 49.0171000, lng: 21.2710000, name: 'Station 26'},
        {lat: 49.0198000, lng: 21.2740000, name: 'Station 27'},
        {lat: 49.0305000, lng: 21.3000000, name: 'Station 28'},
    ];
    
    // Zoom and center map automatically by stations (each station will be in visible map area)
    var lngs = stations.map(function(station) { return station.lng; });
    var lats = stations.map(function(station) { return station.lat; });
    map.fitBounds({
        west: Math.min.apply(null, lngs),
        east: Math.max.apply(null, lngs),
        north: Math.min.apply(null, lats),
        south: Math.max.apply(null, lats),
    });
    
    // Show stations on the map as markers
    for (var i = 0; i < stations.length; i++) {
        if (!stations[i].name)
            continue;
        new google.maps.Marker({
            position: stations[i],
            map: map,
            title: stations[i].name
        });
    }

    // Divide route to several parts because max stations limit is 25 (23 waypoints + 1 origin + 1 destination)
    for (var i = 0, parts = [], max = 8 - 1; i < stations.length; i = i + max)
        parts.push(stations.slice(i, i + max + 1));

    // Callback function to process service results
    var service_callback = function(response, status) {
        if (status != 'OK') {
            console.log('Directions request failed due to ' + status);
            return;
        }
        var renderer = new google.maps.DirectionsRenderer;
        renderer.setMap(map);
        renderer.setOptions({ suppressMarkers: true, preserveViewport: true });
        renderer.setDirections(response);
    };
        
    // Send requests to service to get route (for stations count <= 25 only one request will be sent)
    for (var i = 0; i < parts.length; i++) {
        // Waypoints does not include first station (origin) and last station (destination)
        var waypoints = [];
        for (var j = 1; j < parts[i].length - 1; j++)
            waypoints.push({location: parts[i][j], stopover: false});
        // Service options
        var service_options = {
            origin: parts[i][0],
            destination: parts[i][parts[i].length - 1],
            waypoints: waypoints,
            travelMode: 'WALKING'
        };
        // Send request
        service.route(service_options, service_callback);
    }
  }
html, body {
    height: 100%;
    margin: 0;
    padding: 0;
}
#map {
    height: 100%;     
    width: 100%;
    height: 100%;
}
<div id="map"></div>

<!-- without API KEY set variable "max" to 8 -->
<script async defer src="https://maps.googleapis.com/maps/api/js?callback=initMap"></script>

<!-- with API KEY set variable "max" to 25 -->
<!-- <script async defer src="https://maps.googleapis.com/maps/api/js?callback=initMap&key=YOUR_API_KEY"></script>-->

С помощью следующего кода вы можете использовать столько путевых точек, сколько вам нужно, и вы никогда не получите ошибку MAX_WAYPOINTS_EXCEEDED. Не забудьте заменить «YOUR_API_KEY» на ваш API KEY или удалить &key=YOUR_API_KEY из URL-адреса API Google и установить для переменной «max» значение 8 (max = 25 при использовании API KEY, max = 8, если нет используя ключ API).

<div id="map"></div>
<script>
  function initMap() {
    var service = new google.maps.DirectionsService;
    var map = new google.maps.Map(document.getElementById('map'));

    // list of points
    var stations = [
        {lat: 48.9812840, lng: 21.2171920, name: 'Station 1'},
        {lat: 48.9832841, lng: 21.2176398, name: 'Station 2'},
        {lat: 48.9856443, lng: 21.2209088, name: 'Station 3'},
        {lat: 48.9861461, lng: 21.2261563, name: 'Station 4'},
        {lat: 48.9874682, lng: 21.2294855, name: 'Station 5'},
        {lat: 48.9909244, lng: 21.2295512, name: 'Station 6'},
        {lat: 48.9928871, lng: 21.2292352, name: 'Station 7'},
        {lat: 48.9921334, lng: 21.2246742, name: 'Station 8'},
        {lat: 48.9943196, lng: 21.2234792, name: 'Station 9'},
        {lat: 48.9966345, lng: 21.2221262, name: 'Station 10'},
        {lat: 48.9981191, lng: 21.2271386, name: 'Station 11'},
        {lat: 49.0009168, lng: 21.2359527, name: 'Station 12'},
        {lat: 49.0017950, lng: 21.2392890, name: 'Station 13'},
        {lat: 48.9991912, lng: 21.2398272, name: 'Station 14'},
        {lat: 48.9959850, lng: 21.2418410, name: 'Station 15'},
        {lat: 48.9931772, lng: 21.2453901, name: 'Station 16'},
        {lat: 48.9963512, lng: 21.2525850, name: 'Station 17'},
        {lat: 48.9985134, lng: 21.2508423, name: 'Station 18'},
        {lat: 49.0085000, lng: 21.2508000, name: 'Station 19'},
        {lat: 49.0093000, lng: 21.2528000, name: 'Station 20'},
        {lat: 49.0103000, lng: 21.2560000, name: 'Station 21'},
        {lat: 49.0112000, lng: 21.2590000, name: 'Station 22'},
        {lat: 49.0124000, lng: 21.2620000, name: 'Station 23'},
        {lat: 49.0135000, lng: 21.2650000, name: 'Station 24'},
        {lat: 49.0149000, lng: 21.2680000, name: 'Station 25'},
        {lat: 49.0171000, lng: 21.2710000, name: 'Station 26'},
        {lat: 49.0198000, lng: 21.2740000, name: 'Station 27'},
        {lat: 49.0305000, lng: 21.3000000, name: 'Station 28'},
        // ... as many other stations as you need
    ];

    // Zoom and center map automatically by stations (each station will be in visible map area)
    var lngs = stations.map(function(station) { return station.lng; });
    var lats = stations.map(function(station) { return station.lat; });
    map.fitBounds({
        west: Math.min.apply(null, lngs),
        east: Math.max.apply(null, lngs),
        north: Math.min.apply(null, lats),
        south: Math.max.apply(null, lats),
    });

    // Show stations on the map as markers
    for (var i = 0; i < stations.length; i++) {
        new google.maps.Marker({
            position: stations[i],
            map: map,
            title: stations[i].name
        });
    }

    // Divide route to several parts because max stations limit is 25 (23 waypoints + 1 origin + 1 destination)
    for (var i = 0, parts = [], max = 25 - 1; i < stations.length; i = i + max)
        parts.push(stations.slice(i, i + max + 1));

    // Service callback to process service results
    var service_callback = function(response, status) {
        if (status != 'OK') {
            console.log('Directions request failed due to ' + status);
            return;
        }
        var renderer = new google.maps.DirectionsRenderer;
        renderer.setMap(map);
        renderer.setOptions({ suppressMarkers: true, preserveViewport: true });
        renderer.setDirections(response);
    };

    // Send requests to service to get route (for stations count <= 25 only one request will be sent)
    for (var i = 0; i < parts.length; i++) {
        // Waypoints does not include first station (origin) and last station (destination)
        var waypoints = [];
        for (var j = 1; j < parts[i].length - 1; j++)
            waypoints.push({location: parts[i][j], stopover: false});
        // Service options
        var service_options = {
            origin: parts[i][0],
            destination: parts[i][parts[i].length - 1],
            waypoints: waypoints,
            travelMode: 'WALKING'
        };
        // Send request
        service.route(service_options, service_callback);
    }
  }
</script>
<script async defer src="https://maps.googleapis.com/maps/api/js?key=YOUR_API_KEY&callback=initMap"></script>
17.04.2017
  • Это не работает, поскольку вы делите маршрут на несколько частей, но эти части представляют собой фрагменты из 25 совершенно произвольных точек. Нет никакой гарантии, что точки, которые вы случайным образом сгруппировали в группы по 25, будут хотя бы близки друг к другу. На самом деле, если бы вы могли быть уверены, что point[i] близко к point[i+1], то вообще не было бы необходимости оптимизировать маршрут. 04.03.2020
  • Оптимизация очков в моем случае не понадобилась. Точки в моем случае известны и мне нужно было только их соединить (точки - это остановки общественного транспорта и обычно они идут от одной к другой подряд). Это зависит от цели. Во многих случаях это подходящее решение, но я согласен, что не для 100% случаев. Голосование за этот ответ и этот stackoverflow.com/a/43458012/3826175, включая положительные комментарии, помогло многим пользователям. Нет другого лучшего способа, пока Google не увеличит лимит. 04.03.2020
  • В вопросе предлагается найти лучший порядок путевых точек, чего этот ответ не сделает. 04.03.2020
  • Я думаю, что может быть решение. В моем случае точки обычно идут одна за другой подряд (потому что точки автовокзалов уже оптимизированы), поэтому мое решение работает хорошо. Если точки случайны, вы должны сначала отсортировать их по расстоянию - например. с использованием алгоритма haversine stackoverflow.com/a/365853/3826175 или есть более простые и быстрые алгоритмы, которые можно использовать, когда все точки находятся в радиусе несколько километров (можно считать, что земля плоская). При сортировке точек по расстоянию (не случайно) есть большая вероятность получить правильный результат при передаче точек моему решению, которое разбивает маршрут на части. 05.03.2020
  • Сортировка по расстоянию до чего? К вашей точке отсчета? Затем вы сортируете их по радиусу в сфере/окружности вокруг вас, после сортировки по расстоянию всего в 1 км точки будут находиться на расстоянии от 0 до 2 радиусов (2 км) друг от друга в зависимости от направления, в котором они расположены от вас. Если вы сортируете каждую точку по расстоянию до предыдущей ближайшей точки, то у вас есть алгоритм O (n ^ 2), который выполняет случайное блуждание, тогда лучше просто выполните случайное блуждание. Задача коммивояжера не может быть решена таким образом. Пресловутая сложность решения — вот почему путевые точки так ограничены. 05.03.2020
  • Извини, я не хочу тебя сильно обижать. Мне было важно указать, что это не даст оптимизированных маршрутов. 05.03.2020

  • 2

    Я создал обходной путь, но он немного дороже (с точки зрения вызовов API).

    Вместо того, чтобы создавать один вызов с начальной, конечной и путевой точками LatLng, я разделил путевые точки на пары, чтобы сделать вызовы по паре.

    Пример:

    Задача: проложить маршрут и проложить маршрут за 100 баллов

    Решение:

    • Вызов 1: точка 1 и точка 2
    • Вызов 2: точка 2 и точка 3
    • Вызов 3: точка 3 и точка 4

      ... и так далее.

    С этим решением вам никогда не придется беспокоиться об ограничении в 8 путевых точек, поскольку вы каждый раз делаете запрос только в 2 точки. Слабость этого решения заключается в том, что вы будете создавать много звонков, и оно съест ваши 2500 бесплатных звонков в день, если его не использовать должным образом.

    04.08.2014
  • Да, ты прав. Этот процесс израсходует весь доступный лимит бесплатных звонков. В моем случае будет 19K-20K очков в день. Так что это решение мне не поможет. 17.03.2015
  • Как насчет оптимизации маршрута? Что-нибудь за это? 05.08.2016
  • Привет, Google обычно делает свою собственную оптимизацию маршрута на лету на основе переданных вами параметров. 09.08.2016

  • 3

    К сожалению, это невозможно сделать.

    Если у вас есть бизнес-аккаунт, вы можете добавить до 25 путевых точек. Бизнес-аккаунт стоит довольно дорого.

    Вам нужно искать другого поставщика, если вам нужно использовать более 25 путевых точек.

    26.02.2014

    4

    Я нашел этот обходной путь.

    Кажется, он делает именно то, что вам нужно. взгляните: http://lemonharpy.wordpress.com/2011/12/15/working-around-8-waypoint-limit-in-google-maps-directions-api/

    26.02.2014
  • Это не поможет в моей ситуации, потому что это не дает точного порядка путевых точек для лучшей помощи в направлении водителя. 26.02.2014

  • 5

    ЗДЕСЬ Карты (https://developer.here.com/blog/delivery-made-easy-with-the-here-waypoint-sequence-api) предлагает оптимизацию путевых точек до 120 путевых точек. Загляните к ним, цены у них очень даже приемлемые.

    30.10.2016
  • Ваша ссылка не работает. 04.03.2020
  • Исправлено в обновленной ссылке. Спасибо, что обратили мое внимание на Робин. Пожалуйста, поддержите мой ответ, так как я не могу удалить ваш отрицательный голос. :) 04.03.2020
  • Это не я проголосовал за него ;) Я перешел по ссылке, чтобы узнать, почему кто-то проголосовал за него. Вы также можете улучшить качество своего ответа, предоставив краткий пример кода для путевых точек с помощью HERE API. (Тогда я сам проголосую за это) 04.03.2020
  • Новые материалы

    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..

    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..

    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..

    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..

    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..

    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..

    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..