Asp Forum - Algorytmy do problemów transportowych

lotoWYTNIJTO

8/11/2007 8:47:00 AM

Witam. Szukam algorytmów do rozwi?zywania problemów transportowych - mam np.
kilka cie?arówek i kilka miejsc zbiórek/dostaw - optymalizacja, itp..... czego
szukaa w ogóle bo ja nie mam pojeci :/ Chyba genetyczne nie warto od razu rzucaa :P

Dzieki

--
Wys3ano z serwisu OnetNiusy: http://niu...

8 Answers

loto

8/11/2007 1:49:00 PM

> Witam. Szukam algorytmów do rozwi?zywania problemów transportowych - mam np.
> kilka cie?arówek i kilka miejsc zbiórek/dostaw - optymalizacja, itp..... czego
> szukaa w ogóle bo ja nie mam pojeci :/ Chyba genetyczne nie warto od razu
rzucaa :P
>
> Dzieki
>
> --
> Wys3ano z serwisu OnetNiusy: http://niu...
Mo?e napisze dok3adniej:
szukam algorytmu do rozwi?zania nastepuj?cego problemu :)

Mam klika miejscowo?ci, A, B, C, D, E, F, G, H, I
mam odleg3o?ci z ka?dej do ka?dej innej A-B, B-C, A-C itp...
Mam trzech komiwoja?erów :)

Teraz ka?de miasto musi bya odwiedzone przez jednego (przynajmniej i tylko przez
jednego).

To jest pierwsza cze?a zadania :P Niby proste, niby prosty problem komiwoja?era,
ale kilku komiwoja?erów i ju? wszystkie znane mi algorytmy id? w krzaki :/

Pó?niej dodane bedzie, ?e ka?dy z komiwoja?erów startuje z miejscowo?ci J, K, L
i wszyscy musz? skonczya w miejscowo?ci Z :D Ale to zostawiam na potem :P

Dzieki za pomoc :)

--
Wys3ano z serwisu OnetNiusy: http://niu...

Wit Jakuczun

8/11/2007 4:13:00 PM

Dnia 11 Aug 2007 15:49:03 +0200
loto@poczta.onet.pl napisal(a):

> Moze napisze dokladniej:
> szukam algorytmu do rozwiazania nastepujacego problemu :)
>
http://osiris.tuwien.ac.at/~wgarn/VehicleRouting/vehicle_ro...
http://www.branchandcu...

Poczytaj tez o Clarke-Wright heuristics, chociaz ta heurystyka
nie zawsze daje rozwiazanie dopuszczalne jak masz ograniczona
liczbe pojazdów.
Jak szukasz rozwiazania optymalnego to proponuje sformulowac
zadanie jako zadanie programowania calkowitoliczbowego i
spróbowac rozwiazac przy pomocy np. glpk albo lp_solve (mój
faworyt z rozwiazan OS). Ewentualnie mozesz tez spróbowac
sciagnac wersje testowa OPL Studio firmy ILOG albo odpowiednik
firmy Dash Optimization.

> Mam klika miejscowosci, A, B, C, D, E, F, G, H, I
> mam odleglosci z kazdej do kazdej innej A-B, B-C, A-C itp...
> Mam trzech komiwojazerów :)
>
> Teraz kazde miasto musi byc odwiedzone przez jednego (przynajmniej i tylko przez
> jednego).
>
Rozumiem, ze minimalizujesz dlugosc trasy. Mi brakuje jeszcze informacji
o wielkosci zadania oraz o tym ile masz czasu na znalezienie rozwiazania.

> To jest pierwsza czesc zadania :P Niby proste, niby prosty problem komiwojazera,
> ale kilku komiwojazerów i juz wszystkie znane mi algorytmy ida w krzaki :/
>
Poczytaj o problemie marszrutowania (vehicle routing problem) albo o
M-TSP problem.

>
> Pózniej dodane bedzie, ze kazdy z komiwojazerów startuje z miejscowosci J, K, L
> i wszyscy musza skonczyc w miejscowosci Z :D Ale to zostawiam na potem :P
>
To nie jest wielka komplikacja.

Pozdrawiam
--
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsol... ]

pdemb

8/11/2007 5:53:00 PM

loto@poczta.onet.pl writes:

[...]

> Niby proste, niby prosty problem komiwoja?era,

Niech mnie kto? poprawi je?li sie myle, ale zwyk3y problem
komiwoja?era jest trudny obliczeniowo nawet je?li rozwa?a sie
obliczenia na (teoretycznym) komputerze kwantowym.

--
http://www.piotr.dembin...

Wit Jakuczun

8/11/2007 6:05:00 PM

Dnia Sat, 11 Aug 2007 19:53:17 +0200
pdemb@gazeta.pl (Piotr Dembinski) napisal(a):

> loto@poczta.onet.pl writes:
>
> [...]
>
> > Niby proste, niby prosty problem komiwojazera,
>
> Niech mnie ktos poprawi jesli sie myle, ale zwykly problem
> komiwojazera jest trudny obliczeniowo nawet jesli rozwaza sie
> obliczenia na (teoretycznym) komputerze kwantowym.
>
Masz racje, problem jest NP-trudny. Istnieja jednak dosc
efektywne metody, które pozwalaja rozwiazywac problemy o
dosc duzej liczbie miast. Mówie tutaj o znajdowaniu rozwiazan
optymalnych bo istnieje tez sporo heurystyk, które
pozwalaja szybko znalezc rozwiazania dopuszczalne.
Problem komiwojazera jest uwazany za "prosty" glównie
dlatego, ze bardzo duzo czasu zostalo mu poswiecone. Nie pomyle
sie wiele jak powiem, ze jest to najbardziej "rozgryziony"
problem NP-trudny.

