스쿨 버스 라우팅 문제의 특성과 알고리듬에 관한 연구

Abstract

This dissertation addresses the school bus routing problem (SBRP) which is an important class of vehicle routing problems. SBRP seeks to plan an efficient schedule for a fleet of vehicles where each vehicle transports students between their homes and schools. In SBRP, various constraints such as the maximum capacity of a bus, the maximum riding time of a student in a bus, and the time window of a school are considered. This class of problem consists of different sub-problems involving bus stop selection, bus trip generation, school bell time adjustment, and bus scheduling. This dissertation consists of three sub researches as follows.First, we provide a comprehensive review of the school bus routing problem. The various assumptions, constraints, and solution methods used in the literature on SBRP are summarized. A list of issues requiring further research is also presented. Second, two mixed integer programming (MIP) formulations for SBRP are provided. The first model is for mixed load SBRP and the second is for single load SBRP. A lower bound is investigated for mixed load SBRP. Third, heuristic based algorithms considering various real world issues such as routing special-education students, morning/afternoon routing problem and allowance of mixed loading are developed. A constructive heuristic, mainly consists of a sweep-based algorithm and the Hungarian algorithm, is introduced to provide solutions for bus trip generation and bus scheduling problems. A post improvement algorithm based on simple relocation operation is developed to allow mixed load, in which students to different schools can get on the same bus at the same time.The proposed algorithms are tested on some benchmark instances and real world instances. The algorithms could generate efficient solutions within a reasonable time, and outperform the existing algorithm on the benchmark problem instances. It also has been successfully applied to real world instances and shows better results compared to the current practice. And three strategies for afternoon problem are compared. In addition, some issues required further research efforts are discussed.