Algorytmy optymalizacyjne ułatwiające wyznaczanie tras autobusów szkolnych

emapa

Niewydajne zarządzanie flotą pojazdów to strata czasu i pieniędzy. Czy lepsze wyznaczanie tras autobusów szkolnych może się przyczynić do oszczędności, które szkoły wyraźnie odczują?

Zwiększenie wydajności kierowania pojazdami może znacząco wpłynąć na rentowność przedsiębiorstw. Jednak nie zapominajmy o instytucjach publicznych, które przecież tak samo korzystają z usług transportowych.

W przeciwieństwie do prywatnych firm, sektor publiczny, do którego należą min: autobusy szkolne, wciąż traktowany jest z pominięciem nowoczesnych metod usprawniających trasowanie. A szkoda, bo mogłoby to pozwolić na wygenerowanie oszczędności na transporcie, które szkoły przeznaczyłyby na realizowanie innych celów.

Szkoły często dotkliwie odczuwają wszelkie programy publiczne prowadzące do szukania oszczędności. Słabo opłacani nauczyciele i pedagodzy muszą mierzyć się z cięciami budżetowymi, a co za tym idzie, z problemami finansowymi. Zwykle podczas szukania pieniędzy instytucje publiczne w pierwszej kolejności przyglądają się kosztom związanym z pracownikami. Warto aby zaczęły analizować także sposób zarządzania flotą, w tym autobusów szkolnych. Bardzo często jest ona nieprofesjonalna i odbywa się na zasadzie przypadkowego planowania. Nadkładanie trasy, długie postoje, nieefektywne wykorzystanie czasu kierowców- to częste problemy, których szkoły nie próbują rozwiązać. Głównie dlatego, że nie znają możliwości, które mogłyby w tym pomóc.

Jak algorytmy optymalizacyjne mogą pomóc szkołom?

Dzięki poprawie efektywności procesów optymalizujących uwzględniających planowanie transportu, możliwa jest pomoc organizacjom publicznym.

Codzienne trasy komunikacyjne pokonywane przez autobusy szkolne są ustalane z uwzględnieniem trzech różnych celów: liczby pojazdów, całkowitego czasu trasy i średniego czasu podróży pasażera. Problem z wyznaczaniem tras dla autobusów szkolnych może być zaliczany jako jeden z zastosowań VRP. Celem towarzyszącym definiowaniu tras transportowych dla uczniów jest optymalne zaplanowanie trasy od domu ucznia do szkoły.

Planowanie tras autobusów szkolnych jest zwykle podzielone na trasowanie i planowanie. Rozdzielenie tych dwóch etapów może prowadzić do rozwiązań o wyższych ogólnych kosztach niż jakbyśmy potraktowali je jako całość. Zaniedbanie, bądź zignorowanie problemu dotyczącego ograniczonej liczby miejsc w autobusie, może prowadzić do wzrostu kosztów. Przede wszystkim, ze względu na potrzebę wykorzystania większej liczby autobusów. Widzimy zatem, że trasowanie pojazdów powinno uwzględniać planowanie dotyczące np. maksymalnej liczby pasażerów. W innym wypadku rozwiązanie jednego problemu może powodować powstanie kolejnego.

Główne problemy w ustalaniu tras

Do ustalania tras dla autobusów szkolnych można podejść dwojako. Pierwsze podejście obejmuje scenariusz dla jednej szkoły, drugie natomiast dotyczy już kilku scenariuszy. Na podstawie dwóch powyższych perspektyw wyłania się problem uwzględniania różnych ograniczeń takich jak lokalizacja szkoły i domu ucznia.

W pierwszym z problemów planowanie transportu autobusowego dla uczniów uczęszczających do różnych szkół jest niemożliwe. W związku z tym uczniowie z różnych szkół nie mogą dzielić tego samego autobusu.

Z drugiej strony podejście zorientowane na dom bierze pod uwagę możliwość dzielenia jednego środku transportu dla wielu uczniów uczących się w różnych szkołach.

Zaawansowana optymalizacja tras przy użyciu algorytmów matematycznych przybliża szkoły do osiągania wielu korzyści, które mogą być rozumiane również jako cele. Dodatkowo umożliwia zarządzanie fundamentalnymi ograniczeniami utrudniającymi planowanie tras. Należą do nich, m.in: ograniczona pojemność pojazdu oraz okna czasowe, które muszą być przestrzegane.

Jakie korzyści mogą przynieść algorytmy vrp?

Za korzyści, które są efektem korzystania z algorytmów VRP uznaje się zredukowanie liczby pojazdów, minimalizację odległości trasy, ograniczenie czasu podróży uczniów a także wykorzystanie efektywności autobusów.

Jedną z potrzeb związanych z problematyką transportu szkolnego jest alokacja uczniów do autobusów szkolnych oraz określenie sekwencji odcinków trasy, które są odwiedzane przez każdy pojazd. W przypadku uwzględniania kilku rodzajów wcześniej wspomnianych ograniczeń, potrzebne jest zastosowanie modelu uogólniającego. Model tego typu uwzględnia ograniczenia dotyczące czasu podróży, zdolności przewozowe pojazdów, ilość punktów wsiadania i wysiadania uczniów. Zakłada on także istnienie okien czasowych związanych z zaplanowanymi przyjazdami i odjazdami z przystanków.

Algorytmy optymalizacyjne umożliwiają osiągnięcie założonych celów dotyczących poprawy jakości świadczonych usług przewozowych i osiągnięcia oszczędności na transporcie.

Omawiany model wykorzystuje algorytm heurystyczny. Dzięki wykorzystaniu VRP w efekcie końcowym powstaje zbiór „optymalnych” tras, które uwzględniają założone cele. Umożliwia to planistom dokonanie wyboru możliwie najbardziej optymalnej trasy pasującej do preferencji.

Sweep Algorithm

Jednym z algorytmów używanych przy rozwiązaniu Vehicle Routing Problem w transporcie publicznym, w tym możliwym przy optymalizowaniu tras autobusów szkolnych, jest algorytm „Sweep Algorithm”. Algorytm ten stosuje się jako metodę wyszukiwania najkrótszej trasy podczas kierowania pojazdami.

W celu oceny i identyfikacji rezultatów osiągniętych przez algorytm zostaje prezentowany aktualny profil transportu publicznego odzwierciedlający obecną sytuacje na drogach. Generowane trasy są wykonywane wielokrotnie przy użyciu różnych ograniczeń, w celu uzyskania optymalnego rozwiązania. Trasę wybiera się na podstawie najkrótszej odległości i ograniczonej pojemności pojazdu. Każde znane ograniczenie umieszczone w algorytmie wpływa na wybór tras ze względu na dokonanie selekcji tras. Odbywa się to na podstawie uzyskanej różnorodnej kombinacji.

Koszty operacyjne i prognozowane maksymalne przychody związane z wyznaczoną trasą są przyjęte jako czynnik decydujący o wyborze najlepszej i zoptymalizowanej kombinacji tras. W tym celu służy również porównywanie wyników aby znaleźć najlepsze rozwiązanie. Dotychczasowe wyniki osiągane dzięki użyciu „Sweep Algorithm” potwierdzają skuteczność i zdolność do rozwiązywania problemu kierowania pojazdów transportu publicznego. Uwzględniają one również zmieniające się ograniczenia.

Przykład z rynku

Studium przypadku opisuje sytuację realnie występująca w Cancún (Meksyk).

Grupa 7500 uczniów i 500 nauczycieli z 10 rozmieszczonych szkół w Cancún musi mieć zapewniony transport publiczny z przystanku znajdującego się w okolicach ich miejsca zamieszkania, do swoich szkół. Problem polega na znalezieniu serii kombinacji tras autobusów szkolnych, które sprawią, że przedsiębiorstwo autobusowe będzie świadczyło usługę w sposób sprawiedliwy i wygodny dla wszystkich uczniów.

Dodatkowe ograniczenia dotyczą odległości, którą uczniowie mogą pieszo pokonywać ze swoich domów do i z przystanków.

Celem jest znalezienie optymalnych tras autobusów szkolnych poprzez zmniejszenie:

  • liczby autobusów
  • liczby różnych tras
  • łącznej liczby kilometrów z wszystkich tras
  • czasu trwania najdłuższej trasy
  • odległość, jaką uczniowie muszą przejść ze swoich domów do i z ich przystanków.

Optymalne rozwiązanie powinno zawierać:

  • Liczbę autobusów
    Każda wybrana magistrala może codziennie wykonywać różne trasy. Co więcej, wszystkie autobusy mają tą sama pojemność.
  • Najlepsze możliwe rozmieszczenie uczniów na przystankach autobusowych
    Liczba uczniów na każdym przystanku nie może być większa niż pojemność jednego autobusu. Jednak wszyscy studenci muszą być odbierani przez wszystkie wybrane autobusy.
  • Najlepsze przypisanie przystanków do autobusów
    Liczbę przystanków autobusowych należy obliczyć na podstawie zestawu dostępnych autobusów. Każdy wybrany przystanek może być odwiedzany przez więcej niż jedną wybraną magistralę. Liczba uczniów w każdym wybranym autobusie nie może przekraczać pojemności autobusu.
  • Trasy autobusowe do szkół
    Każda trasa jest zdefiniowana jako sekwencja przystanków z liczbą uczniów (> 0) do odebrania. Każda trasa zaczyna się z pierwszego wybranego przystanku na tej trasie i dociera do wybranej przez ucznia szkoły. Czas podróży każdego wybranego autobusu nie może przekroczyć dozwolonego czasu.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *