Real-Time Dynamic Route Generation Algorithm for Demand-Responsive Driverless Transit Operation (DRDTO) Applied to Corridors to Consider U-Turns

Hyun Kim; Seonhyung Yoo; Jinwoo Lee; Beomyeol Baek; Junghee Shin

doi:10.7470/jkst.2022.40.2.260

All Issue

2022 Vol.40, Issue 2 Preview Page

Article

Real-Time Dynamic Route Generation Algorithm for Demand-Responsive Driverless Transit Operation (DRDTO) Applied to Corridors to Consider U-Turns 유턴을 고려한 교통축 적용 수요대응 자율주행 대중교통(DRDTO)의 실시간 동적 경로 생성 알고리즘

30 April 2022. pp. 260-276

PDF XML

Abstract

Recently, autonomous vehicle is receiving much attention in various sectors including transportation and public transportation. This study presents an adaptive routing algorithm for the real-time demand response service of autonomous transit vehicles. The experimental setting includes the real-time demand occurring randomly over time within the study area. Each demand (service call) request the transit service from designated origin to destination. The routing algorithm is designed to make U-turn and skip stops to improve service and reduce the wait time of users. This study adapts Reinforcement Learning, one of the machine learning techniques, namely reinforcement learning, which can precede a complex calculation process in an offline process. Simulation experiments conducted on a testbed of the Chungju campus of the Korea National University of Transportation. The simulation results show that the proposed routing algorithm can improve the adaptive transit service over the fixed operation in selected performance indicators.

Keywords

autonomous vehicle

demand response

flexible route

public transport

reinforcement learning

최근 자율주행 차량이 대중교통분야로 진출하여 관련 연구들이 활발히 진행되고 있다. 본 연구에서는 시공간적으로 다양하게 발생하는 실시간 호출수요에 대응하여 자율주행 차량에 동적경로를 제시하여 효율적인 대중교통 서비스를 제공할 수 있는 알고리즘을 개발했다. 실시간 호출수요는 다수의 출발지와 다수의 목적지로 구성되어 복잡하고 다양한 경우의 수를 고려하여 최적 경로를 제시할 수 있는 방안이 필수적이다. 복잡한 계산과정은 오프라인 과정에서 선행할 수 있는 방법으로 머신러닝의 강화학습 기술을 사용하여 제시하였다. 개발된 자율주행 대중교통(DTO)를 위한 실시간 호출 수요대응 동적경로 알고리즘은 테스트베드를 선정하여 시뮬레이션 실험이 이루어 졌다. 시뮬레이션 결과는 개발된 실시간 호출 수요대응 동적경로 생성 알고리즘을 고정노선의 운행결과 대비하여 효율적인 운행결과가 나타났다. 이는 실시간 호출수요량이 적을수록 효과가 크게 나타나지만 호출 수요량이 증가하면서 그 효과 폭이 점차적으로 감소했다.

키워드

강화 학습

동적경로

대중교통

수요대응

자율주행 대중교통

References

Arhin S. A., Gatiba A., Anderson M., Manandhar B., Ribbisso M. (2019), Acceptable Wait Time Models at Transit Bus Stops, Engineering, Technology & Applied Science Research, 9(4), 4574-4580. 10.48084/etasr.2966

Becker F., Axhausen K. W. (2017), Literature Review on Surveys Investigating the Acceptance of Automated Vehicles, Transportation, 44(6), 1293-1306. doi:10.1007/s11116-017-9808-9 10.1007/s11116-017-9808-9

Cordeau J. F., Laporte G. (2007), The Dial-a-ride Problem: Models and Algorithms, Annals of Operations Research, 153, 29-46. 10.1007/s10479-007-0170-8

Diana M., Dessouky M. M. (2004), A New Regret Insertion Heuristic for Solving Large-scale Dial-a-rideproblems with Time Windows, Transportation Research Part B, 38, 539-557. 10.1016/j.trb.2003.07.001

Fagnant D. J., Kockelman K. (2015), Preparing a Nation for Autonomous Vehicles: Opportunities, Barriers and Policy Recommendations, Transportation Research Part A: Policy and Practice, 77, 167-181. doi: 10.1016/j.tra.2015.04.003

Faisal A., Kamruzzaman M., Yigitcanlar T., Currie G. (2019), Understanding Autonomous Vehicles: A Systematic Literature Review on Capability, Impact, Planning and Policy, Journal of Transport and Land Use, 12(1), 45-72. Retrieved from https://www.jstor.org/stable/26911258 10.5198/jtlu.2019.1405

Gendreau M., Laport G., Semet F.(2001), A Dynamic Model and Parallel Tabu Search Heuristic for Real-time Ambulance Relocation, Parallel Computing, 27(12), 1641-1653. doi: 10.1016/S0167-8191(01)00103-X

Guo J., Susilo Y., Antoniou C., Pernestål A. (2021), When and Why Do People Choose Automated Buses over Conventional Buses? Results of a Context-dependent Stated Choice Experiment, Sustainable Cities and Society, 69(102842), 1-9. doi: 10.1016/j.scs.2021.102842

Huang T., Fang B., Bei X., Fang F. (2019), Dynamic Trip-Vehicle Dispatch with Scheduled and On-Demand Requests, arXiv. 10.1049/joe.2018.9258

