Using dijkstra algorithm in calculating alternative shortest paths for public transportation with transfers and walking

Abstract

In this study, the possibility of using the Dijkstra algorithm in calculate shortest paths and using GIS to connect transport lines for increasing efficiency in the accessibility to shortest paths was studied. The results are presented as spatial maps. Basically, the research question this thesis addresses is: “Can Iraqi authorities use graph theory and shortest path algorithm to build a system to develop a public transit system including exchanging lines and walking, based on the experiences of transport systems in Turkey?"As a research methodology, Ankara’s mass transportation has been examined as considerable similarities are found between Ankara and Baghdad in terms of population in number and in density. Hence, an introduction is given on both cities. Additionally, information technologies to investigate and promote public transport systems in the literature are visited. As gathering spatial data has required considerable time and resources, sample datasets of Ankara’s mass transport system are used to run demonstrative applications to highlight potential problems in the technical side. The surveyed literature also includes graph theory, transportation network, shortest path problems and GIS usage in the public transportation. The used MapInfo Professional and MapBasic software tools are available on the market. Specific application programs are developed in MapBasic to ease analyses and implementation in MapInfo. Additionally, programs are coded in C++ to apply Dijkstra algorithm to feed data to GIS software. Limitations are also reported to open further research avenues including other algorithms for path optimization. The results show that Dijkstra algorithm can be successfully applied to reform and design mass transportation systems. An unfortunate finding underlined that it is too early to jump to application design as the primary problem is to collect reliable and up to date spatial data of Baghdad.

Bu çalışmada, Dijkstra algoritması kullanılarak kısa yol hesaplanmasının ve ulaşım hatlarının bağlanmasında CBS kullanımının etkinliği arttırması işlenmistir. Sonuçlar mekansal veri haritaları şeklinde sunulmuştur. Temel olarak, tezin hedef aldığı araştırma sorusu: "Irak, çizge kuramı ve kısa yol algoritması ve Türkiye'deki yürüme dahil aktarmalı hat değiştirme deneyimlerini kullanarak toplu taşımacılık sistemi kurabilir mi?" Bağdat'la Ankara arasında nüfus yoğunluğu ve çokluğu bakımından önemli benzerlikler görüldüğünden, araştırma yöntemi olarak, Ankara'nın toplu taşıması incelenmiştir. Bu sebebten, her iki şehir hakkında tanıtıcı bilgi verilmiştir. Ek olarak, vii literatürde toplu taşım sistemlerini incelemek ve iyileştirmek için kullanılan bilgi teknolojileri taranmıştır. Bağdat'ın mekansal verisini almak önemli miktarda zaman ve kaynak gerektirdiğinden, Ankara toplu taşıma sistemin örnek verisi toplanmış ve bu veriler, olası teknik sorunları açığa çıkarmak için örnek uygulamalarda kullanılmıştır. Taranan literatür çizge kuramı, taşıma ağları, kısa yol ve toplu taşımacılıkta CBS kullanımını da içermektedir. Kullanılan MapInfo Professional ve MapBasic programları piyasada olan uygulamalardır. MapInfo'da uygulamaları kolaylaştırabilmek için, MapBasic'de konuya yönelik uygulamalar geliştirilmiştir. Ek olarak, Dijkstra algoritmasını uygulamak ve CBS yazılımına girdi oluşturmak için C++ programlama dilinde uygulama yazılmıştır. Tezdeki sınırlamalar, örneğin başka algoritmalar, olası devam projeleri için rapor edilmiştir. Sonuçlar gösteriyor ki Dijkstra algoritması, toplu taşıma sistemlerinin iyileştirilmesinde ve tasarımında kullanılabilir. Bir talihsiz bulgu da gösteriyor ki doğrudan uygulama tasarımına geçmek için çok erken çünkü birincil sorun Bağdat'ın doğru ve güncel mekansal verisinin toplanmasıdır.