Symmetric generalized optimum requirement graphs for grids

Abstract

As the demand for efficient public transport is constantly growing, new and more efficient planning methods are also needed. Whilst the underlying infrastructure of an area and the budget of the operator affect the possible lines to be operated, public transport should also be an appealing option for passengers as a means of transport. Thus, researching methods that consider all of these aspects is needed. Passenger assignment is a necessary step in traditional sequential public transport planning before a line plan can be created. As some cities have a grid plan, researching possible methods of simplifying the passenger assignment process on grid plans is necessary.

This thesis aims to develop the formulation by Heinrich et al. into a more compact version that also takes into account the wanted symmetry of the solution. Similarly to the original formulation, the new formulation can be used for passenger assignment. The developed formulation is then experimentally evaluated on a 3x3 grid graph with different demand data and a horizontal axis of symmetry.

The developed formulation allows us to find horizontally symmetric passenger assignments on grid graphs. Requiring symmetry allows us to decrease the amount variables and constraints, thus also making the formulation easier to solve in practice. The formulation shows the most significant difference compared to the original formulation developed by Heinrich et al. when experimental evaluations are done with extremely asymmetrical demand. The results show that the demand has a strong effect on the solutions obtained by both formulations. To confirm the results, the symmetric generalized optimum requirement graph formulation should be tested for larger grid graphs. In further research, the formulation should be extended to different axes of symmetry.

Uusien ja tehokkaampien julkisen liikenteen suunnitelumenetelmien kehittäminen on tarpeen, koska kysyntä tehokkaalle julkiselle liikenteelle kasvaa jatkuvasti. Vaikka alueiden infrastruktuuri ja julkisen liikenteen operoijien budjetti rajoittavat julkisen liikenteen kulkureittejä, täytyy julkisen liikenteen silti olla myös matkustajan kannalta mieluisa vaihtoehto liikkumiselle. Kaikki nämä näkökohdat huomioon ottavien suunnittelumenetelmien kehittäminen on siis tarpeellista. Ennen varsinaista julkisen liikenteen linjasuunnittelua, täytyy kysyntä jakaa osoittamalla matkustajat mahdollisille reiteille.

Tämän työn tavoitteena on kehittää Heinrichin ym. optimointimallista yksinkertaisempi versio, joka ottaa ratkaisuissa huomioon myös vaatimuksen symmetriasta. Kuten alkuperäistä optimointimallia, uutta, symmetristä mallia voidaan myös käyttää matkustajien osoittamiseen julkisen liikenteen verkon reiteille. Kehitettyä symmetristä verkkojen optimointimallia testataan 3x3 neliöverkolla eri kysynnällä, vaakasuoralla symmetria-akselilla.

Kehitetty malli mahdollistaa matkustajien osoittamisen kevennetyssä symmetrisessä julkisen liikenteen verkon reiteille. Vaatimus symmetriasta mahdollistaa myös muuttujien ja rajoitteiden lukumäärän vähentämisen, jolloin ratkaisun löytäminen optimointimallilla on käytännössä helpompaa. Suurin ero alkuperäisen ja tässä työssä kehitetyn mallin välillä nähdään kokeellisissa arvioinneissa, kun käytetty matkustajien kysyntä on erittäin epäsymmetristä. Tuloksista voidaan huomata, että testaamisessa käytetty kysyntä vaikuttaa merkittävästi lopullisen verkon rakenteeseen. Tulosten varmentamiseksi, kehitettyä optimointimallia tulisi testata suuremmilla neliöverkoilla. Optimointimallin toimintaa eri symmetria-akseleilla tulee tarkastella tulevassa tutkimuksessa.