Iclodean C., Cordos N., Varga B. O. (2020), Autonomous Shuttle Bus for Public Transportation: A Review, Energies, 13(11, 2917), 1-45. Retrieved from https://www.mdpi.com/1996-1073/13/11/2917 10.3390/en13112917

Kassens-Noor E., Kotval-Karamchandani Z., Cai M. (2020), Willingness to Ride and Perceptions of Autonomous Public Transit, Transportation Research Part A: Policy and Practice, 138, 92-104. doi: 10.1016/j.tra.2020.05.010

Korea National University for Transportation (2022), Smart Campus Challenge Project: A Demonstration of Multi-purpose Mobility Service Using OHMIO Shuttle.

LeBeau P. (2018), Waymo Starts Commercial Ride-share Service, Retrieved from https://www.cnbc.com/2018/12/05/waymo-starts-commercial-ride-share-service.html

Lee E., Cen X., Lo H. K. (2021), Zonal-based Flexible Bus Service under Elastic Stochastic Demand, Transportation Research Part E: Logistics and Transportation Review, 152, 1-25. doi: 10.1016/j.tre.2021.102367

Lee Y.-J., Meskar M., Nickkar A., Sahebi S. (2019), Development of an Algorithm for Optimal Demand Responsive Relocatable Feeder Transit Networks Serving Multiple Trains and Stations, Urban Rail Transit, 5(3), 186-201. 10.1007/s40864-019-00109-z

Li M., Zheng N., Wu X., Huo X. (2019), An Efficient Matching Method for Dispatching Autonomous Vehicles, 2019 IEEE Intelligent Transportation Systems Conference (ITSC) Auckland, NZ, October 27-30. 10.1109/ITSC.2019.8917334

Melachrinoudis E., Ilhan A. B., Min H. (2007), A Dial-a-ride Problem for Client Transportation in a Healthcare Organization, Computers & Operations Research, 34, 742-759. 10.1016/j.cor.2005.03.024

Narayanan S., Chaniotakis E., Antoniou C. (2020), Shared Autonomous Vehicle Services: A Comprehensive Review, Transportation Research Part C: Emerging Technologies, 111, 255-293. doi: 10.1016/j.trc.2019.12.008

Pettigrew S., Cronin S. L., Norman R. (2019), Brief Report: The Unrealized Potential of Autonomous Vehicles for an Aging Population, Journal of Aging & Social Policy, 31(5), 486-496. doi: 10.1080/08959420.2018.1500860

Psaraftis H. N.(1980), A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem, Transportation Science 14(2), 130-154. doi: 10.1287/trsc.14.2.130

Raj A., Kumar J. A., Bansal P. (2020), A Multicriteria Decision Making Approach to Study Barriers to the Adoption of Autonomous Vehicles, Transportation Research Part A: Policy and Practice, 133, 122-137. doi: 10.1016/j.tra.2020.01.013

Rekiek B., Delchambre A., Saleh H. A. (2006), Handicapped Person Transportation: An Application of the Grouping Genetic Algorithm, Engineering Application of Artificial Intelligence, 19, 511-520. 10.1016/j.engappai.2005.12.013

Ritzinger U., Puchinger J., Hartl R. F. (2016), A Survey on Dynamic and Stochastic Vehicle Routing Problems, International Journal of Production Research, 54(1), 215-231. doi: 10.1080/00207543.2015.1043403

Schilde M., Doerner K. F., Hartl R. F. (2011), Metaheuristics for the Dynamic Stochastic Dial-a-ride Problem with Expected Return Transports, Computers & Operations Research, 38(12), 1719-1730. doi: 10.1016/j.cor.2011.02.006

Sultana Z., Mishra S., Cherry C. R., Golias M. M., Tabrizizadeh Jeffers S. (2018), Modeling Frequency of Rural Demand Response Transit Trips, Transportation Research Part A: Policy and Practice, 118, 494-505. doi: 10.1016/j.tra.2018.10.006

Sutton R. S., Barto A. G. (1998), Introduction to Reinforcement Learning (Vol.2): MIT Press Cambridge.

Tafreshian A., Abdolmaleki M., Masoud N., Wang H. (2021), Proactive Shuttle Dispatching in Large-scale Dynamic Dial-a-ride Systems, Transportation Research Part B: Methodological, 150, 227-259. doi: 10.1016/j.trb.2021.06.002

Yigitcanlar T., Mohamed A., Kamruzzaman M., Piracha A. (2019), Understanding Transport-Related Social Exclusion: A Multidimensional Approach, Urban Policy and Research, 37(1), 97-110. doi: 10.1080/08111146.2018.1533461

Information

Publisher :Korean Society of Transportation
Publisher(Ko) :대한교통학회
Journal Title :Journal of Korean Society of Transportation
Journal Title(Ko) :대한교통학회지
Volume : 40
No :2
Pages :260-276
Received Date : 2021-11-25
Revised Date : 2021-12-24
Accepted Date : 2022-03-28
DOI :https://doi.org/10.7470/jkst.2022.40.2.260

Journal of Korean Society of Transportation ISSN:1229-1366(Print) 2234-4217(Online) 대한교통학회지

All Issue