본문 바로가기
KERD
논문KCI 등재

진입-진출 요금을 반영한 수도권 도시철도망의 일반화 K-경로탐색

Generalized K Path Searching in Seoul Metropolitan Railway Network Considering Entry-Exit Toll

이미영
한국ITS학회 (The Korean Society of Intelligent Transport Systems)|2022.12|한국ITS학회 논문지 (Journal of Korean Society of Intelligent Transport Systems)|제21권 제6호|pp. 1-20

0

조회

0

다운로드

3

인용

0

참고문헌

키워드

Network Expansion링크표지Link Label진입-진출요금대중교통망네트워크확장One-to-One K-경로탐색Entry-Exit TollPublic Transit NetworkOne-to-One K-Path Search

초록

도로교통망과 대중교통망에서 요금을 부과하는 기본방식은 진입-진출요금체계이다. 진입- 진출요금체계는 HI-PASS 및 대중교통카드를 이용하는 단말기를 통과하는 방식으로 적용된다. 한편 진입-진출요금을 고려해서 경로를 탐색하는 문제는 경로의 열거를 포함하는 비가산성문제를 포함하고 있다. 이는 모든 경로를 열거해서 최적해를 도출하는 NP-완전문제로 알려져 있다. 지금까지 진입-진출요금에 대한 해법은 도로망을 대상으로 네트워크를 변형하는 기법이제안되었으며 교통카드가 일반화된 대중교통망과 같이 환승, 다수단, 복수단말기와 같이 네트워크확장이 요구되는 상황에서는 검토되지 않았다. 본 연구는 교통카드단말기로 구성된 대중교통망에 대하여 링크표지를 도입해서 네트워크확장을 우회하면서 One-to-One K-경로탐색을통해 경로를 열거함으로서 최적해를 선정하는 방안을 마련하였다. 본 연구에서 제안하는 방법은 비교적 적은 경로집합을 구성하기 때문에 컴퓨팅 파워의 부담없이 최적해를 도출하는 것이가능하며, 경로간 민감도를 비교하기 용이한 측면에서 보다 일반화된 최적경로해법으로 활용이 가능하다.

Abstract

The basic way to charge vehicles for using road and public transport networks is the entry-exit toll system. This system works by reading Hi-Pass and public transportation cards of the vehicles using card readers. However, the problems of navigating a route in consideration of entry-exit toll systems include the non-additive costs of enumerating routes. This problem is known as an NP-complete task that enumerates all paths and derives the optimal path. So far, the solution to the entry-exit toll system charging has been proposed in the form of transforming the road network. However, unlike in the public transport network where the cards are generalized, this solution has not been found in situations where network expansion is required with a transfer, multi-modes and multiple card readers. Hence, this study introduced the Link Label for a public transportation network composed of card readers in which network expansion is bypassed in selecting the optimal path by enumerating the paths through a one-to-one k-path search. Since the method proposed in this study constructs a relatively small set of paths, finding the optimal path is not burdensome in terms of computing power. In addition, the ease of comparison of sensitivity between paths indicates the possibility of using this method as a generalized means of deriving an optimal path.

