Matematyka dyskretna dla WMS: algorytm kompresji towarów w komórkach (część 1)

W artykule opiszemy, jak rozwiązaliśmy problem braku wolnych miejsc na magazynie oraz jak opracowaliśmy algorytm dyskretnej optymalizacji, aby poradzić sobie z takim zadaniem. Opowiemy, jak "budowaliśmy" matematyczny model zadania optymalizacji i z jakimi trudnościami niespodziewanie się zmierzyliśmy podczas przetwarzania danych wejściowych do algorytmu.

Jeśli interesują Cię zastosowania matematyki w biznesie i nie boisz się trudnych przekształceń wzorów na poziomie 5. klasy, to serdecznie zapraszamy pod kat!

Artykuł będzie przydatny dla tych, którzy wprowadzają WMS-systemy, pracują w branży logistyki magazynowej lub produkcyjnej, a także dla programistów, którzy interesują się zastosowaniami matematyki w biznesie i optymalizacją procesów w przedsiębiorstwie.

Część wprowadzająca

Ta publikacja kontynuuje cykl artykułów, w których dzielimy się swoim udanym doświadczeniem we wdrażaniu algorytmów optymalizacji w procesy magazynowe.

W poprzedniej artykule opisano specyfikę magazynu, w którym wdrożyliśmy WMS-system, a także opowiedziano, dlaczego potrzebne było rozwiązanie problemu klasteryzacji partii pozostałych towarów podczas wdrażania WMS-systemu, i jak to zrobiliśmy.

Kiedy skończyliśmy pisać artykuł o algorytmach optymalizacji, okazał się on bardzo obszerny, dlatego postanowiliśmy podzielić zebrany materiał na 2 części:

• W pierwszej części (ten artykuł) opowiemy, jak "budowaliśmy" matematyczny model zadania oraz z jakimi dużymi trudnościami niespodziewanie się zmierzyliśmy podczas przetwarzania i przekształcania danych wejściowych do algorytmu.
• W drugiej części szczegółowo omówimy realizację algorytmu w języku C++, przeprowadzimy eksperyment obliczeniowy i podsumujemy doświadczenia, które zdobyliśmy podczas wdrażania takich "inteligentnych technologii" w procesy biznesowe klienta.

Jak czytać artykuł. Jeśli czytałeś poprzedni artykuł, możesz od razu przejść do rozdziału „Przegląd istniejących rozwiązań”, jeśli nie, to opis rozwiązania problemu znajduje się w spoilerze poniżej.

Opis rozwiązywanego problemu na magazynie klienta

Wąskie miejsce w procesach

W 2018 roku zrealizowaliśmy projekt wdrożenia WMS-systemu w magazynie "Dom Handlowy "LD" w Chelyabinsku. Wdrożyliśmy produkt "1C-Logistyka: Zarządzanie magazynem 3" na 20 stanowisk roboczych: operatorzy WMS, magazynierzy, kierowcy wózków widłowych. Magazyn średniej wielkości, około 4 tys. m2, liczba komórek 5000 i liczba SKU 4500. W magazynie przechowywane są kulowe zawory własnej produkcji w różnych rozmiarach, od 1 kg do 400 kg. Zapasy w magazynie są przechowywane w podziale na partie, ponieważ istnieje potrzeba selekcji towaru według FIFO.

Podczas projektowania schematów automatyzacji procesów magazynowych napotkaliśmy istniejący problem nieoptymalnego przechowywania zapasów. Specyfika przechowywania i układania zaworów jest taka, że w jednej komórce do przechowywania jednostkowego może znajdować się tylko asortyment jednej partii (patrz rys. 1). Produkty przychodzą do magazynu codziennie, a każdy przyjazd to oddzielna partia. W wyniku miesiąca pracy magazynu powstaje 30 oddzielnych partii, przy tym każda musi być przechowywana w oddzielnej komórce. Towar często jest pobierany nie w całości, a sztukami, co powoduje, że w strefie poboru jednostkowego w wielu komórkach sytuacja prezentuje się następująco: w komórce o objętości ponad 1 m3 znajduje się kilka sztuk zaworów, które zajmują mniej niż 5-10% objętości komórki.

Rys. 1. Zdjęcie kilku sztuk w komórce

