Karolina N.

Karolina N. Koordynator ds.
standaryzacji
procesów na
Terminalach Pal...

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Witam wszystkich, mam pytanie:
Z racji, że zaciekawił mnie temat "problem komiwojażera" postanowiłam stworzyć algorytm, który będzie optymalizował długość trasy dla kilku miejsc rozładunku. Niestety w związku z tym, że nie znam na odpowiednim poziomie accessa algorytm tworzę w excelu. Przyznam szczerze, że jest to dośc skomplikowane, ponieważ jest ogromna ilośc warunków i obawiam się, że excel sobie z tym nie poradzić. Czy ktoś może wie coś więcej na ten temat, mógłby mi jakoś pomóc, nakierować?
Do algorytmu jest sporządzona macierz zaciągająca dane. Na ten moment algorytm znajduje najkrótszą trasę jednak nie uwaględnia takich warunków jak: miejsce i daty rozładunków oraz zakazy poruszania się. Ma ktoś może pomysł jak to rozwiązać?
Tadek Jacek W.

Tadek Jacek W. Kierownik Projektu

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Zobacz zabawki spedytora
Tadek

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Karolina Neska:
Ma ktoś może pomysł jak to rozwiązać?


To niekoniecznie problem logistyczny, raczej programistyczny. Firmy logistyczne używają z reguły bardziej złożonych narzędzi, żadnych opartych na Excelu, tak więc skierowałbym pytanie raczej do grupy poświęconą Excelowi np. takiej:

http://www.excelforum.com/excel-programming-vba-macros...
Dorota K.

Dorota K. TSL + IT -
konsultant

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Albo może takiej: Fani Excela.
Karolina N.

Karolina N. Koordynator ds.
standaryzacji
procesów na
Terminalach Pal...

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Dziękuję za pomoc.

konto usunięte

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Tego zadania nie trzeba komplikować Excelem, wystarczy dobra mapa, np.http://maps.google.pl/maps?hl=pl&tab=wl

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Marek O.:
Tego zadania nie trzeba komplikować Excelem, wystarczy dobra mapa, np.http://maps.google.pl/maps?hl=pl&tab=wl

No niezupelnie, chociaz mapa z reguly pojedyncza droge optymalnie wyznaczy. W problemie komiwojazera nie wszystkie miejsca sa "po drodze".

konto usunięte

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Problem komiwojażera to problem algorytmiczny, na dodatek dość trudny, bowiem optymalny algorytm działa w czasie wykładniczym, czyli w praktyce jest zbyt mało wydajny, żeby go zastosować.

Tyle teorii. Istnieje jednak wiele algorytmów przybliżonych, całkiem nieźle radzących sobie z tym problemem. Warto popróbować np. tutaj:

http://gebweb.net/optimap/

(oczywiście punkty można podawać w dowolnej kolejności - nie muszą być "po drodze")

Ten projekt używa solvera stąd:

http://code.google.com/p/google-maps-tsp-solver/Adam Michalski edytował(a) ten post dnia 11.10.12 o godzinie 13:31
Karolina N.

Karolina N. Koordynator ds.
standaryzacji
procesów na
Terminalach Pal...

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Dziękuję, sprawdzę i dam znać :)
Marek Biesiekierski

Marek Biesiekierski poszukuje nowych
wyzwań

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

http://gebweb.net/optimap/ jest bardzo prostym algorytmem. Nie uwzględnia np. czasu pracy kierowcy, godzin pracy odbiorców i dostawców, czasów rozładunku, ilości bram i przepustowości magazynów odbiorców. A to dopiero wierzchołek góry lodowej zmiennych, które należy uwzględnić przy budowie algorytmu.

konto usunięte

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Marek Biesiekierski:
http://gebweb.net/optimap/ jest bardzo prostym algorytmem. Nie uwzględnia np. czasu pracy kierowcy, godzin pracy odbiorców [...]

Oczywiście, jest to tylko punkt wyjścia. Ten program ilustruje matematyczny problem komiwojażera w najprostszej postaci. W żadnym wypadku nie uważam, że jest to rozwiązanie, które można z miejsca użyć do rozwiązania wszystkich problemów optymalnego rozładunku. Gdyby tak było, firmy nie kupowałyby dedykowanego oprogramowania. Jak już wcześniej wspomniano, to są duże systemy i nie wystarczy programik w JavaScripcie czy nawet w Excelu...Adam Michalski edytował(a) ten post dnia 15.10.12 o godzinie 14:55

konto usunięte

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

editTen post został edytowany przez Autora dnia 19.09.16 o godzinie 09:31

konto usunięte

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Konrad B.:
Da się to zrobić zapewne w poważniejszym narzędziu programistycznym, ale to wymaga co najmniej średnio zaawansowanej wiedzy z zakresu programowania (której jeszcze nie przyswoiłaś sądząc po Twoim profilu)

Nie da się :) Nawet zakładając dużą wiedzę z logistyki i dużą wiedzę z programowania. Ściślej: nie da się zrobić czegoś lepszego niż narzędzia, które są rozwijane przez lata przez całe zespoły programistów i logistyków (i które tanie nie są).

To tak samo jak by ktoś powiedział: zróbmy własnego Excela, tyle że "lepszego". Nie da się, ponieważ nad tym programem pracuje od lat sztab dobrze wykwalifikowanych ludzi. Kluczową kwestią jest tutaj dojrzałość projektu...Adam Michalski edytował(a) ten post dnia 18.10.12 o godzinie 01:03

Temat: Algorytm problemu komiwojażera dla kilku miejsc rozładunku

Konrad B.:
Jeśli to drugie, to chyba szkoda Twojego czasu - tego nie da się zrobić w excelu ( w sposób jaki myślisz że się da zrobić - na funkcjach i formułach)

Myślę, że nie chodzi o to w czym bo dla paru miast to może i w Excelu wyjdzie, nie jest to tez problem samego (pojedynczego albo sekwencyjnego) algorytmu lecz raczej liczby punktów czy miast bo ze wzrostem tej liczby sprawa się bardzo komplikuje (algorytmy równoległe, obliczenia równolegle). Sprawdzenie przy większej liczbie wymaga niesamowitych mocy obliczeniowych i zadanie staje się szybko nierozwiązalne.

Nie tylko Amerykanie czy Japończycy lecz także Polacy mają tutaj spore osiągnięcia.. :)

http://www.springerlink.com/content/w4058030m2876724/
http://sun.aei.polsl.pl/~zjc/
http://www.goldenline.pl/miroslaw-blocho (to chyba ten drugi autor)

Następna dyskusja:

Serdeczne powitanie dla Moniki




Wyślij zaproszenie do