6570141617

4. Model Matematyczny

Problemy marszrutyzacji, sklasyfikowane w poprzednim rozdziale, można opisać za pomocą dokładnego modelu matematycznego, to znaczy takiego, który przedstawia problem optymalizacyjny dający deterministyczne rozwiązanie optymalne. Model ten stanowi zestaw równań i nierówności formułujący problem programowania liniowego, który jest wykorzystywany w zadaniach optymalizacyjnych. Istnieją metody programowania liniowego pozwalające na wyznaczenie dokładnego optimum danego problemu (jeśli takie optimum istnieje), np. algorytm sympleksowy. W niniejszym rozdziale sformułowane zostaną zadania programowania liniowego reprezentujące wybrane problemy marszrutyzacji. Na początku zostanie wyprowadzony model dla podstawowego problemu (PPM), następnie zaprezentowane zostaną możliwości rozszerzenia modelu do reprezentacji bardziej złożonych procesów (na przykładzie PMOC). Do zrozumienia wyprowadzanego modelu niezbędna jest znajomość zagadnień związanych z programowaniem liniowym (szerzej: badań operacyjnych) oraz ogólna znajomość metod optymalizacji liniowej.

Opis modelu matematycznego został zamieszczony w niniejszej pracy w dwóch celach; aby przedstawić precyzyjną specyfikację problemu oraz aby wykorzystać część wyprowadzonych ograniczeń przy konstruowaniu heurystyk i algorytmów w dalszej części pracy. Zamodelowane zostały wybrane problemy z dziedziny marszrutyzacji, od problemu bazowego (PPM) do bardziej złożonego (PMOC). Obydwa modele różnią się od siebie złożonością, są rozszerzalne i mogą być zastosowane z pewnymi modyfikacjami do szerszej grupy problemów.

4.1. Przepływ pojazdów w PPM - model 2-i

Model oparty na równaniach przepływu pojazdów wykorzystujący podwójnie indeksowane zmienne całkowitoliczbowe do opisu ilości przejść przez daną krawędź w grafie (ile pojazdów przejechało daną krawędzią) oznaczamy jako model 2-i. Model taki dobrze nadaje się do formułowania problemu, w którym rozwiązanie może być zaprezentowane jako suma kosztów powiązanych z krawędziami, gdzie najistotniejsze ograniczenia wpływające na kształt rozwiązania dotyczą bezpośredniego przejścia pomiędzy klientami. Wtedy ograniczenia mogą zostać zamodelowane jako zestaw definicji dla krawędzi oraz kosztów przejść.

Bazowy model wykorzystuje 0(n²) podwójnie indeksowanych zmiennych boolowskich x do wskazania, czy pojazd przejeżdża przez krawędź w optymalnym rozwiązaniu - zmienna e(i,j') 6 E przyjmuje wartość 1 jeśli należy do rozwiązania, 0 w przeciwnym przypadku. Dodatkowo używana jest podwójnie indeksowana zmienna całkowitoliczbowa określająca koszt przebycia drogi

19