Есть справочник адресов, с координатами. По формуле КОРЕНЬ((X1-X2)^2+(Y1-Y2)^2) можно высчитать примерное расстояние между каждой парой точек. Проверить можно через UDF функцию с запросом к Api (Здесь) Я даже думал через тот же API и рассчитывать путь, доработав вышеуказанную функцию, но у гугла есть ограничение в 8 доп точек... (Здесь) А в маршруте их может быть более 30.... Как расчитать оптимальную последовательность проезда этих точек, так чтобы в конце маршрута вернутся в начальную точку? Прочитал про метод коммивояжера... может как то так? но как его воплотить в Вба пока не нашел. Что-то по маршрутам было здесь, но не совсем то. Есть у кого то соображения, как это сделать?
Есть справочник адресов, с координатами. По формуле КОРЕНЬ((X1-X2)^2+(Y1-Y2)^2) можно высчитать примерное расстояние между каждой парой точек. Проверить можно через UDF функцию с запросом к Api (Здесь) Я даже думал через тот же API и рассчитывать путь, доработав вышеуказанную функцию, но у гугла есть ограничение в 8 доп точек... (Здесь) А в маршруте их может быть более 30.... Как расчитать оптимальную последовательность проезда этих точек, так чтобы в конце маршрута вернутся в начальную точку? Прочитал про метод коммивояжера... может как то так? но как его воплотить в Вба пока не нашел. Что-то по маршрутам было здесь, но не совсем то. Есть у кого то соображения, как это сделать?SLAVICK
Иногда все проще чем кажется с первого взгляда.
Сообщение отредактировал SLAVICK - Воскресенье, 25.05.2014, 01:26
По описанию - классическая задача коммивояжера Задача не простая, рабочего эффективного алгоритма у меня нет, но решить ее можно перебором. Для 8 точек это сделать очень легко всего 7! вариантов перебрать, а вот для 30 - это уже нереально Сколько может быть адресов в реальности?
По описанию - классическая задача коммивояжера Задача не простая, рабочего эффективного алгоритма у меня нет, но решить ее можно перебором. Для 8 точек это сделать очень легко всего 7! вариантов перебрать, а вот для 30 - это уже нереально Сколько может быть адресов в реальности?MCH
MCH, в реальности может быть и больше... но они поделены на регионы. И это внутри одного региона. Оптимизация регионов - следующий шаг. просто не могу придумать алгоритм. У гугла в премиум пакете можно расчитать до 23 путевых точек+начало+конец. .. итого 25.( при этом создается правильный маршрут) Работает быстро.... Рассчитать в одну сторону легко, вопрос как создать именно оптимальный маршрут... т.е. чтобы получилось что то вроде круга. Думаю нужно расчитать возможные сочетание точек с созданием словаря или колекции ... но вот что дальше делать?
MCH, в реальности может быть и больше... но они поделены на регионы. И это внутри одного региона. Оптимизация регионов - следующий шаг. просто не могу придумать алгоритм. У гугла в премиум пакете можно расчитать до 23 путевых точек+начало+конец. .. итого 25.( при этом создается правильный маршрут) Работает быстро.... Рассчитать в одну сторону легко, вопрос как создать именно оптимальный маршрут... т.е. чтобы получилось что то вроде круга. Думаю нужно расчитать возможные сочетание точек с созданием словаря или колекции ... но вот что дальше делать?SLAVICK
не 7, а 7! (семь факториал = 5040 вариантов). Различные варианты определяются перестановкой семи точек.
Приложите небольшой пример (не более 8 - 10 точек), для понимания, какова организация данных. Можно попробовать решить перебором. За разумное время можно перебрать до 12 точек (11! ~ 40 млн комбинаций)
не 7, а 7! (семь факториал = 5040 вариантов). Различные варианты определяются перестановкой семи точек.
Приложите небольшой пример (не более 8 - 10 точек), для понимания, какова организация данных. Можно попробовать решить перебором. За разумное время можно перебрать до 12 точек (11! ~ 40 млн комбинаций)MCH
Вот пример, на первом листе - то что должно получится - с небольшим количеством данных - это можно рассчитать через гугл АПИ или здесь На втором листе вторая матрица расстояний, нужно получить расчет как на первом листе, но для всех точек. т.е. Выезжаем из 1-й точки, проезжаем все точки, в последовательности которую нужно рассчитать, и приезжаем обратно в 1-ю точку. Вроде бы понятно написал
Интересно по какому принципу работает Гугл? если их сервис позволяет рассчитать до 23 доп.точек?
Вот пример, на первом листе - то что должно получится - с небольшим количеством данных - это можно рассчитать через гугл АПИ или здесь На втором листе вторая матрица расстояний, нужно получить расчет как на первом листе, но для всех точек. т.е. Выезжаем из 1-й точки, проезжаем все точки, в последовательности которую нужно рассчитать, и приезжаем обратно в 1-ю точку. Вроде бы понятно написал
Интересно по какому принципу работает Гугл? если их сервис позволяет рассчитать до 23 доп.точек?SLAVICK
Нашел интересное решение там есть файл он строит графики, и высчитывает положение следующей точки по координатам, быстро считает... конечно не 100% попадание, но лучше чем ничего Может как то пойти по этому пути, а не по пути простого перебора комбинаций?... или как-то сочетать их
Нашел интересное решение там есть файл он строит графики, и высчитывает положение следующей точки по координатам, быстро считает... конечно не 100% попадание, но лучше чем ничего Может как то пойти по этому пути, а не по пути простого перебора комбинаций?... или как-то сочетать ихSLAVICK
Разобрался сам воспользовался встроенной надстройкой "Поиск решения" - делает расчет для 40 адресов меньше чем за две минуты Правда, хотелось бы макрос - легче запускать... Для того чтобы сработало - нужно включить надстройку "Поиск решения".
Разобрался сам воспользовался встроенной надстройкой "Поиск решения" - делает расчет для 40 адресов меньше чем за две минуты Правда, хотелось бы макрос - легче запускать... Для того чтобы сработало - нужно включить надстройку "Поиск решения".SLAVICK