Optymalizacja trasy w mieście: proste modele i obliczenia

Czym jest optymalizacja trasy w mieście i po co ją liczyć?

Optymalizacja trasy w mieście to świadome wybieranie takiej kolejności przejazdu i takich ulic, aby osiągnąć konkretny cel: skrócić czas podróży, przejechać jak najmniej kilometrów, zmniejszyć koszt paliwa albo zrealizować więcej zleceń w ciągu dnia. W praktyce chodzi o przekucie chaosu miejskich ulic w prosty model matematyczny, na którym da się wykonać obliczenia.

W miejskiej rzeczywistości trasa rzadko jest „najkrótsza” w sensie geometrycznym. Korki, światła, ograniczenia prędkości, buspasy, remonty, zakazy skrętu – to wszystko powoduje, że trasa „po linii prostej” okazuje się najgorsza. Proste modele i obliczenia pomagają przenieść te problemy na język liczb i krok po kroku znaleźć rozwiązanie lepsze niż typowe „jadę na czuja”.

Optymalizacja trasy w mieście przydaje się nie tylko firmom logistycznym. Dotyczy dowozu jedzenia, kurierów, serwisantów, handlowców, a nawet planowania własnego dnia: przejazdu przez kilka punktów w mieście, wizyt domowych czy objazdu sklepów. Nawet bardzo prosty model trasy, zapisany na kartce lub w arkuszu kalkulacyjnym, pozwala ograniczyć zbędne kilometry i spóźnienia.

W praktyce da się wyróżnić kilka typowych problemów tras w mieście:

• dojazd z punktu A do B jak najszybciej lub najtaniej,
• odwiedzenie wielu punktów i powrót do startu,
• przydzielenie wielu punktów do kilku pojazdów,
• zaplanowanie przejazdu z uwzględnieniem okien czasowych (np. dostawy między 10:00 a 12:00).

Do każdego z tych zadań pasują inne modele. Nie zawsze trzeba od razu sięgać po zaawansowane algorytmy. W wielu miejskich zastosowaniach wystarczą proste, intuicyjne metody, które da się policzyć ręcznie lub w prostym arkuszu.

Jak zamienić miasto na model matematyczny: grafy i sieci

Drogi jako krawędzie, skrzyżowania jako węzły

Podstawowym narzędziem matematycznym do opisu sieci ulic jest graf. Graf składa się z:

• węzłów – mogą odpowiadać skrzyżowaniom, przystankom, adresom dostaw, kluczowym punktom w mieście,
• krawędzi – odcinkom dróg, którymi można się poruszać między węzłami.

Jeśli ulica jest jednokierunkowa, krawędź w grafie też będzie jednokierunkowa. Oznacza to, że można po niej jechać tylko w jednym kierunku. Jeśli ruch jest dwukierunkowy, między dwoma węzłami można mieć dwie krawędzie (w przeciwnych kierunkach) albo jedną nieskierowaną, w zależności od tego, jak szczegółowo chcemy modelować ruch.

Tworząc prosty model miasta, wystarczy wybrać tylko te węzły, które faktycznie są nam potrzebne: adres startu, adresy dostaw, ważniejsze skrzyżowania. Nie trzeba od razu przenosić całego miasta – im mniej elementów, tym łatwiej potem wykonać obliczenia.

Wagi krawędzi: czas, odległość, koszt

Sam graf ulic niewiele daje, jeśli wszystkie drogi są „równoważne”. Dopiero kiedy każdej krawędzi przypiszemy wagę, model staje się użyteczny. Waga krawędzi opisuje „koszt” przejazdu daną ulicą. Może to być:

• długość odcinka w kilometrach,
• czas przejazdu (np. w minutach),
• koszt paliwa na tym odcinku,
• łączny koszt – np. w minutach przeliczone na pieniądze.

W praktyce najczęściej używa się czasu przejazdu, bo to on decyduje o terminowości dostaw i ogólnej efektywności. Długość trasy ma znaczenie głównie tam, gdzie liczy się koszt paliwa czy zużycie pojazdu. Nic nie stoi na przeszkodzie, by zbudować model z kilkoma rodzajami wag, np. osobno czas i kilometrówkę, a potem łączyć je w jeden wskaźnik.

