Logistyka - nauka

Logistyka 6/2013

905

Dr inż. Robert Kostek UTP w Bydgoszczy

Dr inż. Marcin Łukasiewicz UTP w Bydgoszczy

Dr inż. Tomasz Kałaczyński UTP w Bydgoszczy

Optymalizacja tras transportu drogowego w celu minimalizacji emisji CO

2

Streszczenie

W pracy tej przedstawiono zagadnienie optymalizacji drogi transportu pomiędzy

dwoma punktami. Jako kryterium optymalizacji przyjęto minimalizację emisji CO

2

.

Najczęściej przyjmowanym kryterium optymalizacji tras są długość trasy i czas transportu,

natomiast minimalizacja emisji CO

2

nie jest często spotykana. Przyjęcie emisji CO

2

jako

kryterium pociąga za sobą konieczność modelowania ruchu pojazdu, dlatego zastosowano

graf skierowany, w którym wagi krawędzi są funkcjami czasu. Taki model umożliwia

modelowanie zmiennych warunków drogowych w funkcji czasu oraz różnych prędkości

pojazdów w przeciwnych kierunkach jazdy.

1.

Wstęp

W pracy tej przedstawiono zagadnienie modelowania i optymalizacji drogi transportu

pomiędzy dwoma punktami, dla którego jako funkcje kryterialną przyjęto minimalizację

emisji CO

2

. W większości prac z zakresu badań operacyjnych prezentuje się modele

pozwalające na znalezienie najkrótszej lub najszybszej drogi, natomiast zagadnienie emisji

CO

2

nie jest w nich omawiane. Zagadnienie to zamodelowano stosując graf skierowany, w

którym wagi krawędzi są funkcjami czasu. Takie podejście pozwala na odwzorowanie różnej

prędkości ruchu w przeciwnych kierunkach oraz modelowanie zmiennych warunków

drogowych w funkcji czasu, co odnosi się do powstawania zatorów drogowych w godzinach

szczytu. Do rozwiązania takiego zagadnienia należy użyć specjalnych algorytmów, na

przykład genetycznych.

Zagadnienie minimalizacji emisji CO

2

jest ściśle związane z minimalizacją zużycia

paliwa przez pojazd. Ciągnik siodłowy z naczepą o masie całkowitej 40t zużywa około

0,30kg oleju napędowego na kilometr. Roczne jedna ciężarówka pokonuje dystans około

Logistyka - nauka

Logistyka 6/2013

906

120000 [km], co daje roczne zużycie paliwa rzędu 36000 [kg]. To pozwala oszacować emisję

CO

2

dla jednej ciężarówki na 111960 [kg] CO

2

roczne przy założeniu, że spalenie jednego

kilograma oleju napędowego powoduje emisję 3,11 [kg] CO

2

[1]. To pokazuje, że temat

zmniejszenia emisji CO

2

jest wart podjęcia zarówno z uwagi na ekonomikę jak i ekologie

transportu drogowego.

2.

Modelowanie jednostkowego zużycia paliwa

Jednostkowe zużycie paliwa jest funkcją: masy całkowitej pojazdu, prędkości pojazdu,

przełożenia skrzyni biegów, nachylenia drogi, prędkości wiatru, jak i wielu innych

czynników. Do celów praktycznych zależność tę należy wyestymować bazując na wynikach

eksperymentalnych uzyskanych dla danego pojazdu. Jako funkcję estymowaną można przyjąć

wielomian wielu zmiennych, który dobrze opisuje łagodne przebiegi funkcji. Stopień

wielomianu, stałe wielomianu jak i zmienne niezależne określa się na podstawie testów

matematycznych. Testy te pozwalają uchwycić istotne statystycznie wyrazy oraz odrzucić

zmienne nieistotne statystycznie. Przykładowy wielomian opisujący średnie zużycie paliwa w

funkcji masy całkowitej pojazdu przedstawiono poniżej:

g = 0.0002m

2

– 0.0059m + 0.239,

(1)

gdzie:

g – oznacza jednostkowe zużycie paliwa [kg/km], natomiast

m – masę całkowitą pojazdu wyrażoną w [t].

Wzór ten został opracowany dla ciągnika siodłowego z naczepą, których masa brutto znajduje

się w przedziale od 16 do 40 [t]. Podobną zależnością można opisać zużycie paliwa w funkcji

prędkości stosując wielomian stopnia trzeciego. Można także zastosować wielomian

opisujący zużycie paliwa w funkcji dwóch zmiennych, który ma następującą postać:

g = a

0

+a

1

v+a

2

v

2

+a

3

v

3

+a

4

m+a

5

m

2

+a

6

m

3

+a

7

mv+a

8

mv

2

+a

9

m

2

v,

(2)

gdzie:

a

0

... a

9

