Journal Search Engine

to

Search Advanced Search Adode Reader(link)
View PDF Download PDF Export Citation Korean Bibliography PMC Previewer
The Journal of The Korea Institute of Intelligent Transport Systems Vol.21 No.1 pp.17-34
DOI : https://doi.org/10.12815/kits.2022.21.1.17

Development of a Model for Dynamic Station Assignmentto Optimize Demand Responsive Transit Operation

Jinju Kim*, Soohyuk Bang**
*Center for Connected & Automated Driving Research, Korea Transport Institute
**Corresponding author: Associate Research Fellow, Autonomous Collaborative Driving Research Center, Korea Transport Institute
† Corresponding author : Soohyuk Bang, sbang@koti.re.kr
25 November 2021 │ 7 December 2021 │ 22 December 2021

Abstract


This paper develops a model for dynamic station assignment to optimize the Demand Responsive Transit (DRT) operation. In the process of optimization, we use the bus travel time as a variable for DRT management. In addition, walking time, waiting time, and delay due to detour to take other passengers (detour time) are added as optimization variables and entered for each DRT passenger. Based on a network around Anaheim, California, reserved origins and destinations of passengers are assigned to each demand responsive bus, using K-means clustering. We create a model for selecting the dynamic station and bus route and use Non-dominated Sorting Genetic Algorithm-III to analyze seven scenarios composed combination of the variables. The result of the study concluded that if the DRT operation is optimized for the DRT management, then the bus travel time and waiting time should be considered in the optimization. Moreover, it was concluded that the bus travel time, walking time, and detour time are required for the passenger.


Demand Responsive Transit , Dynamic Station , Multi-objective Genetic Algorithm

수요대응형 모빌리티 최적 운영을 위한 동적정류장 배정 모형 개발

김 진 주*, 방 수 혁**
*주저자 : 한국교통연구원 자율협력주행연구센터 연구원
**교신저자 : 한국교통연구원 자율협력주행연구센터 부연구위원

초록


본 논문은 수요대응형 모빌리티 이용객의 출발지와 목적지까지 최적 경로 산정을 위한 동 적정류장 배정 모형을 개발하였다. 여기서 최적화를 위한 변수로는, 운영자 측면에서 버스통행 시간과 이용자 측면에서 서비스 이용 시 추가로 소요되는 정류장까지 도보시간 및 대기시간, 우회시간을 사용하였다. 미국 캘리포니아주 애너하임과 주변 도시를 포함하는 네트워크를 대 상으로 승객이 예약한 시종점에서 접근 가능한 동적정류장 리스트를 산정하고 K-means 클러 스터링 기법을 이용하여 시종점 그룹들을 각기 차량에 배정하였다. 버스통행시간과 이용자 추 가소요시간을 최소화하는 동적정류장 위치 및 버스노선 결정을 위한 모형을 개발하고 다목적 최적화를 위해 NSGA-III 알고리즘을 적용하였다. 최종적으로, 모델의 효용성을 평가하기 위해 이용자 추가소요시간 간의 변수를 조정하여 7개의 시나리오를 설정하였고 이를 통해 목적함수 의 타당성을 분석하였다. 그 결과, 운영자 측면에서는 버스통행시간과 승객 대기시간만 고려한 시나리오가, 이용자 측면에서는 버스통행시간, 도보시간, 우회시간을 적용한 시나리오가 가장 우수하였다.