Przykład prostego przypisania wag:

• ulica lokalna – 0,5 km, średnia prędkość 30 km/h → około 1 min,
• główna arteria – 1,5 km, średnia prędkość 40 km/h → około 2,25 min (zaokrąglamy do 2–3 min),
• skręt w lewo przez dwa pasy ruchu – dodatkowe 0,5 min „kary” za światła i oczekiwanie.

W prostym modelu dzięki takim szacunkom można policzyć nie tylko minimalną odległość, ale przede wszystkim najkrótszy czas przejazdu.

Jak uprościć miasto do kilku kluczowych punktów

Pełne odwzorowanie miasta byłoby niewygodne obliczeniowo i całkiem zbędne na potrzeby planowania codziennej trasy. W praktyce tworzy się uproszczony graf, w którym:

• łączone są niewielkie odcinki ulic w dłuższe segmenty, jeśli na całej długości warunki są podobne,
• pomija się małe uliczki, z których w praktyce nie korzysta się w danej trasie,
• zostawia się tylko te skrzyżowania, na których realnie może nastąpić wybór kierunku.

Takie uproszczenie ma jedną ogromną zaletę: łatwiej policzyć trasę. Zamiast kilkuset skrzyżowań w modelu pojawi się kilkanaście–kilkadziesiąt. Optymalizacja nie będzie idealna w sensie matematycznym, ale zwykle wystarczy, by realnie skrócić przejazd i uprościć plan dnia.

W małych firmach logistycznych, które obsługują wciąż te same osiedla, dobrze sprawdza się podejście: raz przygotować mały graf „dzielnicowy”, opisać go w arkuszu kalkulacyjnym (lista węzłów, lista krawędzi z czasami) i potem jedynie aktualizować wagi, gdy zmienia się organizacja ruchu.

Najprostszy problem: najkrótsza droga między dwoma punktami

Intuicyjne szukanie najkrótszej trasy po sieci ulic

Najbardziej podstawowym zadaniem optymalizacji trasy w mieście jest znalezienie najkrótszej drogi z punktu A do punktu B. Przy niewielkiej liczbie możliwych dróg da się to zrobić „na oko”: narysować siatkę ulic, oznaczyć odległości (lub czasy) na odcinkach i porównać kilka sensownych wariantów.

W takim podejściu warto trzymać się kilku prostych zasad:

• unikać ostrych skrętów w lewo na ruchliwych skrzyżowaniach,
• często korzystać z równoległych, mniej zatłoczonych ulic,
• dobierać odcinki tak, aby jak najrzadziej przejeżdżać przez skrzyżowania ze światłami.

To jest już swego rodzaju „algorytm mentalny”, choć nie ma jeszcze formalnych obliczeń. Można go jednak łatwo zamienić na model liczbowy i poprosić arkusz kalkulacyjny o policzenie łącznego czasu przejazdu dla kilku wariantów, a następnie wybrać najlepszy.

Algorytm Dijkstry w wersji „bez wzorów”

Klasycznym sposobem znajdowania najkrótszej drogi w grafie z dodatnimi wagami jest algorytm Dijkstry. Nie trzeba go znać od strony formalnych dowodów, żeby z niego skorzystać. W wersji uproszczonej można go sprowadzić do prostego schematu:

1. Przypisz wszystkim węzłom „koszt dojścia” równy nieskończoności, a punktowi startowemu – 0.
2. Ustaw się w węźle startowym i zapisz koszt dojścia do wszystkich sąsiadów (koszt startu + waga krawędzi).
3. Wybierz węzeł o najmniejszym znanym koszcie, którego jeszcze nie „zamknąłeś”, i przejdź do niego.
4. Z tego węzła spróbuj poprawić koszty dojścia do jego sąsiadów (jeśli nowa trasa jest tańsza, zaktualizuj koszt).
5. Powtarzaj kroki 3–4, aż dojdziesz do węzła docelowego i nie da się go już poprawić.

