All Issue

2024 Vol.42, Issue 6 Preview Page

Article

Real-time On-demand Service for Dynamic Route Generation Considering User Utility: A Case Study of Namyang New Town, Hwaseong, Gyeonggi-do

이용자 효용을 반영한 실시간 수요대응형 서비스 동적 경로 생성: 경기도 화성시 남양뉴타운을 중심으로

Juhyoun YOUM1
,
Jinhee KIM2*
염 주현1
,
김 진희2*
1Combined Masters & PhD Course, Department of Urban Planning and Engineering, Yonsei University, Seoul 03722, Korea
2Associate Professor, Department of Urban Planning and Engineering, Yonsei University, Seoul 03722, Korea
1연세대학교 도시공학과 석박사통합과정
2연세대학교 도시공학과 부교수
*Corresponding Author
31 December 2024. pp. 706-723
PDF XML Citation
Abstract

With advancements in big data and technology, on-demand public transportation services that process real-time reservations based on user requests and acceptance are gaining attention. Unlike fixed-route public transport, on-demand services dynamically generate routes according to demand, which may alter travel times as other users join. However, these variations can reduce user satisfaction and increase ride cancellations. This study proposes a framework incorporating a utility function, commonly used in service acceptance decision estimation, into the route-matching cost function of on-demand public transport. The dynamic route generation algorithm is based on an Insertion Heuristic with constraints such as maximum waiting time, additional in-vehicle travel time, and vehicle capacity. A simulation was conducted in Namyang New Town, Hwaseong, Gyeonggi-do, comparing vehicle travel time-based and user utility-based cost functions. Results demonstrated that integrating user utility into the dispatch algorithm improved performance, including travel delay ratio and service acceptance rates, thus enhancing user service efficiency. This suggests that applying user utility to dispatch algorithms can improve real demand capture and foster a flexible, user-centric service.

Keywords
acceptance rate
dynamic route generation
on-demand
stated preference
user utility

최근 빅데이터 수집 및 기술의 발전으로 실시간으로 사용자의 요청과 수락에 기반하여 예약이 확정되는 수요대응 대중교통 서비스가 주목받고 있다. 한편, 수요대응 대중교통은 수요에 기반하여 경로가 생성됨에 따라 전통적인 대중교통 서비스와 달리 타인의 서비스 호출로 인하여 승객의 통행시간의 변화가 발생한다. 그러나 통행시간의 변화는 이용자 관점에서 비효용을 야기한다는 점에서 실제 서비스 환경에서 이용자의 호출 취소가 발생할 수 있다. 이에 본 연구는 실시간 수요대응형 대중교통의 경로 생성 과정에 서비스 수락 의사결정 추정 연구에서 활용되고 있는 효용함수를 경로 매칭 비용함수에 접목시키는 프레임워크를 제시하였다. 동적 경로 생성은 삽입 휴리스틱 알고리즘을 기반으로 하되 최대 대기시간과 최대 추가 차내 통행시간, 차량 용량에 대한 제약조건을 추가하여 경로 탐색을 수행하였다. 또한, 제시한 프레임워크의 효과를 검증하기 위하여 시뮬레이션 실험을 수행하고 선행연구에서 제시한 차량 총 통행시간 기반의 경로 매칭 비용함수와 이용자 효용기반 비용함수 배차 결과를 운영자와 이용자 관점에서 비교하였다. 시뮬레이션은 실시간 수요대응 자율주행 대중교통 모빌리티 서비스 기술 개발 연구가 수행중인 경기도 화성시 남양읍 남양뉴타운을 중심으로 수행되었다. 시뮬레이션 실험 시 비용함수에 따른 경로 생성 결과물이 이용자의 서비스 수락에 미치는 영향을 판별하기 위하여 잠재선호 실험 기반의 수락률 모형을 적용하여 배차 정보에 따른 실 수락 여부를 판별하였다. 그 결과 이용자 효용을 배차 알고리즘의 비용함수에 적용하는 것이 이용자 서비스 효율을 나타내는 통행지연 비중과 서비스 수락 관점에서 더 우수한 결과를 보였으며, 총 차량 통행거리 대비 서비스 인원에 대한 운영자 관점 지표에 대하여 더 높은 수치를 보였다. 이를 통하여 향후 남양뉴타운과 같이 소도시 지역을 중심으로 수요대응형 대중교통 서비스를 운영함에 있어 이용자 효용을 배차 알고리즘에 적용하는 것이 실 수요를 확보하고 유동적이고 이용자 친화적인 서비스를 제공하는데 기여할 수 있음을 확인하였다.

키워드
수락률
동적 경로 생성
수요대응형
잠재선호
이용자 효용
References
1

Attanasio A., Cordeau J.-F., Ghiani G., Laporte G. (2004), Parallel Tabu Search Heuristics for The Dynamic Multi- vehicle Dial-a-ride Problem, Parallel Comput, 30(3), 377-387.

10.1016/j.parco.2003.12.001
2

Cappart Q., Thomas C., Schaus P., Rousseau L.-M. (2018), A Constraint Programming Approach for Solving Patient Transportation Problems, The International Conference 24th Principles and practice of constraint programming, 490-506.

10.1007/978-3-319-98334-9_32
3

Carotenuto P., Martis F. (2017), A Double Dynamic Fast Algorithm to Solve Multi-vehicle Dial-a-ride Problem, Transp. Res. Procedia, 27, 632-639.

10.1016/j.trpro.2017.12.131
4

Çetin T. (2017), The Rise of Ride Sharing in Urban Transport: Threat or Opportunity? In Urban transport systems, IntechOpen, London, UK.

