Abstract
이 논문은 각 학교에 대해 trip이 주어지는 학교 버스 스케줄링 문제를 다룬다. 각 trip은 여러 개의 버스 정류장과 해당 trip이 도착해야 하는 학교로 구성된다. 각 학교는 trip이 완료되어야 하는 고정된 시간 창(time window)을 가지고 있다.
하나의 학교 버스는 여러 학교의 여러 trip을 수행할 수 있다. 학교 버스 스케줄링 문제의 목표는 주어진 모든 trip을 학교의 시간 제약을 만족하도록 배정하면서, 버스 운행 스케줄을 최적화하는 것이다.
본 논문에서는 각 trip을 하나의 가상 정류장(virtual stop)으로 간주하여 문제를 Vehicle Routing Problem with Time Windows(VRPTW)로 모델링한다. 또한, 특정한 경우에 대해 두 가지 Assignment Problem 기반의 정확한 해법을 제안하고, 보다 일반적인 경우를 위해 하나의 휴리스틱 알고리즘을 제안한다. 마지막으로 benchmark 문제들과 계산 실험을 통해 제안한 방법들의 성능을 평가하며, 실험 결과는 제안된 접근법의 효과성을 보여준다.
1. Introduction
Fig.1은 학교 버스 스케줄링 문제의 예시를 보여준다.
- ti: 여러 정류장과 목적 학교로 구성된 trip
- sm: 하나의 학교
해당 그림에서는 학교 sa, sb, sc에 대해 각각 3개, 3개, 4개의 trip이 존재한다.
각 학교 m에 대해 [sm_st, sm_et]를 해당 학교의 시간 창이라고 하자.
각 학교에 다니는 모든 학생들은 이 시간 창(등교 시간) 내에 도착해야 한다.
두개의 trip이 버스 용량 제약과 각 학교의 시간 제약을 위반하지 않는다면, 하나의 버스가 이 두 trip을 연속으로 수행할 수 있다.
Fig.2는 Fig.1 문제의 하나의 해를 보여준다.
{t2, t6, t9}, {t1, t4, t8}, {t3, t7}, {t5, t10}은 각각 버스 1,2,3,4에 의해 수행된다.
또한 sa_et ≤ sb_st, sb_et ≤ sc_st가 성립한다고 가정한다.
본 논문에서는 먼저 각 trip을 하나의 가상 정류장(virtual stop)으로 간주하여 문제를 Vehicle Routing Problem with Time Windows(VRPTW)로 모델링한다.
그러나 이 VRPTW는 원래 문제의 비대칭성 asymmetric nature 때문에 일반적인 VRPTW와는 다른 특성을 가진다.
학교들의 시간 창이 서로 충분히 떨어져 있고, 각 trip의 서비스 시간에 비해 시간 창의 폭이 크지 않기 때문에, 두 trip을 같은 버스가 수행할 수 있는 경우 그 수행 순서는 사실상 고정된다.
즉, 하나의 trip 뒤에 다른 trip이 이어질 수 있다면 그 반대 순서는 불가능하다고 가정한다.
또한, 본 논문은 다음과 같은 특수한 경우를 보인다:
- trip의 시작/종료 시간이 고정되어 있고
- 버스가 동일한 성능을 갖는 homogeneous fleet인 경우
이 문제는 Assignment Problem으로 모델링 가능하며 쉽게 해결할 수 있다.
이후
- homogeneous fleet을 가정한 일반적인 경우에 대해 assignment problem 기반 branch-and-bound 방법을 제안
- heterogeneous fleet (버스가 서로 다른 경우)에 대해서는 휴리스틱 알고리즘을 제안
마지막으로 계산 실험을 통해 제안된 방법들의 효과성 검증한다.
2. Literature Review
학교 버스 routing 문제는 크게 3가지 하위 문제로 구성된다:
- 버스 정류장 선택 bus stop selection
- 각 학교별 경로(또는 trip) 생성
- 버스 스케줄링 문제
본 절에서는 이 중 버스 스케줄링 문제에 초점을 둔다. 일반적인 학교 버스 routing 문제에 대한 자세한 설명과 관련 연구는 Park and Kim (2010)에 정리되어 있다.
버스 스케줄링 문제는 각 경로의 정확한 시작 및 종료 시간을 결정하고, 하나의 버스가 연속적으로 수행할 수 있는 trip들의 체인 chain을 구성하는 것을 의미한다.
Gavish et al. (1987)은 trip의 시작 및 종료 시간이 주어진 버스 스케줄링 문제를 다루었으며, 이를 수송 문제(Transportation Problem, TP)로 모델링하였다. Orloff (1976)와 Carraresi and Gallo (1984)는 동일한 문제를 다루었지만, 이를 Assignment Problem(AP)으로 모델링하였다.
Lobel (1998a,b)은 대중교통에서의 다중 차고 차량 스케줄링 문제 MDVSP를 연구하였다. 이 문제는 서로 다른 버스를 사용하는 학교 버스 스케줄링 문제와 유사하다.
- 각 차량은 특정 depot에 속함.
- 반드시 해당 depot에서 출발하고 다시 돌아와야 함.
이 문제는 multi-commodity flow problem으로 모델링되었고, trip의 시간표가 주어져도 NP-complete임이 증명되었다. 또한 해결 방법으로 column generation 기법이 제안되었다.
하지만 본 논문에서 다루는 문제는 depot에서 출발/복귀해야 한다는 제약이 없다.
Hadjar et al. (2006)은 MDVSP에 대해 branch-and-price-and-cut 알고리즘을 제안하였고, Pepin et al. (2009)은 여러 휴리스틱 및 메타휴리스틱 방법을 비교하였다.
Desaulniers et al. (1998)은 시간 창이 있는 다중 차고 차량 경로 문제 MDVRPTW에 대해 정수 비선형 모델과 column generation 기반 branch-and-bound를 제안하였다.
Hadjar and Soumis (2009)은 동적 window 축소 기법을 포함한 branch-and-price 알고리즘을 제안하였다.
Orloff (1976)는 다음을 보였다:
- trip 도착 시간이 고정되지 않고
- 학교의 time window만 주어지는 경우
homogeneous fleet의 학교 버스 스케줄링 문제는 NP-complete
또한 matching 기반 구성 알고리즘과 3-opt 개선 방법을 제안하였다.
Newton and Thomas (1974), Bodin (1975), Bodin and Berman (1979)는 시간을 여러 구간 period으로 나누는 가정을 사용하였다.
- 각 period 시작 시, 버스는 이전 학교에 위치
- 한 period 동안 각 버스는 최대 1개의 trip만 수행
- 각 버스는 한 학교만 담당
이 경우 문제는 여러 개의 TP를 풀어 해결할 수 있었지만, 현실을 지나치게 단순화한 가정이다.
Swersey and Ballard (1984)는 비선형 프로그래밍 모델과 이를 이산화한 MIP 모델을 제안하였다:
- 학교 time window를 여러 개의 도착 시간으로 나눔.
- 선형 완화로 풀고
- 정수가 아닌 해는 수동으로 조정
Graham and Nuttle (1986)은 Orloff (1976)와 Swerwey and Ballard (1984)의 알고리즘을 비교하였다.
또한 AP 기반 알고리즘도 실험했는데,
- 초기 해는 AP로 구하고
- time window 제약은 수동으로 맞춤.
feasibility를 보장하면서 계산시간이 짧은 휴리스틱이 필요
Braca et al. (1997)은 뉴욕시 학교 버스 문제를 다루었다.
기존 연구는 학교별로 문제를 따로 풀었지만, 이들은 모든 학교를 한 번에 통합하여 해결하였다.
Spada et al. (2005)는 여러 학교를 고려한 라우팅 문제를 다루었다.
- 시작 시간이 빠른 학교부터 처리
- greedy 방식으로 경로 생성
- 이후 경로를 병합
- simulated annealing / tabu search로 개선
Desrosiers et al. (1981, 1986a)는 다음 모듈을 포함하는 시스템을 제안하였다:
- 정류장 배경
- 경로 생성
- 학교 시작 시간 결정
- 경로 스케줄링
특히 학교 시작 시간을 조정하여 필요한 버스 수를 줄일 수 있다고 가정하였다.
스케줄링 문제는 여러 TP를 풀어 해결하였다.
Fugenschuh (2009)는
- 학교 시작 시간 조정 가능
- 학생을 trip 간 이동 가능
한 문제를 다루었으며, 이를 VRPTW 기반 정수계획 모델로 만들고 branch-and-cut으로 해결하였다.
하지만.
- homogeneous fleet 가정
- 작은 문제도 시간 제한 내 최적해 어려움.
문제의 복잡성이 매우 크다.
3. Formulation of the Bus Scheduling Problem
버스 스케줄링 문제는 다음과 같이 VRPTW로 모델링할 수 있다.
- 각 trip ti를 하나의 가상 정류장(virtual stop) vi로 정의한다.
- trip의 서비스 시간 pi는 해당 가상 정류장의 서비스 시간으로 사용된다.
가상 정류장 vi의 시간 창 [ai, bi]는 다음과 같이 설정:
- 학교 시간창:
- trip 서비스 시간: pi
따라서 [ai, bi]는 다음과 같다:
- 두 가상 정류장 vi → vj 사이 이동 시간 dij:
- trip i의 학교 → trip j의 첫 정류장까지 이동 시간
인덱스 정의
파라미터 (constants)
- Eik: 버스 k가 trip i 수행 가능하면 1
- D+(i): i 다음에 올 수 있는 stop 집합
- D(j): j 이전에 올 수 있는 stop 집합
- M: big-M (큰 상수)
결정 변수 (Decision Variables)
- xijk: 버스 k가 i 다음에 j를 수행하면 1
- wik: 버스 k가 i에서 서비스 시작 시간
MIP 모델
- 목적함수
- 이동 거리 최소화
- 사용 버스 수 최소화 (더 중요, lexicographic)
- 제약조건
- (2) 모든 trip은 반드시 수행: 각 trip은 정확히 한 번, 가능한 버스에 의해 수행
- (3) 흐름 보존 (flow balance): 들어온 횟수 = 나간 횟수
- (4) 시간 흐름 제약: i → j로 이동하면 j 시작 시간 ≥ 끝 + 이동시간
- (5) 시간 창 제약: 정해진 시간 안에 시작해야 함.
- (6), (7) depot 제약
- 모든 버스는 depot에서 출발
- depot으로 돌아옴.
- (8) binary 변수
일반적인 VRPTW와 비교했을 때, 본 모델은 두 가지 다른 특성을 가진다:
첫째, 버스와 정류장 간의 적합성(eligibility)이 존재한다.
일반적인 VRPTW에서는 모든 차량이 모든 정류장을 서비스할 수 있다고 가정하지만, 본 문제에서는 버스가 해당 정류장을 서비스하기에 충분한 수용 능력을 갖는 경우에만 가상 정류장을 서비스할 수 있다. 즉, Eik=1이어야 한다. 예를 들어, 60명의 학생을 수송하는 trip은 50인승 버스로는 수행될 수 없다.
둘째, 본 문제에서는 버스 운행 일정동안 학생 수의 누적을 고려하지 않는다.
일반적인 VRPTW에서는 차량에 적재된 물량의 누적이 차량 용량을 초과하지 않도록 해야하지만, 본 문제에서는 각 가상 정류장이 해당 학생들의 목적지인 학교를 포함하고 있기 때문에 학생 수의 누적을 확인할 필요가 없다. 버스는 학교를 방문할 때마다 수용 용량이 다시 초기화될 수 있다.
이러한 특성으로 인해 본 문제는 full truck load 문제와 유사한 성격을 가진다.
Homogeneous fleet 모델 MIPHO
버스가 모두 동일하면 더 간단해진다.
- 변수 변경
- xij: 같은 버스가 i 다음 j 수행
- wi: i 시작 시간
- 목적함수
- 제약조건
- (10) 각 trip은 한 번 수행
- (11) flow balance
- (12) 시간 제약
- (13) time window
- (14) binary
먼저 각 trip을 하나의 가상 정류장으로 간주해 문제를 VRPTW로 모델링한다.
또한, 가상 정류장 간의 연결은 시간 창 제약을 위반하지 않는 경우에만 가능하도록 정의된다.
목적함수는 사전식(lexicographic) 방식으로 차량 수를 최소화하고, 동시에 총 이동 거리를 최소화하는 것을 목표로 한다.
4. Solution approaches
다음 절들에서는 서로 다른 가정을 바탕으로 한 문제에 대해 다양한 해결 방법들을 제안한다.
4.1. Problem with an assumption of homogeneous buses and fixed start time
문제의 특수한 경우를 다룬다.
가상 정류장의 서비스 시작 및 종료 시간이 고정되어 있고, 모든 차량이 모든 trip들을 수행할 수 있는 동일한 버스 집합(homogeneous fleet)이 주어졌다고 가정하면, 이 문제는 Assignment Problem(AP)으로 모델링할 수 있다.
이와 같은 유형의 문제는 최근 산업 연구 프로젝트에서 실제로 관찰된 바 있다.
이러한 가정을 가진 문제는 Fig.3과 같이 AP로 모델링 가능하다.
노드 i와 노드 j 사이으 ㅣ비용 cij는 다음과 같이 정의:
- 가상 정류장 i 이후에 가상 정류장 j를 주어진 서비스 시작 및 종료 시간 제약을 위반하지 않고 수행할 수 있는 경우, cij=dij로 설정한다.
즉, 정류장 i를 수행한 후 정류장 j에 도착하는 시간(= 정류장 i의 서비스 종료 시간 + i에서 j까지의 이동 시간)이 정류장 j의 서비스 시작 시간보다 늦지 않으면, cij=dij로 설정한다.
반대로, 도착 시간이 정류장 j의 서비스 시작 시간보다 늦으면, cij = M0 + 1로 설정한다.
또한, 이전 절에서 설명한 문제의 비대칭성으로 인해, cij가 작은 값을 가지면, cji는 M0+1이 되어야 한다.
마지막으로, cii=M0으로 설정한다.
의사결정 변수는 다음과 같이 정의:
- yij=1: 노드 i가 노드 j에 할당된 경우
- yij=0: 그렇지 않은 경우
할당 문제 모델은 다음과 같다:
이 할당 문제는 Hungarian method를 이용해 쉽게 해결할 수 있으며, 이는 O(n^3) 시간 복잡도를 갖는 알고리즘이다.
여기서 n은 노드의 개수를 의미한다.
충분히 큰 M0을 설정하면, 이 모델은 버스의 수를 최소화하려는 방향으로 작동한다.
이 모델의 해는 버스 스케줄링 문제의 해로 변환될 수 있다.
최적해에서 yij=1이고 cij<M0인 경우, trip j는 trip i 바로 다음에 동일한 버스에 의해 수행된다.
만약 최적해에서 yii=1이면, trip i를 수행하는 버스는 다른 trip을 수행하지 않는다.
해를 구성할 때는 cij ≤ M0인 경우의 변수만 고려한다.
예를 들어,
n=6이고 최적해가 y13 = t25 = y34 = y41 = y52 = y66 = 1이고,
c13 < M0,c26 < M0, c34 < M0, c41 = M0+1, c52 = M0+1, c66 = M0이라면,
trip 1-3-4, 2-5, 6은 총 3개의 버스에 의해 수행된다.
가능한 trip 연결만 비용을 작게 두고, 나머지는 큰 값으로 막아서 AP로 bus chaining 문제를 푼다.
4.2. Problem with an assumption of homogeneous buses
가상 정류장의 서비스 시작 및 종료시간이 고정되어 있지 않고, 주어진 시간 창에 따라 결정될 수 있는 경우, 동일한 버스 집합을 가정하더라도 문제는 더 어려워진다.
가상 정류장의 시작 시간이 고정되어 있다고 가정하면, 정류장 A에서 B로의 연결과 B에서 C로의 연결이 모두 가능할 경우, A에서 B를 거쳐 C로 가는 연결 또한 항상 가능하다.
그러나 이러한 관계는 시간 창 문제가 있는 경우에는 성립하지 않을 수 있다.
Fig.4는 이러한 예를 보여준다. 그림에서 각 수평선의 길이는 가상 정류장 간 서비스 및 이동에 필요한 총 시간을 나타낸다. 수직선은 각 학교의 시간 창을 나타낸다.
trip A와 B를 함께 수행하는 경우, 그리고 B와 C를 함께 수행하는 경우는 각각 하나의 버스로 가능하지만, 모든 trip을 하나의 버스로 수행하는 것은 시간 창 위반 때문에 불가능하다.
따라서, 앞서 설명한 assignment problem 기반 접근 방법은 시간 창 문제에 직접적으로 적용될 수 있다.
하지만, 각 trip이 Fig.5와 같이 가능한 한 가장 늦은 시간에 수행된다고 가정하면, 정류장 A→B와 B→C의 연결이 가능할 경우, A→B→C 연결 또한 항상 가능하게 된다.
이 경우 각 trip의 서비스 시작 시간이 고정되므로, 이전 소절의 assignment problem 기반 접근을 사용할 수 있다.
따라서, 서비스 시작 시간을 가능한 가장 늦은 시점으로 설정하고 assignment problem 기반 방법을 사용하면, 상한(upper bound) 해를 얻을 수 있다.
반대로, A→B와 B→C 연결이 가능하면 A→B→C도 가능하다고 가정하면, assignment problem 기반 접근으로 해를 구할 수 있다. 이 가정은 일종의 완화(relaxation)임, 이때 얻어진 해는 원래 문제에 대한 하한(lower bound)을 제공한다.
이러한 관찰을 바탕으로 branch-and-bound 알고리즘을 제안한다:
- APU: upper bound 문제
- APL: lower bound 문제
초기에는 APU와 APL을 구성하고 이를 해결한다.
만약 APU의 해가 최적이 아니라면(즉, APU와 APL의 목적함수 값이 다르면), branching이 수행된다.
분기 과정에서는 APL 해에서 비실현(infeasible)한 버스 스케줄과 문제를 일으키는 연결(link)을 찾는다.
예를 들어, A→B 연결이 시간 창 제약 때문에 불가능하다면, 현재 노드는 다음 두 개의 노드로 분기된다:
- “A→B 금지 (prohibit)”
- “A→B 결합 (combine)”
- A → B를 금지하려면: C_AB를 무한대로 설정
- A → B를 결합하려면: 하나의 가상 정류장으로 합친다.
- 서비스 시간 = A와 B의 서비스 시간 + 이동 시간 + 대기 시간
- 시간 창도 이에 맞게 조정
이후 일반적인 bounding 절차를 수행한다.
branch-and-bound 과정은 최적해를 찾거나, 주어진 계산 시간이 종료될 때까지 반복된다.
Branch-and-Bound 알고리즘
- Step 0: 초기화
- APU와 APL 설정 후 Hungarian method로 풀이
- APL 해가 feasible이면 → 최적 → 종료
- 아니면
- V_U = f(APU)
- V_L = f(APL)
- APL을 partial problem list에 추가
- Step 1로 이동
- Step 1: 종료 조건
- 리스트가 비었거나 시간초과 → 종료
- 아니면 첫 번째 문제(RAPL) 선택
- Step 2로 이동
- Step 2: 분기
- RAPL에서 infeasible link A → B 찾기
- 두 문제 생성:
- PAP: A → B 금지
- CAP: A → B 결합
- Step 3로 이동
- Step 3: Bounding 1 (PAP)
- PAPU, PAPL 설정 후 Hungarian method로 풀이
- PAPL 해가 feasible이면:
- V_U > f(PAPL)이면 → V_U 갱신
- infeasible이면:
- V_U < f(PAPL)이면 → 가지치기(fathom)
- 아니면 → 리스트에 추가
- Step 4로 이동
- Step 4: Bounding 2 (CAP)
- CAPU, CAPL 설정 후 Hungarian method로 풀이
- CAPL 해가 feasible이면:
- V_U > f(CAPL)이면: V_U 갱신
- infeasible이면:
- V_U < f(CAPL)이면: 가지치기
- 아니면: 리스트에 추가
- Step 5로 이동
- Step 5: Bounding 3
- lower bound > V_U인 노드 제거
- Step 1로 돌아감.
4.3. Problem with an assumption of heterogeneous buses
Section 4.2의 branch-and-bound 접근법은 작은 문제에 대해서는 최적해를 생성할 수 있지만, 계산 시간이 길기 때문에 큰 문제에는 사용할 수 없다. 또한, 이 방법은 이질적인 버스 집합 문제를 처리할 수 없다.
보다 일반적인 문제를 위해, 본 논문에서는 반복적인 AP 기반 구성 알고리즘과 개선 알고리즘으로 이루어진 휴리스틱 접근법을 제안한다.
구성 알고리즘에서는 세 가지 가중치 값이 사용된다:
- : 거리(distance)에 대한 가중치
- W_T: 시간(time)에 대한 가중치
- W_V: 차량 용량 적합도(vehicle capacity fitness)에 대한 가중치
이 값들은 주어진 범위 내에서 무작위로 생성된다.
이 구성 알고리즘은 다음과 같이 일련의 AP 문제를 풀어 초기 해를 생성한다:
- 학교의 시간 창을 기준으로 trip들을 오름차순으로 정렬
- 이미 스케줄된 버스가 이후에 수행할 수 없는 trip들의 부분집합을 결정
- 이러한 trip들에 대해, 가중치 값을 이용해 적절한 버스를 선택하고 초기화
버스 스케줄이 하나의 trip으로 초기화되면, 해당 trip의 목적지 학교 도착 시간은 가능한 가장 이른 시간으로 설정된다.
그 다음, 이미 스케줄된 버스들과 아직 스케줄되지 않은 trip들 사이에서 AP 문제를 구성한다.
버스 수와 미배정 trip 수가 일치하지 않는 경우, dummy node를 도입한다.
- 버스가 특정 trip을 수행할 수 있는 경우:
- 비용 = 버스 대기 시간 + 버스의 마지막 위치와 trip 시작 위치 간 거리 고려
- 수행할 수 없는 경우: 비용 = M0
AP를 풀고 나면, 현재 대상 학교에 속하는 trip들 중에서 AP에 의해 기존 버스에 할당된 것들을 버스 스케줄에 추가한다.
이 과정을 반복하면서 버스 스케줄을 점진적으로 확장한다.
예를 들어, Fig.6에서, trip 1,2,3,4,5,11이 다른 trip 뒤에 수행될 수 없다면, 이들은 각각 다른 버스에 배정된다.
버스에서 나온 실선은 생성된 버스 스케줄을 나타낸다.
학교 1의 모든 trip이 배정되면, 학교 2가 다음 대상이 된다.
만약 점선이 AP의 최적해를 나타낸다면, 그 중 현재 대상 학교와 관련된 할당(예: 1-6, 2-7, 3-8)만 확정되어 버스 1,2,3에 추가된다.
나머지 trip(9,10,12)은 일시적으로 제외되며 다음 반복에서 다시 고려된다.
구성 알고리즘 단계
- Step 0
- trip들을 시간 창 기준 오름차순 정렬
- 학교도 시간 창 기준 오름차순 정렬
- Step 1
- 모든 trip을 unrouted로 설정
- Step 2
- 가중치 W_D, W_T, W_V를 무작위 생성
- Step 3
- s=1 설정
- Step 4
- 모든 trip이 배정되었으면 Step 10으로
- Step 5
- 아직 배정되지 않은 trip i에 대해 어떤 버스에도 포함될 수 없다면, 수용 가능하고 Value1이 최소인 버스를 선택
→ 해당 버스로 스케줄 생성
→ trip i를 routed로 설정
- Step 6
- 모든 trip이 배정되었으면 Step 10으로
- Step 7
- 버스와 미배정 trip 사이 AP 구성
- 비용 정의:
- 가능할 경우: Cost = W_D * Dist + W_T * Wait + W_V * (Capacity - Students)
- 불가능할 경우: Cost = M0
- Step 8
- AP 결과 중 현재 학교 s에 해당하는 trip을 선택
- 버스 스케줄에 추가
- routed로 설정
- AP 결과 중 현재 학교 s에 해당하는 trip을 선택
- Step 9
- s = s + 1, Step 4로
- Step 10
- max_iteration만큼 반복 후
- 최소 버스 수
- 최소 이동 거리를 만족하는 최적 해 반환
- max_iteration만큼 반복 후
개선 알고리즘 Improvement
- 최적 해를 얻은 후, 추가 개선 수행:
- 사용되는 연산: (아래 순서로 적용)
- one-to-zero: 한 stop을 다른 버스로 이동
- one-to-one: 두 버스 간 stop 교환
- one-to-two: 한 stop ↔ 두 stop 교환
- two-to-two: 두 stop ↔ 두 stop 교환
- 사용되는 연산: (아래 순서로 적용)
전체 과정은 더 이상 개선이 없을 때까지 반복된다.
각 알고리즘 내부에서도 가능한 모든 조합을 탐색하여 가장 개선이 큰 변경을 적용한다.
이 개선 과정의 목표: 버스 수 감소 + 총 이동 거리 감소
5. Computational results
- 실험 설정
- C++ 구현, Hungarian algo. 사용
- benchmark 데이터 직접 생성 (homogeneous 15 + heterogeneous 15개)
- 다양한 규모의 문제로 성능 비교
- 알고리즘별 성능 비교
- MIP (수학적 모델)
- 작은 문제: 최적해 가능
- 큰 문제: 시간/메모리 한계로 실패
- 정확하지만 확장성 부족
- AP 기반 branch-and-Bound
- 작은 문제: 빠르게 최적해
- 큰 문제: 시간 오래 걸림
- MIP보다 효율적이지만 여전히 scalability 한계
- Heuristic (제안 방법)
- 작은 문제: optimal 또는 near-optimal
- 큰 문제: 빠르게 좋은 해 생성
- 다른 방법보다 대규모에서 더 좋은 성능
- 실제 문제에서 가장 현실적
- Lower Bound (AP LB)
- 작은 문제: 정확한 기준 제공
- 큰 문제: 성능 미확인
- 해 품질 평가 기준 역할
- MIP (수학적 모델)
- 핵심 결과
- 문제 규모가 커질수록 exact 방법(MIP, B&B) → 비효율적
- Heuristic → 성능 우수
- 실제 데이터 결과
- 버스 수 감소: 14~18%
- 이동 거리 감소: 12~16%
- 계산 시간: 1분 이내
- 현실에서도 효과 입증
6. Conclusion
본 논문은 각 학교에 대해 trip이 주어지는 학교 버스 스케줄링 문제를 소개했다. 각 trip은 시작 정류장, 서비스 시간, 운송하는 학생 수, 그리고 도착 학교로 구성된다. 각 학교는 모든 trip이 완료되어야 하는 고정된 시간 창을 갖고 있다.
학교 버스 스케줄링 문제의 목적은 이러한 학교 시간 창을 고려하여 주어진 모든 trip을 수행할 수 있도록 버스 스케줄을 최적화하는 것이다.
본 연구에서는 먼저 각 trip을 하나의 가상 정류장으로 간주하여 문제를 VRPTW로 모델링하였다. 이후, 특수한 경우에 대해서는 두 가지 assignment problem 기반의 정확한 해법을 제안하였고, 보다 일반적인 경우를 위해 assignment problem 기반의 휴리스틱 알고리즘을 제안하였다. 또한, benchmark 문제들을 생성하여 다른 연구자들이 참고할 수 있도록 인터넷에 공개하였다. 계산 실험을 통해 제안된 알고리즘들의 정확성과 효율성을 확인하였다.
- MIP 모델과 assignment problem 기반 branch-and-bound 알고리즘은
→ 작은 규모의 homogeneous fleet 문제에 적합하며, - 휴리스틱 알고리즘은
→ 대규모 문제 및 heterogeneous fleet 문제에 적합하다.
또한, 본 논문에서 다룬 문제에 대해 최신 metaheuristic 기법들을 적용하는 것도 가능할 것이다. 정확한 방법과 휴리스틱을 결합하는 것 또한 향후 연구 방향이 될 수 있다. 대규모 문제에서 제안된 접근법의 성능을 평가하기 위해서는 보다 강력한 lower bound 방법이나 효율적인 exact 방법의 개발이 필요하다.