Open Access System for Information Sharing

Login Library

 

Thesis
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

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

Title
스쿨 버스 라우팅 문제의 특성과 알고리듬에 관한 연구
Authors
박준혁
Date Issued
2011
Publisher
포항공과대학교
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.
URI
http://postech.dcollection.net/jsp/common/DcLoOrgPer.jsp?sItemId=000000893788
http://oasis.postech.ac.kr/handle/2014.oak/938
Article Type
Thesis
Files in This Item:
There are no files associated with this item.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Views & Downloads

Browse