Generalized public transportation scheduling using max-plus algebra

In this paper, we discuss the scheduling of a wide class of transportation systems. In particular, we derive an algorithm to generate a regular schedule by using max-plus algebra. Inputs of this algorithm are a graph representing the road network of public transportation systems and the number of public vehicles in each route. The graph has to be strongly connected, which means there is a path from any vertex to every vertex. Let us remark that the algorithm is general in the sense that we can allocate any number of vehicles in each route. The algorithm itself consists of two main steps. In the first step, we use a novel procedure to construct the model. Then in the second step, we compute a regular schedule by using the power algorithm. We describe our proposed framework for an example.