ZAGADNIENIE TRASOWANIA POJAZDÓW Z OGRANICZENIAMI

CZASOWYMI ORAZ OGRANICZONĄ LICZBĄ POJAZDÓW.

METODA WYZNACZANIA GÓRNEGO OGRANICZENIA DLA

CAŁKOWITEJ LICZBY ODBIORCÓW

Tomasz AMBROZIAK, Renata PIĘTKA

Politechnika Warszawska

Wydział Transportu

Zakład Logistyki i Systemów Transportowych

ul. Koszykowa 75, 00-662 Warszawa

e–mail: [e-mail]

STRESZCZENIE

W artykule przedstawiono wprowadzenie do problemu trasowania pojazdów z ograniczeniami

czasowymi oraz ograniczoną liczbą pojazdów. Przedstawiono również metodę wyznaczania górnego
ograniczenia całkowitej liczby odbiorców możliwych do obsłużenia daną ograniczoną liczbą pojazdów.

1. WSTĘP

Wiele praktycznych problemów logistyki transportu i dystrybucji może być

sformułowanych jako zagadnienie trasowania pojazdów z ograniczeniami czasowymi.
Rozwiązaniem tego typu problemów jest znalezienie takiej organizacja przewozów, której
celem jest uzyskanie planu tras o minimalnym koszcie obsługującego zbiór odbiorców
ze znanymi popytami. Zakładamy, że każdy odbiorca jest przyporządkowywany do dokładnie
jednej trasy pojazdu, a całkowity popyt każdej z tras nie może przekraczać pojemności
pojazdu.

Większość proponowanych metod znalezienia ww. planu tras zakłada, że liczba

dostępnych pojazdów jest nieograniczona, a celem jest uzyskanie rozwiązania,
które minimalizuje ich liczbą i/lub całkowity koszt przejazdu. Jednakże w rzeczywistości
operatorzy transportowi dysponują ograniczonymi zasobami pojazdów.

POLITECHNIKA WARSZAWSKA

Wydział Transportu

Polska Akademia Nauk

Komitet Transportu

2. CHARAKTERYSTYKA PROBLEMU

2.1.

CHARAKTERYSTYKA

PROBLEMU

TRASOWANIA

POJAZDÓW

Z OGRANICZENIAMI CZASOWYMI ORAZ OGRANICZONA ILOŚCIĄ
POJAZDÓW

W artykule omówiony zostanie problem trasowania pojazdów z ograniczeniami

czasowymi oraz ograniczoną liczbą dostępnych pojazdów polegający na rozwózce lub
zwózce towarów bądź osób, w zależności od rodzaju zagadnienia(np. przewozy z i do
szkoły). Zakładamy, że równoczesna zwózka i rozwózka nie jest dopuszczalna. Przykładowy
schemat problemu zwózki oraz przykład rozwiązania przedstawione został na rys. 1.

Rys. 1. Przykładowy problem zwózki z 7 odbiorcami wraz przykładowym rozwiązaniem. Wierzchołek

0

- baza,

wierzchołek 1 – wierzchołek końcowy.

Wyżej przedstawiony problem można sformułować następująco. Niech n będzie liczbą

odbiorców zgłaszających zapotrzebowanie na przewóz. Tworzymy zbiór N ={2,…, n+1}
numerów wierzchołków oznaczających poszczególnych odbiorców. Wierzchołek 1
reprezentować będzie punkt początkowy(w przypadku rozwózki) bądź punkt końcowy (w
przypadku zwózki) zlecenia, zaś 0 reprezentować będzie bazę pojazdów.

Dla każdego wierzchołka i∈ N mamy określony czas obsługi o

i

, który przykładowo

określać może czas potrzebny do wsiadania bądź wysiadania z pojazdu osób, zależny
chociażby w przypadku przewozu osób niepełnosprawnych od stopnia niepełnosprawności
pasażera.

Wielkość q

i

określa popyt każdego z odbiorców(przykładowo liczbę osób jaką należy

zabrać z i-tego wierzchołka). Zakładamy, że podział wielkości q

i

jest zabroniony. W związku

z tym popyt każdego odbiorcy musi być mniejszy niż największa dostępna pojemności
pojazdu:

max{ } max{ }

a

i

a

i

!

q

q

(2.1)

gdzie a określa typ dostępnego pojazdu.

Zakładamy dodatkowo, że łączny popyt odbiorców jest znacznie większy

od największej dostępnej pojemność pojazdu:

1

2

max{ }

a

i

a

i

+

=

>>

