Ⅰ. 서 론
1. 개요
수요응답형 대중교통체계는 사용자의 요청에 따라 경로와 스케줄을 결정하는 대중교통 서비스이다. 버스 나 기차 등의 기존 대중교통 시스템은 저렴한 비용으로 많은 승객들을 태울 수 있기 때문에 효율적이고 환 경 친화적이나, 경로와 스케줄이 고정되어 있기 때문에 사용자가 이용하기 불편할 수 있다. 반대로 택시와 같은 수단은 사용자의 요청에 따라 서비스를 제공하여 편리하지만, 서비스 비용이 상대적으로 높은 단점이 있다. 이에 따라 고정적 계획의 버스 서비스와 유동적인 택시 서비스 사이에서 비용과 편의성을 함께 충족시 킬 수 있는 수요응답형 대중교통 시스템에 대한 관심이 높아지고 있다.
지금까지 많은 연구에서 수요응답형 대중교통 시스템을 위한 경로탐색 알고리즘이 제안되고 있으며, 이들 은 접근방법에 따라 휴리스틱, 메타 휴리스틱, 시뮬레이션 방법 등으로 분류된다. 경로탐색 알고리즘의 경우 승하차 수요지점을 처리하는 다양한 방법이 사용되는데, 그 중 승객들을 정해진 정차지점으로 모아 서비스 하는 방법은 정차지점 수의 감소를 통한 차량 주행시간의 절약, 차후 네트워크 디자인에서의 범용성 등의 장 점이 있다. 그러나 정차지점을 설정하는 방법에 따라 불필요한 우회경로가 생기거나 차량용량을 충분히 활 용하지 못하여 비효율적인 주행을 하게 될 수 있어, 이를 고려한 경로탐색 방법이 필요하다.
본 논문에서는 차량용량 활용 및 서비스 비율이 높으며 계산속도가 비교적 빠른 기종점 클러스터링 방법 을 결합한 휴리스틱 경로탐색 알고리즘을 제안한다. 2장에서는 수요응답형 대중교통 시스템 및 차량경로탐 색 방법론에 대한 이론적 배경을 설명하고, 3장에서는 본 연구에서 제안하는 기종점 클러스터링 기반의 경 로탐색 방법론에 대해 설명한다. 4장에서는 제안된 방법론의 성능을 확인 및 비교하고, 마지막으로 5장에서 결론 및 향후 연구 내용에 대해 설명한다.
Ⅱ. 이론적 배경
1. 수요응답형 대중교통체계
수요응답형 교통 시스템의 가장 기본적인 형태는 1960년대에 나타난 노인과 장애인을 위한 Dial-a-ride 서 비스로 시작되었다 (Psaraftis, 1980). 이후 일반적 수요에도 서비스를 제공하기 위해 점진적으로 개발 및 확장 되었으며, 다양하게 파생된 개념들이 등장하였다. 파생된 수요응답형 교통 시스템의 대표적 형태는 지역 허 브와 주변 수요를 연결하는 Feeder-DRT (Cortés et al., 2002; Pages et al., 2006;Quadrifoglio et al., 2007), 사전 정의된 경로에서 어느 정도의 변동이 허용되는 Mobility Allowance Shuttle Transit (MAST) (Pages et al., 2006;Quadrifoglio et al., 2007) 등이 있다. 대표적인 수요응답형 교통 시스템이 가지는 특징을 <Table 1>과 같이 간 략히 정리하였다.
<Table 1>
Demand Responsive Transit system
| DRT system | Description | Reference |
|---|---|---|
| Traditional dial-a-ride DRT | Door-to-door para transit service with request rides by telephone | Cervero, 1997 |
| Feeder DRT | Connection of local area and hub | Cortés et al.,2002; Pages et al.,2006;Quadrifoglio et al.,2007 |
| Mobility Allowance Shuttle Transit (MAST) | DRT that allowed to deviate from the predefined fixed route | Pages etal.,2006;Quadrifoglio et al.,2007 |
이러한 수요응답형 대중교통 시스템은 교외 및 농촌지역과 같이 수요가 적은 지역 혹은 기존의 대중교통 시스템이 효율적으로 제공되지 않는 지역을 위해 제안되었으나 (Cervero, 1997), 도시의 빠른 성장과 복잡성 증가로 인해 기존의 대중교통 시스템이 도심 네트워크를 효율적으로 다루기가 어려워졌으며, 보다 향상된 이동성과 접근성의 수요가 증가하였다. 따라서 보다 지속 가능하고 효율적인 운송을 위해 복잡하고 동적인 수요를 수용할 수 있는 교통 시스템의 필요성이 증대되었다. 이러한 점에서 유동적 계획으로 수요를 처리하 는 수요응답형 대중교통 시스템은 자율주행 기술의 발달과 함께, 농촌이나 교외 뿐 아니라 도시 지역의 대중 교통을 보완할 수 있는 (Alonso-Gonzalez et al., 2018;Ullah, 2016) 새로운 수단으로 인식되기 시작하였다. 도 시 지역에서 이 시스템은 대중교통 간의 연결, 야간시간의 교통 서비스, 대중교통 인프라가 미흡한 지역 등 에 성공적으로 활용될 수 있다. 본 연구에서 제시된 수요응답형 대중교통 시스템은 도심 지역에서 복잡하게 변화하는 수요에 대응해 유동적인 경로로 운행하여, 발생한 교통 수요에 대한 응답 비율을 높임과 동시에 대 중교통 차량용량의 활용성을 높이는 것을 목적으로 한다.
2. 차량경로탐색 방법론
수요응답형 대중교통 시스템에서 서비스 제공 차량의 경로를 결정하기 위해 다양한 목적을 갖는 경로탐 색 알고리즘이 개발 및 사용되어왔다. 다양한 알고리즘을 활용한 차량 경로탐색 방법론 연구를 그 목적과 실 험 환경 정의 사항에 따라 <Table 2>와 같이 정리하였다. 많은 연구자들이 다중차량 경로탐색 방법론을 개발 하였고, 또한 한 집결지에서 넓은 지역으로 분산되는 수요 패턴보다는 다양한 지역에서 기종점이 발생하는 형태의 수요 패턴에 대한 연구가 많이 이루어졌다. 각 방법론에서는 각각의 목적이 다양하게 정의되었고, 여 러 가지 최적화 알고리즘이 사용되었다. Saberi and Verbas(2012)은 이산화탄소 배출량 최소화를 목적으로 하 는 Continuous approximation 기반의 모델을 개발하여 최대 50%까지 배출량을 감소할 수 있음을 보였다. Yan et al.(2013)은 서비스 제공자의 비용을 최소화하기 위해 Simulated Annealing 알고리즘과 Monte Carlo 시뮬레 이션을 활용한 휴리스틱 방법론을 개발하였다. Martinez et al.(2015)는 운영수익의 최대화를 위한 수요 그룹 화 및 Mixed integer programming 방법을 사용한 모델을 개발하였고, Yu et al.(2015) 는 tabu 알고리즘을 활용 해 운영 비용과 주행 시간을 최소화하는 경로탐색 방법을 제안하였다. Hao et al.(2018)과 Ma et al.(2018)은 총 지연 시간을 최소화하기 위해 Tabu 알고리즘과 Artificial Bee Colony 알고리즘을 활용한 경로탐색 방법을 개발하였다. Czioska et al.(2019)는 사용자 집결지점의 영향에 주목하였는데, 수요의 기종점을 클러스터링하 여 이용자의 집결지점을 형성하고 이를 연결하는 경로를 최적화하는 경로탐색 방법을 제안하였다.
<Table 2>
Research on routing algorithm for DRT
| Reference | Vehicle (Single/multiple) | Demand distribution | Applied method | Objective |
|---|---|---|---|---|
| Saberi and Verbas(2012) | Multi-vehicle | One-to-many | CA model | emission minimization (transform of time-dependent model) |
| Yan etal.(2013) | Multi-vehicle | Many-to-many | Heuristic solution | cost minimization of operator |
| Martinez etal. (2015) | Multi-vehicle | Many-to-many | Clustering and MIP model optimization | maximize total demand and operational profit |
| Yu etal.(2015) | Multi-vehicle | Many-to-many | Bi-level optimization model with tabu | cost minimization / travel time minimization |
| Hao etal.(2018) | Single → multi vehicle | Many-to-many | Tabu Search-Artificial Bee Colony Algorithm | delay minimization |
| Ma etal.(2018) | Multi-vehicle | Many-to-many | Aartificial bee colony-shuffled frog algorithm | total delay and number of stops minimization |
| Czioska etal. (2019) | Multi-vehicle | Many-to-many | Clustering and neighborhood search algorithm | trade-off between the “service level cost” and the operating cost |
Czioska et al. (2019)와 같이 특정지점으로 승객들을 유도해 서비스하는 방법은 차량의 정차지점 수를 줄 이고 우회길이를 단축하여 총 서비스 시간을 줄일 수 있다는 장점이 있다. 또한, 차후 실제 도로 기반의 시 스템에 활용할 경우 선호되는 정차지점의 특성을 지정해, 보다 안전하거나 식별이 쉬운 정차지점을 우선하 여 수요를 그룹화 할 수 있고, 승객의 정확한 위치와 같은 개인정보의 노출을 방지하는 효과도 있다. 이러한 장점들을 활용하기 위하여 Martínez-Salazar et al.(2014)는 네트워크 그래프의 노드를 중심으로 수요를 그룹화 하였고, Stiglic et al. (2015)는 네트워크 영역에 배치된 정차지점들 중 승객에게 가장 가까운 지점을 찾아 배 정하는 방법을 사용하였으며, Goel et al.(2016)은 주요 도로 교차로의 일부를 정차지점으로 정하고 전체 네트 워크 범위를 서비스할 수 있는 정차지점 구성을 찾았다.
앞서 제시된 정차지점 설정 기반 연구들은 수요의 기점 혹은 종점만으로 수요지점 그룹을 형성하거나, 승 객의 차량 승하차 위치를 사전 지정된 정차지점으로 변경하는 형태로 정차지점의 수를 감소시킨다. 이 경우, 가까이 위치한 기종점들을 구분해 방문하거나 승하차 순서에 따라 동일한 정차지점을 반복 방문하여 우회경 로가 생길 수 있고, 차량용량을 충분히 활용하지 못할 수 있는 단점을 가지고 있다. 사용자의 수요지점들을 기준으로 기종점을 함께 클러스터링하여 처리한다면, 차량의 용량활용 및 경로선택 면에서 더욱 효율적일 수 있다.
본 연구에서는 클러스터링 방법을 이용한 경로탐색 알고리즘이 다양한 상황의 수요 시나리오에서 적합한 솔루션을 얻을 수 있음을 보인다. 잦은 정차로 인한 운행 시간 증가를 줄이기 위해 사용된 클러스터링 기술 기반의 다중차량 경로탐색 방법론은 차량 정차 지점의 수를 저감시키고 차량 용량 활용성을 높여, 고밀도 수 요를 갖는 대도시에서 높은 효율을 보인다.
Ⅲ. 클러스터링 기반의 다중차량 경로탐색 방법론
이번 장에서는 클러스터링을 활용한 휴리스틱 경로탐색과 경로개선 단계로 나뉜 다중차량 경로탐색 방법 론을 제안한다. 본 알고리즘은 (1)사전 정의된 수의 차량 각각의 초기 노선을 생성하는 초기경로 구성 과정, (2)초기경로의 정차지점을 수정하여 개선하는 과정, (3)이전 과정에서 처리되지 못한 수요를 경로에 추가하 는 미배정수요 삽입 과정의 3단계로 이루어진다.
1. 초기경로 구성 단계
각 방문지점이 가까이 위치했을 경우 많은 수의 기종점을 개별적으로 방문하는 것은 비효율적이다. 가까 운 위치의 기종점은 클러스터링하여 함께 서비스하면 차량의 정차지점 수를 줄이고, 총 소요시간을 절감할 수 있다. 한 차량의 초기경로를 구성하기 위해 수요위치 클러스터링과 클러스터 선택이 반복된다. 사전 정의 된 차량 수만큼 이 과정을 반복하여 여러 개의 경로를 생성한다. 수요위치 클러스터링과 순차적 클러스터 선 택 과정이 아래에 차례로 설명된다.
1) 수요위치 클러스터링
수요 기종점들의 그룹으로 이루어진 각각의 클러스터는 1개의 정차지점을 가지며, 이용자들은 클러스터의 정차지점과 각 수요의 기종점 사이를 도보로 이동한다. 정차지점은 클러스터의 중심점으로 정의되며, 클러스 터링 과정은 변형된 k-means 클러스터링 방법을 사용한다. 클러스터링과 클러스터 선택 과정은 연속적, 반복 적으로 진행되며, 생성된 클러스터들 중 다음 목적지를 선택한 뒤 선택되지 않은 나머지 수요지점들을 다시 클러스터링하는 순서로 반복된다. 클러스터링 과정에서는 각 수요의 기점과 종점 중 하나의 지점만 클러스 터링의 대상이 되는데, 이전에 선택된 경로에 포함되지 않았을 경우 기점이, 수요의 기점이 포함되었을 경우 종점이 클러스터링의 대상이 된다.
클러스터링의 대상이 되는 수요 지점들을 클러스터링하는 과정은 변형된 k-means 클러스터링 방법을 사 용하며, <Fig. 2>와 같이 나타난다. 먼저 임의의 클러스터 중심점들이 정해지고, 각 기종점들은 가장 가까운 클러스터에 할당된다. 클러스터 중심점은 해당 클러스터에 할당된 기종점들의 중심점으로 갱신된다. 클러스 터 중심점들은 차량경로의 정차지점으로 간주되므로 각 기종점에서 클러스터 중심까지의 거리는 사용자의 도보거리를 의미한다. 특정 사용자의 도보거리가 사전 정의된 제약조건보다 길 경우, 해당 사용자의 수요 지 에 새로운 클러스터 중 심점을 생성하고, 각 기종점들을 가장 가까운 클러스터에 다시 할당한다. 모든 기종 점들과 클러스터 중심점들이 이 도보거리 제약조건을 만족할 때까지 이 과정이 반복되고, 이 과정을 통해 클 러스터들의 개수가 정해진다.
2) 순차적 클러스터 선택
방문지점 클러스터링 후, 클러스터가 포함한 방문지점의 수에 따라 클러스터의 점수가 결정되며, 가장 높 은 점수의 클러스터가 차량경로의 다음 목적지로 선택된다. 순차선택을 위한 클러스터의 점수는 다음 표현 식을 따른다.
PC, DC 는 클러스터 C가 포함한 수요의 기점과 종점의 수, cap은 차량용량을 의미한다. occC 는 경로 R에 기점이 포함되었지만 종점으로의 방문이 결정되지 않은 수요의 수이며, 즉 차량이 클러스터 C에 도달하였을 때 탑승객의 수와 같다. 탑승객들의 평균 차량점유율을 일정수준으로 유지하기 위해 클러스터에 포함된 기점 과 종점의 수는 차량에 탑승한 승객 수에 따른 가중치를 부여받는다. α 는 탑승객 수에 따라 기점 혹은 종점의 선택에 가중치를 부여하기 위한 계수이다. 차량에 탑승해 있는 승객의 수가 많으면 α 의 값이 작아지고, 종점 을 많이 포함한 클러스터에 큰 점수를 부여하여 하차가 많은 클러스터를 우선하게 된다. 반대로 차량의 탑승객 수가 적으면 α 의 값이 커지고, 기점을 많이 포함한 클러스터를 우대하여 선택, 방문하게 된다.
차량의 이동거리, 용량제한, 우회수준은 클러스터의 선택에 제약조건으로 작용한다. 우회수준은 지나온 경 로의 마지막 진행 방향을 기준으로 대상 클러스터가 위치한 지점까지의 각의 크기를 의미하며, 그 크기가 π /2보다 커질 때 차량은 진행방향을 반대로 바꾸어 되짚어 주행하게 된다. 차량의 경로가 특정 지역을 왕복하 며 맴도는 현상을 방지하기 위하여 우회 수준은 π/2 이내로 제한한다. 특정 거리범위 내에 존재하는 클러스 터 중 승하차 승객의 수가 차량의 용량제한을 충족하고 진행경로의 방향전환이 π/2 이내인 클러스터가 다음 목적지의 후보로 간주되며, 후보 클러스터 중 점수가 가장 높은 클러스터가 다음 목적지로 선택된다.
2. 경로개선 단계
초기경로는 미리 정해진 수의 경로를 순차적으로 구성하는 과정이므로, 먼저 생성된 경로에 많은 수의 승 객이 배정되거나 나중 생성된 경로의 우회가 클 수 있다. 이러한 초기경로를 개선하기 위해 방문지점을 인접 한 경로와 비교하여 더 나은 경로를 탐색한다. <Fig. 3>은 초기 경로 구성이 완료된 경로 a, b와 우회비용이 큰 클러스터 쌍을 대상으로 경로를 개선하는 과정이다. 붉은 색으로 표시된 클러스터 쌍은 경로 b에 배정되 었으나 우회비용이 큰 클러스터 쌍으로, 앞서 방문하는 클러스터를 구성하는 기점에 대응하는 모든 종점이 후에 방문하는 클러스터에 해당한다. 이 경우 클러스터 쌍을 함께 다른 경로로 재배정하여 기존의 경로가 우 회비용이 큰 방문지점을 지나지 않도록 할 수 있다. 우회비용이 큰 클러스터 쌍을 다른 최적경로로 옮겨 총 차량이동거리를 줄이는 것을 경로개선 과정의 목표로 한다.
3. 미배정수요 삽입 단계
다중차량 경로탐색의 마지막 과정으로, 서비스 경로에 배정되지 못한 수요들을 경로에 추가하여 서비스되 는 수요의 비율을 증가시킨다. 임의의 경로 R에 기점 i와 종점 j를 가지는 수요가 추가될 때 발생하는 우회 경로 비용은 아래 식 (4)와 같이 산정되고, 식 (5)와 같이 최저 우회비용을 가지는 경로 R* 을 구한다.
기점 i와 종점 j를 가지는 수요의 경로 R* 에 대한 우회경로 비용이 사전정의 된 기준을 만족시키는 경우 미배정수요가 경로 R* 에 추가된다. <Fig. 4>는 위 식에 따른 우회경로 비용 산출을 통해 미배정수요가 경로 에 추가되는 과정이다. 두 경로 a, b 각각에 대해 미배정수요의 기점과 종점의 우회비용을 산출하고, 최저 우 회비용을 갖는 경로 a에 수요가 추가 배정된다. 사전 정의된 총 주행시간이 초과되지 않는 범위 내에서 모든 미배정수요들에 대해 이 과정이 반복된다.
Ⅳ. 방법론 평가
1. 평가지표 및 시나리오 설정
이번 장에서는 제안한 차량경로탐색 방법론을 평가하기 위한 지표와 기본 시나리오 설정을 설명한다.
1) 평가 지표
각 시나리오는 서비스 비율, 평균 도보시간, 평균 우회시간, 차량 운송거리 비율로 평가된다. 서비스 비율 은 사용된 차량경로탐색 방법론으로 서비스가 완료되는 승객 수와 서비스를 요청한 승객 수의 비율로 산정 된다. 평균 도보시간은 수요의 기종점과 차량 정차지점을 오가기 위한 거리와 일정한 도보속도로 산정된다. 평균 우회시간은 승객의 기종점을 직접 승용차로 이동했을 때의 소요시간과 차량경로탐색 방법론을 통해 서 비스된 경로로 이동했을 때의 소요시간의 차이다. 차량 운송거리 비율은 총 차량 주행거리 대비 총 차량 운 송거리의 비율이며, 총 차량 운송거리는 승객이 탑승한 상태로 운행한 이동거리를 의미한다. 이는 비효율적 인 공석주행의 비율이 얼마인지 확인 할 수 있는 지표이다.
<Table 3>
Evaluation indicator
| Indicator | Definition |
|---|---|
| Service ratio | Ratio of the number of trips that the service is completed to the total number of trip generated |
| Average walking time | Average time to walk to and from the point of demand and vehicle stop |
| Average de tour time | Time difference between directed trip and served trip by vehicle routing algorithm |
| Total transport distance ratio | Ratio of total distance driven with passengers to the total vehicle travel distance |
2) 시나리오 및 파라미터 설정
실험환경은 사전 예약 수요들로 구성된 1시간 단위의 서비스로 정의되었다. 시스템은 사전 예약된 수요에 대해 1시간동안 운행되는 경로를 할당한다. 사용된 기본 수요 시나리오는 3000x3000(m2)의 네트워크에서 무작 위로 생성된 수요이며, 무작위성으로 인해 가까운 거리의 이동 요청이 발생하지 않도록 수요 기종점간의 최소 거리는 600m로 제한한다. 출발 및 도착 차고지의 위치는 네트워크의 중앙인 (1500m, 1500m) 로 설정되었고, 도 로 네트워크는 250m 거리로 정의된 격자 형태이다. 차량 및 경로의 수는 4대, 차량용량은 15인승이며, 차량 주행 속도와 승객 보행속도는 30km/h 와 4km/h이다. 수요위치 클러스터링 시 승객의 최대 도보 허용 시간은 3분, 도보 허용 거리는 200m로 제한하였다. 또한, 수요밀도에 따른 결과 변화를 살펴보기 위해, 네트워크의 승객 수를 20 명에서 300명까지 변화시키며 수요밀도에 따른 결과를 확인한다. 알고리즘 과정의 무작위성으로 인한 영향을 최소화하여 경향성을 확인하기 위하여, 한 시나리오에 대한 20회 반복수행 결과의 평균값을 구한다.
상기 시나리오 설명 및 파라미터 설정에 따르면, 평가 환경은 다음과 같다. 3000x3000(m2) 크기의 격자 형 태의 네트워크에서 1시간 범위로 예약된 승객의 요청을 수행하는 차량 경로를 산출한다. 승객은 최대 200m 이내의 거리에 생성되는 승차 지점에서 배정된 차량에 탑승하고, 같은 거리 이내에 도착 지점이 있는 하차 지점까지 이동한다..
2. 평가 결과
본 연구에서 제안한 방법론의 성능평가는 첫째, 3단계로 구분된 과정의 진행상황에 따른 순차적 변화, 둘 째, 수요 시나리오 변화에 따른 비교, 셋째, 기존의 알고리즘과의 비교로 이뤄진다.
1) 경로개선 및 미배정수요 삽입 단계의 효과 분석
초기경로 구성, 경로개선, 미배정수요 삽입 과정 진행에 따른 순차적 변화과정을 살펴봄으로서, 다중경로 탐색 과정의 중간결과를 평가하고 각 과정의 영향을 확인한다. 각 과정에 따른 변화를 살펴보면 수요밀도가 증가함에 따라 서비스 비율이 감소하지만 승객의 평균 도보시간은 1.5분에서 크게 변화가 없으며, 미배정수 요 삽입 단계에서 차량의 우회시간이 크게 증가함을 알 수 있다. 또한, 차량 운송거리 비율 또한 1에 가까움 을 확인할 수 있다. 차량의 수가 4대로 고정되었기에 최대 수용할 수 있는 승객의 수가 초과된 이후 서비스 비율이 계속 감소하고 우회시간이 늘어나게 된 것으로 해석된다.
2) 수요 시나리오에 따른 알고리즘 성능 비교
수요패턴 차이에 따른 알고리즘의 성능을 비교하기 위해 총 3가지의 서로 다른 수요패턴을 표현하는 시나 리오로 경로생성 결과를 확인한다. 첫 번째 시나리오는 정해진 네트워크 안에서 무작위 위치로 생성된 수요 이고, 두 번째 시나리오는 집중된 기점과 분산된 종점으로 이루어져 한 지점으로부터 흩어지는 수요패턴을 묘사한다. 세 번째 시나리오는 통일된 방향성을 가진 수요로 구성되는데, 수요의 방향성 특성이 잘 보이도록 하면서 수요밀도가 유지되도록 하기 위하여 정사각형 형태 네트워크를 같은 넓이의 직사각형 형태로 조정하 였다. 수요 시나리오의 세부 사항은 <Table 4>과 같다.
수요 시나리오에 따른 서비스 성능을 비교하였을 때, 서비스 비율 혹은 차량 운송거리 비율의 결과는 유 사하다. 평균 도보시간 및 평균 우회시간은 밀집된 수요형태를 보이는 시나리오 2에서 가장 짧았고, 시나리 오 1과 시나리오 3의 결과는 유사한 값으로 나타났다. 수요밀도가 20(pax/km2) 이상으로 비교적 높은 경우에 시나리오 3의 평균 우회시간이 길어지는데, 이는 미배정수요 삽입 단계에서 방향성을 가진 수요가 경로에 추가되며 반대 방향으로 왕복운행하는 구간이 생기기 때문이다.
3) 기존 알고리즘과의 성능 비교
본 논문에서 제안한 차량경로탐색 방법론을 기존의 알고리즘 1) two-index formulation (Furtado et al., 2017), 2) Shared Demand Responsive Transportation problem with Meeting Point(SDRT-MP)(Czioska et al,, 2019)과 비교 한다. two-index formulation model은 Mixed-integer programming을 이용한 차량경로탐색 방법으로, 각각의 방문 지점을 잇는 경로를 선택하는 integer programming의 해를 구하는 방법이며, 본 논문에서는 Genetic algorithm 을 통해 MIP의 해를 구하였다. 수요가 발생한 위치에 차량이 직접 방문하기 때문에 사용자의 도보시간은 서 비스된 모든 수요에 대하여 0이다. SDRT-MP는 가까운 수요들의 집결지점을 설정하고 집결지점을 오가는 차 량의 경로를 최적화하는 방법이다. 요청한 모든 수요에 서비스하는 것이 조건이므로, 서비스 비율은 1로 고 정된다.
<Fig. 7>에서 보인 것과 같이 각 지표에 따른 결과를 비교하였다. 그 중 two-index formulation 방법은 수요 위치에 차량이 직접 방문하기 때문에 모든 수요에 대해 사용자 도보 시간이 0이고, SDRT-MP는 요청한 모든 수요에 서비스하므로 서비스 비율이 항상 1로 나타난다. 알고리즘의 계산 속도를 비교하기 위해 계산시간을 확인하였으나 SDRT-MP의 경우 Czioska의 논문에서 사용된 네트워크 크기와 본 논문에서 제안된 알고리즘 및 two-index formulation 방법으로 구현한 것의 차이가 커서, 제안된 알고리즘과 two-index formulation 방법의 계산속도만 비교하였다.
제안된 알고리즘은 two-index formulation model과 비교하였을 때 수요밀도 증가에 따른 서비스 비율 감소 가 36.5%에서 66.7% 가량 작게 나타나며, 차량 운송거리 비율이 높아 차량용량의 활용성이 좋지만, 수요밀도 가 증가할수록 평균 우회시간이 크게 길어진다. 또한 SDRT-MP와 비교하였을 때, 제안된 알고리즘의 평균 도보시간은 1.5분, SDRT-MP의 평균 도보시간은 5.9분에서 8.5분 정도로 약 4.4분에서 7분 정도의 차이를 보 인다. 제안된 알고리즘의 차량 운송거리 비율은 1에 가까운 반면 SDRT-MP의 차량 운송거리 비율은 0.5 내 외의 값을 보여 제안된 알고리즘의 차량용량의 활용성이 높음을 알 수 있다. 계산속도의 경우, two-index formulation 방법에 비해 본 논문에서 제안한 차량경로탐색 방법론의 계산속도가 현저히 빠름을 확인할 수 있다.
Ⅴ. 결 론
본 연구에서는 수요응답형 대중교통 차량의 용량활용 및 서비스 비율을 높이는 것을 목적으로 하는 클러 스터링 방법 기반의 휴리스틱 경로탐색 알고리즘이 제안되었다. 제안된 알고리즘은 수요 기종점들의 방문순 서를 고려해 수요위치를 클러스터링하여 초기경로를 구성하고, 우회거리 비교를 통해 경로를 수정하며, 추가 조건을 만족하는 미배정수요를 가능한 경로에 추가해 초기경로를 개선한다. 이 경로탐색 방법론은 서비스 비율, 평균 도보시간, 평균 우회시간, 차량 운송거리 비율, 계산 소요시간으로 평가되었다. 제안된 차량경로 탐색 알고리즘의 성능은 수요 시나리오에 따라 달라지는데, 가까운 위치의 수요들을 함께 서비스하는 클러 스터링 기반의 방법론이기에 집중된 수요위치를 가지는 수요패턴에서 승객의 평균 도보시간 및 우회시간이 짧은 결과를 보였다. 기존의 다른 알고리즘들과 비교하였을 때는 차량 운송거리 비율이 높게 유지되어 차량 용량 활용도가 높고, 수요밀도 증가에 따른 서비스 비율 감소가 낮은 경향성을 보였다. 또한, 제안된 알고리 즘의 계산 시간이 다른 알고리즘에 비해 현저히 짧은 결과를 보였다.
본 논문에서 제안된 알고리즘은 비교적 빠른 계산 속도를 가지며 수요밀도 변화에 따른 서비스품질 변화 민감도가 낮으므로, 보다 효율적이고 안정적인 경로를 신속하게 생성할 수 있으며 실제 상황에서 더 넓게 활 용할 수 있다. 이러한 특성에 따라 수요 패턴의 변화에 대응하여 유동적인 경로로 운영 가능하며, 신속한 서 비스 제공 및 솔루션 수정이 필요한 도시 지역의 대중교통체계를 위한 기술로서 활용될 수 있다. 그러나 본 연구에서는 수요 시나리오 패턴, 수요밀도의 크기 변화 외에 차량 수, 클러스터 크기 제약 등의 파라미터는 지정된 값으로 실험하였기 때문에 시스템의 최적화가 충분히 이루어지지 못했고, 경로개선 과정에서 서비스 비율 및 우회거리를 기준으로 사용하여 사용자 입장의 비용이 충분히 고려되지 못했다는 제한점이 존재한 다. 또한 일정 범위 내의 시간에 대한 예약 수요로 경로를 산출하므로 실시간으로 발생하는 수요에 대응할 수는 없고, 수요 요청 시각의 범위가 넓다는 한계점이 있다. 이러한 한계점을 해결하기 위해 수요 발생 시각 을 포함한 3차원 클러스터링 기술을 적용하여 실시간 수요에 대응하고, 이를 통해 사용자 편의성을 증대시 킬 수 있는 알고리즘의 개발이 필요하다.
