6570141611

3. Klasyfikacja problemów marszrutyzacji

Rodzina problemów marszrutyzacji jest klasyfikowana następująco [7]:

•    z uwzględnieniem ładowność pojazdów (pojemnościowy PM, PPM)

•    z uwzględnieniem ograniczenia odległości (odległościowy PM, OPM)

•    PM z oknami czasowymi (PMOC)

•    PM z transportem powrotnym (PMTP)

•    PM z transportem powrotnym i oknami czasowymi (PMTPOC)

•    PM z dostawą/odbiorem (PMOD)

•    PM z dostawą/odbiorem i oknami czasowymi (PMODOC)

Bazowym problemem jest PPM, najszerzej opisywany w źródłach [1][2][5]. Kolejne problemy stanowią warianty bądź rozszerzenia problemu bazowego, układając się w hierarchię (rys. 2). Sam problem pojemnościowej marszrutyzacji stanowi generalizację problemu komiwojażera (3.1) oraz problemu plecakowego (3.2).

Rys 2. Hierarchia problemów marszrutyzacji. Strzałka od problemu A do problemu B oznacza, że B stanowi rozszerzenie A.

3.1. Problem komiwojażera

Dla danego zupełnego grafu nieskierowanego G = (V,E) oraz funkcji kosztu w(e) przyporządkowującej każdej krawędzi e należącej do E nieujemną wartość, należy znaleźć cykl

13