스쿨버스 경로문제는 학생들을 다수의 승차지점으로부터 학생들의 해당 학교까지 안전하고 효율적으로 수송할 수 있는 방법을 찾는 문제이다. 일반적인 스쿨버스 경로문제의 제약 조건으로는 차량의 용량, 학생의 최대 수송 시간, 학교의 도착 시간 제약 등이 있다. 본 연구에서는 기존의 혼승을 허용한 스쿨버스 경로 문제를 확장한 모델을 구축하고, 국내의 대학교 스쿨버스 운영 형태를 고려하여 학생들이 승차지점에 유동적으로 유입이 되는 상황을 고려한다. 본 연구에서 제시하는 모델에 대한 실험을 하기 위하여, 첫 단계로 Sweep Algorithm을 이용하여 초기 경로를 구성한다. 두 번째 단계에서는 전역탐색 능력이 있는 메타 휴리스틱 방법인 Genetic Algorithm을 이용하여 최선해을 도출 한다. 또한, 기존의 스쿨버스 경로문제에 적용되었던 현실 가능성 있는 제약들을 완화하여 다양한 시나리오를 구성하고 시나리오별 비교우위 평가를 한다.
스쿨버스 경로문제는 학생들을 다수의 승차지점으로부터 학생들의 해당 학교까지 안전하고 효율적으로 수송할 수 있는 방법을 찾는 문제이다. 일반적인 스쿨버스 경로문제의 제약 조건으로는 차량의 용량, 학생의 최대 수송 시간, 학교의 도착 시간 제약 등이 있다. 본 연구에서는 기존의 혼승을 허용한 스쿨버스 경로 문제를 확장한 모델을 구축하고, 국내의 대학교 스쿨버스 운영 형태를 고려하여 학생들이 승차지점에 유동적으로 유입이 되는 상황을 고려한다. 본 연구에서 제시하는 모델에 대한 실험을 하기 위하여, 첫 단계로 Sweep Algorithm을 이용하여 초기 경로를 구성한다. 두 번째 단계에서는 전역탐색 능력이 있는 메타 휴리스틱 방법인 Genetic Algorithm을 이용하여 최선해을 도출 한다. 또한, 기존의 스쿨버스 경로문제에 적용되었던 현실 가능성 있는 제약들을 완화하여 다양한 시나리오를 구성하고 시나리오별 비교우위 평가를 한다.
The School Bus Routing Problem(SBRP) seeks to plan an efficient schedule of a fleet of school buses that must pick up student from various bus stops and deliver them by satisfying various constraints; maximum capacity of the bus, maximum riding time of students, arrival time between a school's time ...
The School Bus Routing Problem(SBRP) seeks to plan an efficient schedule of a fleet of school buses that must pick up student from various bus stops and deliver them by satisfying various constraints; maximum capacity of the bus, maximum riding time of students, arrival time between a school's time window. By extending the existing SBRP, we consider a case study of SBRP with allowance of mixed-loading and dynamic arrivals reflecting the school bus operation of university in Korea. Our solution procedure is based on constructing the initial solution using sweep algorithm and then improving solution within the framework of the evolutionary approach known as efficient meta-heuristics. By comparing the various scenarios through the constraints relaxation for reflecting the real operational strategies, we assess the merit of our proposed procedure.
The School Bus Routing Problem(SBRP) seeks to plan an efficient schedule of a fleet of school buses that must pick up student from various bus stops and deliver them by satisfying various constraints; maximum capacity of the bus, maximum riding time of students, arrival time between a school's time window. By extending the existing SBRP, we consider a case study of SBRP with allowance of mixed-loading and dynamic arrivals reflecting the school bus operation of university in Korea. Our solution procedure is based on constructing the initial solution using sweep algorithm and then improving solution within the framework of the evolutionary approach known as efficient meta-heuristics. By comparing the various scenarios through the constraints relaxation for reflecting the real operational strategies, we assess the merit of our proposed procedure.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
대중교통 수단이 승차지점 도착 시간 간격을 고려할 경우, 시간대별 승차지점에 어떤 차량이 방문하는지가 중요한 고려요소가 될 수 있으며, 또한 스쿨버스의 수는 비용과 높은 연관성을 갖고 있으므로 차량의 수 또한 중요 요인이 될 수 있다. 따라서 본 연구에서는 근접한 학교간의 통합적인 스쿨버스 운영 전략과 혼승을 허용하는 스쿨 버스 경로 문제를 대상으로 하고 있으며, 총 탑승학생 수와 버스의 총 운행시간을 목적으로 시간대별 상이한 수로 승차지점에 도착하는 학생들을 최대로 수송하기 위하여 특정 시간대에 어떠한 정류소를 방문하여야 하는지에 대한 스쿨버스 경로 계획 문제를 다루고자 한다. 문제 해법으로 2단계 해 개선 과정을 고려하였으며, Sweep Algorithm 을 이용하여 초기 해를 생성하고, 해의 개선을 위해 변형된 진화 알고리즘을 제안하여 혼승과 시간대별 변화하는 학생 수를 고려한 스쿨버스 경로 계획 문제를 풀었으며, 부분 탑승 허용, 승차지점에서 차량의 여러 시간대 대기 가능, 상이한 차량의 한 승차지점의 중복 방문 가능 등과 같은 현실적인 스쿨버스 운영 전략을 기초로 다양한 시나리오를 수립하여 각 시나리오들의 효과성을 검증하고자 한다.
이는 하나의 정류소에 대한 하나의 스쿨버스의 중복 방문을 제어하기 위함이다. 또한, 일반적으로 이러한 점 교차는 돌연변이 연산자에서 많이 사용이 되나, 본 연구에서는 경로 탐색의 다양성을 유지하고자 낮은 확률의 돌연변이 연산 보다 교차 연산을 하여 한 부모로부터 자손이 생성되는 교차 방법을 제시하였다. 그 예는 Fig.
본 연구는 기존의 Mixed-Load SBRP의 기본사항에서 승차지점에서의 학생들의 수가 시간의 흐름에 따라 변화 하는 모델을 추가하여 탑승 학생 수를 최대화 하면서, 총 운행시간을 최소화할 수 있는 해를 구하고자 한다. Fig.
본 연구는 기존의 SBRP 모델을 확장하여, 넓은 지역에 걸쳐 거주지가 분산되어 있으며, 대중교통(버스, 지하철 등)을 이용하여 목적지 학교로부터 인접한 지역까지 이동한 후 해당 학교의 스쿨버스를 이용하는 대학교 학생의 스쿨버스 문제를 다루고자 한다. 이는 기존의 SBRP에서 다루고 있는 형태인 승차지점에서 탑승하는 학생 수가 일정하다는 가정을 탈피하여, 대중교통(버스, 지하철 등) 을 이용하여 스쿨버스 승차지점으로 학생들이 도착하는 상황을 반영하여 일정한 시간간격으로 승차시점에 대기 하는 학생 수가 동적으로 변화하는 모형을 대상으로 한다.
본 연구에서는 실행 불가능한 해의 발생을 줄이기 위해, 돌연변이 연산을 수행함에 있어, 상이한 시간대를 가지는 동일한 유전자를 대상으로 점 돌연변이를 수행하였다. Fig.
본 연구에서는 현실적인 대안을 고려한 다양한 시나리오 구성 및 실험 결과를 비교 하고자 한다. Table 4는 본 연구의 실험을 위한 6가지 시나리오에 대한 설명을 나타낸다.
가설 설정
첫째, 각 대중교통 정류소에서의 대중교통 도착 간격은 동일하다.
제안 방법
Sweep Algorithm을 통해 생성된 초기 경로의 개선을 위해 본 연구에서는 GA를 적용함에 있어, 2단계 교차 연산 과정을 고려하였다. 1단계 교차 연산은 스쿨버스의 방문 시간대를 교차하여 해를 탐색하는 과정으로 동일차량이 같은 정류소를 상이한 시간대에 방문하여 보다 많은 학생들을 탑승할 수 있도록 유도하였으며, 2단계 교차는 다양한 경로 탐색을 위해 해의 개선을 유도하였다. 본 연구에 적용된 유전자 알고리즘의 세부 절차는 Fig.
Sweep Algorithm을 통해 생성된 초기 경로의 개선을 위해 본 연구에서는 GA를 적용함에 있어, 2단계 교차 연산 과정을 고려하였다. 1단계 교차 연산은 스쿨버스의 방문 시간대를 교차하여 해를 탐색하는 과정으로 동일차량이 같은 정류소를 상이한 시간대에 방문하여 보다 많은 학생들을 탑승할 수 있도록 유도하였으며, 2단계 교차는 다양한 경로 탐색을 위해 해의 개선을 유도하였다.
본 연구는 기존의 혼승을 허용한 스쿨버스 경로 문제 (Mixed-Load SBRP)의 확장한 모델에 대한 검증으로 기존의 혼승을 허용한 스쿨버스 경로 문제의 승차지점에 한번의 방문으로 모든 학생을 수송할 수 있는 모델을 시간의 흐름에 따라 동적으로 학생 수가 변화하는 모델을 구축하고 현실에서 실현 가능한 기존의 스쿨버스 경로문제에 적용된 제약사항들을 완화하여 다양한 시나리오를 구성하였다. 또한, 사례연구를 통하여 제약완화를 통한 시나리오별 비교우위를 평가하였다. 평가결과 기존의 스쿨버스 경로문제에서는 학생들의 승차지점에서의 대기 학생 수가 스쿨버스의 잔여용량을 초과할 경우 방문 하지 못하였던 제약을 완화하여 스쿨버스의 잔여용량만큼 학생을 수송하는 제약과 차량의 방문 허용 제약을 완화한 중복 방문 허용을 통하여 기본적인 SBRPMLDA 모델보다 약 26% 이상의 학생을 수송하는 결과를 도출 하였다.
Table 5는 본 연구에서 제안한 SBRPMLDA 모형에 대해 차량 중복 방문을 허용할 경우의 효과를 검증하기 위한 실험 결과를 보여주고 있다. 먼저, GA를 통한 해 개선 효과를 검증하기 위해 Sweep Algorithm을 통해 도출된 초기 해와 GA를 통해 해를 개선한 결과를 비교하였다. 총 탑승 학생 수에서 358명에서 391명으로 약 9.
따라서 본 연구에서는 근접한 학교간의 통합적인 스쿨버스 운영 전략과 혼승을 허용하는 스쿨 버스 경로 문제를 대상으로 하고 있으며, 총 탑승학생 수와 버스의 총 운행시간을 목적으로 시간대별 상이한 수로 승차지점에 도착하는 학생들을 최대로 수송하기 위하여 특정 시간대에 어떠한 정류소를 방문하여야 하는지에 대한 스쿨버스 경로 계획 문제를 다루고자 한다. 문제 해법으로 2단계 해 개선 과정을 고려하였으며, Sweep Algorithm 을 이용하여 초기 해를 생성하고, 해의 개선을 위해 변형된 진화 알고리즘을 제안하여 혼승과 시간대별 변화하는 학생 수를 고려한 스쿨버스 경로 계획 문제를 풀었으며, 부분 탑승 허용, 승차지점에서 차량의 여러 시간대 대기 가능, 상이한 차량의 한 승차지점의 중복 방문 가능 등과 같은 현실적인 스쿨버스 운영 전략을 기초로 다양한 시나리오를 수립하여 각 시나리오들의 효과성을 검증하고자 한다.
본 연구는 기존의 혼승을 허용한 스쿨버스 경로 문제 (Mixed-Load SBRP)의 확장한 모델에 대한 검증으로 기존의 혼승을 허용한 스쿨버스 경로 문제의 승차지점에 한번의 방문으로 모든 학생을 수송할 수 있는 모델을 시간의 흐름에 따라 동적으로 학생 수가 변화하는 모델을 구축하고 현실에서 실현 가능한 기존의 스쿨버스 경로문제에 적용된 제약사항들을 완화하여 다양한 시나리오를 구성하였다. 또한, 사례연구를 통하여 제약완화를 통한 시나리오별 비교우위를 평가하였다.
이철문 (2005)은 GA에서 초기 모집단을 생성하는 방법은 크게 발견적 기법과 임의생성 방법들을 활용되는데, 발견적 기법에 의해 생성된 해들은 조기 수렴하여 해공간의 다양한 탐색을 방해하는 경향이 있고, 임의 생성방법은 초기에 다수의 실행 불가능 해를 포함하고 있어 효과 적인 해의 탐색이 어렵다고 언급하였다. 본 연구에서 초기 해는 하나의 실행 가능 해를 생성하고, 이 실행 가능해의 표현에 따라 임의생성 방법을 이용하여 실행 불가능해를 감소시켜 효율적으로 해를 탐색하도록 유도하였다.
본 연구에서 효율적인 해 개선을 위해 2단계 교차 연산을 활용하였다. 첫 번째 교차는 복수 점 교차를 통하여 정류소의 방문 시간대를 교차하여 다양한 해 공간을 탐색한다.
본 연구에서는 시간대에 따라 학생 수가 상이한 문제이므로 유전자 표현을 하나의 해가 방문 순서와 방문 시간대의 정보를 갖는 String 구조로 설정한다. 이는 정류소 간의 이동시 방문시간대에 따라 달라지는 학생 수를 반영할 수 있도록 다음의 Fig.
모형 구축을 위한 전반적인 순서는 다음과 같다. 실험 대상지역을 선정한 후 대상지역에 위치한 목적지 학교 및지하철 역 그리고 임의의 차고지 간의 이동 시간 및 각 정류소에 도착하여 대기하는 학생 수에 대한 DB를 포아송 분포로 구축한다.
그들의 연구에서는 연간 스쿨버스의 총 운영 시간과 거리에 대하여 고려하였다. 즉, 적은 수의 버스 운영과 짧은 이동거리 및 시간을 효율성의 척도로 판단하였다. 유효성 측면에서는 학생이 버스에 탑승한 상태에서 머무는 이동시간에 관한 것과 다수의 학생 거주지에 단일 버스 스탑 결정시 버스 스탑까지 학생이 걸어서 도착 하는 시간들에 대하여 연구가 진행되어왔다(Li and Fu, 2002).
(2005)는 다수의 학교에 대하여 경로 결정 문제를 휴리스틱을 이용하여 풀었다. 학교마다 다른 시작 시점을 가지고 있다는 가정하에 Greedy Algorithm으로 경로를 우선 결정하고, Simulated Annealing 과 Tabu Search를 이용 하여 경로를 통합하는 방식을 사용하여 풀었다. 하지만 SBRP 는 NP-Hard 문제로서 수리 모형을 이용하여 최적해를 도출 하기 어렵고 일부 작은 크기 문제의 해만 도출한 바 있다.
한편, 종료 조건으로는 GA를 수행하는 과정에서 현재 해보다 일정 횟수동안 해의 개선이 발생하지 않으면 종료하도록 설정하였다.
2%의 개선 효과가 있는 것으로 나타나, GA를 통한 해 개선이 뚜렷함을 보였다. 한편, 차량의 중복 방문 허용에 대한 효과를 분석하기 위해 시나리오 1과 시나리오 3, 5를 비교하였다. 차량 중복을 허용하지 않는 시나리오 1에 비해 동일 차량에 대해 상이한 시간대에 재방문을 허용한 시나리오 3의 경우, 총 탑승 학생 수에서 약 4.
대상 데이터
실험 대상의 각 지하철 역 명과 목적지 학교는 부록 1에서 소개하고 있다. 또한, 각 지하철역에서 시간대별 탑승하는 학생의 수를 사전에 포아송 분포를 이용하여 데이터를 수집하였다. 각 지하철의 상이한 T1의 시작 시점은 지하철의 흐름을 반영하였다.
본 연구 모형의 적용 가능성을 평가하기 위해 서울시 북서지역에 위치한 5개의 학교와 20개의 지하철역 그리고 임의의 지역에 위치한 차고지를 대상으로 실험을 수행 하였다. 실험 대상의 각 지하철 역 명과 목적지 학교는 부록 1에서 소개하고 있다.
만약, 스쿨버스의 용량과 학생의 최대 수송 시간 제약조건을 만족한다면, 첫 번째 방문한 승차지점으로 부터 가장 근접한 거리에 위치한 정류소를 다음 방문지로 선정하고 제약조건의 위배사항을 다시 한 번 체크한다. 제약조건이 위배가 된다면, 이전까지 확정되었던 정류소를 최종 방문 지점으로 결정하고, 다른 스쿨버스를 추가 하여 첫 번째 버스가 방문하지 않은 정류소 중에 차고지로부터 가장 근접한 거리에 위치한 정류소를 두 번째 차량의 첫 방문 후보지로 선정한다. 이러한 방식으로 학생의 최대 수송 시간 제약 또는 차량용량을 초과하지 않을 때까지 작업을 반복 수행하여 모든 승차지점을 방문한다.
이론/모형
본 연구에서 제시한 SBRPMLDA 모델의 실험을 위한 초기 경로 구성을 Sweep Algorithm(Gillett and Miller, 1974)를 이용하여 초기 경로를 구한다. 초기 경로 구성 과정을 통하여 도출한 경로를 전역 탐색 능력이 있는 메타 휴리스틱 기법 중 하나인 Genetic Algorithm (Holland, 1975)을 이용하여 최적의 경로를 탐색한다.
유전자의 선택은 개체들의 적합도에 비례하여 선택하는 대표적인 방법인 룰렛 휠 선택 방법을 적용하였다. 룰렛 휠 선택은 개체들의 적합도의 합을 계산하여 각 개체의 선택확률을 계산한다.
유전자 알고리즘의 진화과정 속에서 확률적 속성 때문에 아주 높은 적합도를 지닌 개체가 다음세대로 진화하지 못하고 소멸되는 경우가 있다. 이를 방지하기 위하여 엘리트 보존 전략을 사용하였다.
본 연구에서 제시한 SBRPMLDA 모델의 실험을 위한 초기 경로 구성을 Sweep Algorithm(Gillett and Miller, 1974)를 이용하여 초기 경로를 구한다. 초기 경로 구성 과정을 통하여 도출한 경로를 전역 탐색 능력이 있는 메타 휴리스틱 기법 중 하나인 Genetic Algorithm (Holland, 1975)을 이용하여 최적의 경로를 탐색한다.
성능/효과
넷째, 각 스쿨버스의 학생 수송 용량은 스쿨버스의 용량을 초과할 수 없다.
다섯째, 각 대중교통 정류소는 한 번의 방문만을 허용한다.
둘째, 각 대중교통 정류소에서 대기하는 학생 수는 동일한 시간 간격에 따라 포아송 분포로 발생되며, 시간대가 변화함에 따라 누적 증가 한다.
한편, 상이한 차량의 중복방문과 부분 탑승을 모두 허용할 경우(시나리오 6), 시나리오 1에 비해 약 40%에 가까운 증가를 볼 수 있었다. 따라서, 차량의 중복방문이나 부분 탑승을 허용하는 것이 실제 탑승 학생 수를 개선하는 데 큰 효과를 보임을 알 수 있었다.
한편, 앞서 언급한 버스의 통합 관리의 효과를 보기 위해 모든 차량에 대해 모든 승차지점에 중복 방문을 허용하는 시나리오를 검토해 본 결과, 중복 방문을 허용하지 않는 시나리오 1에 비해서는 약 32%의 총 탑승 학생 수 증가 효과가 나타났으며, 버스의 운행 시간 또한 미비하나마 감소되는 효과를 볼 수 있었다. 또한, 동일차량만을 중복 방문 허용하는 시나리오 3에 비해서도 총 탑승 학생 수에서 408명에서 516명으로 약 26%가 넘는 개선효과가 있는 것으로 나타났다.
Table 3은 3절 연구모형에서 언급된 가정사항을 반영한 기본적인 SBRPMLDA 모형에 대한 실험 결과를 보여 주고 있다. 실험 결과, 총 수송 학생수 391명, 스쿨버스의 평균 이동시간 37.7 분의 결과를 얻을 수 있었다.
여섯째, 각 스쿨버스는 차고지에서 출발하여 하나이상의 대중교통 정류소를 방문하여야 한다.
일곱째, 학생이 버스에 탑승한 상태로 수송될 수 있는 최대시간은 제한되어 있다.
한편, 차량의 중복 방문 허용에 대한 효과를 분석하기 위해 시나리오 1과 시나리오 3, 5를 비교하였다. 차량 중복을 허용하지 않는 시나리오 1에 비해 동일 차량에 대해 상이한 시간대에 재방문을 허용한 시나리오 3의 경우, 총 탑승 학생 수에서 약 4.3%, 버스의 평균 운행시간에 대해서는 5.8%의 개선 효과가 있는 것으로 보아 차량 중복 허용 효과가 있는 것을 확인할 수 있었다. 한편, 앞서 언급한 버스의 통합 관리의 효과를 보기 위해 모든 차량에 대해 모든 승차지점에 중복 방문을 허용하는 시나리오를 검토해 본 결과, 중복 방문을 허용하지 않는 시나리오 1에 비해서는 약 32%의 총 탑승 학생 수 증가 효과가 나타났으며, 버스의 운행 시간 또한 미비하나마 감소되는 효과를 볼 수 있었다.
먼저, GA를 통한 해 개선 효과를 검증하기 위해 Sweep Algorithm을 통해 도출된 초기 해와 GA를 통해 해를 개선한 결과를 비교하였다. 총 탑승 학생 수에서 358명에서 391명으로 약 9.2%의 개선 효과가 있는 것으로 나타나, GA를 통한 해 개선이 뚜렷함을 보였다. 한편, 차량의 중복 방문 허용에 대한 효과를 분석하기 위해 시나리오 1과 시나리오 3, 5를 비교하였다.
또한, 사례연구를 통하여 제약완화를 통한 시나리오별 비교우위를 평가하였다. 평가결과 기존의 스쿨버스 경로문제에서는 학생들의 승차지점에서의 대기 학생 수가 스쿨버스의 잔여용량을 초과할 경우 방문 하지 못하였던 제약을 완화하여 스쿨버스의 잔여용량만큼 학생을 수송하는 제약과 차량의 방문 허용 제약을 완화한 중복 방문 허용을 통하여 기본적인 SBRPMLDA 모델보다 약 26% 이상의 학생을 수송하는 결과를 도출 하였다.
4분 증가하는 것으로 보아 비교 우위를 말하기 어려웠다. 하지만, 차량 중복방문과 부분 탑승을 동시에 고려하는 시나리오 4와 6의 결과를 보면, 동일차량의 중복방문과 부분 탑승을 허용하는 시나리오 4의 경우, 시나리오 1에 비해 버스 운행시간이 미미하게 증가하였지만, 총 수송 학생수 측면에서는 약 10% 이상의 개선 효과가 있는 것으로 나타났으며, 평균 승차율에서도 약 9% 증가되는 것으로 볼 수 있었다. 한편, 상이한 차량의 중복방문과 부분 탑승을 모두 허용할 경우(시나리오 6), 시나리오 1에 비해 약 40%에 가까운 증가를 볼 수 있었다.
8%의 개선 효과가 있는 것으로 보아 차량 중복 허용 효과가 있는 것을 확인할 수 있었다. 한편, 앞서 언급한 버스의 통합 관리의 효과를 보기 위해 모든 차량에 대해 모든 승차지점에 중복 방문을 허용하는 시나리오를 검토해 본 결과, 중복 방문을 허용하지 않는 시나리오 1에 비해서는 약 32%의 총 탑승 학생 수 증가 효과가 나타났으며, 버스의 운행 시간 또한 미비하나마 감소되는 효과를 볼 수 있었다. 또한, 동일차량만을 중복 방문 허용하는 시나리오 3에 비해서도 총 탑승 학생 수에서 408명에서 516명으로 약 26%가 넘는 개선효과가 있는 것으로 나타났다.
후속연구
추후에는 본 연구에서 제안한 SBRPMLDA의 현실 적용 가능성을 검증하기 위하여 더욱 큰 규모의 사례연구와 GA의 종료 시간을 계산하기 위한 추가적인 알고리즘 개발에 대한 연구가 이루어져 현실 가능한 스쿨버스 경로 문제에 대한 더욱 심도 있는 연구가 이루어 질 수 있을 것으로 기대한다.
질의응답
핵심어
질문
논문에서 추출한 답변
일반적인 스쿨버스 경로문제의 제약 조건은 어떠한 것들이 있는가?
스쿨버스 경로문제는 학생들을 다수의 승차지점으로부터 학생들의 해당 학교까지 안전하고 효율적으로 수송할 수 있는 방법을 찾는 문제이다. 일반적인 스쿨버스 경로문제의 제약 조건으로는 차량의 용량, 학생의 최대 수송 시간, 학교의 도착 시간 제약 등이 있다. 본 연구에서는 기존의 혼승을 허용한 스쿨버스 경로 문제를 확장한 모델을 구축하고, 국내의 대학교 스쿨버스 운영 형태를 고려하여 학생들이 승차지점에 유동적으로 유입이 되는 상황을 고려한다.
스쿨버스 경로문제는 VRP 문제와 유사한 점과 차이점은 무엇인가?
SBRP 는 Location-Routing Problem(LRP)의 범주에 속하는 것으로, 버스 정류소 결정문제, 버스 경로 결정 문제, 그리고 버스 스케쥴링 문제 등을 포함하고 있다. 일반적으로 널리 알려진 차량 경로 계획 문제(Vehicle Routing Problem, 이하 VRP)와 유사한 점을 갖추고 있으나, 일반적인 VRP 문제에서는 수송하여야 하는 대상이 화물이지만, SBRP는 단순 화물을 다루는 문제가 아닌 학생의 수송을 다루는 문제이므로 VRP와는 다른 성격을 지닌 제약 조건을 필요로 한다 (Park and Kim, 2010). 일반적인 화물의 특성상 수송되는 시간적 제약이 크지 않지만, 학생은 스쿨버스에 탑승하여 이동할 수 있는 시간의 범위가 화물보다 크지 않다.
스쿨버스 경로문제란 무엇인가?
스쿨버스 경로문제는 학생들을 다수의 승차지점으로부터 학생들의 해당 학교까지 안전하고 효율적으로 수송할 수 있는 방법을 찾는 문제이다. 일반적인 스쿨버스 경로문제의 제약 조건으로는 차량의 용량, 학생의 최대 수송 시간, 학교의 도착 시간 제약 등이 있다.
참고문헌 (14)
Bodin, L.D. and Berman, L.(1979), Routing and Scheduling of School Buses by Computer, Transportation Science, Vol.13, pp.113-129.
Bowerman, Rm Hall., and Calamai, P.(1995), A multi-objective optimization approach to urban school bus routing : Formulation and solution method. Transportation Research Part A, Vol. 29, No.2 , pp. 107-123.
Desrosiers, J., Ferland, J. A., Rousseau, J. M., Lapalme, G., and Chapleau, L. (1986), TRANSCOL : a Multi-period School Bus Routing and Scheduling System, TIME Studies in the Management Sciences, Vol.22, pp.47-71.
Fugenschuh, A. (2009), Solving a school bus scheduling problem with integer programming, European Journal of Operational Research, Vol.193, No.3, pp.867-884.
Park, J., Tae, H., and Kim, B. (2009), The Effects of Allowing Mixed Loads in the Commuter Bus Routing Problem, Proceedings of the 10th Asia Pacific Industrial Engineering and Management Systems Conference, Kitakyushu, Japan, pp.1353-1359.
Park, J. and Kim, B. (2010), The School Bus Routing Problem : A Review, European Journal of Operational Research, Vol.202, No.2, 311-319.
Ripplinger, D. (2005), Rural School Vehicle Routing Problem, Transportation Research Record : Journal of the Transportation Research Board, Vol. 1922, pp. 105-110.
Schitterkar, P., Sevaux, M., and Sorensen, K. (2006), A mathematical formulation for a school bus routing problem, Proceedings of the IEEE 2006 International Conference on Service System and Service Management.
Spada, M., Bierlaire, M., Liebling, and Th. M. (2005), Decision-aiding methodology for the school bus routing and scheduling problem, Transportation Science, Vol. 39, pp. 477-490.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.