Widać nieoptymalne wykorzystanie mocy magazynowych. Aby obrazować skalę problemu, przytoczę liczby: średnio takich komórek o objętości powyżej 1 m3 z 'niewielkimi' zapasami w różnych okresach pracy magazynu można naliczyć od 100 do 300 komórek. Ponieważ magazyn jest stosunkowo mały, w sezonach wzmożonej pracy to zjawisko staje się 'wąskim gardłem', co znacznie spowalnia procesy przyjęć i wydania towarów.

Pomysł rozwiązania problemu

Pojawił się pomysł: partie zapasów z najbliższymi datami sprowadzać do jednej wspólnej partii, a takie zapasy z ujednoliconą partią umieszczać kompaktowo razem w jednej komórce lub w kilku, jeśli miejsca w jednej nie będzie wystarczające na przechowanie całej ilości zapasów. Przykład takiego 'ściśnięcia' przedstawiono na rysunku 2.

Rys. 2. Schemat ściśnięcia zapasów w komórkach

To znacznie redukuje zajmowaną przestrzeń magazynową, która będzie wykorzystywana pod nowy towar. W sytuacji przeciążenia zdolności magazynowych taka miara jest absolutnie konieczna, w przeciwnym razie może zabraknąć wolnej przestrzeni na umieszczenie nowego towaru, co doprowadzi do zastoju procesów magazynowania oraz zaopatrzenia, a co za tym idzie, do zastoju przyjęć i wysyłek. Wcześniej, przed wdrożeniem systemu WMS, taką operację wykonywano ręcznie, co było mało efektywne, ponieważ proces wyszukiwania odpowiednich zapasów w komórkach był dość długi. Teraz, wraz z wdrożeniem systemu WMS, zdecydowano się zautomatyzować, przyspieszyć i uczynić go inteligentnym.

Proces rozwiązania takiego zadania dzieli się na 2 etapy:

• na pierwszym etapie znajdujemy grupy partii bliskie pod względem daty do skompresowania (temu zadaniu poświęcone poprzedni artykuł);
• na drugim etapie obliczamy dla każdej grupy partii maksymalnie kompaktowe rozmieszczenie zapasów towaru w komórkach.

W bieżącym artykule zatrzymamy się na drugim etapie algorytmu.

Przegląd istniejących rozwiązań

Zanim przejdziemy do opisu opracowanych przez nas algorytmów, warto przeprowadzić krótki przegląd systemów już istniejących na rynku, WMSw których zrealizowano podobną funkcjonalność optymalnego skompresowania.

Na pierwszym miejscu należy zauważyć produkt „1C: Przedsiębiorstwo 8. WMS Logistyka. Zarządzanie magazynem 4”, który należy do firmy 1C i jest dystrybuowany przez tę firmę, i należy do czwartej generacji WMS-systemów opracowanych przez firmę AXELOT. W tym systemie zgłoszono funkcjonalność kompresji, mającą na celu łączenie rozproszonych zapasów towarów w jednej wspólnej komórce. Należy dodać, że funkcjonalność kompresji w takim systemie obejmuje także inne możliwości, na przykład poprawę rozmieszczenia towarów w komórkach zgodnie z ich klasami ABC, ale na tym się nie zatrzymamy.

Analizując kod systemu "1C: Przedsiębiorstwo 8. WMS Logistyka. Zarządzanie magazynem 4" (który w tej części funkcjonalności jest otwarty), można wyciągnąć następujące wnioski. Algorytm kompresji zapasów wdraża dość prymitywną liniową logikę, a o jakiejkolwiek "optymalnej" kompresji nie może być mowy. Oczywiście, nie przewiduje on klastrowania partii. Kilku klientów, u których taki system został wdrożony, skarżyło się na wyniki planowania kompresji. Na przykład, w praktyce często miała miejsce taka sytuacja: 100 szt. zapasów towaru z jednej komórki planuje się przenieść do innej komórki, gdzie leży 1 szt. towaru, chociaż optymalnie z punktu widzenia czasu lepiej byłoby zrobić odwrotnie.

Funkcjonalność kompresji zapasów towarów w komórkach jest również zgłaszana w wielu zagranicznych WMS-systemach, ale niestety nie mamy ani rzeczywistych recenzji dotyczących efektywności pracy algorytmów (to jest tajemnica handlowa), ani tym bardziej pojęcia o głębokości ich logiki (oprogramowanie własnościowe z zamkniętym kodem), więc nie możemy ocenić.

