A Label Correcting Algorithm with Storing Partial Solutions to Solving the Bus Routing Problem

Article type: Research Article

Authors: Widuch, Jacek

Affiliations: Silesian University of Technology, Institute of Informatics, ul. Akademicka 16, 44-100 Gliwice, Poland, e-mail: [email protected]

Abstract: In the paper we describe the bus routing problem (BRP), which the goal is to find a route from the start stop to the final stop minimizing the time and the cost of travel and the length of the route. Additionally the time of starting travel at the start stop is given. Analysis of the problem is presented and in particular we point at properties of routes. The BRP is an example of multicriteria optimization problem (MOP), which the solution is the set of non-dominated solutions. This paper proposes a label correcting algorithm with storing partial solutions for solving the BRP. 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. Additionally the results are compared with results for the BRP where the goal is to minimize only the time and the cost of travel and the length of the route is not taken into consideration.

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

Journal: Informatica, vol. 24, no. 3, pp. 461-484, 2013