Trasa na mapě

3. 11. 2011 10:42:35

Chtěl bych se zeptat zda nějaké mapové API umožňuje plánování trasy.

Jde mně o to, že dostanu seznam 50 adres na které mam rozvézt květiny a potřebuji pro řidiče vytisknout z těchto adres mapu nejoptimálnější trasy, tak aby ta místa navštívil co nejrozumněji po sobě a ne aby se neefektivně vracel z jedné strany města na druhou a zpět.

3. 11. 2011 10:42:35

https://webtrh.cz/diskuse/trasa-na-mape#reply694161

Martin Schlemmer

(36 hodnocení)

3. 11. 2011 10:52:17

A, travelling salesman problém. To by mě taky zajímalo.

Wikipedie píše zajímavou věc

It is observed that humans are able to produce good quality solutions quickly.

Možná bude nejlevnější si API udělat z nějakého levného zaměstnance. Jeden API call bude stát 100 Kč za půl hodiny jeho práce. :)

3. 11. 2011 10:52:17

https://webtrh.cz/diskuse/trasa-na-mape#reply694160

Michal Brůžek

(58 hodnocení)

3. 11. 2011 11:02:23

rekl bych, ze i navigace v mobilu tohle umi celkem spolehlive... az na nejake bugy, ze se ocitnu pred vratama na silnici :)

3. 11. 2011 11:02:23

https://webtrh.cz/diskuse/trasa-na-mape#reply694159

zlutejbanan

3. 11. 2011 18:06:36

Asi by šlo využít měření vzdálenosti cesty mezi jednotlivýma trasama a pak to nějak propočítat kudy to bude nejrozumnější.

Potřebuji totiž pak z toho mít i online výstup kdy zákazník bude vědět přesně v kolik mu zboží doručí s nějakou časovou rezervou +/- 10 min, s tím že na mapě online uvidí pohyb autíčka jak se k němu blíží a proto potřebuji předem znát trasy, nasypat je po připojení do navigace řidiči atd.

3. 11. 2011 18:06:36

https://webtrh.cz/diskuse/trasa-na-mape#reply694158

martinzsa

(1 hodnocení)

4. 11. 2011 01:16:42

a co tak napisat skript ktory by postupoval nasledovne:

1 nacita zoznam vsetkych adries

2 k adresam vytvori maticu vzdialenosti medzi kazdym bodom(vzdialenosti by si dostal napr takto)

3 zvolil by sa startovaci bod

4 v matici by sa vyhladal najblizsi bod k startovaciemu a oznacil sa za uz navstiveny

5 opakovat bod 4 ibaze hladat z posledneho navstiveneho bodu a takto dokola az kym nenavstivis vsetky body

4. 11. 2011 01:16:42

https://webtrh.cz/diskuse/trasa-na-mape#reply694157

Martin Schlemmer

(36 hodnocení)

4. 11. 2011 09:09:53

Tomu problému se říká Travelling Salesman problem a je to velmi starý matematický a informatický problém, dosud nevyřešený optimálně (a možná nevyřešitelný).

Podívejte se na shrnutí na Wikipedii, na které jsem odkázal.

http://en.wikipedia.org/wiki/Travelling_salesman_problem

Srozumitelně tam jsou vysvětlené různé algoritmy.

Algoritmus navržený Martinem Zsa se jmenuje Nearest Neighbour nebo Greedy. Je rychlý a jeho trasa je průměrně cca o 25%, nikdy však o víc než 100% delší než nejkratší trasa.

Brute-force řešení, permutace všech tras, roste s faktoriálem počtu měst a nehodí se pro víc než jednotky měst (20 měst vyžaduje porovnat 2 triliony permutací)

Lidé to dokáží vyřešit rychle a poměrně efektivně.

Obvykle o tom bývá kapitola v každé knize o algoritmech, jako ukázka NP-complete problému, plus nějaká možná řešení.

4. 11. 2011 09:09:53

https://webtrh.cz/diskuse/trasa-na-mape#reply694156

Jiří Adámek

(20 hodnocení)

4. 11. 2011 09:39:13

Napsal zlutejbanan;719659
Asi by šlo využít měření vzdálenosti cesty mezi jednotlivýma trasama a pak to nějak propočítat kudy to bude nejrozumnější.
Potřebuji totiž pak z toho mít i online výstup kdy zákazník bude vědět přesně v kolik mu zboží doručí s nějakou časovou rezervou +/- 10 min, s tím že na mapě online uvidí pohyb autíčka jak se k němu blíží a proto potřebuji předem znát trasy, nasypat je po připojení do navigace řidiči atd.

Ja bych rekl, ze na to jdes prilis slozite. Proste ridicovi kopni navigaci, a podle te at jezdi. Pokud bude trasy jezdit casteji, sam si je zoptimalizuje, ze bude jezdit efektivne a to mnohem lepe, nez podle nejakyho algoritmu :))

Sledovani pro zakazniky je zcela jiny problem. Pokud to chces opravdu presne, hod ridicovi do auta monitoring s GPS, ktery se vyuziva u knihy jizd a na zaklade udaju, ktere ti bude zarizeni z auta posilat muzes zakaznikum ukazat na mape, kde se momentalne ridic nachazi. Cena je cca 150Kc/mesic a cena zarizeni cca 5tis.

4. 11. 2011 09:39:13

https://webtrh.cz/diskuse/trasa-na-mape#reply694155

takatom

(2 hodnocení)

4. 11. 2011 09:59:41

Když moc, tak bych zobrazil jen ta místa na mapě a nechal na řidiči, aby to zmáknul. Podmínky budou složitější kvůli termínům, algoritmizace se při tomto počtu uzlů nemůže "vyplatit". Určitě tam musí být i jiné metriky, třeba důležitost doručit kytice na svatbu za 5000 nebo na zapomenuté narozeniny tchýně, která živí širokou rodinu, atd. Sotva vyrazí na cestu, objeví se objednávka, kvůli které se musí za hodinu vrátit.

4. 11. 2011 09:59:41

https://webtrh.cz/diskuse/trasa-na-mape#reply694154

Martin Schlemmer

(36 hodnocení)

4. 11. 2011 10:02:11

Takatome, vynikající připomínka. Přes algoritmy jsme zapomněli, že některé dodávky jsou důležitější než jiné, přestože jejich upřednostněním vznikne neoptimální trasa!

VIP zákazníci, naštvaní zákazníci atd.

Kolikrát se navíc stane, že si lidé s řidičem domlouvají jiné časy, že řidič musí někde čekat, že se dostane do zácpy atd.

4. 11. 2011 10:02:11

https://webtrh.cz/diskuse/trasa-na-mape#reply694153

zlutejbanan

4. 11. 2011 12:02:37

Sledování auta online máme již naprogramováno včetně zobrazení trasy kudy jede na google mapách.

Teoreticky by asi mohlo stačit kdyby řidič do soupisu adres označil pořadí v jakém je navštíví a v případě změny by operativně z auta změnil číslo pořadí kam zrovna jede, díky jeho aktuální poloze bych tak věděl kde se nachází a vím kam jede, pak už není problém spočítat za jak dlouho tam asi dorazí. Jakmile tam dojede a zásilku předá, tak vím okamžitě že ji předal a vím kam by měl mít namířeno dále.

4. 11. 2011 12:02:37

https://webtrh.cz/diskuse/trasa-na-mape#reply694152

Pro odpověď se přihlašte.

Přihlásit