!

n

q

Q

(2.2)

Zakładamy, że przewozy odbywać się będą uwzględniając w każdym i-tym zleceniu

następujące kryteria jakości:
-

dla każdego odbiorcy i∈ N obsługa w wierzchołku 1 nie może w przypadku rozwózki
rozpocząć się wcześniej niż wartość

ro

T

1

dla wierzchołka 1, zaś w przypadku zwózki

zakończyć później niż

pr

T

1

;

-

rzeczywisty czas jazdy każdego klienta nie może przekraczać maksymalnej wartości

max

,

1 i

t

dla rozwózki, a

max

1

,

i

t

dla zwózki, będącej pewną funkcją bezpośredniego czasu

jazdy t

1,i

(dla rozwózki) lub t

i,1

(dla zwózki) między wierzchołkiem 1 a wierzchołkiem

i∈ N (np. podwojonej wartości bezpośredniego czasu jazdy między tymi
wierzchołkami);

-

różnica („czas odchylenia”) pomiędzy rzeczywistym momentem odbioru(dowozu) a
pożądanym momentem odbioru(dowozu) nie może przekraczać ustalonej wartości
maksymalnej

max

od

t

.

Na podstawie podanych powyżej kryteriów jakości dla każdego i∈ N wyznaczamy,

okna czasowe [a

i

, b

i

], określające przedziały, w zakresie których należy rozpocząć/zakończyć

obsługę w i-tym wierzchołku.

Dla problemu rozwózki okna te wyznaczamy z następujących zależności:

- najwcześniejszy możliwy moment rozpoczęcia obsługi w wierzchołku 1

ro

T

a

1

1

=

(2.3)

- najpóźniejszy dopuszczalny moment rozpoczęcia obsługi w wierzchołku 1

max

1

1

od

t

a

b

+

=

(2.4)

- najwcześniejszy możliwy moment rozpoczęcia obsługi w wierzchołku i

i

i

t

a

a

,

1

1

+

=

(2.5)

- najpóźniejszy dopuszczalny moment rozpoczęcia obsługi w wierzchołku i

max

,

1

1

i

i

t

b

b

+

=

(2.6)

natomiast dla problemów zwózki zależności te są następujące:

- najpóźniejszy możliwy moment rozpoczęcia obsługi w wierzchołku 1

pr

T

b

1

1

=

(2.7)

- najwcześniejszy dopuszczalny moment rozpoczęcia obsługi w wierzchołku 1

max

1

1

od

t

b

a

!

=

(2.8)

- najwcześniejszy możliwy moment rozpoczęcia obsługi w wierzchołku i

1

,

1

i

i

t

a

a

!

=

(2.9)

- najpóźniejszy dopuszczalny moment rozpoczęcia obsługi w wierzchołku i

max

1

,

1

i

i

t

b

b

!

=

(2.10)

Na rys. 2. powyższe zależności zostały przedstawione graficznie dla obu przypadków.

Określony jest również dla każdej pary wierzchołków i,j∈ N ∪{ 0 ,1} ∧ (i≠j) czas

podróży t

i,j

oraz odległość d

i,j

między wierzchołkami i oraz j .

Zakładamy, że w bazie 0 z oknem czasowym

0

0

[ , ]

a b

mamy do dyspozycji A typów

pojazdów. Zbiór A={1,…, a,…, A} oznacza zbiór numerów typów pojazdów. Każdy pojazd
typu a charakteryzuje się pojemnością Q

a

∈

/{0}, oraz ustalonym kosztem eksploatacyjnym

a

c

określonym na jednostkę odległości. Niech zbiór P(a)={1

a

,…,L(a)

a

} określa zbiór

numerów pojazdów typu a, przy czym L(a) określa liczbę pojazdów typu a. Niech
P=

a !

U

A

P(a) będzie zbiorem numerów wszystkich dostępnych pojazdów.

Rys. 2. Schemat okien czasowych: a) przypadek rozwózki; b) przypadek zwózki.

Ciąg wierzchołków T = 〈 1, i

1

,…, i

m

, 0 〉(rozwózka) lub T = 〈0 , i

1

,…, i

m

, 1 〉(zwózka)

gdzie i

1

,…, i

m

jest m-elementowym ciągiem liczb ze zbioru N nazywać będziemy trasą. Zbiór

tras mających tę własność, że każdy wierzchołek występuje dokładnie raz w jednej z tras
nazywać będziemy planem przewozów.

Zadaniem jest uzyskanie takiego planu przewozów składającego się maksymalnie z