Poszukiwanie modelu matematycznego zadania

Aby zaprojektować wysokiej jakości algorytmy do rozwiązania zadania, najpierw należy to zadanie jasno matematycznie sformułować, co uczynimy.

Istnieje wiele komórek , w których znajdują się zapasy pewnego towaru. Takie komórki będziemy dalej nazywać komórkami-dawcami. Oznaczmy objętość towaru znajdującego się w komórce $.

Ważne jest, aby powiedzieć, że w procedurze kompresji może brać udział tylko jeden towar z jednej partii lub kilku partii, które wcześniej zostały połączone w klaster (czytaj poprzedni artykuł), co wynika ze specyfiki przechowywania i układania towarów. Dla różnych towarów lub różnych klastrów partii powinna być uruchamiana osobna procedura kompresji.

Istnieje wiele komórek , do których potencjalnie mogą być przeniesione zapasy z komórek-dawców. Takie komórki będziemy dalej nazywać komórkami-pojemnikami. Mogą to być zarówno wolne komórki w magazynie, jak i komórki-dawcy z zbioru . Zawsze zbiór jest podzbiorem .

Dla każdej komórki z zbioru ustawione są ograniczenia dotyczące pojemności , mierzone w dm3. Jeden dm3 to sześcian o bokach 10 cm. Produkty przechowywane w magazynie są wystarczająco duże, dlatego w tym przypadku taka dyskretyzacja jest jak najbardziej wystarczająca.

Podano macierz najkrótszych odległości w metrach między każdą parą komórek , gdzie i należą do zbiorów i odpowiednio.

Oznaczmy „koszty” przemieszczenia towaru z komórki do komórki . Oznaczmy „koszty” wyboru kontenera do przemieszczenia w niego odpadów z innych komórek. Jak dokładnie i w jakich jednostkach miar będą obliczane wartości i przyjrzymy się dalej (zob. rozdział przygotowanie danych wejściowych), teraz wystarczy powiedzieć, że takie wielkości będą wprost proporcjonalne do wielkości i odpowiednio.

Oznaczmy przez zmienną przyjmującą wartość 1, jeśli odpady z komórki są przemieszczenia do kontenera , i 0 w przeciwnym razie. Oznaczmy przez zmienną przyjmującą wartość 1, jeśli kontener zawiera odpady towarów, i 0 w przeciwnym razie.

Zadanie jest sformułowane w ten sposób: należy znaleźć taki zbiór kontenerów i w ten sposób „przypiąć” komórki-dawcy do komórek-kontenerów, aby zminimalizować funkcję

przy ograniczeniach

Łącznie w trakcie obliczania rozwiązania zadania dążymy do:

• po pierwsze, oszczędzania przestrzeni magazynowej;
• po drugie, oszczędzania czasu magazynierów.

Ostatnie ograniczenie oznacza, że nie możemy przemieszczać towarów do kontenera, którego nie wybraliśmy, a tym samym nie „ponieśliśmy kosztów” jego wyboru. To ograniczenie oznacza również, że objętość przemieszczanych towarów z komórek do kontenera nie powinna przekraczać pojemności kontenera. Pod rozwiązaniem zadania rozumiemy zbiór kontenerów i sposoby przypinania komórek-dawców do kontenerów.

Takie sformułowanie zadania optymalizacji nie jest nowe i było badane przez wielu matematyków już od początku lat 80. ubiegłego wieku. W literaturze zagranicznej istnieją 2 zadania optymalizacji z odpowiednim modelem matematycznym: Problem lokalizacji obiektów z jednego źródła o ograniczonej pojemności i Problem lokalizacji obiektów z wielu źródeł o ograniczonej pojemności (o różnicach zadań porozmawiamy później). Warto zauważyć, że w literaturze matematycznej sformułowania tych dwóch zadań optymalizacji wyrażane są w terminach rozmieszczenia przedsiębiorstw na terenie, stąd nazwa „Facility Location”. W większości to jest ukłon w stronę tradycji, ponieważ po raz pierwszy potrzeba rozwiązania takich zadań kombinatorycznych pojawiła się w dziedzinie logistyki, głównie w przemyśle wojskowym w latach 50. XX wieku. W terminach rozmieszczenia przedsiębiorstw takie zadania formułuje się w ten sposób:

