The Demand Responsive Transit (DRT) system is the flexible public transport service that determines the route and schedule of the service vehicles according to users' requests. With increasing importance of public transport systems in urban areas, the development of stable and fast routing algorithms for DRT has been the goal of many researches over the past decades. In many studies, routing algorithms for DRT systems have been proposed and developed. In this study, a new heuristic method is proposed to generate fast and efficient routes for multiple vehicles using demand clustering and destination demand priority searching method (DDPS) considering the imbalance of users’ origin and destination demands. The proposed algorithm is tested in various demand distribution scenarios including random case, concentration case, and directed case. The result shows that the proposed DDPS method decreases the drop of service ratio due to an increase in demand density and computation time compared to other mixed-integer programming-based algorithms. In addition, compared to other clustering-based algorithm, the walking cost of the passengers is significantly reduced, but the detour time and in-vehicle travel time of the passenger is increased due to the detour burden. This can be further improved by additional adjustments of the constraints given to the routing algorithm process.
수요응답형 대중교통체계 시스템은 사용자의 요청에 따라 서비스 차량의 경로와 스케줄을 설정하는 유동적인 대중교통 서비스이다. 도시 지역에서 대중교통 시스템의 중요성이 증가함에 따라, 수요응답형 대중교통체계를 위한 안정적이고 빠른 경로 탐색 방법의 개발 또한 다양하게 연구되고 있다. 본 연구에서는 빠르고 효율적인 다중차량의 경로 탐색을 위해, 승객들의 시종점 수요의 불균형을 고려한 수요의 군집화 방법과 종점 수요 우선 탐색의 휴리스틱 방법이 제안되었다. 제안된 방법은 시종점 수요 분포가 무작위인 경우, 집중된 경우와 방향성을 가지는 시나리오들에 대하여 테스트되었다. 제안된 알고리즘은 수요 밀도의 증가로 인한 경로 매칭 비율의 감소를 저감시키며, 계산 속도가 비교적 빠른 장점을 보인다. 또한, 다른 군집화 기반 알고리즘에 비해 승객의 보행요구시간을 감소시키며, 반대로 승객의 차량 탑승 시간은 상대적으로 증가하는 경향을 보이나, 이는 제한 조건들의 추가적인 조정을 통해 보다 개선될 수 있다.
