Problem komiwojażera

Czyli ciekawy problem matematyczny, z którym na co dzień borykają się np. największe firmy kurierskie.

[lisekchz]

Problem znany z dziedziny inżynierii systemów logitycznych.

[mar111cin]

@lisekchz: kończyłem, pamiętam jak rozwiązywałem problem komiwojażera ręcznie na kartce :)

[mar111cin]

@lisekchz: pa pa pa panie mo mo mo możli żli żli wie ;)

[luke2k4]

Nic nie wspomnieli o metodach znajdywania rozwiązań optymalnych problemu komiwojażera (opartych np. na programowaniu ograniczeniowym ).

Swego czasu napisałem bibliotekę do jednego z open-source-owych systemów do optymalizacji kombinatorycznej, która służy do znajdywania "Cyklu Hamiltona", o najniższym koszcie, w grafie (bo do tego sprowadza się problem komiwojażera). Załączam link do biblioteki i przykładu z Polskimi miastami :)

http://eclipseclp.org/doc/bips/lib_public/cycle/index.html

[A.....6]

Nie wiedziałam, że w USA rozwożą pocztę helikopterem. A nie taniej by było kupić sobie drugi?

[hoRacy]

Ktoś ma informacje jakich algorytmów wyznaczania tras (w kolejności) używa Google Maps?

[WhosYourDaddy]

@Ginden: Najbardziej oczywista odpowiedź: Dijkstra jest zbyt wolna. Jakby nie można było pre-processować w jakiś sposób tras, to A*. Jak można preprocessować to już bardziej wyszukane rzeczy.

[G.....n]

@hoRacy: Prawdopodobnie algorytmu Dijkstry, to najbardziej oczywista odpowiedź.

[poznaniak]

Miałem to na badaniach operacyjnych na UE w Poznaniu. Pozdrawiam wszystkich, którzy musieli przez to przejść ;)

[CzystaMaestria]

OOOO proszę. W końcu coś co mieli Wykopki na studiach i są w stanie coś napisać.

Bo o prawdziwym życiu, nie z książki, nic nie wiedzą !

[TheeMI]

Nikt nie zakopie ? ; ) Rekord chyba. Prawie tysiąc bez zakopania.

[krossmaker]

a pro po tematu: w ubiegłym tygodniu miałem taką sytuację, że zadzwonił do mnie kurier, że ma dla mnie przesyłkę, i czy mógłbym dojechać 2 km do większej miejscowości. Odpowiedziałem mu, że nie, na co on od razu zaproponował inny dzień. Gdy zapytałem go dlaczego, to stwierdził, że droga do mojej miejscowości jest oblodzona, i że nie może przyjechać.

Dodam tylko, że nie jest to żadna droga szutrowa, tylko normalna asfalt po

[sogen]

@krossmaker: moze, przeczytaj regulamin. Wszystkie firmy kurierskie się zabezpieczają przed złą pogodą w ten sposób.

[plushy]

Wszystko ładnie i pięknie dopóki nie okaże się że mamy nie tylko wiele miejsc do odwiedzenia ale też wielu kurierów. A jak się na dodatek okaże że mamy ograniczoną pojemność i różne ilości przesyłek do odebrania w poszczególnych miejscach to robi się zabawa na całego.

[medykydem]

To było naprawdę ciekawe.