Solving City Bus Scheduling Problems in Bangkok by Eligen-Algorithm
The modeling of city bus scheduling problems is considered to optimize the number of buses and their scheduling in the city. The vehicle scheduling problem (VSP) can be solved by some heuristic algorithms. The disadvantage of these algorithms is that the
- PDF / 226,489 Bytes
- 8 Pages / 439.324 x 666.21 pts Page_size
- 8 Downloads / 191 Views
2 3
Department of Mathematics, Chulalongkorn University, Thailand [email protected], [email protected] Institute of Computer Science, University of Heidelberg, Germany [email protected] Interdisciplinary Center for Scientific Computing (IWR), University of Heidelberg, Germany [email protected]
Abstract The modeling of city bus scheduling problems is considered to optimize the number of buses and their scheduling in the city. The vehicle scheduling problem (VSP) can be solved by some heuristic algorithms. The disadvantage of these algorithms is that the solution quality decreases as the number of depots increases. Therefore, in this paper, we develop the Eligen-algorithm, which uses the techniques of column elimination and column generation, for solving the multiple-depot vehicle scheduling problems (MDVSPs). The advantage of this algorithm is that the solution quality improves as the number of depots grows. Moreover, this algorithm is faster and gives better solutions than the nearest bus-stop heuristic algorithm (NB) and the joined nearest bus-stop heuristic algorithm (JNB) which we developed before. For example problem instance, we use the modeling of city bus scheduling problem in Bangkok, Thailand.
1 Introduction At present, metropolitan cities, defined as cities with populations of at least one million people are very crowded. A major problem, which menaces the economic situation and reduces health and sanitation of people in these big cities, is the traffic jam problem. One effect of this problem is that many people are unable to reach appointments on time. This is due to the lack of good transportation schedules to the destination and the lack of information concerning how to get there in the shortest time. Moreover, one more reason for the traffic jam problem is the increase in the number of private cars on the main streets. Some related governments try to convince people to use public bus transport instead of private cars in order to reduce the number of private
558
C. Surapholchai et al.
cars on the main streets. The optimization of the number of buses should help ease the traffic jam problem. Therefore, in this paper we consider the modeling of city bus scheduling problems. The aim of this research is to optimize the number of buses. Hence, we try to solve this problem to obtain the optimal number of buses used. Two problem cases modified from [8] are considered: the Single-Depot Vehicle Scheduling Problem (SDVSP) and the Multiple-Depot Vehicle Scheduling Problem (MDVSP). The city bus problems, which are real-world problems, are high dimensional integer programming problems and they cannot be solved in polynomial time (NP-hard problems) for the multiple depot case. Therfore, problem-specific algorithms are considered for the solutions. Bangkok, the capital city of Thailand, is one of metropolitan cities, which is very crowded, with a population of approximately ten million people. Thus, for the example problem instance, we use the mode
Data Loading...
