Mefisto...diabeł czy anioł?
Zak³adam ten temat poniewa¿ chcê wprowadziæ pewien Algorytm do excela dotyczy on grupowania zleceñ transportowych w trasê. Wygl±da to w ten sposób, ¿e mam swoje centrum we wroc³awiu i obs³ugujê pewien rejon. Startuje od tego ¿e posiadam dane w postaci macierzy w której znajdujê siê czasy przejazdu pomiêdzy wroc³awiem a miastami gdzie wykonujê zlecenie jak równie¿ czasy po¶rednie pomiêdzy tymi wszystkimi miastami. Macierz 10x10. natomiast w kolumnie 11 ilo¶æ palet które muszê przewie¼æ do danego miasta. Problem polega na tym aby ³±czny czas jednej trasy nie przekracza³ np. 960 minut oraz maksymalna ³adowno¶c to np. 32 palety.
Nastepnym krokiem jest stworzenie tzw macierzy oszczêdno¶ci na podstawie tej wy¿ej wymienionej. Wygl±da to tak ¿e na przecieciu siê np. 3 elementy z 4 (warto¶æ te to inaczej miasta) dokonujemy nastêpuj±cego obliczenia:
odleg³o¶æ z 3 do wroc³awia + odleg³o¶æ z 4 do wroc³awia - odleg³o¶æ pomiêdzy 3 a 4.
I w ten sposób tworzymy ca³± macierz.
Kolejnym krokiem jest uporz±dkowanie warto¶ci w tej macierzy od najwiekszej do najmniejszej ( ale tylko dodatniej) wraz z numerem wiersza i kolumny w której wystapi³a. Czyli je¿eli to by³a macierz 10X10 to uzyskujemy 100 kolumnowy ci±g warto¶ci (lub mniejszy poniewa¿ interesuj± nas tylko warto¶ci dodatnie) oraz pod nim odpowiadaj±cy tej warto¶ci nr wiersza i nr kolumny.
I tutaj zaczyna siê sedno sprawy czyli kolejne iteracje algorytmu. ( to z czym nie mogê sobie poradziæ)
zaczynamy od trasy której przypisana zosta³a najwieksza warto¶æ oszczêdno¶ci ( czyli bierzemy pierwszy nr wiersza i nr kolumny w naszym ci±gu np 7 wiersz 8 kolumna i tworzymy trase [ 1 7 8 1 ] - 1 poniewa¿ wyjezdzamy z Wroc³awia nastepnie przez miasto o indeksie 7 potem 8 i ponownie musimy wrócic do wroc³awia. Dla tej trasy obliczamy ³±czny czas i ³adowno¶æ ( to okazalo siê dosyæ ³atwe u¿ywaj±c funkcji wyszukaj.pionowo , indeks )
Je¿eli trasa spe³nia nasze ograniczenia co do ³adowno¶ci i czasu to sprawdzamy czy mo¿emy do³±czyæ kolejne miasta wystêpuj±ce w kolejno¶ci utworzonego ci±gu warto¶ci lub tworzymy now± trasê. Zaznaczyæ trzeba równie¿ ¿e wychodzimy pocz±tkowo z za³o¿enia ¿e jest 9 tras ( tyle co zlecen poniewa¿ macierz 10x10 - Wroc³aw=9) i stosunkowo ³±cz±c trasy zmniejszamy jej liczbê to minimalnej tak aby przy tym spe³nione by³y warunki ograniczaj±ce.
[ Dodano: 2010-02-13, 18:54 ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl katkaras.opx.pl
Nastepnym krokiem jest stworzenie tzw macierzy oszczêdno¶ci na podstawie tej wy¿ej wymienionej. Wygl±da to tak ¿e na przecieciu siê np. 3 elementy z 4 (warto¶æ te to inaczej miasta) dokonujemy nastêpuj±cego obliczenia:
odleg³o¶æ z 3 do wroc³awia + odleg³o¶æ z 4 do wroc³awia - odleg³o¶æ pomiêdzy 3 a 4.
I w ten sposób tworzymy ca³± macierz.
Kolejnym krokiem jest uporz±dkowanie warto¶ci w tej macierzy od najwiekszej do najmniejszej ( ale tylko dodatniej) wraz z numerem wiersza i kolumny w której wystapi³a. Czyli je¿eli to by³a macierz 10X10 to uzyskujemy 100 kolumnowy ci±g warto¶ci (lub mniejszy poniewa¿ interesuj± nas tylko warto¶ci dodatnie) oraz pod nim odpowiadaj±cy tej warto¶ci nr wiersza i nr kolumny.
I tutaj zaczyna siê sedno sprawy czyli kolejne iteracje algorytmu. ( to z czym nie mogê sobie poradziæ)
zaczynamy od trasy której przypisana zosta³a najwieksza warto¶æ oszczêdno¶ci ( czyli bierzemy pierwszy nr wiersza i nr kolumny w naszym ci±gu np 7 wiersz 8 kolumna i tworzymy trase [ 1 7 8 1 ] - 1 poniewa¿ wyjezdzamy z Wroc³awia nastepnie przez miasto o indeksie 7 potem 8 i ponownie musimy wrócic do wroc³awia. Dla tej trasy obliczamy ³±czny czas i ³adowno¶æ ( to okazalo siê dosyæ ³atwe u¿ywaj±c funkcji wyszukaj.pionowo , indeks )
Je¿eli trasa spe³nia nasze ograniczenia co do ³adowno¶ci i czasu to sprawdzamy czy mo¿emy do³±czyæ kolejne miasta wystêpuj±ce w kolejno¶ci utworzonego ci±gu warto¶ci lub tworzymy now± trasê. Zaznaczyæ trzeba równie¿ ¿e wychodzimy pocz±tkowo z za³o¿enia ¿e jest 9 tras ( tyle co zlecen poniewa¿ macierz 10x10 - Wroc³aw=9) i stosunkowo ³±cz±c trasy zmniejszamy jej liczbê to minimalnej tak aby przy tym spe³nione by³y warunki ograniczaj±ce.
[ Dodano: 2010-02-13, 18:54 ]