Problem Lokalizacji Obiektów: Gdzie Umieszczać Zasoby do Maksymalnego Okrycia

Dlaczego proste wybory glodne zasobów się nie sprawdzają

Naturalnym pierwszym instynktem jest rangowanie każdego kandydata według tego, ile bliskiej wagi może on spełnić, a następnie po prostu przyjęcie p najlepszych miejsc. To nie działa, ponieważ ignoruje konkurencję między instalacjami o to samo miejsce wagi. Jeśli dwie z najbardziej rangowanych instalacji są obecnie blisko tej samej gęstej grupy wagi, wybieranie obu jest bezsensowne, ponieważ jedna z nich będzie nadmiernie pokrywana, podczas gdy inny obszar mapy pozostaje całkowicie niezabudowany. W rzeczywistości, jak tylko instalacja jest otwarta, bliskie punkty wagi są przypisywane do niej, a konkurencja z innymi instalacjami o to samo miejsce wagi już nie ma sensu. To oznacza, że wartość dodania instalacji na konkretnym miejscu nie jest stałą liczbą, którą można obliczyć w izolacji; zależy od tych innych instalacji, które już zostały wybrane. Dwa średnio dobre miejsca, które pokrywają komplementarnie obszary, mogą zastąpić dwa lokalnie doskonałe miejsca, które się nadmiernie pokrywają. Ta zależność między decyzjami jest dokładnie tym, co sprawia, że lokalizacja instalacji jest prawdziwym problemem optymalizacji kombinatorycznej zamiast prostej operacji sortowania, i to dlatego dziedzina ta potrzebuje formalnych funkcji celu i dedykowanych algorytmów zamiast jednokrotnego rangowania.

Cel p-mediana: minimalizacja średniej odległości podróży

Najczęściej używane formalne zapisanie to problem p-median. Dany jest zestaw punktów odbioru, każdy z wagą w_i reprezentującą ilość obciążenia pochodnego stamtąd (liczbę ludności, objętość zamówień, liczbę pojazdów), oraz zestaw kandydatów do otwarcia lokalizacji obsługiwanych. Cel polega na wyborze dokładnie p tych lokalizacji do otwarcia tak, aby suma ważonych odległości podróży była jak najmniejsza. Formalnie, jeśli d(i, nearest open facility) oznacza odległość z punktu odbioru i do najbliższego otwartego obsługiwanej lokalizacji, cel polega na minimalizacji sumy ważonej dla wszystkich punktów odbioru i, czyli w_i razy d(i, nearest open facility). Każdy punkt odbioru jest serwowany przez najbliższą mu otwartą obsługiwaną lokalizację, a cel p-mediana dodaje wszystkie te odległości ważone i próbuje minimalizować ich sumę. Jest to podstawowo cel typu średnio-casowego, orientowany na efektywność: jest naturalnym wyborem, gdy interesuje Cię minimalizacja całkowitego kosztu lub czasu podróży w całości systemie, takim jak sieć dystrybucji, gdzie każda przejechana mila kosztuje pieniądze, czy łańcuch handlowy próbujący minimalizować agresywne podróżowanie klientów. Użyteczny model myślowy to, że p-mediane skupiają się na centrach mas gęstych klastrow obciążenia, ponieważ serwując wiele ważonego obciążenia z krótkim średnim dystansem, bardziej efektywnie zmniejsza ona całą sumę niż dobrze serwując kilka odległych punktów z niewielką wagą.

Cel p-centra: Minimizacja Najgorszego Przypadku

Różne, równie ważne podejście to problem p-centra. Zamiast minimizować całą lub średnią odległość, ono minimizuje maksymalną odległość, jaką musi przebyć dowolny punkt zapotrzebowania do najbliższego otwartego obiektu. Formalnie: minimalizacja maksimum, wyliczonego dla wszystkich punktów zapotrzebowania i, z d(i, najbliżej otwartego obiektu). Gdy p-mediana pyta o systemowy pytanie (ile całościowej odległości musi przebyć sieć), problem p-centra pyta o najgorszy przypadek (jak długo ktoś będzie musiał czekać lub podróżować, w najmniej wygodnym przypadku). Ta różnica ma ogromne znaczenie w praktyce. W celu minimalizacji kosztów transportowych dla sieci magazynowej, średnie koszty są kluczowe, więc p-median jest odpowiednim narzędziem. Ale przy siedzeniu stacji pożarnych lub ambulansów, nikt nie chce być tym domem, który na podstawie średnich wartości systemu jest dobrze usługiwany, ale przypadkowo znajduje się w nieakceptowalnie długim odległości od jakiegokolwiek obiektu; planer kryzysowy zwraca uwagę na najgorszy czas reakcji, a nie miastośrednie wartości, które dokładnie kontroluje p-centr. Dlatego p-centr jest naturalnym ramem w każdym razie, gdy celem jest równość lub gwarancja poziomów usługi zamiast agresywnego efektywności, a dwie formuły mogą naprawdę się rozdzielić na miejsca umiejscowienia obiektów: optymalne rozwiązanie p-median może pozostawić jedno odległe punkt zapotrzebowania bardzo nieusługiwanym, nawet gdy osiąga doskonałą systemową średnią, dokładnie taki wynik, który jest zaprojektowany do zapobiegania rozwiązaniem p-centra.

