A Label Correcting Algorithm for the Bus Routing Problem

Article type: Research Article

Authors: Widuch, Jacek

Affiliations: Institute of Informatics, Silesian University of Technology, ul. Akademicka 16, 44–100 Gliwice, Poland, jacek.widuch@polsl.pl

Note: [] Address for correspondence: Institute of Informatics, Silesian University of Technology, ul. Akademicka 16, 44–100 Gliwice, Poland

Abstract: This paper proposes a label correcting algorithm for solving the bus routing problem (BRP). The goal of the BRP is finding a route from the start stop to the final stop minimizing the time and the cost of travel. Additionally the time of starting travel at the start stop is given. The problem belongs to the group of multicriteria optimization problems (MOP), whose the solution is a set of non-dominated solutions. The algorithm makes possible to find all routes which belong to the set of non-dominated solutions. Apart from that the results of experimental tests are presented.

Keywords: bus routing problem, multicriteria optimization, relation of dominance, set of non-dominated solutions, bicriterion shortest path problem, directed weighted graph, variable weights, shortest path, label correcting algorithm

DOI: 10.3233/FI-2012-716

Journal: Fundamenta Informaticae, vol. 118, no. 3, pp. 305-326, 2012