Optimizare traseu OpenStreetMap
Last Updated: Aug 01 2017 13:11, Started by
ThePuiu
, Jul 31 2017 11:22
·
0
#1
Posted 31 July 2017 - 11:22
Salut, vreau sa optimizez un traseu (distanta cea mai scurta) format dintr-un punct de plecare, unu de sosire si citeva puncte intermediare. Trebuie sa tin cont de sensul unic al strazilor - mod autovehicol. Punctele intermediare se ofera intr-o lista nesortata (pozitia lor in lista nu trebuie sa influenteze algoritmul - adica nu vreau ca ordinea de parcurgere sa fie ordinea lor din lista!). Se poate face asta cu ceea ce ofera implicit vreun api de la OpenStreetMap? Am incercat o abordare de genul: iau punctul de pornire si caut pe baza unei functii din api care este cel mai apropiat punct din lista, apoi il consider pe acesta punct de plecare si il caut pe urmatorul cel mai apropiat in care nu am mai fost, samd. dar rezultatul iese ciudat de cele mai multe ori... O alta abordare la care ma gindeam ar fi bazata pe o matrice cu NxN linii si coloane care sa aiba pe prima linie si prima coloana toate punctele, iar la intersectia lor distanta intre puncte (sau 0 daca strada nu e cu sens dublu), apoi tot printr-un backtracking sa obtin distanta cea mai scurta...dar metoda asta imi pare tzaraneasca... Aveti vreo sugestie care m-ar putea ajuta? Daca pt OSM nu, atunci pt GoogleMaps?
Multumesc! |
#2
Posted 31 July 2017 - 11:56
tu vrei sa reinventezi teoria grafurilor orientate?
ca raspuns: http://wiki.openstre...rg/wiki/Routing |
#3
Posted 31 July 2017 - 23:14
Am incercat L.Routing.control si problema e ca nu stie (sau nu am gasit eu) sa faca determinarea drumului cel mai scurt ci genereaza un traseu (e adevarat ca tine cont de sensul drumurilor) in ordinea in care I-am dat punctele intermediare. In cazul meu am mai multe puncte intermediare care trebuie parcurse dupa traseul cel mai scurt. Daca stii cum se face (daca se poate) spune-mi te rog sa nu mai pierd vremea cautand...
Edited by ThePuiu, 31 July 2017 - 23:16. |
#4
Posted 01 August 2017 - 08:34
Asta e ideea punctelor intermediare, se le parcurga in ordinea pe care i-ai dat-o. Trebuie sa faci ceva extra acolo. Cred ca daca nu ai foarte multe puncte se poate face cate un traseu pentru fiecare doua puncte si apoi alese cele mai scurte trasee care sa duca si la cel mai scurt total.
BTW...poti sa cauti si problema comis voiajorului si sa vezi detalii pe acolo. Edited by StefanCBV, 01 August 2017 - 09:02. |
#5
Posted 01 August 2017 - 12:19
ThePuiu, on 31 iulie 2017 - 11:22, said:
Salut, vreau sa optimizez un traseu (distanta cea mai scurta) format dintr-un punct de plecare, unu de sosire si citeva puncte intermediare. Trebuie sa tin cont de sensul unic al strazilor - mod autovehicol. Punctele intermediare se ofera intr-o lista nesortata (pozitia lor in lista nu trebuie sa influenteze algoritmul - adica nu vreau ca ordinea de parcurgere sa fie ordinea lor din lista!). Se poate face asta cu ceea ce ofera implicit vreun api de la OpenStreetMap? Am incercat o abordare de genul: iau punctul de pornire si caut pe baza unei functii din api care este cel mai apropiat punct din lista, apoi il consider pe acesta punct de plecare si il caut pe urmatorul cel mai apropiat in care nu am mai fost, samd. dar rezultatul iese ciudat de cele mai multe ori... O alta abordare la care ma gindeam ar fi bazata pe o matrice cu NxN linii si coloane care sa aiba pe prima linie si prima coloana toate punctele, iar la intersectia lor distanta intre puncte (sau 0 daca strada nu e cu sens dublu), apoi tot printr-un backtracking sa obtin distanta cea mai scurta...dar metoda asta imi pare tzaraneasca... Aveti vreo sugestie care m-ar putea ajuta? Daca pt OSM nu, atunci pt GoogleMaps? Multumesc! |
#6
Posted 01 August 2017 - 13:11
lightpoint, on 01 august 2017 - 12:19, said:
De ce nu folosesti API-urile de la Google Maps ? |
Anunturi
Bun venit pe Forumul Softpedia!
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users