NP-trudność i heurystyki praktyczne

Oba problemy — median p i centrum p — są w ogólności NP-trudne: liczba sposobów wyboru p obiektów z n kandydatów rośnie kombinatorycznie (n nad p), a nie znaleziono algorytmu, który mógłby znaleźć gwarancji optymalne rozwiązanie w czasie proporcjonalnym do rozmiaru problemu. Nawet małe instancje z kilkuset kandydatami i dziesiątką obiektów do umieszczenia mogą mieć więcej możliwych kombinacji niż liczb atomów, które można by przeliczyć siłą. Dlatego w praktyce lokalizacja obiektów wykorzystuje heurystyki, które znaleziono bardzo dobre, choć nie gwarantowane optymalne rozwiązania szybko. Popularnym podejściem jest konstrukcja zbyt zbyt głodna z wyszukiwaniem lokalnym: zaczyna się dodawaniem obiektów jeden po drugim, co najpierw wybiera każdy z pozostałych kandydatów, który najbardziej zmniejsza cel dana jest już umieszczone obiekty, a następnie ulepsza wynik poprzez wymiany, które próbują zamienić otwartą obserwację na zamkniętą kandydatkę i zachowuje wymianę, jeśli zwiększa cel, powtarzając proces aż nie pozostanie żadna korzystna wymiana. Inny rodzaj heurystyk pochodzi od algorytmu Lloyd'a w klasterowaniu k-means: alternatywnie przypisuje każdemu punktowi popytu jego najbliższy obecnie otwarty obiekt, a następnie przenosi każdy obiekt do punktu (lub kandydatki), który najlepiej usługuje punktom popytu przypisanym mu w tej chwili, powtarzając tę cykl reasignacji i przesunięcia aż do osiągnięcia stabilności. Nie obiekt nie gwarantuje prawdziwej optymalizacji, a obie mogą zatrzymać się w lokalnie dobrym, ale globalnie suboptymalnym układzie, dlatego praktycy często uruchamiają je z wielu losowych konfiguracji początkowych i zachowują najlepszy wynik znaleziony, traktując dowód optymalności za korzyść szybkiego i wystarczająco dobrego rozwiązania w praktyce.

Zastosowania w praktyce

Problem lokalizacji obiektów występuje tam, gdzie ograniczone ilości zasobów fizycznych muszą służyć rozproszonemu społecznościowi. Planowanie sieci stacji ładowania samochodów elektrycznych wykorzystuje modele podobne do p-mediany, aby określić, gdzie umieścić ustaloną liczbę stacji ładowania na autostradach lub w całym mieście, tak aby ostateczna odległość detour dla wszystkich kierowców była minimalna. Niektóre planery dodają ograniczenia typu p-centra, aby zapewnić, że żaden kierowca z rejonu wiejskiego nie zostanie zmuszony do czekania na najbliższy charger daleko od siebie. Lokalizacja magazynów i centrów dystrybucji jest przykładem klasykowym p-mediany: handlowcy i firmy logistyczne wybierają kilka lokalizacji magazynowych z wielu potencjalnych miejsc, aby minimalizować ostateczną odległość przesyłki m.in. wagi do wszystkich klientów lub sklepów, co bezpośrednio prowadzi do niższych kosztów paliwa i szybszych średnich czasów dostawy. Lokalizacja usług ratowniczych, w tym stacji pożarnych, depozytów ambulansów oraz zapasów pomocy przy katastrofach, opiera się głównie na myśleniu typu p-centra, ponieważ regulatorzy i planery zazwyczaj dbają o zapewnienie maksymalnie krótkiego czasu reakcji dla każdego dzielnicy, a nie tylko minimalizacji średniego miastowca. Wiele rzeczywistych implementacji połącza oba te pomysły: najpierw używa ograniczeń typu p-centra, aby zapewnić, że każda punkt znajduje się w jakiejś maksymalnej dozwolonej odległości od obiektu, a następnie wybiera konkretną konfigurację z wszystkich spełniających tę gwarancję, która minimalizuje ostateczny koszt.

Często zadawane pytania