• Istnieje skończona liczba miast, w których potencjalnie można ulokować zakłady produkcyjne (dalej miasta-producentów). Dla każdego miasta-producenta określono koszty otwarcia zakładu oraz ograniczenia mocy produkcyjnych otwieranego w nim przedsiębiorstwa.
• Istnieje skończona liczba miast, w których faktycznie znajdują się klienci (dalej miasta-klienci). Dla każdego takiego miasta-klienta określono wolumen popytu na produkty. Dla uproszczenia przyjmijmy, że produkt wytwarzany przez zakłady i konsumowany przez klientów jest jeden.
• Dla każdej pary miasto-producent i miasto-klient określono wysokość kosztów transportu związanych z dostawą wymaganego wolumenu produktów od producenta do klienta.

Należy znaleźć, w jakich miastach otworzyć zakłady oraz jak przypisać klientów do tych zakładów, aby:

• Suma kosztów otwarcia zakładów i kosztów transportu była minimalna;
• Wolumen popytu klientów przypisanych do jakiegokolwiek otwartego zakładu nie przekraczał możliwości produkcyjnych tego zakładu.

Teraz warto powiedzieć o jedynej różnicy między tymi dwoma klasycznymi zadaniami:

• Single-Source Capacitated Facility Location Problem – klient zaopatrywany jest tylko z jednego otwartego zakładu;
• Multi-Source Capacitated Facility Location Problem – klient może być zaopatrywany z kilku otwartych zakładów jednocześnie.

Różnica między tymi dwoma zadaniami na pierwszy rzut oka wydaje się znikoma, ale w rzeczywistości prowadzi do zupełnie różnej struktury kombinatorycznej takich zadań i, w konsekwencji, do zupełnie różnych algorytmów ich rozwiązania. Różnice między zadaniami zaprezentowane są na poniższym rysunku.

Rys.3. a) Multi-Source Capacitated Facility Location Problem

Rys.3. b) Single-Source Capacitated Facility Location Problem

Oba zadania -trudne, tzn. nie ma dokładnego algorytmu, który w czasie wielomianowym względem rozmiaru danych wejściowych rozwiązałby takie zadanie. Mówiąc prościej, wszystkie dokładne algorytmy do rozwiązania tego problemu będą działać w czasie eksponencjalnym, chociaż być może szybciej niż pełne przeszukiwanie wszystkich możliwości. Ponieważ problem -jest trudny, więc będziemy rozważać tylko przybliżone heurystyki, czyli algorytmy, które będą obliczać stabilne rozwiązania bardzo bliskie optymalnym i będą działać wystarczająco szybko. Jeśli pojawi się zainteresowanie takimi zadaniami, to tutaj można znaleźć dobry przegląd w języku rosyjskim.

Jeśli odniesiemy to do terminologii naszego zadania optymalnego pakowania towarów w komórkach, to:

• miasta-klienci – to komórki-dawcy z pozostałościami towaru,
• miasta-producenci – komórki-pojemniki , do których planowane jest umieszczenie pozostałości z innych komórek,
• koszty transportu – koszty czasu magazyniera na przeniesienia objętości towaru z komórki-dawcy do komórki-pojemnika ;
• koszty otwarcia przedsiębiorstwa – koszty wyboru pojemnika , równe objętości komórki-pojemnika , pomnożonej przez pewien współczynnik oszczędności wolnych objętości (wartość współczynnika zawsze > 1) (patrz rozdział przygotowanie danych wejściowych).

Po tym, jak analogię do znanych klasycznych zadań transportowych przeprowadzono, konieczne jest odpowiedzenie na ważne pytanie, od którego zależy wybór architektury algorytmu rozwiązania: czy przenoszenie pozostałości z komórki-dawcy jest możliwe tylko do jednego i tylko jednego pojemnika (Single-Source), czy też przenoszenie pozostałości może odbywać się do kilku komórek-pojemników (Multi-Source)?

Warto zauważyć, że w praktyce obie formy zadania mogą mieć miejsce. Przedstawimy wszystkie 'za' i 'przeciw' dla każdej z takich form poniżej:

Tabela 1. Plusy i minusy wariantów Single-Source i Multi-Source.

