LUB-Narzędzia to oprogramowanie open source do kombinacyjnej optymalizacji, które ma na celu znalezienie najlepszego rozwiązania problemu przy użyciu bardzo dużego zestawu możliwych rozwiązań. Oto przykłady problemów, które można rozwiązać przy użyciu narzędzi LUB:
- Kierowanie pojazdem: znajdowanie optymalnych tras dla flot pojazdów, które odbierają i dostarczają pakiety z uwzględnieniem ograniczeń (np. „W przypadku tego ciężarówki ważność nie może być większa niż 20 000 funtów” lub „wszystkie dostawy muszą być realizowane w ciągu 2 godzin”.
- Planowanie: znajdź optymalny harmonogram dla złożonego zestawu zadań, z których niektóre należy wykonywać przed innymi, na stałym zestawie komputerów lub innymi zasobami.
- Pakowanie kontenerów: umieść jak najwięcej obiektów o różnych rozmiarach w stałej liczbie kontenerów z maksymalną pojemnością.
W większości przypadków tego typu problemy można przygotować na wiele sposobów – jest ich zbyt wiele na komputerze, aby można było je wszystkie wyszukać. Aby rozwiązać ten problem, organizacja OR-Tools stosuje najnowocześniejsze algorytmy w celu zawężenia zbioru wyszukiwania w celu znalezienia optymalnego (lub prawie zbliżonego) rozwiązania.
Narzędzie OR zawiera narzędzia do rozwiązywania problemów:
- Programowanie ograniczeń
- zestaw metod znajdowania możliwych rozwiązań problemu wyrażonego jako ograniczenia (np. sali nie można używać jednocześnie na 2 zdarzenia, lub odległość od upraw musi być mniejsza niż długość węża lub nie można nagrać więcej niż 5 programów telewizyjnych jednocześnie);
- Programowanie linearne i z różnymi liczbami całkowitymi
- optymalizator liniowy Glop znajduje optymalną wartość funkcji celu liniowego ze względu na zestaw nierówności liniowych jako ograniczenia (np. przypisywanie osób do zadań lub znajdowanie najlepszego przydziału zasobów przy minimalizowaniu kosztów). Narzędzie Glop i oprogramowanie do śledzenia liczby mieszanej SCIP są również dostępne w Usłudze optymalizacji Google Apps Script.
- Kierowanie pojazdem
- Specjalna biblioteka do wybierania najlepszych tras pojazdów z powodu ograniczeń.
- Algorytmy wykresów
- Kod wyszukiwania najkrótszych ścieżek na wykresach, procesów o minimalnym koszcie, maksymalnych przepływów i przypisań liniowych.
W następnej sekcji dowiesz się, jak szybko używać narzędzi LUB.