gifts2017

Пример построения маршрута и оптимизация его с помощью Яндекс карт и api Яндекса 2.1

Опубликовал Трактор Трактор (Трактор) в раздел Программирование - Практика программирования

Пример использования карт Яндекса и api 2.1. Построение оптимального маршрута движения курьеров. Оптимальность маршрута считается для общественного транспорта. Потом можно переключить маршрут на автомобиль.

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

В прикреплённом архиве внешняя обработка и html файл. Они работают независимо друг от друга. Маршрут строится с использованием yandex api 2.1. Яндекс не умеет оптимизировать маршрут. Он обрабатывает полученные точки в переданном ему порядке. Для оптимизации яваскрипт рассчитывает расстояние от исходной точки до каждой точки доствки. Находит ближайшую. Делает её исходной. Повторяет расчёт для оставшихся точек. Обработанные точки помещает в итоговый массив. После того как все точки выстроены в нужном порядке Яндексу отдаётся команда на собственно построение маршрута. Результат выводится пользователю. При переключении на автомобиль повторная оптимизация маршрута не выполняется, поэтому для автомобиля маршрут может оказаться неоптимальным. Вся эта логика работает на яваскрипте. Если адрес не найден, то он исключается из списка доставки.

Обработка демонстрационная, поэтому работает в любой конфигурации, только позволяет ввести адреса доставки и показывает карту. Никаких объектов конфигурации не использует. Работает как в клиенте 1С яндекс так и в web клиенте. Тестирована в Хроме и Фирефоксе.

Осталась небольшая ошибка, которую пока решил не исправлять. Если указать два одинаковых адреса, то Яндекс сообщает об ошибке и карта не строится.

газета Суть Времени

Обновление от 03.10.2014 18:30

Исправлена ошибка при которой иногда не строился маршрут.

Информация от 08.06.2016.

На текущий момент при отображении карт Яндекса в 1С выдаётся сообщение об ошибке.Ошибка в тонком и толстом клиентах. В веб клиенте не проверял. Проверил на версии 8.3.8.1652. Маршрут при этом строится и отображается верно. Сообщение об ошибкаях можно отключить в настройках IE.

Работу под линуксом не проверял.

Ответ Яндекса на вопрос

Яндекс.Карты нельзя использовать в десктопных приложениях и закрытых системах. Только сайты.

https://yandex.ru/blog/mapsapi/28445

Скачать файлы

Наименование Файл Версия Размер Кол. Скачив.
Пример оптимизации маршрута с помощью Яндекс карт api 2.1.zip
.zip 12,48Kb
03.10.14
273
.zip 1.0 12,48Kb 273 Скачать

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Александр Медведев (anig99) 03.10.14 10:59
Какие ограничения на число точек?
2. Трактор Трактор (Трактор) 03.10.14 11:14
Какие ограничения на число точек?

(1) anig99, не знаю. В документации об этом ничего не сказано http://api.yandex.ru/maps/jsbox/2.1/
На некоторых адресах яндекс глючит. Не строит к ним маршрут.
3. Яков Коган (Yashazz) 03.10.14 11:25
Советую пробовать такие фокусы в Гугл-картах. Похожие возможности API, но стабильнее, и адреса корректнее обрабатывает.
Вообще, отличная работа проделана, респект! Главное ведь именно логику реализовать, вон, сами яндексовцы не осилили и даже плакались об этом где-то в "песочнице".
Однозначный плюс.
4. Dmitry E (harmer) 03.10.14 12:08
Обязательно скачаю, как только появятся мани.
Но есть один вопрос: почему выбран "жадный" алгоритм построения маршрута, ведь для задачи коммивояжера есть множество готовых реализаций?
5. Трактор Трактор (Трактор) 03.10.14 12:19
почему выбран "жадный" алгоритм построения маршрута

(4) harmer, потому, что я никогда ранее не занимался этой задачей. Готовых решений не искал. Решил способом, первым пришедшим в голову.
6. Трактор Трактор (Трактор) 03.10.14 14:04
Запустил сегодня этот же скрипт и маршрут построился по-другому :-) Прикольно. Похоже Яндекс переоценил расстояния от Селезнёвской до метро Новослободская и до метро Достоевская.

http://infostart.ru/upload/iblock/049/%D0%92%20%D0%B1%D1%80%D0%B0%D1%83%D0%B7­%D0%B5%D1%80%D0%B5.png

Обновление 14:12
Понял в чём дело!!! Дело в том, что расстояние меряется не в километрах, а в минутах!!! Сейчас до Красноказарменной добраться на метро быстрее, чем на том же метро до Ленинградского проспекта 40.
7. Трактор Трактор (Трактор) 03.10.14 23:31
(2)
На некоторых адресах яндекс глючит. Не строит к ним маршрут.