Ponieważ liczba plusów dla wariantu Single-Source jest większa, a także biorąc pod uwagę, że im mniejsza ilość resztek w komórkach-dawcach, tym różnica w stopniu kompaktowości kompresji, obliczonej w obu wariantach zadania, jest mniejsza, nasz wybór padł na wariant Single-Source.

Warto powiedzieć, że rozwiązanie wariantu Multi-Source również ma swoje miejsce. Istnieje wiele efektywnych algorytmów do jego rozwiązania, większość z nich sprowadza się do rozwiązania szeregu zadań transportowych. Są także nie tylko efektywne algorytmy, ale i eleganckie, na przykład, tutaj.

Przygotowanie danych wejściowych

Zanim przystąpimy do analizy i opracowywania algorytmu do rozwiązania zadania, należy określić, jakie dane i w jakiej formie będziemy mu dostarczać na wejściu. Nie ma problemu z objętościami resztek towarów w komórkach-dawcach oraz pojemnością komórek-pojemników, ponieważ to jest trywialne – takie wielkości będą mierzone w m3, ale z kosztami korzystania z komórki-pojemnika i macierzą kosztów przeniesienia sprawa nie jest już taka prosta!

Na początku rozważmy obliczenia. kosztów transportu towarów z komórki-dawcy do komórki-pojemnika. Przede wszystkim należy określić w jakich jednostkach miary będziemy obliczać koszty transportu. Dwie najoczywistsze opcje to metry i sekundy. W „czystych” metrach liczenie kosztów transportu jest bezsensowne. Pokażmy to na przykładzie. Niech komórka znajduje się na pierwszym poziomie, komórka jest oddalona o 30 metrów i znajduje się na drugim poziomie:

• Transport z do jest bardziej kosztowny niż transport z do , ponieważ łatwiej zsuwać w dół z drugiego poziomu (1,5-2 metry od podłogi) niż podnosić na drugi, chociaż odległość będzie przebyta taka sama;
• Przemieszczenie 1 szt. towaru z komórki do będzie łatwiejsze niż przemieszczenie 10 szt. tego samego towaru, chociaż odległość będzie przebyta taka sama.

Koszty transportu najlepiej uwzględnić w sekundach, ponieważ pozwala to uwzględnić różnice w poziomach oraz różnice w przemieszczeniu ilości towaru. Aby uwzględnić koszty transportu w sekundach, musimy rozłożyć operację transportu na elementarne składniki i dokonać pomiarów czasu na wykonanie każdej elementarnej części.

Niech z komórki przemieszcza się szt. towaru do kontenera . Niech to średnia prędkość ruchu pracownika po magazynie, mierzona w m/s. Niech i to średnie prędkości jednorazowego wykonania operacji weź i połóż odpowiednio dla objętości towaru równej 4 dm3 (średnia objętość, jaką pracownik zabiera za 1 raz w magazynie podczas wykonywania operacji). Niech i to wysokości komórek, z których wykonywane są operacje weź i połóż odpowiednio. Na przykład, średnia wysokość pierwszego poziomu (podłoga) wynosi 1 m, drugiego poziomu 2 m itd. Wtedy wzór na obliczenie całkowitego czasu wykonania operacji transportu wygląda następująco:

W tabeli 2 przedstawiono statystyki czasu wykonania każdej elementarnej operacji, zebrane przez pracowników magazynu z uwzględnieniem specyfiki przechowywanego towaru.

Nazwa operacji	Oznaczenie	Średnia wartość
Średnia prędkość ruchu pracownika po magazynie		1,5 m/s
Średnia prędkość wykonania jednej operacji połóż (dla objętości towaru 4 dm3)		2,4 sek

Tabela 2. Średni czas wykonania operacji magazynowych

Ustaliliśmy metodę obliczania kosztów transportu. Teraz należy ustalić, jak je obliczać. koszty wyboru pojemnika. Tutaj wszystko jest znacznie, znacznie bardziej skomplikowane niż w przypadku kosztów przemieszczania, ponieważ:

• po pierwsze, koszty powinny być ściśle powiązane z objętością pojemnika – tę samą objętość reszty, przemieszczaną z komórek-donorów, lepiej umieścić w mniejszym pojemniku niż w dużym pojemniku, pod warunkiem, że taka objętość całkowicie mieści się w obu pojemnikach. W ten sposób, minimalizując całkowite koszty wyboru pojemników, staramy się oszczędzać "deficytowe" wolne moce magazynowe w obszarze strefy selekcji, aby zrealizować następne operacje rozlokowania towaru w komórkach. Na rysunku 4 pokazano opcje przemieszczania reszty do dużych i małych pojemników oraz konsekwencje tych opcji przemieszczania przy wykonywaniu następnych operacji magazynowych.
• po drugie, ponieważ w rozwiązaniu pierwotnego zadania musimy zminimalizować całkowite koszty, a to suma kosztów zarówno przemieszczania, jak i wyboru pojemników, to objętości komórek w metrach sześciennych należy jakoś powiązać z sekundami, co wcale nie jest trywialne.

Rys. 4. Opcje przemieszczania reszty do pojemników o różnej pojemności.

Na rysunku 4 na czerwono przedstawiono objętość reszty, która już nie mieści się w pojemniku na drugim etapie rozmieszczania następnych towarów.

Pomogą powiązać metry sześcienne kosztów wyboru pojemnika z sekundami kosztów przemieszczania następujące wymagania dotyczące obliczanych rozwiązań zadania:

• Należy zapewnić, aby reszty z komórki-donora były przemieszczane do komórki-pojemnika w każdym przypadku, jeśli zmniejsza to ogólną liczbę komórek-pojemników, w których znajduje się towar.
• Należy zachować równowagę między objętościami pojemników a kosztami czasu na przemieszczanie: na przykład, jeśli w nowej wersji rozwiązania zadania w porównaniu z poprzednią wersją zysk na objętości jest duży, a strata w kosztach czasu mała, to należy wybierać nową wersję.

Zacznijmy od ostatniego wymagania. Aby sprecyzować wieloznaczne słowo „równowaga” przeprowadziliśmy ankietę wśród pracowników magazynu w celu ustalenia następującego. Niech będzie komórka-pojemnik o objętości , do której zaplanowano przemieszczanie reszty towarów z komórek-donorów, a całkowity czas tego przemieszczania wynosi . Niech będą jeszcze kilka alternatywnych opcji rozmieszczenia tej samej ilości towaru z tych samych komórek-donatorów w inne pojemniki, gdzie każde rozmieszczenie ma swoje oceny. , gdzie < i , gdzie >.

Pytanie brzmi: jaki minimalny zysk objętości jest akceptowalny, przy danej wartości straty czasowej? ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Rys. 5. Wykres zależności minimalnej dopuszczalnej oszczędności objętości od zwiększenia różnicy w czasie wykonania operacji.

To znaczy, jeśli dodatkowy czas wydatkuje 40 sekund, to jesteśmy gotowi go poświęcić tylko wtedy, gdy zysk w objętości będzie wynosił co najmniej 500 dm3. Pomimo tego, że w obserwowanej zależności występuje niewielka nieliniowość, dla ułatwienia dalszych obliczeń będziemy przyjmować, że zależność jest liniowa i opisuje ją nierówność.

Na poniższym rysunku rozważamy następujące sposoby rozmieszczenia towaru w pojemnikach.

Rys. 6. Opcja (a): 2 pojemniki, łączna objętość 400 dm3, łączny czas 150 sek.

Rys. 6. Opcja (b): 2 pojemniki, łączna objętość 600 dm3, łączny czas 190 sek.

Rys. 6. Opcja (c): 1 pojemnik, łączna objętość 400 dm3, łączny czas 200 sek.

Opcja (a) wyboru pojemników jest bardziej preferowana niż pierwotna opcja, ponieważ nierówność jest spełniona: (800-400)/10>=150-120, z czego wynika 40 >= 30. Opcja (b) jest mniej preferowana niż pierwotna opcja, ponieważ nierówność nie jest spełniona: (800-600)/10>=190-150, z czego wynika 20 >= 40. Ale opcja (c) nie mieści się w podobnej logice! Przyjrzyjmy się tej opcji bliżej. Z jednej strony nierówność (800-400)/10>=200-120, a więc nierówność 40 >= 80 nie jest spełniona, co oznacza, że zysk w objętości nie jest wart tak dużej straty czasu.

