Problem komiwojażera

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

[collien]

świetne! :)

[O.....k]

Matematyka, fuck yeah.

[m.....o]

Ciekawe podejście, jednak tylko w teorii. Co w przypadku gdy klient jest nieobecny i nie odbierze przesyłki?

[m.....o]

@norbert108: Wiadomo, ale przecież będzie musiał wrócić. Czyli optymalizacja trasy sprawdza się jedynie w teorii, tzn. wtedy gdy każdy z odbiorców jest dostępny i odbierze przesyłkę.

[P.....k]

@marwro: No ale tak czy siak ją musi dostarczyć więc nawet jeśli zrobi to nastepnego dnia i tak skorzysta z optymalizacji

[printf]

To nic niezwykłego sam kiedyś milem napisać na zaliczenie program rozwiązujący ten problem jest wiele algorytmów ja stosowałem genetyczny ale mrówkowy o którym wspominano też jest dość ciekawy :)

[minuano68]

Ciekawe, jak poradziłby sobie tabu search?

[P.....k]

@minuano68: UPS dla przykładu używa programu ORION. Tutaj można więcej o nim przeczytać http://www.forbes.com/sites/alexkonrad/2013/11/01/meet-orion-software-that-will-save-ups-millions-by-improving-drivers-routes/. Można też łatwo zauważyć korzyści wynikające ze stosowania takich algorytmów. Załóżmy, że optymalizacja jest w stanie zaoszczędzić kierowcy 30 minut mnożąc to przez liczbę kierowców i liczbę dni w roku przynosi to ogromną oszczędność czasu, a co za tym idzie, pieniędzy.

[minuano68]

@Pismak: Ciekawe, ile płacą za ten soft, skoro mogą aż tyle zaoszczędzić?

[frez]

Zasadniczo to wychodzi, że trzeba w kółko jechać po miastach :)

[cham_i_bezczel]

O co tu chodzi? Ktoś to wyjaśni? Dlaczego nie można po prostu ustalić normalnej trasy od miasta do najbliższego miasta, tylko trzeba jakichś programów używać? Nie wystarcza po prostu kartka i długopis i się łączy punkciki tak jak w pierwszym przykładzie na tej prezentacji?

[P.....k]

@cham_i_bezczel: no wystarcza, ale taka trasa jest dłuższa. Dzięki temu algorytmowi opracujesz krótszą i bardziej efektywną trasę. Zaoszczędzisz czas i pieniądze.

[UnnAmmEdd]

Lol, możliwych tras jest duuuużo więcej od liczby cząsteczek we wrzechświecie.

[eudialit]

@UnnAmmEdd: ...w czym?

[v.....x]

@UnnAmmEdd: nawet więcej niż szacowana liczba atomów we wSZechświecie

[tomek_jg]

Czyli wszystko dąży do kształtu koła... pewnie ma to związek z tym, że kształt koła ma najkorzystniejszy stosunek pole-objętość.

[SamiS]

@tomek_jg: Koło i objętość?

[tomek_jg]

@SamiS: Oczywiście, że pole po objętość to w kuli ;)