Моя ошибка была. Исправил.
Ещё исправил отображение в клиенте 1С спасибо FallenMad за ответ в теме http://forum.infostart.ru/forum26/topic117885/
Кто скачал файл до 23:51 03.10.2014 скачайте ещё раз. Если нема денег - давайте адрес пришлю файлик,
8. Головаченко Дима (Smaylukk) 04.10.14 10:16
Я думаю, что стоит упомянуть в посте о том, что цикл вычисления расстояний между точками реализован тоже с помощью маршрутизации Яндекс. А на нее Яндекс поставил ограничения. По моему 25000 запросов в сутки, но точно не скажу - не могу найти.
Я занимаюсь автоматизацией службы доставки, поэтому этот вопрос изучал. В моем случае это более 200 маршрутов в день и в каждом в среднем 25 точек (325 запросов в цикле). Итого на один день надо 65 000 запросов. Так что соглашусь с harmer, алгоритм жадный.
По Google - позволяет построить маршрут не более чем по 25 точкам для платного API и 10 для бесплатного. API Google может само оптимизировать промежуточные точки.
9. Трактор Трактор (Трактор) 04.10.14 10:42
(8) Smaylukk, спасибо за сведения.
Так что соглашусь с harmer, алгоритм жадный.

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

API Google может само оптимизировать промежуточные точки.

О как! Это интересно. Я до этого не докопался.
10. Ivan Khorkov (vano-ekt) 07.10.14 12:09
25к / сутки это на один ip или 1 ключ апи? :)
+
11. Трактор Трактор (Трактор) 07.10.14 16:15
(10) vano-ekt, ключ api в этом интерфейсе не используется.
12. olga pt (pt_olga) 08.10.14 18:57
(8) Smaylukk, а за ~9 килобаксов в год Гугл строит и оптимизирует маршруты без ограничений по количеству точек :) вроде так было, когда мы считали
13. Дмитрий Котельников (kotlovD) 14.10.14 17:40
Скачал, спасибо. А как сделать чтобы маршрут сразу для автомобиля формировался?
14. Трактор Трактор (Трактор) 14.10.14 17:59
(13) kotlovD,
как сделать чтобы маршрут сразу для автомобиля формировался?

В параметре, передаваемом функции route заменить строку
routingMode: 'masstransit'
на
routingMode: 'auto'
15. Дмитрий Котельников (kotlovD) 14.10.14 18:26
(14) Трактор, отлично. Спасибо за оперативность
16. Дмитрий Котельников (kotlovD) 14.10.14 18:58
правда в этом случае маршрут сразу не строится, приходиться нажимать кнопку "Переключить на общественный транспорт" и обратно, тогда маршрут выстраивается
17. assa Петренко (assa) 14.10.14 19:50
Не качал. Хотел спросить на счет логики.
Для оптимизации яваскрипт рассчитывает расстояние от исходной точки до каждой точки доставки. Находит ближайшую. Делает её исходной.
С год назад написал такое же, но с гуглом. И тоже применил такой алгоритм. Был поражен результатом. Представьте ситуацию: исходная точка №1, далее следует перекресток, в лево точка А на расстоянии 1000м, в право тоже точка В, но на расстоянии 800 м. Такая логика делает точкой №2 точку В . Далее за точкой №2 следует точка С и, если от точки В до точки С расстояние меньше, чем от В до А, то точка А все больше удаляется и по итогу она становится последней в маршруте. Вы у себя проверяли такой вариант? У меня так завернуло, что пропала охота дальше что то выдумывать. После получения такого результата забросил. За обработку однозначно +
Прикрепленные файлы:
18. Трактор Трактор (Трактор) 14.10.14 22:34
(17) я уже опубликовав обработку почитал на эту тему. Да, маршрут не всегда оптимальный. Но в большинстве случаев попадает близко. Этой темой я занялся недавно. Может быть допилю логику под другой алгоритм.
Сейчас пилю раздачу заявок курьерам. Вкупе с задачей построения маршрута получается некислая задача.

(16) kotlovD, завтра посмотрю в чём дело.
19. Трактор Трактор (Трактор) 17.10.14 13:46
(16) лучше поздно, чем никогда. В прикреплении файл, который по умолчанию строит маршрут на автомобиле. Файл "ymap.html"

Некто Гоша Забыл http://forum.infostart.ru/profile/324667/ просил вывести только метки, без построения маршрута.
Заглушил построение маршрута. Тем более, что метки я всё-равно ставил отдельно. Но при этом скрипт выполняет оптимизацию. То есть много лишних действий. Файл "ymap только метки.html"
Прикрепленные файлы:
ymap.html
ymap только метки.html
20. Kostya Zhurov (It-developer) 29.10.14 15:38
Почему в ИТ статье ссылка на левый сайт? МИНУС автору!!!
Agapov_Stas; +1 1 Ответить
22. Сергей Козулин (Veselchak) 10.02.15 11:04
Не отображается карта, только пустое html-поле. В чем может быть дело?
23. Трактор Трактор (Трактор) 11.02.15 01:15
24. Сергей Козулин (Veselchak) 12.02.15 10:56
В веб клиенте, тонком и толстом карта не отображается, а если открыть файл html браузером, то отображается.
А в картах 1.3 наоборот - в 1С работает, но не отображается если открыть файл html браузером.
25. Дарья Зубра (daria.zubra@ace-target.ru) 15.03.15 14:18
Добрый день! скачала файл но не понимаю как им пользоваться! html открыла в гугле, а вот что делать с фалом epf? заранее благодарю.
26. Трактор Трактор (Трактор) 17.03.15 22:50
то делать с фалом epf