수요대응형 모빌리티 , 동적정류장 , 다목적 최적화

    Ⅰ. 서 론

    수요대응형 모빌리티는 스마트시티 국가 시범도시에 적용되어있는 8개 서비스 중에 하나로, 새로운 대중 교통의 하나로 각광을 받고 있다. 흔히, 수요대응형 셔틀 또는 버스로 불리며, 호출형 택시와 기존 지선버스 의 각각의 단점을 최소화하고 장점을 혼합한 모빌리티이다. 전자는 탑승수요에 따른 택시 호출을 통해 비교 적 탑승 장소에 제한 없이 이용할 수 있으며, 출발지부터 목적지까지 정해진 경로가 아닌 운전자 판단 또는 내비게이션 안내를 바탕으로 교통 및 도로 상황에 적절한 경로로 이동한다. 하지만, 택시는 합승은 불가하여 1회 운행 시 하나의 탑승수요 (출발지-목적지)만 수용된다. 지선 버스는 1회 운행 시 다양한 탑승수요 (출발 지- 목적지)가 반영 가능하나, 정해진 정류장에서만 탑승 가능하며, 정해진 경로로만 주행한다. 수요응답형 모빌리티는 정해진 노선이 없어 교통 및 도로 상황, 탑승수요에 따라 최적의 경로로 운행 가능하며, 동시에 복수의 탑승수요를 대상으로 서비스를 제공할 수 있다. 하지만, 수요응답형 버스의 물리적인 크기 또는 1회 탑승 시 인원이 택시보다 크고 많아서 탑승 장소의 제약이 다소 있지만, 고정된 노선이 없는 관계로 모든 부 근의 지선버스 정류장을 활용 가능하며, 교통류 방해를 최소로 할 수 있는 물리적 공간이 확보되는 곳에 정 류장을 지정할 수 있어 지선버스보다 접근성이 우수하다. 수요응답형 버스가 정차하는 정류장은 운행 시마 다 탑승수요에 따라 정차하는 정류장이 동적으로 변경되므로 본연구에서 동적정류장으로 칭한다.

    수요대응형 모빌리티는 주로 교통 소외지역이나, 비교적 작은 지역 규모를 대상으로 운영되고 있으며, 탑 승을 원하는 승객이 스마트폰 애플리케이션을 통해 승차와 하차를 원하는 정류장을 직접 입력하여 요청하거 나, 탑승 요청을 한 지점에서 가장 가까운 정류장을 안내한다. 현재 이와 같이 운영되고 있는 수요대응형 모 빌리티의 주된 불편 사항은 정류장에서 긴 대기시간이다. 이를 위해서는 버스의 운행 시간을 최소화하는 것 에 더해, 승객이 서비스를 이용하기 위해 소요하는 시간인 도보 시간, 대기시간 등을 고려하여 운영자 측면 에서 동적정류장을 선정하여 승객에게 제공하는 것이 필요하다.

    수요대응형 모빌리티 운영에 관련된 연구를 살펴보면, 많은 논문에서는 수요대응형 서비스 운영자의 관점 이나 서비스를 제공받는 이용자의 관점에서 목적함수를 설계하고 최적의 경로 산정 연구를 수행했다. 수요 대응형 서비스 운영자 측면에서는 운영된 버스 대수, 버스 운행 시간 및 노선 길이, 연료비, 온실가스 배출량 등 운영비용 최소화를 목적으로 버스 경로를 산정하였다. 혹은 Time Window를 함께 고려하거나(Dumas et al., 1991;Diana et al58., 2004;Mahmoudi and Zhou, 2016), 수요를 동적으로 설계(Savelsbergh and Sol, 1998)하 여 운영비용 최소화하는 연구를 진행하였다. 이와 같은 선행연구에서는 Branch-and-cut(Cordeau, 2006)이나 Heuristic clustering algorithm 등 여러 휴리스틱 알고리즘을 적용하여 이용객을 배정하고 운행노선을 산정 (Dondo and Cerdá, 2007)하는 연구도 수행되었다. 이외에도 수요대응형 서비스를 제공할 때 최소한의 버스를 이용하여 배차간격과 노선을 산정하거나(Diana et al., 2006) 수요대응형 서비스 제공시 발생하는 지연시간을 최소화(Alonso-Mora et al., 2017)하는 연구들이 수행되었다. Alonso-Mora et al.(2017)은 차량과 수요의 위치를 반영하여 10인승 미니버스에 승객들을 배정하고 최적의 경로를 산정하는 연구를 수행했다. 이때 제한조건으 로 차량 배차간격, 용량, 대기시간, 운영비용 간 균형을 맞췄다. Wang et al.(2018)은 수요대응형 서비스를 제 공하는 지역을 여러 개의 존으로 분할하고 동일한 존의 승객들에게 동일한 서비스를 제공하여 최적의 수요 대응형 모빌리티 시스템 운영방안을 연구했다.

    이용자 관점에서 최적의 수요대응형 버스 경로 산정 연구에서는 제공하는 서비스의 품질을 평가하며, 그 항목으로는 이용객의 대기시간, 수용 가능한 이용객 수, 승객의 차량 내 통행시간 등이 있다. Bodin and Sexton(1983)과 Calvo and Colorni(2007)은 탑승 시간 제약을 두었고 이용객의 대기시간을 토대로 서비스의 질 을 산정하고 이를 최대화하는 버스 노선 산정 연구를 수행했다. 반대로 대기시간이 길어짐에 따라 이용객의 만족도는 감소하기 때문에 이를 최소화 하거나(Coslovich et al., 2006) 승객의 차량 내 통행시간도 고려하여 이를 최소화하는 연구(Wang, 2017)도 진행되었다. Sun et al.(2018)은 지하철 환승과 같은 교통상황을 고려하 여 승객들의 통행시간을 최소화하는 지선버스 운영 방법을 연구하였다. 버스는 승객들을 픽업하여 지하철 역에 내려주되 지하철 운행 시간표를 고려하여 대기시간을 최소화함으로써 승객 이동시간을 최소화하는 버 스 노선을 산정했다. 이용자 입장에서 수요대응형 서비스를 제공할 경우 선행연구 대다수에서는 대기시간을 가장 많이 고려했다. 이러한 대기시간을 산정하기 위해서는 Time Window의 제약조건을 두고 긴 대기시간이 발생할 경우 페널티를 부과하는 방식으로 진행했다.

    앞서 선행연구들에서는 수요대응형 버스의 노선을 산정하는데 있어 운영자와 이용자의 관점에서의 목적 함수를 개별적으로 적용했다는 한계가 있다. 따라서, Kuah and Perl(1989)은 버스 운영비용과 승객의 대기시 간을 함께 최소화하는 연구를 처음으로 제시하였고, Fan and Machemehl(2006)은 서비스에 불만족된 수요를 비용화 하고 운영자와 이용자 비용을 같이 최소화하는 최적의 버스 경로를 산정하는 연구를 수행했다. 위 연 구들은 운영자 입장이나 이용자 입장을 단일목적 최적화(Single-objective Optimization) 문제로 설계되었으며, 이로 인해 버스 경로가 길수록 이용자의 접근성이 좋아질 수 있다는 상충 가능성을 제대로 고려하지 않고 있다. 따라서 운영자 입장의 버스 운영시간과 이용자 입장의 대기시간은 특성이 다르며, 둘 사이 간 Trade-off를 통한 최적의 방안을 도출할 필요가 있다.

    이를 보완하는 차원으로 운영자 입장과 이용자 입장을 분리한 다목적 최적화(Multi-objective Optimization) 모형을 설정한 연구들이 제시되었다. 버스 운행 거리 최소화와 서비스를 제공받는 이용객 수 최대화(Horn, 2002;Pan et al., 2015) 연구나, 운영 차량 대수 및 운행 거리 최소화(Chiang and Hsu, 2014), 버스 운영비용과 승객 대기시간 최소화(Arbex and da Cunha, 2015) 등 다양한 관점의 연구들이 수행되었다. 이외에도 차량의 공석 운영 최소화와 차량 대수 최소화 모형을 Hybrid-MOGA에 적용하여 경로 산정 연구(Chebbi and Chaouachi, 2016)를 진행했다. Dou et al.(2017) 역시 유전알고리즘과 Frank-Wolfe 알고리즘을 융합한 하이브리 드 알고리즘으로 승객 환승 시간과 차량 운행시간 최소화 문제를 설계했고, 버스 운영회사의 수익을 극대화 하고 버스 탑승 비용을 최소화(Parvasi et al., 2017)나, 버스통행시간 최소화 및 도보 접근성 최대화(Taplin and Sun, 2019), 버스 운영시간 및 이용자 이동시간 최소화(Lee et al., 2019) 등의 연구에서 메타휴리스틱 기법을 적용하였다. Chen et al.(2016)은 통행 지연시간 최소화와 에너지 효율성을 극대화하는 전기버스 배차간격과 버스 경로 산정 연구를 진행했다. 이처럼 운영자 입장과 이용자 입장으로 각각의 목적함수를 설정한 연구에 서는 단일목적 최적화보다 복잡해졌으나 메타휴리스틱 기법을 적용함으로써 다양한 연구가 수행되었다. 그 러나 수요대응형 버스의 노선에 집중되어 있으며 이용객들의 승하차 위치에 대해서는 대다수가 고려하지 않 는다는 한계가 있었다. Qiu et al.(2014)은 시점과 종점이 정해져 있고, 이를 지나가는 기저 노선이 있을 때 버 스에 탑승 요청을 받아들이면 승객의 위치에 동적정류장이 생성되고, 거절된 경우 정류장이 생성되지 않는 식으로 노선 운행 연구를 수행했다. 이때 생성된 동적정류장은 기저 노선에 벗어날 수 없으며 노선 인근 수 요만을 채택한다는 점에서 한계가 존재했다. 더욱이, 노선 및 경로 최적화에 초점이 맞추어져 있어서, 시종 점이 실제 승객 예약 출발지-목적지 위치가 아닌 네트워크 상의 노드나 링크 위로 설정되어 충분한 현실 반 영이 부족하여, 정류장까지의 거리 및 도보시간 등 접근성에 대한 요소가 최적화 과정에 포함되어 있지 않았다.

    공통적으로 대다수의 기존연구가 버스 최단 경로를 산정할 시, 도로 상황에 따른 교통혼잡을 고려하고 있 지 않다는 한계점이 있었으며, 또한 수요가 노드에서 발생하여 버스 주정차가 불가능한 교차로 지점에서 이 용객이 승하차한다는 점에서 현실과 괴리감이 있었다. 그리고, 다양한 최적화 항목 또는 변수들을 적용하였 지만, 이 중 각 조합에 따른 비교 분석 결과는 제시되지 않았다.

    따라서, 본 연구의 목적은 운영자와 이용자 측면을 같이 고려하되, 다목적 최적화를 수행하였으며, 승객의 예약 위치와 예약 목적지를 기반으로 최적의 동적정류장 선정하는 알고리즘을 개발하는 것이다. 이 과정에 서, 동적정류장이 네트워크 상에서 노드에 해당되는 교차로처럼 주정차가 어려운 지점이 아닌 실제 승객이 승하차 가능한 지점을 제시하였으며, 승객의 시종점이 예약 출발지와 목적지 위치 또한 네트워크의 노드나 링크 위가 아닌 지도상의 임의의 지점이 되도록 하였다. 다시 말해, 승객이 도로상의 정류장을 출발지와 목 적지로 설정하는 것이 아닌, 현재위치나 집 또는 회사와 같이 특정 위치를 시종점으로 선택한다. 이처럼 버 스와 이용객의 위치 정보를 바탕으로 수요대응형 버스에 탑승하는 승객을 배정하고, 승객이 접근 가능한 동 적정류장 중 이용할 동적정류장을 선정한 후, 선정된 동적정류장을 토대로 수요대응형 버스의 노선을 산정 하고자 한다. 최종적으로는 이용자들이 예약 출발지 및 목적지 부근 정류장에서 산정된 노선에 맞게 순서대 로 각각 승하차가 이루어진다. 본 연구는 선행연구의 한계점이었던 도로 상황을 고려하여 사용자 평형으로 기존 교통수요를 배정하고, 운영자 측면에서 버스의 통행시간과 이용자 측면에서 서비스 이용 시 추가적인 소요시간을 각각 최소화하는 목적함수를 구축한다. 이용자 추가소요시간으로는 승객이 승하차할 정류장까지 의 도보시간, 차량이 도착할 때까지 대기시간, 수요대응형 버스가 다른 정류장을 경유함으로 인해 생기는 우 회시간을 고려하였다. 그리고 버스통행시간과 이용자 추가소요시간 변수별 조합으로 구성된 시나리오를 설 정하고 메타휴리스틱 기법인 NSGA-III(Non-dominated Sorting Genetic Algorithm-III)을 적용하여 가장 최적의 모형을 선정하고자 한다. 시나리오별 평가는 파레토 해의 분포도 분석과 다목적 최적화에서의 수렴성과 다 양성 측면에서 비교 분석하여 상황별 모형에 적용될 변수를 제시하였다.

    2장에서부터는 다목적 최적화의 입력자료가 되는 네트워크, 동적정류장, 차량 및 승객 배정에 대해 설명 하며, 3장에서는 동적정류장 선정 알고리즘에 적용할 모형을 개발하고, 4장에서는 개발된 모형을 바탕으로 진행할 최적화기법을 제시한다. 5장에서 운영자 및 이용자 측면의 요소간 조합으로 구성된 시나리오들에 대 해 최적화한 결과를 도출하고, 마지막으로 6장에서 결론 및 향후 연구내용을 설명한다.

    Ⅱ. 입력자료 설정

    1. 네트워크

    본 연구에서 미국 캘리포니아주 남부 애너하임과 주변 10개 도시를 아우르는 면적 약 222.75km2의 네트 워크를 사용하였다 (Ban. J. and Jayakrishnan. R; Transportation Networks for Research Core Team). 해당 네트워 크는 <Fig. 1>과 같이 416개의 노드와 914개의 링크로 구성되어 있으며, 38개의 존 센트로이드에서 104,694 대/일의 교통수요가 발생한다.

    <Fig. 1>

    Anaheim Network

    KITS-21-1-17_F1.gif

    2. 동적정류장

    수요대응형 버스의 정차지점에 대한 물리적 한계와 주정차 금지구역 (고속도로, 고속도로 진출입로, 교차 로 등)을 반영하여 동적정류장을 설정하였다. 교통영향분석·개선대책수립 지침(2013)에 따른 도시형 버스정 류장의 권장 이격거리가 400m임을 감안할 때, 일반버스 대비 수요대응형 버스의 크기 및 최대 승차인원을 고려하여 동적정류장간 거리를 300m로 양방향의 링크 위에 배치하였으며, 동일한 방향의 경우에 정류장 선 택에 따라 최소 5분의 충분한 걷는 시간의 차이가 나도록 하였다. 여기서, 이용자의 도보 속도는 4km/h로 가 정하였다. 이용자가 정류장까지 최대 10분까지 걸어서 이용할 수 있다고 판단하여, 서비스 예약 시 시점과 종점에 반경 500m 이내의 이용 가능한 동적정류장 리스트 D 가 선정하였다. 이용 가능한 동적정류장 개수는 시종점 별로 다르며, 최종적으로 이용객은 시점 동적정류장 o와 종점 동적정류장 d에 배정된다.(o,d∈D )

    3. 차량 및 승객 배정

    제한된 버스 대수에서 효율적인 서비스 운영을 위해 K-means 클러스터링 기법을 사용하여 승객이 예약한 시종점에 대해 차량을 배정하였다. K-means 클러스터링은 비지도학습 기법으로, 유사한 특성을 지닌 데이터 끼리 K개의 그룹으로 분배하는데 우수한 성능을 지녀 그룹화 관련 연구에 널리 사용된다(Celebi et al., 2013). 본 연구에서는 예약된 시종점을 그룹화하기 위한 기준으로 면적인 요소인 행정구역(Council District)과 고속 도로 및 지선도로 구분한 블록 (Arterial District)을 함께 사용하였다. 이는 행정구역 단위는 도시의 규모에 따 라, 분배된 행정구역 개수에 따라 면적과 분포도가 불균형적인 모습을 보여 이를 보완하는 차원에서 블록단 위의 구역을 추가하여 고려하였다. 선적인 요소로는 네트워크의 4방위에 끝점(End Point)을 두어 각 점과의 거리를 제시하였다.

    본 장에서는 공간적으로 임의로 생성된 수요대응형 버스 탑승 예약 시종점 100건을 대상으로 기준인 면적 인 요소, 선적인 요소를 조합하여 클러스터링을 진행하였다. 차량 수용인원을 최대 10명을 가정할 때, 차량 대수, 즉 그룹 개수는 평균 재차율 100%인 10개와 평균 재차율 50%인 20개로 나누어서 진행하고, 실행회수 는 100회로 설정하였다. 클러스터링 성능을 비교하기 위해서는 각 그룹 중심점으로 그룹 내 시종점간의 거 리에 대한 평균 (Mean), 표준편차 (Standard deviation, Std), 최소값 (Min), 최대값 (Max)을 통해 버스에 배차된 이용자가 예약한 시종점들간의 밀집도를 비교하였고, 값이 작을수록 유사한 시종점으로 구성된 이용자끼리 배정되어 있음을 의미한다. 그 결과, <Table 1>와 같이 선적인 요소만 적용하고 차량이 20대였을 경우가 가 장 좋은 그룹화 성능을 보였고 <Fig. 2>와 같이 이용자의 시종점이 버스 (Bus ID)에 배정되었다. 따라서 본 연구에서는 선적인 요소만 적용하여 100건의 예약을 대상으로, 최대 차량 20대로 운영되는 상황에 대해서 최적의 동적정류장 선정 모형을 개발하였다. 실제 분석에서는 승객이 예약한 출발지를 시점으로 가정하고, 예약된 목적지를 종점으로 설정하였다. 이와 같은 클러스터링 진행 시, 그룹 개수에 따른 그룹화 성능에 대 한 세부적인 민감도 분석이 요구된다. 하지만, 본 연구는 각 차량에 배정된 시종점 주변의 최적 동적정류장 을 찾는 것이 주 목적이므로 해당 민감도 분석은 제외하였다.

    <Table 1>

    Passenger Assignment Result

    KITS-21-1-17_T1.gif
    <Fig. 2>

    Personal Time Diagram

    KITS-21-1-17_F2.gif

    Ⅲ. 동적정류장 배정 모형

    본 장에서는 입력자료들을 토대로 동적정류장 배정 모형을 구축하고자 한다. 설계모형은 차량의 통행시간 최소화와 이용객의 대기시간을 최소화하는 다목적 버스 정류장 시설입지 결정 문제에 입각하여 설계하였다. 네트워크에 배정될 전체 교통량 I 은 기존의 교통수요(Background Traffic) Ib와 수요응답형 버스(Demand Respond Transit, DRT) 서비스를 제공했을 시 이용하는 유발수요(Service Derived Traffic) Id로 구성되어 있으 며 고정되어 있다.(I = Ib+Id) Ib는 센트로이드 Nc의 시점 i에서 출발하여 종점 j에 도착하는 것을, 서비스 유발 교통 수요 Id는 동적정류장 시점 o에서 종점 d에 도착하는 것을 목적으로 하고 있다.(i,j ∈Nc, o,d∈D )

    모든 수요는 링크를 통해 이동하며 모든 링크의 집합을 A , 임의의 링크를 a(a∈A )라 했을 때 링크 a에서 의 교통량을 xa라 한다. 시점 i에서 종점 j로 이동하는 기존 교통수요가 지나가는 경로를 r이라 했을 때, Ib 에 해당하는 모든 경로의 집합을 R (r∈R , R ∈A )로 표현한다. 링크 a가 경로 r에 포함 여부는 파라미터 KITS-21-1-17_I1.gif 에 의해 결정되며 포함된 경우 1, 포함되지 않는 경우 0의 값을 부여한다.(Sheffi, 1985) 동일한 관점으로 동적정류장 o에서 d를 지나는 DRT 버스 b의 노선 p는 전체 노선 P (p∈P , P ∈A )에 포함되고 경로 p의 링 크 a의 포함 여부 변수 θ a , p o , d 역시 0, 1 두 가지의 값을 가진다.

    r = ∑ a ∈ A a × δ a , r i , j   ∀ r ∈ R , ∀ R ∈ A
    (1)

    p = ∑ a ∈ A a × θ a , p o , d   ∀ p ∈ P , ∀ P ∈ A
    (2)

    경로 r에 대한 기존 교통량을 f r i , j , 경로 p에 대한 DRT 서비스 유발 교통량은 f p o , d 이라 했을 때 링크 a에 대한 교통량 xa은 기존 교통량과 DRT 서비스 유발 교통량의 합을 의미하고 이를 수학적으로 표현하면 식 (3)과 같다.

    x a = ∑ i ∈ N c ∑ j ∈ N c ∑ r ∈ R f r i , j δ a , r i , j + ∑ o ∈ D ∑ d ∈ D ∑ p ∈ P f p o , d θ a , p o , d   ∀ a ∈ A , ∀ i , j ∈ N c ,   ∀ r ∈ R ,   ∀ o , d ∈ D , ∀ p ∈ P
    (3)

    통행시간은 교통량에 따라 혼잡이 발생하여 통행시간이 증가하는 경향이 있다. The Bureau of Public Roads Function(BPR함수)는 자유 통행시간 t0을 기준으로 링크용량 V 대비 교통량 x의 비율에 비례하여 통행시간 이 증가한다는 이론에 근거하며(United States, Bureau of Public Roads, 1964) 링크의 혼잡도를 잘 묘사하며 가 장 보편적으로 쓰이고 있다. BPR함수에 의거하여 링크 a의 통행시간은 t a ( x a ) = t a 0 ( 1 + B × ( x a V a ) p o w e r ) 식을 토대로 산정되며 여기서 t a 0 는 자유 통행일 때 링크 a에서의 통행시간을, Va 는 링크 a의 용량을 의미한다. 각각의 B 와 power는 링크당 파라미터를 의미하며, 통상적으로 B 의 값은 0.15, power의 값은 4를 사용한다. 설정된 통행시간 함수를 토대로 모든 수요는 Wardrop(1952)이 제시한 사용자 균형 원리 (User Equilibrium Principal : UE)에 따라 전체 통행시간 최소화를 목적으로 Frank-Wolfe 알고리즘을 적용하여 통행을 배정시켰 다. 사용자 균형 원리는 모든 이용객이 합리적인 의사결정을 하는 주체로서 통행시간이 적은 방향으로 이동 하되, 동일한 출발지에서 목적지로 이동하는 승객들은 모두 동일한 시간이 소요되어 전체 통행시간을 최소 화한다.

    a r g m i n ∑ a ∫ 0 x a t ( x a ) d x
    (4)

    본 연구에서는 DRT 버스통행시간과 이용자 추가소요시간을 최소화하는 다목적 최적화 연구를 수행하였 다. 먼저 버스통행시간은 버스 b가 노선 p에 따라 운영했을 때의 시간으로 모든 이용자가 승하차를 완료한 후 차고지 등으로 이동하는 시간은 포함되지 않는다. 버스노선은 외판원 순환 문제(Traveling Salesman Problem:TSP)을 통해 설계되며, 동적계획법(Dynamic Programming, DP)을 적용하여 버스통행시간이 최소화되 는 노선을 산정하였다. 여기서 버스는 승차 정류장에 먼저 도착한 후 하차 정류장을 방문해야 하고 버스 용 량은 탑승하는 이용객의 수를 넘길 수 없다. 버스 b에 배정된 이용객을 h이라 할 때 이용객의 차량 탑승 여 부는 파라미터 Zh에 의해 결정되며 버스 용량 Cb은 탑승할 이용객의 수를 넘길 수 없으며 전체 DRT 서비스 이용객의 수는 운행하는 버스의 용량보다 작다. 버스 운행 여부는 파라미터 Yb에 의해 결정되며 버스 k가 운행될 경우 Yk = 1, 그렇지 않다면 Yk = 0이다.

    ∑ h ∈ H h Z h ≤ C b
    (5)

    ∑ b ∈ B ∑ h ∈ H h Z h ≤ ∑ b ∈ B C b Y b ∀ h ∈ H , ∀ b ∈ B
    (6)

    버스 b는 이용객들 모두를 탑승시킨 후 목적지에 도착하는 노선으로 운행되며 현위치 k에서 이용객 h을 승차 정류장 o에서 탑승시키는 경로 집합을 po , 마지막 승객을 탑승시킨 후 하차 정류장 d 에 도착하는 경로 집합을 pd 라 하여 버스의 노선 p = po∪pd 이다. 여기서 승차 정류장의 개수는 버스 b에 탑승하는 이용자의 수 ∑ h ∈ H h Z h 이고, 버스가 k 위치에서 노선 po를 따라 정류장 o에 도착하는 경로는 무조건 1개 존재해야 한 다. 따라서 po의 부분집합(Subset)을 So라 했을 때 So의 서브투어(Subtour) 크기는 2 이상, 전체 승차 정류장 개수 - 2 이하로 발생할 수 있으며 식 (9)는 이를 방지하는 제약조건이다. 노선 pd 도 마찬가지로 마지막 승 객을 태운 이후의 버스 위치를 k′, 부분집합을 Sd라 했을 때 제약조건은 아래와 같다.

    ∑ o u k o = 1
    (7)

    ∑ d υ k ′ d = 1
    (8)

    ∑ k ∑ o u k o ≤ | S o | − 1 ∀ S o ∈ p o     2 ≤ | S o | ≤ ∑ h ∈ H h Z h − 2
    (9)

    ∑ k ′ ∑ d υ k ′ d ≤ | S d | − 1 ∀ S d ∈ p d     2 ≤ | S d | ≤ ∑ h ∈ H h Z h − 2
    (10)

    버스 b가 동적정류장 o와 d를 지나는 노선 p를 따라 이동했을 때 버스통행시간 최소화는 아래 식 (11)과 같이 표현된다.

    M i n i m i z e   ∑ k ≠ o , o = 1 t ( x p o ) u k o + ∑ k ′ ≠ d ,   d = 1 t ( x p d ) υ k ′ d
    (11)

    본 연구에서 설정한 이용자 추가소요시간tpassenger에는 총 3가지 결정변수로 구성되어 있으며 각각 시종점 에서 동적정류장까지의 도보시간 twalk, 차량이 도착할 때까지 대기시간 twait , 차량이 목적지 외 다른 정류장 을 경유함으로써 지연된 우회시간 tdetour 을 의미한다. 이용객 h 관점에서 승차 및 하차하여 목적지에 도착하 는 과정을 도식화하면 <Fig. 2>와 같다.

    이용객의 승차 정류장 o의 도보시간을 t w a l k o 하차 정류장 d에서 목적지까지 걸어가는 시간을 t w a l k d 이라 했 을 때 도보시간은 twalk = t w a l k o + t w a l k d 이다. 버스 위치 k에서 이용객이 탑승하는 정류장에 도착하는 시간을 tbus라 했을 때 일반적으로 이용객의 대기시간 twait = tbus - t w a l k o 이다. 그러나 이용객이 정류장에 도착하는 시 간보다 차량이 도착하는 시간이 빠른 경우 대기시간 twait = 0이다. DRT 버스를 통해 이용객에게 서비스를 제공하다 보면 다른 이용객의 합승으로 인해 지연이 발생할 수 있으며 이를 본 연구에서는 우회시간 tdetour 이라고 명명하였다. 즉 tdetour 는 경유지를 우회하여 목적지에 도착했을 때 발생하며 이용객이 목적지까지 개 인 차량으로 이동한다고 가정했을 때 소요시간을 tdirect , DRT 버스를 타고 목적지에 도착한 시간을 tDRT라고 할 때 이용객의 우회시간 tde 이다. 본 연구에서는 DRT 버스 서비스를 신청한 이용객들이 목적지에 도착하기 까지 기다리게 된 시간을 최소화하는 것을 목적으로 하며, 아래 식 (12)와 같다.

    M i n i m i z e   ∑ b ∈ B t p a s s e n g e r = ∑ b ∈ B ( t w a l k + t w a i t + t det o u r )
    (12)

    Ⅳ. 다목적 최적화 알고리즘

    유전알고리즘(Genetic Algorithm, 이하 GA)은 생물의 진화 형태를 모방하여 만든 알고리즘으로 다윈의 적 자생존 원칙에 따라 우수한 해를 도출한다. 염색체가 진화하는 과정을 모방했기에 유전정보를 지닌 유전자 (Gene)와 그 집합인 염색체(Chromosome), n번째 세대 염색체 집합(Population)으로 구성되어 있다. 염색체는 교차(Crossover)나 변이(Mutation)와 같은 유전자 재조합(Recombination) 과정을 통해 진화하고 적합도(Fitness) 로 염색체의 우열 여부를 판단한다. 여기서 여러 개의 적합도를 고려할 수 있는 다목적 유전알고리즘 (Multi-objective GA, MOGA)(Konak et al., 2006)라 하며, 더이상 개선될 수 없는 최적해 집합(Pareto Optima, 파 레토 해)을 산출한다. MOGA의 일종인 NSGA(Non-dominated Sorting Genetic Algorithm)는 비지배 정렬 순위 (Non-dominated Sorting)를 이용하여 복잡도를 낮추고 파레토 해를 전역적으로 효과적이고 빠르게 도출한다는 장점이 있어 많이 개발되었고 다양한 분야에 널리 쓰였다. Deb et al.(2002)은 NSGA에 과밀거리(Crowding Distance)를 적용하여 성능을 높인 NSGA-II를 제시했다. 그러나 한 세대의 부모, 자식세대에 모두 포함된 해 가 다음 세대의 모집단 선택시 중복되기 때문에 상대적으로 해공간(Objective Space) 내의 탐색 성능은 떨어 진다는 단점이 있어, 정규화 과정(Normalization)을 통한 해의 다양성을 보존하는 기법을 적용한 NSGA-III(Deb and Jain, 2013)를 개발했다. 이는 적소(Niche) 개념을 인용하여 염색체 간의 거리 정보를 측정 하고, 밀집도가 낮은 해가 다음 세대에 생존하기 때문에 다양성을 보장한다는 장점이 있었다. 본 연구에서는 해의 수렴성과 다양성을 보장하고 성능이 가장 우수한 NSGA-III 알고리즘을 적용하여 연구를 수행하고자 한 다. <Fig. 3>은 본 연구에서 적용하고자 하는 NSGA-III의 개념도를, <Fig. 4>는 설정한 목적함수를 토대로 적 용한 순서도이다.

    <Fig. 3>

    NSGA-III Diagram

    KITS-21-1-17_F3.gif
    <Fig. 4>

    NSGA-III Flowchart

    KITS-21-1-17_F4.gif

    연구에서는 유전정보를 이용객들이 승하차하는 동적정류장으로 설정하여 Np 크기의 초기 부모세대 Pt 를 생성하고 목적함수에 따라 적합도를 산정하였다. 첫 번째 적합도 f1은 버스통행시간을 의미하고, 두 번째 적 합도 f2는 이용자 추가소요시간으로 값이 작을수록 우수한 염색체로 인식한다. t번째 세대의 Pt와 Ot를 합 산한 유전자 개체군을 Rt 이라 했을 때 적합도를 토대로 염색체 간 비지배 정렬 순위를 매겨 α개의 파레토 경계(Pareto Front) PF1 , PF2, ···, PFα를 선정한다. 엘리티즘 전략에 따라 우선순위가 높은 PF 는 생존하고 열 성적인 염색체는 소거된다. 여기서, 엘리티즘 전략에 의해 생존한 염색체 집합을 St라 지정하고 이 중 다양 성이 보장된 해가 우선적으로 생존한다. 파레토 해의 다양성을 보장하기 위해 먼저 정규화 과정을 진행하여 해공간을 균등하게 분할한다. 구역 분할은 M 개의 목적함수를 지닌 다목적 최적화 문제에서 나누고자 하는 구역의 개수를 ρ라 했을 때 체계적 접근법(Systematic Approach)을(Das and Dennis, 1998) 이용하여 참조점 (Reference Point) Zr의 H = ( M + ρ − 1 ρ ) = ( M + Λ − 1 ) C ρ 개수를 산정하였다. 본 연구의 목적함수는 M = 2, 세 개 의 구역으로 분할했을 때 ρ = 3, 참조점 개수는 총 H = ( 2 + 3 − 1 3 ) = 4 개이며 3개의 구역으로 분할했을 때 가 장 고르게 분포되어 있다. 이때 양 끝단에 있는 점의 좌표는 (1,0), (0,1)이고 이 둘을 연결한 직선은 정규화된 초평면(Normalized Hyperplane)이라 한다. Zr는 정규화된 초평면 상에 존재하며, 각각의 Zr과 원점(Ideal Point)이 지나는 직선을 참조선(Reference Lane)이라 한다. St는 참조선에 따라 다시 재분류되는 작업 (Association Operation)을 수행한다. 즉, St내 개체들은 가장 가까운 참조선에 포괄(Span)되어 집합 Q1,Q2, ··· ,QH으로 배정되고, 이때 참조선에 직교한 벡터의 길이를 수직거리(Perpendicular Distance) l이라고 한다. l 은 해의 분포도를 확인해주고 다양성이 보장된 염색체를 다음 세대에 보존시키는 지표로 이용된다. 각각의 Q 는 적소계수(Niche Count) ∈β 를 지니고 있으며, 적소 보존법(Niche Preservation)에 따라 임의의 참조점 β (β ∈Q )가 선택되면, j에 배정된 해 중 임의의 한 염색체가 다음 세대에 생존한다. 만약 ∈j = 0이면 두 가지 의미를 지니고 있는데, 첫 번째는 β에 배정된 염색체가 모두 Pn +1에 보존된다는 것과 수직거리가 짧은 염 색체가 Pn +1에 계승되었다는 것을 의미한다. 두 번째는 β에 배정된 염색체가 없다는 것을 의미하며 이번 진화 과정에서 β를 배제하고 진행한다. 적소 보존법은 Pn +1의 크기가 Np에 도달할 때까지 진행되며, NSGA-III 알고리즘의 수렴조건이 충족될 때까지 동일한 과정을 반복한다.

    본 연구에서는 하나의 개체군 당 염색체 개수를 30개로 설정하였고 알고리즘의 종료조건은 최대 진화 횟 수 50회 또는 알고리즘 수행시간 2시간 초과로 설정했다.

    V. 시나리오 분석 결과

    본 장에서는 앞서 구축된 설계모형과 알고리즘을 Anaheim 교통망에 적용했을 때 도출된 파레토 해의 결 과를 토대로 목적함수와 알고리즘의 적합도와 우수성을 분석한다. 먼저, 목적함수의 적합도를 평가하기 위해 본 연구에서는 이용자 추가소요시간 구성 변수를 이용하여 <Table 2>와 같이 7가지 시나리오로 구성하였다. 각각의 시나리오는 버스통행시간을 모두 고려하지만, 정류장까지 걸어가는 도보시간, 차량이 도착할 때까지 정류장에서 대기시간, 우회시간 변수에 따라 다르게 설계되었다. 구축된 시나리오별 알고리즘을 수행한 결과 는 <Fig. 5>와 같이 파레토 해가 도출되었고 도출된 결과를 바탕으로 설계된 이용자 추가소요시간 변수의 타 당성을 비교 분석하고자 한다.

    <Table 2>

    Scenario Information

    KITS-21-1-17_T2.gif
    <Fig. 5>

    Scenario Result

    KITS-21-1-17_F5.gif

    다목적 최적화 문제에서는 단일최적화 문제와 다르게 여러 개의 해를 제시하기 때문에 다양한 상황과 제 약조건에도 손쉽게 적용할 수 있다. 이러한 특성으로 다목적 최적화 문제에서는 목적함수가 최적 해에 수렴 하는 정도와 다양한 파레토 해 제시 여부에 따라 알고리즘의 우수성이 평가된다. 따라서 본 장에서는 시나리 오별 파레토 해의 성능을 비교하기 위해 버스통행시간과 이용자 추가소요시간 변수를 분석 기준으로 삼아 파레토 해의 분포도, 수렴성, 다양성 세 가지 측면에서 분석하였다. 시나리오별 도출된 파레토 해의 분포도 분석 방법으로, 가장 일반적이지만 최대/최소값, 사분위 값을 나타내는 박스 플롯(Box Plot)으로 시각화하였 고 평균과 분산을 토대로 비교 분석하였다. 파레토 해의 수렴성과 다양성 평가는 Non-dominated Share (ND-Share)와 Delta Value 지표를 토대로 진행하였다.

    n개의 시나리오에서 산출된 파레토 해 집단을 f1, f2, ···, fn , 이들을 합산한 하나의 집합 S 라고 할 때 집 합 S 에 대한 파레토 해 집단 f′ 을 산정한다. 여기서 f′에 해당하고 해 집단 fn 에 해당하는 해의 개수를 σn 라고 할 때 n번째 시나리오에 대한 ND-Share 값은 σn/fn이다. 시나리오별 파레토 해 개수를 F , 인접한 파레토 해 사이의 거리를 Di , Di의 평균 거리를 D라 할 때 Delta value Δ = ∑ i = 1 | F | | S i − S ¯ | / | F | 이다. 여 기서 ND-Share 값이 클수록 알고리즘의 수렴성능이 우수하다는 것을 의미한다. Di 가 작을수록 파레토 해가 목적함수 축에 가깝거나 밀집되어 있다는 것을 의미하고 Δ는 목적 공간 내 파레토 해의 분포 정도를 나타 내며 0에 가까울수록 균등한 간격으로 분포된다. <Table 3>과 <Fig. 6>은 앞서 소개한 7가지 시나리오를 바 탕으로 이용자 추가소요시간 변수별 파레토 해와 분포도 분석 결과이다.

    <Table 3>

    Scenario Result of Mean and Variance (unit : min)

    KITS-21-1-17_T3.gif
    <Fig. 6>

    Comparison of Distribution Analysis Result

    KITS-21-1-17_F6.gif

    버스통행시간과 이용자 추가소요시간을 함께 고려할 때, 시나리오 2번이 평균 전체 이용자 서비스 경험 시간이 1095.8분으로 가장 좋은 결과를 보였으며, 그다음으로는 시나리오 5번이 1151.0분으로 우수했다. 운영 자 측면에서 시나리오 5번이 262.5분으로 제일 낮은 평균 버스통행시간을 보였으며, 두 번째로 시나리오 2번 이 264.4분으로 산출되었다. 이용자 측면에서 평균 이용자 추가소요시간은 시나리오 2번이 831.4분으로 첫 번째, 시나리오 5번이 888.5분으로 두 번째로 좋을 성능을 나타냈다.

    이용자 추가소요시간 중 도보시간을 기준으로 시나리오를 분석한 결과 도보시간을 고려하지 않은 시나리 오 3, 6의 평균과 분산이 압도적으로 높았으며 파레토 해가 비균질하게 양극단에 분포된 것으로 확인했다. 시나리오별 평균 도보시간은 시나리오 1-4-7-2-5-3-6 순으로 짧았고, 도보시간을 고려한 시나리오들이 우수했 다. 시나리오별 분포도 역시 시나리오 2, 7이 가장 협소했으며 뒤를 이어 4-5-1-6-3 시나리오 순으로 고르게 분포되어 있었다. 분석 결과 도보시간을 중점적으로 고려했던 1, 7, 4번 순으로 시나리오의 성능이 우수했으 며 이용객 관점으로 목적함수를 설정할 때 도보시간을 배제하여 설계한다면 이용객의 입장을 대변하지 못한 미흡한 성능을 보였다.

    버스 대기시간의 경우 모든 시나리오에 대해 분산이 비교적 높게 나타났는데 시나리오 2의 평균은 322.6 분, 분산은 13.4으로 다른 시나리오에 비에 해의 수렴성과 동질성 높은 해로 구성되어 가장 성능이 우수했다. 반면에 대기시간을 고려하지 않은 시나리오 1의 성능이 가장 열성적이었고, 시나리오 3의 분산은 53.7로 가 장 널리 분포되어 있었다. 우회시간도 함께 고려한 시나리오 6에서도 준수한 성능을 보였는데, 시나리오 2보 다 넓은 분포도를 가지고 더 다양한 파레토 해를 지니고 있었다. 반면에 도보시간 변수는 버스 대기시간 변 수와 보완되지 못한 연유로 시나리오 4의 성능은 도보시간을 고려했음에도 성능이 떨어진 모습을 보였다. 따라서 상호보완적인 변수로 목적함수를 적용한다면 시나리오 1, 7과 같이 분포도가 고르고 균등하게 나열 된 표본을 산출할 수 있을 것으로 판단된다.

    우회시간의 경우 이를 고려한 시나리오 3, 6에서의 분포도가 다른 시나리오보다 널리 분포되어 있었을뿐 더러 평균 역시 368.1분, 355.0분으로 가장 성능이 좋았다. 특히 버스 대기시간을 함께 고려한 시나리오 5, 7 역시 우수했다. 이로써 우회시간을 고려할 때 버스 대기함수 변수도 함께 적용하면 시나리오의 효율이 높아 진다는 것을 확인하였다.

    <Table 4>

    Comparison of ND-Share and Delta Value Result

    KITS-21-1-17_T4.gif

    앞서 이용자 추가소요시간 변수별 분석을 수행했다면 모든 변수를 고려했을 때 시나리오별 파레토 해의 수렴성과 다양성 측면에서 분석해보았다.

    시나리오별 파레토 해 수렴성은 시나리오 2가 가장 우수하고 4, 5가 열성적인 것으로 나타났다. 이용객 대 기함수 변수별 ND-Share를 검토하자면, 도보시간의 경우 1, 버스 대기시간은 2, 우회시간에 대해서는 6의 성 능이 가장 우수했으며 분포도 분석 결과와 일치했다. Δ 지표를 통한 시나리오별 파레토 해의 다양성을 분석 한 결과는 시나리오 5, 6가 가장 멀리 분포되어 있고 시나리오 2, 7의 해가 밀집되어 있었다. Δ에 의하면 시 나리오 2의 파레토 해는 제일 균등하게 분포되어 있었고, 다음으로 시나리오 7의 해가 고르게 분포되어 있었 다. 반면에 시나리오 5는 가장 불규칙적으로 분포되어 있었다.

    시나리오별 파레토 해의 분포도, 수렴성, 다양성 측면에서 분석한 결과, 어떠한 지표를 중점적으로 볼 것 인지에 따라 다양한 해석이 가능했다. 운영자 측면에서 버스통행시간을 기준으로 봤을 때, 이용객의 도보시 간과 우회시간을 고려한 시라니오 5가 가장 우수했으며 뒤를 이어 시나리오 2와 4의 성능도 준수했다. 이용 자 측면에서 승객 추가 소요시간을 비교한 결과 시나리오 2, 5, 6 순으로 성능이 뛰어났고 이용자 시간 변수 별 성능은 시나리오에 따라 각기 다른 양상을 보였다. 도보시간의 경우 시나리오 1, 4, 7이, 대기시간에선 시 나리오 2, 6, 5가, 우회시간에선 시나리오 6, 3, 5의 성능이 우수했다. ND-Share와 Δ 지표를 통한 시나리오 비교 결과 시나리오 2의 수렴성 측면에서 시나리오 2의 성능이 가장 우수했으나 파레토 해 표본이 적고 유 사한 정류장을 비슷한 순서로 버스가 운행한 것으로 확인되었다. 이는 목적함수를 결정짓는 요인이 너무 적 다보니 유전정보가 변화해도 목적함수의 변화율이 미비했고 이로 인해 목적 공간 내 광범위하게 해를 탐색 하지 못했다는 한계가 나타났다. 마지막으로 본 연구에서는 승객 추가 소요시간 변수가 시나리오에 미치는 영향에 대해서 분석했다. 대체적으로 버스 대기시간을 중점으로 고려했을 때 성능이 우수했으나, 도보시간과 우회시간을 각기 분리하여 설정한 시나리오의 파레토 해는 최적에 도달하지 못한 것으로 나타났다. 특히 우 회시간을 단독으로 고려했을 때 운영자, 이용자 입장 모두 열성적인 성능을 보였으나, 시나리오 5에서 볼 수 있듯이 도보시간을 함께 적용되었을 때 우수한 성능을 냈다. 이는 우회시간은 주요한 시간변수는 아니나 다 른 변수들을 상호보완하여 모형의 성능을 효과적으로 개선한다고 볼 수 있었다. <Fig. 7>은 가장 우수한 성 능을 보인 시나리오 2를 수행했을 때, 도출된 버스 1대에 대한 노선을 나타낸다.

    <Fig. 7>

    Bus Route Example

    KITS-21-1-17_F7.gif

    Ⅳ. Conclusion

    본 논문은 승객의 위치 정보를 바탕으로 예약한 목적지에 도착하기까지 최적의 버스 노선을 산정하기 위 한 동적정류장 선정 모형을 개발하고, 최적노선 산정시 고려할 요소로는 차량 관점에서 버스통행시간과 더 불어 승객입장에서 서비스 이용시 추가소요시간인 도보시간, 대기시간, 우회시간을 제시했다.

    미국 캘리포니아주 남부의 애너하임 시를 둘러싼 실제 네트워크를 기준으로 예약 승객의 시종점에서 접 근 가능한 동적정류장 리스트를 산정하고 K-means 클러스터링 기법을 이용하여 각 승객에 대한 차량배정을 완료하였다. 이후, 버스통행시간 최소화와 이용자 추가소요시간을 최소화하는 동적정류장 위치 결정 및 버스 노선 결정 문제에 입각하여 다목적 최적화 모형을 NSGA-III 알고리즘에 적용하였다. 다목적 최적화를 수행 한 결과로 파레토 해를 제시하기 때문에 버스 운영 목적이나 특정 상황에 따른 다양한 선택지가 제시된다. 즉, 버스 운행 예산이 줄어들거나 이용객에게 제공하는 서비스의 질을 보장과 같은 제약이 있다면 도출된 파 레토 해 중에서 제한범위 내에서 여러 운영방안을 선택할 수 있다. 따라서 본 연구는 다양한 교통상황이나 운영 제한조건에도 유연하게 적용 가능하며 다양한 대안을 제공함으로써 시민들에게 편리한 서비스를 제공 할 수 있다는 의의가 있다.

    본 연구에서는 모형의 효용성을 평가하기 위해 이용자 추가소요시간 변수를 조정하여 7개의 시나리오를 설정하였고 이를 통해 목적함수의 타당성을 검토 및 비교 분석하였다. 시나리오별 파레토 해의 성능을 비교 하기 위해 파레토 해의 분포도 분석을 수행하였고, 다목적 최적화 측면에서 파레토 해의 수렴성과 다양성을 평가하기 위해 ND-Share와 Δ 지표를 이용하여 분석하였다.

    버스통행시간과 승객 추가 소요시간을 합친 전체 이용자 서비스 경험 시간을 보면, 시나리오 2인 버스통 행시간과 승객 대기시간을 고려한 경우가 가장 낮았으며, 그다음으로 버스통행시간, 도보시간, 우회시간을 적용한 시나리오 5였다. 버스통행시간만 보면 시나리오 5가 더 우수한 결과를 보였고, 승객 추가 소요시간은 시나리오 2가 더 낮았다.

    현재 일반 승객을 대상으로 운영되고 있는 수요응답형 버스의 주 불편 사항이 승객의 긴 대기시간인 만 큼, 시나리오 2 적용 시 개선된 서비스 운영이 가능하며, 만약 교통 소외지역이나 교통 약자를 대상으로 수 요대응형 버스를 운영할 시, 정류장까지의 거리, 즉 승객의 도보시간이 중요한 요소이므로 시나리오 5를 고 려할 수 있다.

    향후 연구내용으로, 이미 버스와 승객 측면에서 다양한 변수의 최적 조합을 개발했지만, 각 변수 간의 상 관관계를 분석하여 목적에 따른 각 측면에서 상호보완적인 변수 조합 방법을 제시할 수 있다. 또한, 현장 상 황을 반영하여 설계한 네트워크와 데이터를 적용한 결과, 상당한 알고리즘 수행시간이 요구되었고 따라서 최대 수행시간을 다소 제한하였다. 이에 대한 해결책으로 향후 다른 다양한 휴리스틱, 메타휴리스틱 알고리 즘을 접목한 하이브리드 알고리즘을 개발하여 알고리즘 성능 개선 방안의 모색이 필요하다. 마지막으로, 본 연구에서는 이용자가 시종점을 예약한 시간정보가 최적화 변수에 포함되지 않았다. 다음 연구에서는 이를 반영하여 차고지 기준 운행 스케줄 등의 차량 배차(dispatch)를 포함하여 설계하겠다.

    ACKNOWLEDGEMENTS

    본 연구는 국토교통부 교통물류연구사업(21TLTP-B146748-04)의 연구비지원 및 한국교통연구원 지원으로 수행하였습니다.

    Figure

    KITS-21-1-17_F1.gif

    Anaheim Network

    KITS-21-1-17_F2.gif

    Personal Time Diagram

    KITS-21-1-17_F3.gif

    NSGA-III Diagram

    KITS-21-1-17_F4.gif

    NSGA-III Flowchart

    KITS-21-1-17_F5.gif

    Scenario Result

    KITS-21-1-17_F6.gif

    Comparison of Distribution Analysis Result

    KITS-21-1-17_F7.gif

    Bus Route Example

    Table

    Passenger Assignment Result

    Scenario Information

    Scenario Result of Mean and Variance (unit : min)

    Comparison of ND-Share and Delta Value Result

    Reference

    1. Alonso-Mora, J. , Samaranayake, S. , Wallar, A. , Frazzoli, E. and Rus, D. (2017), “On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment”, Proceedings of the National Academy of Sciences, vol. 114, no. 3, pp.462-467.
    2. Arbex, R. O. and Da Cunha, C. B. (2015), “Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm”, Transportation Research Part B: Methodological, vol. 81, no. 2, pp.355-376.
    3. Ban, J. and Jayakrishnan, R. ,http://www.bgu.ac.il/~bargera/tntp/, 2021.11.22.
    4. Bodin, L. D. and Sexton, T. R. (1983), The Multi-vehicle subscriber dial-a-ride problem, Monterey, California, Naval Postgraduate School.
    5. Bureau of Public Roads (1964), Traffic Assignment Manual, United States, Department of Commerce, Urban Planning Division, Washington D.C.
    6. Calvo, R. W. and Colorni, A. (2007), “An Effective and fast heuristic for the Dial-a-Ride problem”, A Quarterly Journal of Operations Research, vol. 5, no. 1. pp.61-73.
    7. Celebi, M. E. , Kingravi, H. A. and Vela, P. A. (2013), “A comparative study of efficient initialization methods for the k-means clustering algorithm”, Expert Systems with Applications, vol. 40, no. 1, pp.200-210.
    8. Chebbi, O. and Chaouachi, J. (2016), “Reducing the wasted transportation capacity of personal rapid transit systems: An integrated model and multi-objective optimization approach”, Transportation Research Part E: Logistics and Transportation Review, vol. 89, pp.236-258.
    9. Chen, T. , Zhang, B. , Pourbabak, H. , Kavousi-Fard, A. and Su, W. (2016), “Optimal routing and charging of an electric vehicle fleet for high-efficiency dynamic transit systems”, IEEE Transactions on Smart Grid, vol. 9, no. 4, pp.3563-3572.
    10. Chiang, T. C. and Hsu, W. H. (2014), “A Knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows”, Computers & Operations Research, vol. 45, pp.25-37.
    11. Cordeau, J. F. (2006), “A Branch-and-cut algorithm for the dial-a-ride problem”, Operations Research, vol. 54, no. 3 pp.573-586.
    12. Coslovich, L. , Pesenti, R. and Ukovich, W. (2006), “A Two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem”, European Journal of Operational Research, vol. 175, no. 3, pp.1605-1615.
    13. Das, I. and Dennis, J. E. (1998), “Normal-boundary Intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems”, SIAM Journal on Optimization, vol. 8, no. 3, pp.631-657.
    14. Deb, K. and Jain, H. (2013), “An Evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: Solving problems with box constraints”, IEEE Transactions on Evolutionary Computation, vol. 18, no. 4, pp.577-601.
    15. Deb, K. , Pratap, A. , Agarwal, S. and Meyarivan, T. A. M. T. (2002), “A Fast and elitist multiobjective genetic algorithm: NSGA-II”, IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp.182-197.
    16. Diana, M. and Dessouky, M. M. (2004), “A New regret insertion heuristic for solving large-scale dial-a-ride problems with time windows”, Transportation Research Part B: Methodological, vol. 38, no. 6, pp.539-557.
    17. Diana, M. , Dessouky, M. M. and Xia, N. (2006), “A Model for the fleet sizing of demand responsive transportation services with time windows”, Transportation Research Part B: Methodological, vol. 40, no. 8, pp.651-666.
    18. Dondo, R. and Cerdá, J. (2007), “A Cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows”, European Journal of Operational Research, vol. 176, no. 3, pp.1478-1507.
    19. Dou, X. , Gong, X. , Guo, X. and Tao, T. (2017), “Coordination of feeder bus schedule with train service at integrated transport hubs”, Transportation Research Record, vol. 2648, no. 1, pp.103-110.
    20. Dumas, Y. , Desrosiers, J. and Soumis, F. (1991), “The Pickup and delivery problem with time windows”, European Journal of Operational Research, vol. 54, no. 1, pp.7-22.
    21. Fan, W. and Machemehl, R. B. (2006), “Optimal transit route network design problem with variable transit demand: Genetic algorithm approach”, Journal of Transportation Engineering, vol. 132, no. 1, pp.40-51.
    22. Holland, J. H. (1975), Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence, MIT Press.
    23. Horn, M. E. (2002), “Fleet scheduling and dispatching for demand-responsive passenger services”, Transportation Research Part C: Emerging Technologies, vol. 10, no. 1, pp.35-63.
    24. Konak, A. , Coit, D. W. and Smith, A. E. (2006), “Multi-objective optimization using genetic algorithms: A tutorial”, Reliability Engineering & System Safety, vol. 91, no. 9, pp.992-1007.
    25. Kuah, G. K. and Perl, J. (1989), “The Feeder-bus network-design problem”, Journal of the Operational Research Society, vol. 40, no. 8, pp.751-767.
    26. Lee, Y. J. , Meskar, M. , Nickkar, A. and Saheb, S. (2019), “Development of an algorithm for optimal demand responsive relocatable feeder transit networks serving multiple trainsand stations”, Urban Rail Transit, vol. 5, no. 3. pp.186-201.
    27. Mahmoudi, M. and Zhou, X. (2016), “Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state-space-time network representations”, Transportation Research Part B: Methodological, vol. 89, pp.19-42.
    28. Ministry of Land, Infrastructure and Transport (2013), Traffic impact analysis·improvement strategy guideline.
    29. Pan, S. , Yu, J. , Yang, X. , Liu, Y. and Zou, N. (2015), “Designing a flexible feeder transit system serving irregularly shaped and gated communities: Determining service area and feeder route planning”, Journal of Urban Planning and Development, vol. 141, no. 3.
    30. Parvasi, S. P. , Mahmoodjanloo, M. and Setak, M. (2017), “A Bi-level school bus routing problem with bus stops selection and possibility of demand outsourcing”, Applied Soft Computing, vol. 61, pp.222-238.
    31. Qiu, F. , Li, W. and Zhang, J. (2014), “A Dynamic station strategy to improve the performance of flex-route transit services”, Transportation Research Part C: Emerging Technologies, vol. 48, pp.229-240.
    32. Savelsbergh, M. and Sol, M. (1998), “Drive: Dynamic routing of independent vehicles”, Operations Research, vol. 46, no. 4, pp.474-490.
    33. Sheffi, Y. (1985), Urban transportation networks: Equilibrium analysis with mathematical programming methods, Prentice Hall.
    34. Srinivas, N. and Deb, K. (1994), “Multi-objective function optimization using non-dominated sorting genetic algorithms”, Evolutionary Computation Journal, vol. 2, no. 3, pp.221-248.
    35. Sun, B. , Wei, M. , Yang, C. , Xu, Z. and Wang, H. (2018), “Personalised and coordinated demandresponsive feeder transit service design: A genetic algorithms approach”, Future Internet, vol. 10, no. 7, p.61.
    36. Taplin, J. H. and Sun, Y. (2019), “Optimizing bus stop locations for walking access: Stops-first design of a feeder route to enhance a residential plan”, Environment and Planning B: Urban Analytics and City Science, vol. 47, no. 7, pp.1237-1259.
    37. Transportation Networks for Research Core Team, Transportation Networks for Research,https://github.com/bstabler/TransportationNetworks, 2021.11.22.
    38. Wang, H. (2017), “Routing and scheduling for a last-mile transportation system”, Transportation Science, vol. 53, no. 1, pp.131-147.
    39. Wang, L. , Wirasinghe, S. C. , Kattan, L. and Saidi, S. (2018), “Optimization of demand-responsive transit systems using zonal strategy”, International Journal of Urban Sciences, vol. 22, no. 3, pp.366-381.
    40. Wardrop, J. G. (1952), “Road paper. Some theoretical aspects of road traffic research”, Proceedings of the Institution of Civil Engineers, vol. 1, no. 3, pp.325-362.
    41. Yannibelli, V. , Pacini, E. , Monge, D. , Mateos, C. and Rodriguez, G. (2020), “A Comparative analysis of NSGA-II and NSGA-III for autoscaling parameter sweep experiments in the cloud”, Scientific Programming, vol. 2020, 4653204.

    저자소개

    Footnote