P

tras(gdzie

P

moc zbioru P równa liczbie dostępnych pojazdów), spełniającego następujące

ograniczenia:
-

każda trasa rozpoczyna się/kończy w bazie i kończyć/rozpoczynać w wierzchołku 1;

-

każdy wierzchołek(odbiorca) obsługiwany jest dokładnie raz;

-

całkowity popyt wszystkich odbiorców obsługiwanych na trasie nie przekracza
pojemności pojazdu przypisanego do tej trasy;

-

obsługa w każdym punkcie musi rozpocząć się/zakończyć w przedziale czasu
określonym oknem czasowym;

-

liczba użytych do przewozów pojazdów nie może przekraczać dostępnej ilości.

-

czas pracy pojazdu nie może przekraczać danej wartości maksymalnej(np.
dopuszczalny czas pracy kierowców);

gdzie funkcja celu:
-

maksymalizuje całkowitą liczbę obsługiwanych odbiorców;

-

minimalizuje całkowitą liczbę odbiorców obsługiwanych później (jeśli dozwolone);

-

minimalizuje całkowity czas trwania zwłoki (jeśli dozwolone);

-

minimalizuje całkowitą liczbę użytych pojazdów;

-

minimalizuje całkowitą odległości przejazdu.

Jednym z możliwym sposobów uchwycenia tak wielokryterialnego celu jest

zdefiniowanie funkcji kosztów będącej sumą kosztów odpowiadających poszczególnym
kryteriom z przypisaniem im odpowiednich wag. Jednakże, określenie poprawnych wag może
stać się trudne (lub wręcz niemożliwy), a wynikowa funkcja stanie się bezsensowna
do zinterpretowania.

Innym z podejść do problemu jest zdefiniowanie hierarchicznej struktury kosztów

jak zaproponowano w [1]. Dla przykładu, obsłużenie większej liczby odbiorców jest zawsze
lepsze niezależnie od liczby użytych pojazdów. Zaproponowana hierarchiczna struktura
kosztów odpowiadała w malejący kolejność pierwszeństwa przedstawionej powyżej liście
celów. Dla dokładniejszego opisu hierarchicznej struktury kosztów odsyłamy do publikacji
Lau H.C., Sim M., Teo K.M. [1].

2.2. METODA WYZNACZANIA GÓRNEGO OGRANICZENIA DLA CAŁKOWITEJ

LICZBY ODBIORCÓW
Do wyznaczania górnego ograniczenia dla całkowitej liczby odbiorców, którzy mogą być

obsłużeni ograniczoną liczbą pojazdów w problemach trasowania pojazdów z ograniczeniami
czasowymi Lau H.C., Sim M., Teo K.M. [1] zaproponowali sformułowanie w postaci zadania
programowania całkowitoliczbowego. Sformułowanie takie dzięki swojej prostocie jest
w stanie zapisać problemy dużych rozmiarów, nie jest jednak na tyle uproszone aby jego
wynik odbiegał znacznie od poszukiwanego rozwiązania optymalnego.

Przykładowo dla problemu rozwózki w zastosowanym sformułowaniu będzie brało się

pod uwagę ograniczenia pojemności pojazdów, jaki i ograniczenia czasu narzucone przez
najpóźniejsze momenty powrotu każdego pojazdu do bazy. W tym przypadku górne
ograniczenie liczbą odbiorców możliwych do obsłużenia jest wynikiem rozwiązywania
następującego sformułowania programowania całkowitoliczbowego.
Niech P =

a !

U

A

P(a) będzie zbiorem numerów wszystkich dostępnych pojazdów, zaś

N

c

=N∪{

0

,1} będzie zbiorem numerów wierzchołków reprezentujących odbiorców

wyłączając wierzchołek bazy oraz wierzchołek początkowy. Zdefiniujmy wielkość

,

min

i

j i j

r

t

=

dla i,j∈ N

c

∧ (i≠j), określającą czas przejazdu z wierzchołka i do najbliższego

sąsiada i jest dolnym ograniczeniem czasu przejazdu z wierzchołka i do każdego innego
wierzchołka.
Niech

,0

i

i

i

i

w

b o

t

=

+

+

dla i∈ N

c

oznacza moment powrotu do bazy po obsłużeniu odbiorcy

w wierzchołku i jako ostatniego odbiorcy, przy czym obsługa odbiorcy i rozpoczęło się
w najpóźniejszym momencie rozpoczęcia obsługi. Bez utraty uogólnienia załóżmy,
że wszystkie wartości w