W wersji „na kartce” można to liczyć w prostej tabeli: obok nazwy węzła zapisuje się aktualny koszt dojścia i poprzednika (z którego węzła przyszliśmy). Na końcu, zaczynając od węzła docelowego, cofamy się po poprzednikach, odtwarzając najlepszą trasę.

Na małym przykładzie z 6–7 węzłami takie liczenie zajmuje kilka minut, ale daje pewność, że trasa jest optymalna przy zadanych wagach. Przydatne jest to zwłaszcza, gdy sieć lokalnych uliczek jest pogmatwana i „intuicja” bywa zawodna.

Kiedy najkrótsza trasa nie oznacza najszybszej

W mieście rzadko chodzi wyłącznie o minimalną odległość. Trasa dłuższa o kilometr może okazać się szybsza o kilka lub kilkanaście minut, jeśli prowadzi szeroką arterią zamiast krętymi uliczkami. Dlatego warto jasno rozdzielić trzy różne kryteria:

• najkrótsza trasa – minimalna długość w kilometrach,
• najszybsza trasa – minimalny czas przejazdu,
• najtańsza trasa – minimalny łączny koszt (paliwo, czas pracy kierowcy, opłaty za parkingi, ewentualne myto).

Stosując algorytm najkrótszej drogi, zawsze trzeba precyzyjnie odpowiedzieć: co jest wagą? Jeśli wagi to długości – wyjdzie najkrótsza droga. Jeśli czasy – najszybsza. Jeśli np. „czas w minutach × stawka za godzinę kierowcy + koszt paliwa”, otrzymamy trasę optymalną ekonomicznie.

W miejskiej praktyce dobrze jest przygotować dwa scenariusze:

• gdy liczy się maksymalna liczba zrealizowanych punktów w ciągu dnia – minimalizować czas,
• gdy ważne jest obniżenie kosztów – minimalizować koszt pieniężny trasy, dopuszczając niewielkie wydłużenie czasu.

Trasa przez wiele punktów: prosty model problemu komiwojażera

Na czym polega problem komiwojażera w wersji miejskiej

W praktyce częściej niż pojedynczy przejazd A–B pojawia się zadanie: trzeba odwiedzić wiele adresów. Kurier ma listę kilkudziesięciu przesyłek, serwisant kilka zleceń w różnych dzielnicach, handlowiec serię spotkań. Klasycznym modelem takiej sytuacji jest problem komiwojażera (TSP – Travelling Salesman Problem).

W wersji miejskiej sprowadza się on do pytania: w jakiej kolejności odwiedzić wszystkie punkty, żeby łączny czas (lub odległość) przejazdu był możliwie najmniejszy, przy założeniu, że:

• startujemy z bazy (magazynu, domu),
• odwiedzamy każdy punkt dokładnie raz,
• wracamy do bazy (opcjonalnie, w zależności od scenariusza).

Nawet dla kilkunastu punktów możliwych tras jest ogromnie dużo. Pełne przeszukanie „wszystkich możliwych kolejności” jest kompletnie niepraktyczne bez komputera. Dlatego używa się heurystyk, czyli sprytnych metod przybliżonych, które nie gwarantują matematycznie najlepszego rozwiązania, ale w praktyce dają wynik bardzo dobry.

Metoda najbliższego sąsiada: szybki sposób na sensowną trasę

Najprostsza i często zaskakująco skuteczna heurystyka to metoda najbliższego sąsiada (nearest neighbor). Działa w kilku krokach:

1. Zacznij w punkcie startowym (np. baza).
2. Wybierz z listy ten punkt, do którego aktualnie masz najmniejszy czas dojazdu (lub odległość).
3. Przejedź do niego i oznacz go jako „odwiedzony”.
4. Z nowego punktu znów wybierz najbliższy nieodwiedzony punkt.
5. Powtarzaj, aż odwiedzisz wszystkie punkty, a na końcu wróć do bazy.

Taką procedurę można wykonać ręcznie, jeśli zna się przybliżone czasy dojazdu między punktami, albo wspomóc się prostą tabelą w Excelu. Wadą metody jest to, że skupia się wyłącznie na „lokalnie najlepszym” wyborze – nie patrzy naprzód. Może to prowadzić do sytuacji, w której na końcu trasy zostaje kilka odległych punktów, do których trzeba robić długie dojazdy.

Mimo to w miejskich warunkach przy kilkunastu punktach metoda najbliższego sąsiada zwykle daje trasy znacznie lepsze niż przypadkowa kolejność albo plan „z głowy”. Szczególnie opłaca się jako punkt startowy, a potem można trasę ręcznie poprawić, wykonując drobne zamiany punktów.

Proste poprawianie trasy: zamiana dwóch punktów (2-opt)

Kiedy mamy już wstępną trasę przez wszystkie punkty, często da się ją wyraźnie skrócić prostą techniką znaną jako 2-opt. Idea jest następująca:

Najczęściej zadawane pytania (FAQ)

Co to jest optymalizacja trasy w mieście w prostych słowach?

Optymalizacja trasy w mieście to świadome zaplanowanie kolejności przejazdów i wyboru ulic tak, aby osiągnąć konkretny cel: dojechać jak najszybciej, przejechać jak najmniej kilometrów albo zrealizować więcej zleceń w tym samym czasie. Zamiast jechać „na czuja”, zamieniamy miasto na prosty model liczbowy i porównujemy różne warianty.

W praktyce oznacza to np. wypisanie wszystkich punktów, między którymi musisz się przemieszczać, oszacowanie czasu przejazdu między nimi i wybranie kolejności oraz dróg, które dają najniższy łączny czas lub koszt.

Po co liczyć optymalną trasę, skoro mam nawigację w telefonie?

Nawigacja zwykle liczy najlepszą trasę między dwoma punktami „tu i teraz”. Nie planuje jednak całego dnia pracy: kolejności odwiedzin wielu adresów, podziału zleceń między kilka samochodów czy uwzględnienia okien czasowych dostaw. Do tego potrzebny jest choćby prosty model trasy.

Dodatkowo, przy stałych trasach (np. codzienny objazd tych samych osiedli) raz wykonane obliczenia pozwalają później oszczędzać czas i paliwo bez ciągłego eksperymentowania. Nawigacja staje się wtedy tylko narzędziem pomocniczym, a nie głównym planistą.

Jak zamienić mapę miasta na prosty model matematyczny?

Do opisu sieci ulic używa się grafu. Węzły grafu odpowiadają skrzyżowaniom, przystankom czy adresom dostaw, a krawędzie – odcinkom dróg pomiędzy nimi. Ulice jednokierunkowe modeluje się jako krawędzie jednokierunkowe, a dwukierunkowe – jako dwie krawędzie w przeciwnych kierunkach lub jedną nieskierowaną.

W praktyce wystarczy wybrać tylko najważniejsze miejsca (start, punkty dostaw, kluczowe skrzyżowania) i połączyć je odcinkami dróg, które faktycznie wchodzą w grę. Im mniej punktów i połączeń, tym łatwiej później policzyć optymalną trasę, nawet na kartce lub w arkuszu kalkulacyjnym.

Co oznaczają wagi krawędzi w modelu trasy i jak je dobrać?

Waga krawędzi to liczbowy „koszt” przejazdu daną ulicą. Może to być:

• czas przejazdu (w minutach),
• długość odcinka (w kilometrach),
• koszt paliwa lub ogólny koszt pieniężny,
• połączenie kilku czynników (np. minut przeliczonych na złote).

Najczęściej stosuje się czas, bo to on najlepiej oddaje realną „opłacalność” trasy.

Aby dobrać wagi, można oszacować średnią prędkość na różnych typach ulic (lokalne, główne arterie, objazdy), dodać „kary” za trudne skręty lub światła i na tej podstawie przypisać każdemu odcinkowi przybliżony czas przejazdu. Taki uproszczony model zwykle wystarcza, żeby porównać kilka wariantów trasy.

Jak w praktyce uprościć miasto do kilku kluczowych punktów?

Nie trzeba przenosić całego miasta do modelu. Wystarczy:

• połączyć krótkie, podobne odcinki ulic w dłuższe segmenty,
• pominąć małe uliczki, z których i tak nie będziesz korzystać,
• zostawić tylko skrzyżowania, na których faktycznie podejmujesz decyzję o kierunku jazdy.

Dzięki temu liczba węzłów i krawędzi jest mała, a obliczenia – wykonalne ręcznie lub w prostym arkuszu.

Przykładowo, mała firma może przygotować „graf dzielnicy” w Excelu: tabelę z listą punktów (węzłów) i tabelę połączeń z przypisanymi czasami przejazdu. Potem wystarczy aktualizować czasy, gdy zmienia się organizacja ruchu lub pojawiają się remonty.

Na czym polega algorytm Dijkstry do znajdowania najkrótszej trasy?

Algorytm Dijkstry to metoda szukania najtańszej drogi w grafie z dodatnimi wagami. W wersji praktycznej działa tak:

• startowyemu punktowi przypisujesz koszt 0, pozostałym – „nieskończoność”,
• krok po kroku „rozlewasz się” po sąsiednich węzłach, za każdym razem wybierając nieodwiedzony jeszcze węzeł o najmniejszym znanym koszcie,
• za każdym przejściem sprawdzasz, czy nowa droga do sąsiada nie jest tańsza – jeśli tak, aktualizujesz koszt i poprzednika.

Na końcu cofając się po zapisanych poprzednikach, odtwarzasz najkrótszą możliwą trasę.

Takie liczenie można z powodzeniem wykonać „na kartce” dla małej sieci 6–7 punktów lub zaimplementować w arkuszu kalkulacyjnym, bez znajomości dowodu poprawności algorytmu.

Dlaczego najkrótsza droga nie zawsze jest najszybsza lub najtańsza?

W mieście o czasie przejazdu decydują nie tylko kilometry, ale też:

• korki i średnia prędkość na danym typie ulicy,
• światła, przejścia dla pieszych i trudne skręty,
• buspasy, remonty, objazdy i inne ograniczenia ruchu.

Dlatego trasa nieco dłuższa „po obwodnicy” może być znacznie szybsza niż krótkie, ale zakorkowane uliczki w centrum.

W dobrze zbudowanym modelu kryterium optymalizacji trzeba jasno określić: minimalizujemy czas, długość, koszt paliwa czy może kombinację tych wielkości. Dopiero wtedy „najlepsza” trasa ma sens w odniesieniu do naszego celu (np. punktualność dostaw, a nie minimalny przebieg samochodu).

Co warto zapamiętać

• Optymalizacja trasy w mieście polega na świadomym wyborze kolejności przejazdu i ulic, aby skrócić czas podróży, zmniejszyć dystans, obniżyć koszty lub zrealizować więcej zleceń.
• Nawet proste modele i obliczenia pozwalają uzyskać lepsze trasy niż jazda „na czuja”, bo uwzględniają korki, światła, ograniczenia prędkości i zakazy skrętu.
• Optymalizacja tras jest użyteczna nie tylko w logistyce, ale także dla kurierów, dostawców jedzenia, serwisantów, handlowców i przy planowaniu własnych przejazdów po mieście.
• Miasto można zamodelować jako graf, w którym węzły odpowiadają skrzyżowaniom lub punktom dostaw, a krawędzie – odcinkom dróg (z uwzględnieniem kierunkowości ulic).
• Kluczową rolę odgrywają wagi krawędzi, czyli „koszty” przejazdu (czas, odległość, paliwo, łączny koszt), z których w praktyce najczęściej używa się czasu.
• Uproszczenie sieci ulic do kilku kluczowych punktów i dłuższych segmentów znacznie ułatwia obliczenia, a mimo utraty części szczegółów nadal daje realne oszczędności czasu i kilometrów.
• Nawet najprostszy problem najkrótszej drogi A–B można rozwiązać intuicyjnie, rysując sieć ulic i stosując proste reguły (omijanie trudnych skrętów, korków i sygnalizacji), co już stanowi formę optymalizacji.