(25) daria.zubra@ace-target.ru, дык ради него всё и затеяно. Это внешнаа обработка для 1С. в 1С Файл/Открыть, выбираешь этот файл. Это демонстрация построения маршрута в связке с 1С.
27. ИТ ИТ (korvin76) 28.07.15 12:44
А можно оптимизированный маршрут вернуть в табл.поле (чтобы можно было в печатном виде получить оптимизированный список адресов)?
28. Трактор Трактор (Трактор) 28.07.15 14:21
можно оптимизированный маршрут вернуть в табл.поле

(27) korvin76, можно решить так:
При вычислении маршрута записать точки маршрута в поле html документа.
А потом средствами 1С найти это поле html документа и прочесть информацию из него.
29. Трактор Трактор (Трактор) 29.07.15 10:22
(27) Что-то в (28) я кривое написал. Можно пользовать яндекс api из 1С. Формируешь http запрос из 1С, отправляешь его яндексу. Всё тоже самое, что и в яваскрипте, только из 1С. По сути это работа с rest сервисом.
30. Дмитрий М (reflexcompani) 08.01.16 12:00
Доброго дня. Данная обработка только для Москвы? Какой бы адрес не указывал другого города, ни чего не строится.
31. Трактор Трактор (Трактор) 08.01.16 12:13
(30) Я к Москве не привязывался. Возможно что-то с Яндекс картами. Город в адресе указываете?
32. Дмитрий М (reflexcompani) 08.01.16 13:03
да, город указывал. по разному пробовал.
Скажите, а то, что в обработке в процедуре при открытии, есть такие строки:
ЦентрКарты = "[55.781416, 37.611711]";
ГраницыМосквы = "[[56.1,37.0],[55.3,38.3]]";
ОтправнаяТочка = "['Москва, Селезневская улица, 21']";
Не может мешать построению маршрута в других городах?
cloudysaturn; Трактор; +2 Ответить 1
33. Трактор Трактор (Трактор) 09.01.16 11:24
ГраницыМосквы = "[[56.1,37.0],[55.3,38.3]]";

(32) reflexcompani, точно. Совсем забыл. Надо поправить границы карты.
34. Юля Елисеева (Yulya8888) 21.01.16 14:53
Добрый день. Скачала обработку, запускала и через файл/открыть и через сервис/внешние обработки устанавливала, не запускается. УТ 10.3, предприятие 8.3 С чем может быть связано?
35. Трактор Трактор (Трактор) 21.01.16 15:39
>> С чем может быть связано?
(34) Yulya8888, с тем, что вы пытаетесь открыть её в обычном приложении, а надо в управляемом интерфейсе.
36. GoGi SmIr (orlovskiy-a) 02.03.16 10:43
С недавнего времени при любом действии с картой начали появляться ошибки
,

Помогите исправить.
http://s020.radikal.ru/i719/1603/ac/405df2a7ad23.jpg
http://s016.radikal.ru/i337/1603/af/c0894c028a6e.jpg
37. Трактор Трактор (Трактор) 03.03.16 17:45
(36) похоже 1С изменила js движок в платформе. Фирефокс отработал скрипты без ошибок. А тонкий клиент с руганью. Но маршрут таки построил. Сейчас со временем всё плохо. Боюсь что на разбирательства времени не хватит.
38. Андрей Гармаев (cloudysaturn) 08.06.16 10:52
ну ёмоё, если она криво работает вы напишите в начале описание. что потом возможно доработаю если будет время. я ради вашей работы этой закинул деньги и теперь все коту под хвост(
39. Трактор Трактор (Трактор) 08.06.16 13:57
(38) cloudysaturn, написал комментарий в публикации. Яндекс карты криво отображаются в 1С. Но маршрут строится и отображается. Мешает только сообщение об ошибке при масштабировании карты. Будет время - посмотрю.
В веб клиенте, в фирефоксе, карты отображаются верно и маршруты строятся.
40. Евгений Сидилев (maikl007) 04.07.16 12:22
надо поправить в обработке код
| <meta http-equiv=""Content-Type"" content=""text/html; charset=utf-8"" /><meta http-equiv=""X-UA-Compatible"" content=""IE=8""/>
на
| <meta http-equiv=""Content-Type"" content=""text/html; charset=utf-8"" /><meta http-equiv=""X-UA-Compatible"" content=""IE=9""/>

заменить IE=8 на IE=9
у меня заработало без ошибок
vtas; Трактор; +2 Ответить
41. Alex Nikulin (Al-77) 29.07.16 12:54
Всем привет. я так понимаю сегодня ошибка с яндексом у всех ?
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа