umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimisation of a transportation network by circuit enumeration
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2019 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesisAlternative title
Optimering av ett transportnätverk med uppräkning av cykler (Swedish)
Abstract [en]

The objective of this Master’s Thesis is to explore opportunities to increase the utilization of buses in a transportation network by identifying and analysing cities that could serve to connect, or “link”, bus packages. A bus package is a trip visiting two or more cities over the course of at least one, but usually three or more days. The transportation network is based on these bus packages. To maximize linking, the thesis investigates how many ways different bus packages can be joined together such that that the start city is also the end city (a “circuit”).

A bus packages can be said to have a direct link design but due to some of the cities high popularity, many act as either a start or end city in such a high frequency that they essentially operate in the same way as hubs in a hub and spoke layout. These “unofficial hubs” are the cities that the thesis strives to identify.

In their article “On Algorithms for Finding all Circuits of a Graph”, Mateti and Deo analysed a great number of algorithms for enumerating elementary circuits in a graph and when Donald Johnson presented his circuit finding algorithm in the same journal in 1975, it outperformed all of them in terms of time complexity. This still held true at the end of 2016 when Giscard, Kriege and Wilson presented their article “A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length” and Johnson’s algorithm was therefore chosen for this thesis work. The algorithm presented in this thesis is a modification of the original algorithm which puts a restriction on how many vertices are allowed in a circuit.

Shorter circuits are easier to work with in practice. However, by also allowing the algorithm to find longer circuits, solutions that have the potential to have a greater impact on utilization could be found. When exploring which cities could act as suitable hubs, it is therefore necessary to take different circuit lengths into account.

The result show that Johnson’s circuit finding algorithm, combined with occurrence-based analysis can be used to find suitable connection points. Out of the cities, six show great potential and are recommended for further evaluation.

Place, publisher, year, edition, pages
2019.
National Category
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-164763OAI: oai:DiVA.org:umu-164763DiVA, id: diva2:1366852
External cooperation
EF
Educational program
Master of Science in Engineering and Management
Supervisors
Examiners
Available from: 2019-10-31 Created: 2019-10-31 Last updated: 2019-10-31Bibliographically approved

Open Access in DiVA

No full text in DiVA

By organisation
Department of Mathematics and Mathematical Statistics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf