All Issue

2023 Vol.41, Issue 6 Preview Page

Article

Exploring the Optimization of Demand Responsive Transit Vehicle Routing Using a Deep Q Network

DQN을 이용한 수요응답형 대중교통 차량 최적 경로 탐색

Seunghak KIM1
,
Kiyoung SUNG2
,
Jaecheol KIM3
,
Hyun KIM4*
김 승학1
,
성 기영2
,
김 재철3
,
김 현4*
1Researcher, Center for Convergence of Vehicle, People and ICT, Korea National University of Transportation, Chungju 27469, Korea
2Ph.D. Candidate, Department of Convergence of Mobility and Energy, Korea National University of Transportation, Chungju 27469, Korea
3M.S. Course, Department of Convergence of Mobility and Energy, Korea National University of Transportation, Chungju 27469, Korea
4Professor, Department of Convergence of Mobility and Energy, Korea National University of Transportation, Chungju 27469, Korea
1한국교통대학교 교통ICT융합연구센터 연구원
2한국교통대학교 교통에너지융합학과 박사과정
3한국교통대학교 교통에너지융합학과 석사과정
4한국교통대학교 교통에너지융합학과 교수
*Corresponding Author
31 December 2023. pp. 724-738
PDF XML Citation
Abstract

Demand-responsive transit (DRT) refers to public transport services that operate considering real-time passenger demand. In contrast to conventional public transport like buses and subways, recent advancements in DRT have enabled flexible operations in response to passenger requests by setting origin and destination points, allowing real-time pickup at the passengers’ locations, and dynamically adjusting routes to provide customized service. Various route optimization methods are being developed and studied in the literature. In this study, a vehicle route optimization algorithm for DRT based on the Deep Reinforcement Learning (DRL) machine learning method, referred to as a Deep Q Network, was developed and tested on a simulator to validate its performance using test-bed demand data.

Keywords
deep reinforcement learning
reinforcement learning environment
demand response public transit
path planning
shared bicycle

수요응답형 대중교통은 개별 승객의 호출수요에 따라 운행되는 대중교통 서비스를 의미한다. 일반적인 대중교통 수단인 버스, 지하철과는 달리 최근에는 카카오, 우버 택시와 같이 출발지와 목적지를 설정하면 실시간 호출을 통해 호출한 승객의 현재 위치로 태우는 유연한 운영을 통해 교통취약지역에서 탄력적 운행이 가능하게 되었으며, 동적으로 경유지를 변경하여 승객 맞춤형 서비스를 제공하고 있다. 이용객의 수요기반으로 다양한 최적의 경로 탐색방법 개발 및 연구가 진행되고 있다. 본 연구에서는 Deep Reinforcement Learning 알고리즘 중 하나인 Deep Q Network 알고리즘 기반 차량 최적경로 알고리즘 시뮬레이터를 통해 테스트베드 대상지를 검증 분석하였다.

키워드
심층강화학습
강화학습 환경
수요응답형 대중교통
경로생성
공유자전거
References
1
Belhaiza S. (2019), A Hybrid Adaptive Large Neighborhood Heuristic for a Real-Life Dial-a-Ride Problem, Algorithms, 12(2), 39. 10.3390/a12020039
2
Brockman G., Cheung V., Pettersson L., Schneider J., Schulman J., Tang J., Zaremba W. (2016), Openai gym, arXiv preprint arXiv:1606.01540.
3
Feng Yirui (2019), Create a customized gym environment for Star Craft 2, Towards Data Science. https://towardsdatascience.com/create-a-customized-gym-environment-for-star-craft-2-8558d301131f
4
Glover F., Laguna M. (1998), Tabu search(2093-2229), Springer US. 10.1007/978-1-4613-0303-9_33
5
Kim H. J., Kim Y. M., Kim Y. H. (2020), Dynamic Obstacle Avoidance and Optimal Path Planning Based on Q-learning, Information and Control Symposium, 47-48.
6
Kim H., Yoo S. H., Lee J. W., Baek B. Y., Shin J. H. (2022), Real-time Dynamic Route Generation Algorithm for Demand-responsive Driverless Transit Operation (DRDTO) Applied to Corridors to Consider U-Turns, J. Korean Soc. Transp., 40(2), Korean Society of Transportation, 260-276. 10.7470/jkst.2022.40.2.260
7
Kim S. H. (2015), An Optimization of Vehicles Scheduling and Dynamic Route by Using Meta-Heuristic Algorithm and Real-time Transportation Information, Pukyong National University Graduate School http://www.riss.kr/link?id= T13681950&outLink=K
8
Kim W. G., Roh C. G., Son B. S. (2012), Service Evaluation Models from Transit Users' Perspectives, J. Korean Soc. Transp., 30(1), Korean Society of Transportation, 149-159. 10.7470/jkst.2012.30.1.149
9
Minih V., Kavukcuoglu K., Silver D., Graves A., Antonoglou I., Wierstra D., Riedmiller M. (2013), Playing atari with deep reinforcement learning, arXiv preprint arXiv:1312.5602.
10
Minih V., Kavukcuoglu K., Silver D., Rusu A. A., Veness J., Bellemare M. G., Hassabis D. (2015), Human-level Control through Deep Reinforcement Learning, Nature, 518(7540), 529-533. 10.1038/nature1423625719670
11
Nazari Mohammadreza, Afshin Oroojlooy, Lawrence V. Snyder, Martin Takac (2018), Deep Reinforcement Learning for Solving the Vehicle Routing Problem, Advances in Neural Information Processing Systems 31.
12
Park J. S., Kim J. H Lee J Y. (2022), Optimal Fleet Size for Demand Responsive Transport Service Using Queueing Theory: Focusing on the Case of Yeongjong Island, Incheon, J. Korean Soc. Transp., 40(6), Korean Society of Transportation, 816-831. 10.7470/jkst.2022.40.6.816
13
Peng B., Wang Jiahai, Zhang Zizhen (2020), A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems, International Symposium on Intelligence Computation and Applications, Springer, Singapore. 10.1007/978-981-15-5577-0_51
14
Pihera J., Musliu N. (2014), Application of Machine Learning to Algorithm Selection for TSP, 2014 IEEE 26th International Conference on Tools with Artificial Intelligence, 47-54. 10.1109/ICTAI.2014.18
15
Sunwoo Y. M, Lee W.C. (2021), Map-Based Obstacle Avoidance Algorithm for Mobile Robot Using Deep Reinforcement Learning, Journal of IKEEE, 25(2), 337-343.
16
Sutton Richard S., Andrew G. Barto (2018), Reinforcement Learning: An Introduction, 2nd ed., The MIT Press Cambridge, Massachusetts London, England.
Information
  • Publisher :Korean Society of Transportation
  • Publisher(Ko) :대한교통학회
  • Journal Title :Journal of Korean Society of Transportation
  • Journal Title(Ko) :대한교통학회지
  • Volume : 41
  • No :6
  • Pages :724-738
  • Received Date : 2023-05-16
  • Revised Date : 2023-06-30
  • Accepted Date : 2023-10-05
  • DOI :https://doi.org/10.7470/jkst.2023.41.6.724
Journal Informaiton Journal of Korean Society of Transportation Journal of Korean Society of Transportation
Archives
: 2015 Vol.34~
  • scopus
  • NRF
  • KOFST
  • crossref cited-by
  • crosscheck
  • orcid
  • open access
  • ccl
Journal Informaiton Journal Informaiton - close