шукаю програму/сервіс для побудови оптимального маршруту

[vampirich]

Є кільканадцять сіл в одному районі, які потрібно об"їхати

і хотілося б скласти маршрут з найменьшим кілометражем

Всі ті картографічні сервіси що находив, або вимагають щоб послідовність відвідування вибиралась вручну, або не вміють працювати з одинаковими назвами насерених пунктів (тобто коли мені треба добавити точку "городище" луцького району, скоріше за все мене відправлять у київську область абощо)

Хтось працював з подібними задачами? порадить якийсь простий сервіс?

У мене не постійна а разова задача, тому зручність сервісу питання другорядне

[Saddy]

в свій час в інституті вручну розв'язували подібні задачі (т.з. званий маршрут листоноші) - погугли, знайдеш приклади розв'язання.

[vampirich]

Про таке знаю

Але таке ускладняє задачу

в моєму конкретному випадку є 27 точок маршруту

І щоб скористатися задачою листоноші треба знати відстані:

1 - 2

1 - 3

...

1 - 27

2 - 3

....

2 - 27

...

3 -4

...

ітого 27! раз порахувати відстаней між точками

а потім іще рахувати оптимальні маршрути

не радує така перспектива

[Саня]

або ще називать транспортна задача чи задача комівояжера. Бувають різні варіації.

[MaestroA]

Якщо це разова задача, то чим Вас не влаштовує задати послідовність вручну? Так як я їзджу досить багато, то постійно займаюсь маршрутизацією. Google Maps мені цілком вистачає.

[vampirich]

задати вручну - не проблема

Як взнати найкращу послідовність з мінімальним кілометражем?

якщо 3-5 точок, то методом "пересунув - прикинув" легко вибрати найкращий маршрут

а якщо 27?

[Deemon]

а банально-популярні - карти гугл, навітел - не зроблять такого?

[Artem158]

постав api easyway

[vampirich]

карти гугла хочуть щоб я їм сказав що я хочу спочатку в точку а потім в б потім в с і т д

а мені треба щоб я ввів послідовність точок, а мені сказало: для найкоротшого маршруту їдьте спочатку в с, потім а і аж тоді в б

[Dream]

Почнемо з того чи всі села треба об'їхати за один день? Якщо ні, то де ночувати - в одному з сіл чи вертатись на початок маршруту?

Якщо кілька днів, то задача значно спрощується.

[vampirich]

за день. фактично треба об"їхати більшість сіл одного району, що в принципі за день цілком реально

[MaestroA]

Ради цікавості, поділіться списком населених пунктів.

[Saddy]

до речі, найкоротший шлях не завжди буває найоптимальнішим, тим паче по дорогах через села. Деякі відрізки шляху можуть бути розмиті/розбиті і т.д.

[MaestroA]

Якщо й існує программа, яка сама задає послідовність точок для маршруту, то з великою вірогідністю вона прокладе маршрут через такі дрищі, що будете нераді такій "оптимальності" і останньою точкою стане СТО.

[Will]

до речі, найкоротший шлях не завжди буває найоптимальнішим, тим паче по дорогах через села. Деякі відрізки шляху можуть бути розмиті/розбиті і т.д.

згадати хоча б відрізок Стоянів - Кам’янка Бузька траси Луцьк-Львів...

[vampirich]

Бережанка

Брани

Бужани

Ватин

Вільхівка

Галичани

Горішненє

Губин

Жабче

Журавники

Звиняченськ

Квасів

Колодежне

Лемешів

Лобачів

Мерва

Мирків

Мирне

Михлин

Новосілки

Перемиль

Печихвости

Підбереззя

Пірванче

Піски

Пустомитів

Рачин

Скірче

Скобелка

Скригів

Смолява

Терешківці

Угринів

Холонів

Цегів

Шклінь

марянівка

сенкивечівка

MaestroA, згідний. Але з чогось почати ж треба.

Маршрут "наугад" може бути в рази довшим за оптимальний

[MaestroA]

MaestroA, згідний. Але з чогось почати ж треба. Маршрут "наугад" може бути в рази довшим за оптимальний

Я б почав з паперової карти Волині на столі та маркета в руках.

[Saddy]

найпростіше, можливо не самий коротший варіант - позначити усі точки на детальній карті і намалювати такий собі круг, який буде проходити через них усі і почати з точки, яка найближче від старту.

[vampirich]

так то воно так, але хотілося б "автоматизовано"

+ такий сервіс не одному мені мабуть згодився б

[b0rg]

погугли "задача коммивояжера" типу цього

[Vadimm]

Людина шукає готове рішення а ви його "грузите" паперовими картами і матрицями з алгоритмом Літтла

З власного досвіду скажу що часто буває так, що там де Гугл Мапс показує дорогу, насправді її нема, або вона з'являється лише коли добряче просохне після весни. Тому зауваження

Якщо й існує программа, яка сама задає послідовність точок для маршруту, то з великою вірогідністю вона прокладе маршрут через такі дрищі, що будете нераді такій "оптимальності" і останньою точкою стане СТО.

вважаю слушним і здатним перекреслити любі результати які покаже програма.

[Єретик]

Бережанка

Брани

Бужани

Ватин

Вільхівка

Галичани

Горішненє

Губин

Жабче

Журавники

Звиняченськ

Квасів

Колодежне

Лемешів

Лобачів

Мерва

Мирків

Мирне

Михлин

Новосілки

Перемиль

Печихвости

Підбереззя

Пірванче

Піски

Пустомитів

Рачин

Скірче

Скобелка

Скригів

Смолява

Терешківці

Угринів

Холонів

Цегів

Шклінь

марянівка

сенкивечівка

MaestroA, згідний. Але з чогось почати ж треба.

Маршрут "наугад" може бути в рази довшим за оптимальний

Якщо це всі населені пункти, то задачу можна вирішити тривіально. Просто, надійно, але довго! Для цього можна зробити таблицю відстаней між усіма населенними пунктами, а далі в циклі знайти найменші значення і вивести маршрут. А намалювати це все можна в картах від гугля.

[vampirich]

Для цього можна зробити таблицю відстаней між усіма населенними пунктами

це треба 378 варіантів перебрати

до холєри

Чесно кажучи дивує що немає якогось готового рішення для цього на картографічних сервісах

[guest]

це треба 378 варіантів перебрати

1.0888869e+28

[LSD]

Ось варіант з програмкою при умові що у Вас вийде гамільтоновий граф ...

http://www.kursovik....ing/320357.html

Тут задача комівояжера повним перебором:

http://www.kursovik.com/programming/106018.html