[Algorytmy] Optymalizacja zamówienia kabli

bobek358 · Post autor: **bobek358** » 4 wrz 2014, o 19:08

Witam

Mam pytanie, a właściwie chciałem zapytać o wasze propozycje.
Opracowuje algorytm optymalizacji zamówienia.
Tzn. są zamówienia składające się z kilkunastu odcinków na kable.
Mam też cały wałek kabla o określonej długości i muszę dobrać odcinki tak, aby odpad był możliwie najmniejszy - nawet zerowy.

Macie jakieś propozycje rozwiązania tego problemu?

gryxon · Post autor: **gryxon** » 4 wrz 2014, o 19:41

Jeżeli dobrze zrozumiałem to chyba jest problem plecakowy dla kilku plecaków? aczkolwiek mogę się mylić ;p

kropka+ · Post autor: **kropka+** » 4 wrz 2014, o 20:47

A czy są jakieś typowe długości zamawianych odcinków? Jeśli tak, to ile poszczególnych odcinków zamówiono w ciągu np. ostatniego miesiąca? Podaj długość kabla na całym wałku. Trzeba będzie ciąć z kilku wałków jednocześnie, żeby zminimalizować odpady, więc podaj dane.

bobek358 · Post autor: **bobek358** » 4 wrz 2014, o 20:54

Możemy przyjąć, że kompletujemy zamówienie i rozdzielamy je na kilka wałków.

Dane wejściowe:
długość na wałkach w m: 5000, 12500, 13600, 2000
przykładowe zamówienia:
10000, 345, 250, 2500, 250, 2000, 2500, 3255, 5000, 5000, 500

Teoretycznie, można dopasować, ze na 3 wałkach nie zostanie odpadów a na ostatnim będzie odpad.
Tutaj nie ma typowości. Zamówienia są od różnych klientów i mogą być "losowe".

kropka+ · Post autor: **kropka+** » 5 wrz 2014, o 00:56

No to jak nie ma typowości, to musisz właśnie tak dopasowywać jak napisałeś. Ten odpad jest duży, więc większość z niego sprzedasz przy kolejnych zamówieniach.

Algorytm dopasowania, jaki przychodzi mi do głowy, jest bardzo prosty i możesz go robić w Excelu.

Sortujesz zamówienia malejąco, czyli masz:\(\displaystyle{ 10000,5000,5000,3255,2500,2500,2000,500,345,250,250}\)

Sortujesz wałki rosnąco, i masz \(\displaystyle{ 2000,5000,12500,13600}\)

Odcinasz największe zamówienia od możliwie najmniejszych wałków, czyli:

odcinasz \(\displaystyle{ 10000}\) od trzeciego wałka o długości \(\displaystyle{ 12500}\) i zostaje \(\displaystyle{ 2500}\)
odcinasz \(\displaystyle{ 5000}\) od drugiego wałka o długości \(\displaystyle{ 5000}\) i nie ma odpadu
odcinasz \(\displaystyle{ 5000}\) od czwartego wałka o długości \(\displaystyle{ 13600}\) i zostaje \(\displaystyle{ 8600}\)
odcinasz \(\displaystyle{ 3255}\) od czwartego wałka o długości \(\displaystyle{ 8600}\) i zostaje \(\displaystyle{ 5345}\)
odcinasz \(\displaystyle{ 2500}\) od trzeciego wałka o długości \(\displaystyle{ 2500}\) i nie ma odpadu
odcinasz \(\displaystyle{ 2500}\) od czwartego wałka o długości \(\displaystyle{ 5345}\) i zostaje \(\displaystyle{ 2845}\)
odcinasz \(\displaystyle{ 2000}\) od pierwszego wałka o długości \(\displaystyle{ 2000}\) i nie ma odpadu
pozostałe zamówienia odcinasz od czwartego wałka (bo został tylko on) i odpad jest \(\displaystyle{ 1500}\)

bobek358 · Post autor: **bobek358** » 5 wrz 2014, o 08:22

Ciekawe podejście, muszę je oprogramować aby sprawdzić jego optymalność.

kropka+ · Post autor: **kropka+** » 5 wrz 2014, o 11:55

Jeżeli wiesz np., że raczej nie zdarza się aby ktoś zamawiał mniej niż \(\displaystyle{ 150}\), a odpad mniejszy niż \(\displaystyle{ 50}\) można od biedy zaakceptować, to możesz wprowadzić do algorytmu taką modyfikację: gdy odpad jest w przedziale \(\displaystyle{ (50,150)}\) to zamówienie usuwamy z tego wałka i odcinamy od następnego najmniejszego. Chodzi o to, żeby nie zostawały niesprzedawalne odpady. Dlatego przyjrzałabym się zamówieniom z przeszłości.

bobek358 · Post autor: **bobek358** » 5 wrz 2014, o 17:24

Niestety, ten algorytm się nie sprawdził, przy dużej ilości zamówień i większej ilosci wałków zostaje dużo odpadów.

kropka+ · Post autor: **kropka+** » 5 wrz 2014, o 21:01

No to może skorzystaj z rady gryxona i potraktuj to jako problem plecakowy, gdzie wartość zamówienia i waga zamówienia są takie same (równe zamawianej długości kabla) i plecaków jest tyle co wałków. Spróbuj to zrobić algorytmem z powrotami.
O problemie plecakowym jest tutaj: a algorytm z powrotami jest tutaj:.
Jestem ciekawa, czy to da lepszy wynik.

Post autor: **Afish** » 6 wrz 2014, o 12:54

Jak dla mnie nie ma co kombinować, tylko poszukać w literaturze:
Jeżeli nie masz dodatkowych założeń, to problem jest NP i uwzględniając obecną wiedzę cudów nie zdziałasz. Zaimplementuj to jako LP i użyj profesjonalnego oprogramowania do znalezienia sensownego rozwiązania (możesz użyć NEOSa: ), lub wzoruj się na gotowych implementacjach algorytmów (wiki wskazuje na przykład http://www.codeproject.com/Articles/706 ... ock-Solver )