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 ]