10.5772/66918
5

Chassaing M., Duhamel C., Lacomme P. (2016), An ELS-based Approach with Dynamic Probabilities Management in Local Search for The Dial-a-ride Problem, Eng. Appl. Artif. Intell., 48, 119-133.

10.1016/j.engappai.2015.10.002
6

Cook R. D., Nachtsheim C. J. (1980), A Comparison of Algorithms for Constructing Exact D-Optimal Designs, Technometrics, 22(3), 315-324.

10.1080/00401706.1980.10486162
7

Cordeau J.-F., Laporte G. (2003), A Tabu Search Heuristic for The Static Multi-vehicle Dial-a-ride Problem, Transp. Res. Part B Methodol., 37, 579-594.

10.1016/S0191-2615(02)00045-0
8

Cordeau J. F., Laporte G. (2007), The Dial-a-Ride Problem: Models and Algorithms, Ann. Oper. Res., 153(1), 29-46.

10.1007/s10479-007-0170-8
9

Coslovich L., Pesenti R., Ukovich W. (2006), A Two-phase Insertion Technique of Unexpected Customers for A Dynamic Dial-a-ride Problem, Eur. J. Oper. Res., 175, 1605-1615.

10.1016/j.ejor.2005.02.038
10

Desrosiers J., Dumas Y., Soumis F. (1986), A Dynamic Programming Solution of The Large-scale Single-vehicle Dial-a-ride Problem with Time Windows, Am. J. Math. Manag. Sci., 6(3-4), 301-325.

10.1080/01966324.1986.10737198
11

Häll C. H., Andersson H., Lundgren J. T., Värbrand P. (2009), The Integrated Dial-a-Ride Problem, Public Transport, 1(1), 39-54.

10.1007/s12469-008-0006-1
12

Ho S. C., Szeto W. Y., Kuo Y.-H., Leung J. M. Y., Petering M., Tou T. W. H. (2018), A Survey of Dial-a-ride Problems: Literature Review and Recent Developments, Transp. Res. Part B Methodol., 111, 395-421.

10.1016/j.trb.2018.02.001
13

Lee J., Kim J., Chung J.-H. (2022), Effect of Personal Attitudes and Satisfaction with Public Transportation on Stated Preference of Automated Mobility-on-demand, J. Korean Soc. Transp., 40(1), Korean Society of Transportation, 81-98.

10.7470/jkst.2022.40.1.081
14

Lehuédé F., Masson R., Parragh S. N., Péton O., Tricoire F. (2014), A Multi-criteria Large Neighbourhood Search for The Transportation of Disabled People, J. Oper. Res. Soc., 65, 983-1000.

10.1057/jors.2013.17
15

Luo Y., Schonfeld P. (2011), Online Rejected-reinsertion Heuristics for Dynamic Multivehicle Dial-a-ride Problem, Transp. Res. Rec., 2218(1), 59-67.

10.3141/2218-07
16

Nasri S., Bouziri H., Aggoune-Mtalaa W. (2021), Customer-oriented Dial-a-ride Problems: A Survey on Relevant Variants, Solution Approaches and Applications, The Proceedings of NICE2020 International Conference, Emerging Trends in ICT for Sustainable Development, 111-119.

10.1007/978-3-030-53440-0_13
17

Psaraftis H. N. (1980), A Dynamic Programming Solution to The Single Vehicle Many-to-many Immediate Request Dial-a-ride problem, Transp. Sci., 14(2), 130-154.

10.1287/trsc.14.2.130
18

Ropke S., Cordeau J.-F., Laporte G. (2007), Models and Branch-and-cut Algorithms for Pickup and Delivery Problems with Time Windows, Networks, 49(4), 258-272.

10.1002/net.20177
19

Solomon M. (1987), Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows Constraints, Oper. Res., 35(2), 254-265.

10.1287/opre.35.2.254
20

Stein D. M. (1978), Scheduling Dial-a-Ride Transportation Systems, Transp. Sci., 12(3), 232-249.

10.1287/trsc.12.3.232
21

Vallee S., Oulamara A., Cherif-Khettaf W. R. (2020), New Online Reinsertion Approaches for A Dynamic Dial-a-ride Problem, J. Comput. Sci., 47, 101199.

10.1016/j.jocs.2020.101199
22

Wong K. I., Han A. F., Yuen C. W. (2014), On Dynamic Demand Responsive Transport Services with Degree of Dynamism, Transportmetrica A: Transport Science, 10(1), 55-73.

10.1080/18128602.2012.694491
23

Youm J., Lee J., Chung J.-H., Kim J. (2023), A Study of Automated Mobility-on-demand Service Acceptance Rate Based on Stated Preference Survey, J. Korean Soc. Transp., 41(4), Korean Society of Transportation, 538-551.

10.7470/jkst.2023.41.5.538
Information
  • Publisher :Korean Society of Transportation
  • Publisher(Ko) :대한교통학회
  • Journal Title :Journal of Korean Society of Transportation
  • Journal Title(Ko) :대한교통학회지
  • Volume : 42
  • No :6
  • Pages :706-723
  • Received Date : 2024-10-30
  • Revised Date : 2024-11-06
  • Accepted Date : 2024-12-03
  • DOI :https://doi.org/10.7470/jkst.2024.42.6.706
Journal Informaiton Journal of Korean Society of Transportation Journal of Korean Society of Transportation
Archives
: 2015 Vol.34~
  • NRF
  • KOFST
  • crossref cited-by
  • crosscheck
  • orcid
  • open access
  • ccl
Journal Informaiton Journal Informaiton - close