Pozdrawiam
--
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsol... ]

pdemb

8/11/2007 9:50:00 PM

Wit Jakuczun <wit@mefisto.hades> writes:

> Dnia Sat, 11 Aug 2007 19:53:17 +0200
> pdemb@gazeta.pl (Piotr Dembinski) napisa3(a):
>
>> loto@poczta.onet.pl writes:
>>
>> [...]
>>
>> > Niby proste, niby prosty problem komiwoja?era,
>>
>> Niech mnie kto? poprawi je?li sie myle, ale zwyk3y problem
>> komiwoja?era jest trudny obliczeniowo nawet je?li rozwa?a sie
>> obliczenia na (teoretycznym) komputerze kwantowym.
>>
> Masz racje, problem jest NP-trudny. Istniej? jednak do?a efektywne
> metody, które pozwalaj? rozwi?zywaa problemy o do?a du?ej liczbie
> miast.

Moim zdaniem nadal nie usprawiedliwia to zacytowanego powy?ej
stwierdzenia sugeruj?cego, ?e problem komiwoja?era jest 3atwym
problemem obliczeniowym. OIDP to problemem prostym mo?na --
od niedawna, przyjmuj?c za3o?enie o dostepno?ci komputera
kwantowego -- nazywaa problem faktoryzacji.

> Mówie tutaj o znajdowaniu rozwi?zan optymalnych bo istnieje te?
> sporo heurystyk, które pozwalaj? szybko znale?a rozwi?zania
> dopuszczalne. Problem komiwoja?era jest uwa?any za "prosty" g3ównie
> dlatego, ?e bardzo du?o czasu zosta3o mu po?wiecone. Nie pomyle sie
> wiele jak powiem, ?e jest to najbardziej "rozgryziony" problem
> NP-trudny.

Mo?e dobrze znany, mo?e gruntownie zbadany, ale na pewno nie prosty,
3atwy ani trywialny.

--
http://www.piotr.dembin...

Damian Sobota

8/12/2007 7:52:00 AM

pdemb@gazeta.pl (=?ISO-8859-2?q?Piotr_Dembi=F1ski?=) napisa3(a):
> >> loto@poczta.onet.pl writes:
> >> > Niby proste, niby prosty problem komiwoja?era,
>
> Moim zdaniem nadal nie usprawiedliwia to zacytowanego powy?ej
> stwierdzenia sugeruj?cego, ?e problem komiwoja?era jest 3atwym
> problemem obliczeniowym.

Ale przecie? on nigdzie nie napisa3, ?e to prosty obliczeniowo problem. Ja
jego wypowied? zrozumia3em jako: "ok, jest to zwyk3a modyfikacja TSP, ale nie
wiem, co robia -- znane mi heurystyczne algorytmy w tym przypadku nie daj? rady".

Pozdrawiam,
DS.

--
Wys3ano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta....

Wit Jakuczun

8/12/2007 2:54:00 PM

Dnia Sat, 11 Aug 2007 23:50:04 +0200
pdemb@gazeta.pl (Piotr Dembinski) napisal(a):

> > Masz racje, problem jest NP-trudny. Istnieja jednak dosc efektywne
> > metody, które pozwalaja rozwiazywac problemy o dosc duzej liczbie
> > miast.
>
> Moim zdaniem nadal nie usprawiedliwia to zacytowanego powyzej
> stwierdzenia sugerujacego, ze problem komiwojazera jest latwym
> problemem obliczeniowym.
Eee tam, czepiasz sie slówek. Moim zdaniem OP powinien napisac
"prosty problem komiwojazera" zamiast "zwykly problem komiwojazera"
i wtedy nie mialbys sie czego czepic.

Zdrowia
--
[ Wit Jakuczun <W.Jakuczun [at] wlogsolutions.com> ]
[ WLOG Solutions http://www.wlogsol... ]

pdemb

8/12/2007 5:57:00 PM

"Damian Sobota" <damsob@gazeta.SKASUJ-TO.pl> writes:

> pdemb@gazeta.pl (=?ISO-8859-2?q?Piotr_Dembi=F1ski?=) napisa3(a):
>> >> loto@poczta.onet.pl writes:
>> >> > Niby proste, niby prosty problem komiwoja?era,
>>
>> Moim zdaniem nadal nie usprawiedliwia to zacytowanego powy?ej
>> stwierdzenia sugeruj?cego, ?e problem komiwoja?era jest 3atwym
>> problemem obliczeniowym.
>
> Ale przecie? on nigdzie nie napisa3, ?e to prosty obliczeniowo
> problem.

Tak, tylko ?e problem komiwoja?era jest problemem obliczeniowym,
wiec okre?lanie go mianem 'prosty' implikuje interpretacje, któr?
poda3em powy?ej.

> Ja jego wypowied? zrozumia3em jako: "ok, jest to zwyk3a modyfikacja
> TSP, ale nie wiem, co robia -- znane mi heurystyczne algorytmy w tym
> przypadku nie daj? rady".

Skrót my?lowy. Nawiasem mówi?c, to -- skoro rozwi?zanie jest ju?
znane -- to czy problem udowodnienia Twierdzenia Fermata równie?
uwa?asz za prosty?

--
http://www.piotr.dembin...

pl.comp.programming

Algorytmy do problemów transportowych

lotoWYTNIJTO

loto

Wit Jakuczun

pdemb

Wit Jakuczun

pdemb

Damian Sobota

Wit Jakuczun

pdemb

x Login to ForumsZone