Robust passenger assignment for line planning in public transport

Abstract

Faced with economic inequality, sprawling cities, and the ever-more worrying climate change, problems are many and the search for new solutions is constant. Not all solutions, however, must be entirely new. Public transportation has long been known as a valuable method of providing low-cost transport in dense urban areas with minimal emissions.

Public transport, however, needs extensive planning, which, due to the complexity of the systems involved, is far from a trivial task. A key step in planning is necessarily processing demand data, which can in largest public transport systems consist of millions of daily travelers. It is near impossible to model the behaviour of this many customers, and thus a level of abstraction is often necessary. Previous work has focused on planning with fixed demand data, which is convenient, but does not necessarily represent the real world. This thesis builds on previous work by providing methods for planning with random or varying demand.

We propose an analogue for the fixed demand planning step of passenger assignment -- a spanning graph paired with a passenger assignment strategy -- as well as an algorithm for planning with varying demand. The algorithm we propose is based on the widely studied metaheuristic of genetic algorithms inspired by natural selection.

We also provide some experimental results using our proposed algorithm and compare the results gained using varying data to ones with mean data. These results are promising, as in certain cases it is possible to account for varying demand producing public transport systems, which are more robust against varying demand than those planned with fixed demand.

Taloudellisen epätasa-arvon, laajenevien kaupunkien ja yhä huolestuttavamman ilmastonmuutoksen pyörteissä uusia ratkaisuja näihin yhteiskunnallisen skaalan ongelmiin etsitään jatkuvasti. Kaikkien ratkaisujen ei kuitenkaan tarvitse olla uusia. Julkinen liikenne on laajalti tunnustettu tehokkaana keinona tuottaa edullinen, saavutettava ja vähäpäästöinen liikkumisen muoto kaupunkialueilla.

Julkisen liikenteen vaikeuksiin lukeutuu kuitenkin laaja suunnittelun tarve, mikä liikennejärjestelmien monimutkaisuuden vuoksi ei ole suinkaan helppo tehtävä. Eräs suunnittelun välttämättömistä vaiheista on kysyntädatan analysointi, joka voi suurimmissa julkisissa liikenneverkoissa koostua miljoonista päivittäisistä asiakkaista. Näin monen tekijän käytöksen mallintaminen on lähes mahdotonta, joten jonkinlainen yksinkertaistaminen on välttämätöntä.

Aiemmassa tutkimuksessa julkisen liikenteen saralla on oletettu, että kysyntää voi mallintaa vakiona, mikä on kätevää, muttei välttämättä kuvasta todellisuutta. Laajentaaksemme aiempaa tutkimusta tässä tutkielmassa esitellään uusia tapoja mallintaa ja käsitellä vaihtelevaa kysyntää.

Esittelemme vakiokysynnän suunnitteluvaiheelle, matkustajan reititykselle, vaihtelevan kysynnän vaihtoehdon: matkustajan reititysstrategian yhdistettynä virittävään verkkoon. Esittelemme suunnittelemisen tueksi geneettisen algoritmin, joka löytää optimaalisia virittäviä verkkoja.

Lopuksi käsittelemme kokeellisia tuloksia esittelemästämme algoritmista suoritusajan osalla sekä vertailemme vaihtelevan kysynnän tuloksia vakiokysynnän tuloksiin. Tulokset ovat lupaavia, sillä osoitamme, että keinomme ottaa vaihteleva kysyntä huomioon tuottaa julkisen liikenteen järjestelmiä, jotka ovat tehokkaampia tai yhtä hyviä kaikenlaisen