– oznaczają stałe wielomianu, natomiast

v - reprezentuje prędkość pojazdu.

Logistyka - nauka

Logistyka 6/2013

907

Dla każdego przełożenia skrzyni biegów należy taką funkcje wyestymować. Przy założeniu,

ż

e skrzynia biegów posiada dwanaście przełożeń, należy dwanaście takich funkcji

wyestymować. Dla zadanej masy ładunku, masę całkowitą pojazdu m można w przybliżeniu

potraktować jako stałą. Zakłada się wtedy, że zmiana masy paliwa nie ma istotnego wpływu

na masę całkowitą pojazdu. Pozwala to na znalezienie: prędkości i przełożenia, dla którego

jednostkowe zużycie paliwa będzie najmniejsze; lub przełożenia, dla którego przy zadanej

prędkości pojazdu jednostkowe zużycie paliwa będzie najmniejsze. Innymi słowy, można

zmienić prędkość pojazdu i przełożenie w celu minimalizacji zużycia paliwa. Taka

optymalizacja jest obecnie stosowana w niektórych samochodach ciężarowych, na przykład

firma IVECO stosuje takie rozwiązanie (EcoSwitch, EcoFleet). W rozważanym przypadku,

optymalizacja dotyczy jazdy po płaskim odcinku drogi, pominięto bowiem we wzorze (2) kąt

pochylenia drogi. Zastosowanie trzeciej potęgi we wzorze (2) wynika z nieliniowej

charakterystyki zużycia paliwa.

3.

Modelowanie sieci dróg

Do modelowania sieci dróg można zastosować grafy. Graf składa się z węzłów w

(wierzchołków), które są połączone krawędziami k (łukami). Krawędzie mogą być

skierowane to znaczy, że przebiegają w jednym kierunku lub mogą być nieskierowane to

znaczy, że są dwukierunkowe. Węzłom i krawędzią przyporządkowuje się wartości bądź

funkcje. Matematycy zazwyczaj nie nadają im interpretacji fizycznej, jednak do zastosowań

praktycznych jest ona niezbędna.

Fragment odcinka drogi przedstawiono na rys. 1a. Rozważany odcinek został

podzielony na mniejsze odcinki, to znaczy krawędzie. Każdej krawędzi przyporządkowano

wektor, który zawiera informacje o danej krawędzi. Przykładowe informacje to długość

odcinka drogi, pochylenie, prędkość dopuszczalna, średnia prędkość pojazdów. Takie

podejście pozwala na uwzględnienie różnych warunków jazdy na wybranym odcinku drogi,

natomiast zastosowanie krawędzi skierowanych pozwala na uwzględnienie różnych

warunków jazdy w przeciwnych kierunkach jazdy. Parametr, jakim jest średnia prędkość

pojazdów, podlega dobowym wahaniom wynikającym z przemieszczania się ludzi do i z

pracy oraz oznakowania. Dlatego uwzględnienie wahań prędkości średniej pojazdów pozwala

na modelowanie tworzenia się zatorów drogowych. W kolejnym kroku zablokowane odcinki

drogi mogą być omijane przez pojazdy. Dobowe wahania prędkości średniej pojazdów można

zamodelować stosując ciąg trygonometryczny. Węzły przedstawione na rys.1a nie muszą

Logistyka - nauka

Logistyka 6/2013

908

mieć interpretacji fizycznej, mogą one oznaczać umowny podział odcinka lub mogą oznaczać

na przykład stacje paliw lub parkingi. W kolejnym kroku można zamodelować sieć dróg (rys.

1b). W przypadku sieci dróg węzły są interpretowane na przykład jako skrzyżowania i

parkingi. Powyższy opis pokazuje jak można zastosować grafy do modelowania

infrastruktury drogowej.

Wizualizacje zmiennych warunków jazdy w trakcje doby można obserwować na

przykład na stronie internetowej

www.targeo.pl

(rys. 2). Przedstawione dane pozwalają na

zlokalizowanie dróg, które powinny być omijane, ponieważ przejazd nimi zabiera najwięcej

czasu. Dane te z kolei są niezbędne do minimalizacji zużycia paliwa i planowania trasy. W

przypadku, gdy wagi krawędzi są funkcją czasu, chwila rozpoczęcia podróży oraz okres

postoju wpływają na uzyskany wynik (zużycie paliwa), stają się więc zmiennymi. To z kolei

dodatkowo komplikuje rozwiązywany problem.

Rys. 1. Modele odcinka drogi a) oraz sieci dróg b) przedstawione formie grafów

Logistyka - nauka

Logistyka 6/2013

909

a)

b)

Rys. 2. Wizualizacje średniej prędkości pojazdów na terenie Bydgoszczy uzyskane

dla godzin 6:00 a) i 17:00 b)

Ź

ródło

www.targeo.pl

(dostęp 23.01.2013)

Logistyka - nauka

Logistyka 6/2013

910

4.

Metody rozwiązania zagadnienia optymalizacyjnego

Rozwiązanie tak sformułowanego zagadnienia optymalizacyjnego staje się trudne,

dlatego w pierwszym przybliżeniu pewne uproszczenie zostanie przyjęte. Czas podróży jest

krótki, dlatego dobowe wahania prędkości średniej pojazdów mogą zostać pominięte. To

założenie można przyjąć dla podróży po mieście. Przyjęcie takiego założenia powoduje, że

krawędzią można przyporządkować wagi G, reprezentujące zużycie paliwa wyrażone w [kg],

które nie są funkcjami czasu. Do rozwiązania tego zagadnienia można zastosować na

przykład algorytmy A*, Dijkstry lub Bellmana-Forda. Istotą tych algorytmów jest porównanie

kosztów ścieżek, które docierają do węzłów [2]. Jeżeli dla jakiegoś fragmentu ścieżki,

zostanie znaleziony objazd, którego suma wag jest mniejsza aniżeli suma wag fragmentu

ś

cieżki, to objazd zostaje włączony do ścieżki. W ten sposób można zmniejszać sumę wag

ś

cieżki. Im bardziej selektywnie algorytm szuka rozwiązania i im niej operacji wykonuje, tym

bardziej jest efektywny. To zagadnienie jest klasyczne i nie wymaga dalszego omawiania.

W kolejnym podejściu można przeanalizować wszystkie możliwe ścieżki w grafie

pomiędzy dwoma wybranymi wierzchołkami. Zakładając, że każdy wierzchołek grafu ma

jedne bezpośrednie połączenie z każdym innym wierzchołkiem grafu (graf pełen), wtedy

liczbę możliwych ścieżek, bez powtórzeń wierzchołków, pomiędzy dwoma wierzchołkami

wyraża się wzorem:

∑

−

=

=













−

=

2

0

!

2

w

N

r

r

w

s

r

r

N

N

,

(3)

gdzie:

N

s

– oznacza liczbę możliwych ścieżek w grafie bez powtórzeń węzłów,

N

w

– reprezentuje liczbę węzłów w grafie,

r – jest liczbą węzłów, przez które przebiega ścieżka.

Jak widać z przedstawionego wzoru N

s

rośnie bardzo szybko wraz ze wzrostem N

w

. Dlatego

dla dużej liczby wierzchołków metoda ta staje się nieefektywna. Jednakże w praktyce węzły

posiadają połączenia bezpośrednie zaledwie z kilkoma innymi węzłami, dlatego wzór (3)

podaje zawyżoną liczbę ścieżek dla typowych przypadków. Podsumowując, przeanalizowanie

każdej możliwej ścieżki daje pewność znalezienia najlepszego rozwiązania, ale jest

czasochłonne.

Logistyka - nauka

Logistyka 6/2013

911

W związku z tym, że przeanalizowanie całego zbioru rozwiązań przy dużej liczbie

węzłów staje się niemożliwe, należy zbiór rozwiązań przeszukać w sposób selektywny. Do

przeszukiwania obszaru rozwiązań można zastosować algorytmy genetyczne [3,4,5,6].

Rozwiązaniami początkowymi mogą być najkrótsze ścieżki oraz najszybsze ścieżki, uzyskane

dla wybranych chwil czasowych. Można do zbioru rozwiązań początkowych przyjąć także

ś

cieżki, które policzono dla różnych chwil zakładając stałą wagę ścieżek G. Wagi te wyrażają

zużycie paliwa w [kg]. Kolejne modyfikacje ścieżek, wykonywane zgodnie z metodą

algorytmów genetycznych, prowadzą do zmniejszenia zużycia paliwa. Modyfikacje te

polegają na budowaniu nowych ścieżek z losowych fragmentów wcześniej przyjętych ścieżek

i losowo wybranych łuków. Jeżeli fragmenty ścieżek nie są połączone, to znaczy zaczynają

się i kończą w różnych węzłach, wtedy należy je połączyć. W ten sposób uzyskuje się nową

populacje ścieżek. Dla nowych ścieżek liczy się sumy wag. Ścieżki dla których suma wag jest

największa, zostają odrzucone i nie biorą udziału w dalszych modyfikacjach. Najlepsze

ś

cieżki z poprzedniej populacji mogą także uczestniczyć w tworzeniu nowej populacji

ś

cieżek. W ten sposób selektywnie przeszukuje się obszar rozwiązań. Wprowadzenie

losowego przeszukiwania pozwala natomiast na wychodzenie z minimów lokalnych.

Kolejna metoda znalezienia lepszej ścieżki to metoda szukania objazdu. Znalezienie

alternatywnej drogi (objazdu) o mniejszym koszcie nie musi oznaczać, że nowa ścieżka w

całości będzie mniej kosztowna, jeśli czasy przejazdu są różne t

1

≠

t

2

. Wagi w pozostałej części

ś

cieżki ulegają zmianie w funkcji czasu, dlatego pozostała część ścieżki powinna zostać

przeliczona powtórnie dla nowych warunków. Problem ten zilustrowano na rys. 3. Liczby

przy krawędziach reprezentują wagi krawędzi (koszty krawędzi), podczas gdy liczby

wewnątrz kwadratów reprezentują koszt dotarcia do poszczególnych węzłów (sumę wag

krawędzi). Algorytm który szuka objazdów wydaje się bardziej selektywny od metody

algorytmów genetycznych, ponadto tylko część ścieżki jest przeliczana ponownie, dlatego

powinien być bardziej efektywny. Podsumowując, algorytmy przeszukiwania i generowania

nowych ścieżek wpływają na czas obliczeń i uzyskane wyniki.

Logistyka - nauka

Logistyka 6/2013

912

Rys. 3. Problem wyboru ścieżki w warunkach zmiennych wag

5.

Podsumowanie

Emisja CO

2

jest istotna z uwagi na negatywne oddziaływanie transportu na

ś

rodowisko. Mapy stosowane do planowania tras przejazdu, jako kryteria przyjmują odległość

lub czas. Są to dwa najczęściej stosowane kryteria, natomiast minimalizacja emisji CO

2

nie

jest spotykana. Nieliczne mapy pozwalają na obliczenie zużycia paliwa i emisji CO

2

, jednak

optymalizacja trasy z uwagi na to kryterium nie jest znana autorom. Dlatego w tej pracy

przedstawiono metody optymalizacji trasy przejazdu, w celu minimalizacji emisji CO

2

.

Zagadnienie omijania korków i minimalizacji zużycia paliwa jest szczególnie istotne

dla firm zajmujących się transportem w miastach. Dotyczy to szczególnie firm rozwożących

przesyłki kurierskie. Zagadnienie to nie jest jednak traktowane w należyty sposób przez

decydentów, nie dostrzegają oni znaczenia właściwego planowania tras. Ponadto niewiele jest

map, które podają aktualne informacje o korkach i utrudnieniach w ruchu.

Kolejnym zagadnieniem, które warto podsumować, jest optymalizacja trasy z

uwzględnieniem zmiennej sytuacji drogowej. Rozwiązanie tego zagadnienia wymaga

zastosowania niestandardowych procedur, co jest interesującym zagadnieniem. Autorom nie

są znane programy komercyjne, które rozwiązują to zagadnienie. W artykule tym

przedstawiono natomiast metody rozwiązania tego zagadnienia.

Redukcja zużycia paliwa ma znaczenie praktyczne z uwagi na ekonomikę transportu,

ponieważ koszt paliwa stanowi około połowę kosztów transportu. Należy jednak podkreślić,

ż

e maksymalizacja zysku w jednostce czasu nie jest tożsama z ograniczeniem kosztów

paliwa.

Logistyka - nauka

Logistyka 6/2013

913

OPTIMISATION OF TRANSPORT ROUTES TO REDUCE CO

2

EMISSION

This article presents optimisation of a transport route between two points. The main aim of

optimisation is reduction of CO

2

emission. Most of handbooks present minimisation of delivery time

or the shortest path; thus reduction of CO

2

emission should be described. The CO

2

emission is

modelled with directed graphs. In the presented model, weights assigned to arcs are functions of time,

which reflects nature of road traffic.

Literatura

[1] Żółtowski A.: Opracowanie poradnika ustalania czynników energetyczno- emisyjnych w

zamówieniach publicznych na zakup pojazdów drogowych, PRACA ITS NR 10483

2011

[2] Sikora W.: Badania operacyjne, Polskie Wydawnictwo Ekonomiczne, 2008

[3] Ahn C., Ramakrishna R.: A genetic algorithm for shortest path routing problem and the

sizing of populations, “IEEE Transactions on Evolutionary Computation” 6, s.566–579,

2002.

[4] Babooa S.S., Narasimhan B.: Genetic algorithm based congestion aware routing

protocol (GA-CARP) for mobile ad hoc networks, “Procedia Technology” 4, s. 177–

181, 2012

[5] Senthilkumarana T., Sankaranarayanan V.: Dynamic congestion detection and control

routing in ad hoc networks, “Journal of King Saud University - Computer and

Information Sciences” 25, s. 25–34, 2013

[6] Shigehiro1 Y., Miyakawa T., Masuda T.: Road traffic control based on genetic

algorithm for reducing traffic congestion, “Electronics and Communications in Japan”

95, s. 11–19, 2012