참고문헌 (25)

  1. Azevedo, J. A., "An Algorithm from the Ranking of Shortest Paths", European Journal of Operational Research, 69, pp.97~106 (1993)
  2. Bernstein, D., "Network Optimization", pp.72~102 (1997), Springer
  3. Dijkstra, E. W., "A Note on Two Problems in Connexion with Graphs", Numerishe Matematilk, 1, pp.269~271 (1959)
  4. Gabriel, S., "The Traffic Equilibrium Problem With Nonadditive Path Costs", Transportation Science, 20(5), pp.337~348 (1997)
  5. Gabriel, S., "Nonadditive Shortest Paths : Sub-problem in Multi-agent Competitive Network Models", Computational and Mathematical Organization Theory, 6(1), pp.29~45 (2000)
  6. Larsson, T., "Transportation Planning-State of the Art", pp.19~31 (2002), Kluwer
  7. 이미영, "복합대중교통망의 링크표지갱신 다목적 경로탐색", 대한교통학회지, 26(1), pp.127~135 (2008), 대한교통학회
  8. 이미영, "An Application of a Link-Based Optimal Pathfinding Algorithm with the Integrated Transit Network from Smart Card Systems", KSCE Journal of Civil Engineering, 24(11), pp.3474~3487 (2020), 대한토목학회[DOI]
  9. 이미영, "비가산성 경로비용을 반영한 링크표지기반 Node-to-Link 최적경로탐색", 한국ITS학회 논문지, 18(5), pp.91~99 (2019), 한국ITS학회[DOI]
  10. Lee, M., "Transportation Network Models and Algorithms Considering Directional Delay and Prohibitions for Intersection Movement", Doctor, pp.2004
  11. 이미영, "수도권 도시철도망 승객이동경로추정을 위한 교통카드기반 최적 M-유사경로 구축방안", 한국ITS학회 논문지, 16(2), pp.1~12 (2017), 한국ITS학회[DOI]
  12. 이미영, "역사환승페널티를 고려한 링크표지기반 최적경로탐색 - 교통카드기반 철도네트워크를 중심으로 -", 대한토목학회논문집(국문), 38(6), pp.941~947 (2018), 대한토목학회[DOI]
  13. 이미영, "거리비례제 요금부과에 따른 최소요금경로탐색", 대한교통학회지, 22(7), pp.101~108 (2004), 대한교통학회
  14. 이미영, "거리비례제 요금정책에 따른 K요금경로탐색", 대한교통학회지, 23(1), pp.103~114 (2005), 대한교통학회
  15. 이미영, "사용자 맞춤형 대중교통 경로정보제공을 위한 다계층의 다목적 경로탐색기법 연구", 한국ITS학회 논문지, 7(3), pp.1~14 (2008), 한국ITS학회
  16. Lo, K., "Traffic Equilibrium Problem with Route-specific Costs : Formulation and Algorithms", Transportation Research Part B, 34(6), pp.493~513 (2000)
  17. Martins, E. Q. V., "An Algorithm for Ranking Paths That May Contain Cycles", European Journal of Operational Research, 18, pp.123~130 (1984)
  18. Meng, Q., "Logit-Based Stochastic User Equilibrium Problem for Entry-Exit Toll Schemes", Journal of Transportation Engineering, 130(6), pp.805~813 (2004)
  19. Moore, E. F., "The Shortest Path through A Maze" (1957), Harvard University Press
  20. Scott, K., "Solving a Best Path Problem when the Value of Time Function is Nonlinear", Transportation Research Board, ~ (1997)
  21. Shin, H., "Estimating Revenues of Integrated Fare System for Seoul Metropolitan Public Transportation Using Smartcard Data", Doctor, pp.2022
  22. 신성일, "Stepwise 환승계수를 고려한 Logit 유형 대중교통통행배정모형", 대한교통학회지, 34(6), pp.570~579 (2016), 대한교통학회[DOI]
  23. 신성일, "교통망에 적합한 K 비루프 경로 탐색 알고리즘", 대한교통학회지, 22(7), pp.121~131 (2004), 대한교통학회
  24. 신성일, "누적환승함수를 고려한 경험적 최적경로탐색 방안", 한국ITS학회 논문지, 15(3), pp.60~67 (2016), 한국ITS학회[DOI]
  25. Yang, H., "Modeling Private Highways in Networks With Entry-Exit Based Toll Charges", Transportation Research B, 38, pp.191~213 (2004)

관련 논문AI추천

수도권 도시철도망 승객이동경로추정을 위한 교통카드기반 최적 M-유사경로 구축방안이미영한국ITS학회 · 한국ITS학회 논문지2017 · 제16권 제2호교통카드 Tag 제약을 반영한 통행자 경로선택에 대한 합리성 평가 연구 : 수도권 지하철 네트워크를 중심으로남두희, 심대영, 이미영한국ITS학회 · 한국ITS학회 논문지2020 · 제19권 제6호교통카드 단말기ID Chain OD를 반영한 최적경로탐색- 수도권 철도 네트워크를 중심으로-이미영한국ITS학회 · 한국ITS학회 논문지2018 · 제17권 제6호사용자 맞춤형 대중교통 경로정보제공을 위한 다계층의 다목적 경로탐색기법 연구박동주, 박제진, 이미영, 정점래한국ITS학회 · 한국ITS학회 논문지2008 · 제7권 제3호교통카드기반 수도권 도시철도 환승자료 구축방안손지언, 이미영, 조종석한국ITS학회 · 한국ITS학회 논문지2016 · 제15권 제4호수도권 도시철도 환승통행량 추정방안(교통카드자료를 이용하여)손지언, 이미영한국ITS학회 · 한국ITS학회 논문지2016 · 제15권 제6호

이 간행물의 다른 논문 (19건)

장소별 완속충전기 적정 보급 비율에 관한 연구 : 전기차 이용자의 통행 및 충전행태에 따른 이질성을 중심으로이재현, 김현미, 윤서연pp. 21-35교통사고 정보를 이용한 과실비율 산정 모델 개발강희진, 이요셉, 한음, 박기옥, 윤일수pp. 36-56서울시 전기차 충전수요를 고려한 급속충전소의 최적입지 선정 연구김지규, 이동민, 김수환pp. 57-69미시적 교통 시뮬레이션을 활용한 실시간 수요대응형 자율주행 버스 영향 평가박상웅, 김주영pp. 70-86스마트횡단시스템 활성화를 위한 교통약자의 횡단속도 추정윤여환, 김재석, 변상철, 김형규pp. 87-96
원문 보기