Z drugiej strony, w takiej opcji (c) nie tylko zmniejszamy łączną zajętą objętość, ale także zmniejszamy liczbę zajętych komórek, co jest jednym z dwóch istotnych wymagań stawianych rozwiązywaniu problemów, wymienionych powyżej. Oczywiście, aby to wymaganie zaczęło być spełniane, konieczne jest dodanie do lewej strony nierówności pewnej dodatniej stałej. , przy czym tę stałą należy dodawać tylko wtedy, gdy liczba pojemników maleje. Przypomnijmy, że — to zmienna, która wynosi 1, gdy pojemnik został wybrany, i 0, gdy pojemnik nie wybrano. Oznaczamy, – zbiór pojemników w pierwotnym rozwiązaniu i – zbiór pojemników w nowym rozwiązaniu. W ogólnym ujęciu nowe nierówność będzie wyglądać tak:

Przekształcając nierówność powyżej, otrzymujemy

Na podstawie tego mamy formułę do obliczania całkowitych kosztów pewnej wersji rozwiązania problemu:

Ale teraz pojawia się pytanie: jakie powinno być takie wartość konstanta ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Załóżmy, – maksymalny dystans między komórkami magazynowymi w jednej strefie ABC, równy w naszym przypadku 100 m. Załóżmy, – maksymalna objętość komórki-pojemnika w magazynie, wynosząca w naszym przypadku 1000 dm3.

Pierwszy sposób obliczenia wartości . Rozważmy sytuację, w której znajdują się 2 pojemniki na pierwszym piętrze, w których fizycznie już znajduje się towar, co oznacza, że ​​sami są komórkami-dawcami, a koszty przemieszczania towaru do tych samych komórek są oczywiście równe 0. Należy znaleźć taką wartość konstanta , przy której opłacalne byłoby zawsze przenosić resztki z pojemnika 1 do pojemnika 2. Podstawiając wartości i do nierówności, przedstawionej powyżej, otrzymujemy:

z czego wynika

Podstawiając wartości średniego czasu realizacji operacji elementarnych do powyższej formuły otrzymujemy

Drugi sposób obliczenia wartości . Rozważmy sytuację, w której istnieje komórki-dawcy, z których planuje się przemieszczenie towaru do pojemnika 1. Oznaczmy – odległość od komórki-dawcy do pojemnika 1. Jest również pojemnik 2, w którym już są towary, a jego objętość pozwala pomieścić resztki ze wszystkich komórek. Dla uproszczenia przyjmujemy, że objętość towaru, przenoszonego z komórek-dawców do pojemników jest taka sama i wynosi . Należy znaleźć taką wartość konstanta , przy której umieszczenie wszystkich resztek z komórek w pojemniku 2 byłoby zawsze korzystniejsze niż umieszczenie ich w różnych pojemnikach:

Przekształcając nierówność otrzymujemy

Aby "wzmocnić" wartość wielkości , przyjmujemy, że = 0. Średnia liczba komórek, które zwykle biorą udział w procedurze kompresji resztek w magazynie wynosi 10. Podstawiając znane wartości wielkości, mamy następującą wartość konstanta

Bierzemy największą wartość, obliczoną dla każdej wersji, to będzie wartość wielkości dla zadanych parametrów magazynu. Teraz dla pełności zapiszmy formułę obliczenia całkowitych kosztów dla pewnego dopuszczalnego rozwiązania :

A więc teraz, po wszystkich titanicznych wysiłkach w przekształceniu danych wejściowych, możemy powiedzieć, że wszystkie dane wejściowe zostały przekształcone do pożądanego formatu i są gotowe do użycia w algorytmie optymalizacji.

Podsumowanie

Jak pokazuje praktyka, pracochłonność i znaczenie etapu przygotowania i przekształcenia danych wejściowych dla algorytmu często są niedoszacowane. W tym artykule postaraliśmy się szczególnie zwrócić uwagę na ten etap, aby pokazać, że tylko jakościowo i mądrze przygotowane dane wejściowe mogą uczynić wyniki obliczane przez algorytm naprawdę cennymi dla klienta. Tak, było wiele wniosków z formuł, ale ostrzegaliśmy was o tym już przed katem 🙂

W następnym artykule w końcu dotrzemy do celu, dla którego zaplanowane były 2 poprzednie publikacje – do algorytmu dyskretnej optymalizacji.

Artykuł przygotował
Roman Szangin, programista działu projektów,
firma Pierwszy Bit, m. Chelyabinsk

Źródło: habr.com