i

nie przekraczają okna czasowego dla bazy.

Niech G={g

1

, g

2

,…,

P

g

} będzie listą

P

niepowtarzalnych odbiorców, dla których w

i

≥w

j

dla wszystkich i∈ G ∧ j∉ G. Zakładamy, że wszystkie pojazdy są identyczne, a

P

elementów

zbioru G reprezentują najpóźniejsze możliwe momenty powrotu do bazy dla każdego z

P

pojazdów, dla wykonalności rozwiązania.

Zmienną decyzyjną oznaczamy przez

P

!

"

p

,

1,

0,

i p

je¿eli wierzcholek

jest obslugiwany przez pojazd ,

x

w przeciwnym razie

!

"

= #

$

i N

p

(2.11)

Znaleźć maksimum funkcji

ƒ(x) =

i,p

p

i

x

!

!

" "

c

P

N

→ max

(2.12)

spełniającej ograniczenia:

,

1

i p

i

p

x

!

!

"

#

$

c

N

P

(2.12)

,

i p

i

p

i

x

q

Q

!

!

"

#

$

%

c

P

N

(2.13)

,

0

(

)

i p

i

i

g

p

i

x

o

r

r

w

!

!

"

#

+

+

$

%

c

p

P

N

(2.14)

Ograniczenia (2.12) zapewnia, że wszyscy odbiorcy muszą być przyporządkowywani

co najwyżej do jednego pojazdu. Ograniczenia (2.13) zapewnia, że pojemność każdego
z pojazdów nie jest przekroczona. Ograniczenia (2.14) narzuca, że dla każdego pojazdu,
najwcześniejszy możliwy moment powrotu do bazy nie może przekraczać najpóźniejszego
możliwego momentu powrotu (narzuconego przez G).

Zauważmy, że w tym sformułowaniu, zignorowane zostało całkowicie rozpatrywanie

ograniczeń okien czasowych i rzeczywistego czasu przejazdu pomiędzy dwoma
wierzchołkami. Będzie ono więc mniej efektywne dla problemów z wąskimi oknami
czasowymi.

3. WNIOSKI

Występowanie w problemach trasowania pojazdów ograniczeń na czas pracy

pojazdów, godzin otwarcia bazy i pożądanych czasów obsługi odbiorców znacząco
komplikuje problem. W rzeczywistych problemach mamy jednak do czynienia jeszcze
dodatkowo z ograniczoną liczbą pojazdów, będących w dyspozycji przewoźników.
Konsekwencją tak wielu ograniczeń może być trudność w skonstruowaniu planu
dopuszczalnego, zwłaszcza, kiedy w problemie ograniczenia czasu są restrykcyjne.

Wyznaczenie górnego ograniczenia dla całkowitej liczby odbiorców, którzy mogą

być

obsłużeni

ograniczoną

liczbą

pojazdów

w

problemach

trasowania

z ograniczeniami czasowymi pozwala na wstępne określenie możliwości realizacji
założonych przez przewoźnika zadań.

LITERATURA

[1] Lau H.C., Sim M., Teo K.M.: Vehicle routing problem with time windows and limited number of

vehicles,

European Journal of Operational Research 148 (2003) 559–569.

[2] Savelsbergh M.W.P., Sol M.: The general pickup and delivery problem. Transportation Science

29 (1995).

[3] Solomon M. M., Desrosiers J.: Time window constrained routing and scheduling problems.

Transportation Science 22 (1988)

[4] Piasecki S. Optymalizacja systemów przewozowych. Wydawnictwa Komunikacji i Łączności.

Warszawa 1973.

[5] Ambroziak T., Piętka R. Metoda wyznaczania suboptymalnej organizacji przewozów

terminowych. Materiały Konferencyjne VIII. Konferencji Logistyki Stosowanej "TOTAL
LOGISTIC MANAGEMENT" Zakopane 2004.

[6] Piętka R. Zagadnienie przewozów terminowych. Sformułowanie zadania optymalizacyjnego,

metoda rozwiązania. Zeszyty Naukowe Politechniki Śląskiej Nr 1621 Transport 52 (2004).

VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

AND A LIMITED NUMBER OF VEHICLES.

METOD OF DETERMINING AN UPPER BOUND FOR THE TOTAL NUMBER OF CUSTOMERS.

ABSTRACT

This paper introduces a variant of the vehicle routing problem with time windows where a limited number of vehicles
is given. There is also presented the method of

determining an upper bound for the total number of customers that

can be served by a given fixed number of vehicles.