Journal of Korean Society of Transportation (대한교통학회지)

Korean Society of Transportation (대한교통학회)
권호 표지

Finding a Minimum Fare Route in the Distance-Based System

거리비례제 요금부과에 따른 최소요금경로탐색

  • Published : 2004.01.01
Download PDF
⟨ Previous Next ⟩

Abstract

The new transit fare in the Seoul Metropolitan is basically determined based on the distance-based fare system (DBFS). The total fare in DBFS consists of three parts- (1) basic fare, (2) transfer fare, and (3) extra fare. The fixed amount of basic fare for each mode is charged when a passenger gets on a mode, and it proceeds until traveling within basic travel distance. The transfer fare may be added when a passenger switches from the present mode to another. The extra fare is imposed if the total travel distance exceeds the basic travel distance, and after that, the longer distance the more extra fare based on the extra-fare-charging rule. This study proposes an algorithm for finding minimum fare route in DBFS. This study first exploits the link-label-based searching method to enable shortest path algorithms to implement without network expansion at junction nodes in inter-modal transit networks. Moreover, the link-expansion technique is adopted in order for each mode's travel to be treated like duplicated links, which have the same start and end nodes, but different link features. In this study, therefore, some notations associated with modes can be saved, thus the existing link-based shortest path algorithm is applicable without any loss of generality. For fare calculation as next steps, a mathematical formula is proposed to embrace fare-charging process using search process of two adjacent links illustrated from the origin. A shortest path algorithm for finding a minimum fare route is derived by converting the formula as a recursive form. The implementation process of the algorithm is evaluated through a simple network test.

서울시 대중교통개편에서 요금부과방안은 기본적으로 거리비례제체제(Distance-Based Fare System)에 근거하고 있다. 거리비례제에서 요금은 일정거리를 주행하는 기본요금과 수단간 환승에서 발생하는 환승요금, 일정거리 이상의 주행에 따른 할증요금으로 구분된다. 본 연구는 거리비례제에 따른 요금부과 시 최소요금경로를 탐색하는 방안을 제시한다. 이를 위한 다수의 수단이 존재하는 복합교통망의 환승지점에서 네트워크확장이 필요치 않도록 링크표지을 적용했다. 동일링크에서 복수통행수단의 표현이 가능하도록 수단에 따른 링크확장개념을 활용하였다. 따라서 본 연구에서는 제안하는 최소요금경로 알고리즘은 수단을 표현하기 위한 표식이 별도로 필요하지 않아, 기존의 링크표지 최적경로알고리즘의 적용이 가능하다. 또한 요금부과과정을 네트워크에 적용하기 위하여 출발지를 기준으로 표현된 연속된 두 링크에 대해 기본요금, 환승요금, 할증요금의 부과과정을 수식으로 표현하였다. 이 수식을 재귀(recursive)형태의 수식으로 전환하여 최소요금경로 탐색알고리즘을 제시하였다. 간단한 예제를 통하여 알고리즘 수행과정을 평가하였다.

Keywords

References

  1. 김현명. 임용택. 이승재(1999), 통합교통망 수단선택-통행배정모형 개발에 관한 연구, 대한교통학회지, 제17권 제5호, 대한교통학회, pp.87-98
  2. 김현명. 임용택(2000), 알고리즘을 이용한 전역탐색 최단경로 알고리즘개발, 대한교통학회지, 제16권 제2호, 대한교통학회, pp.157-167
  3. 장인성(2000) 서비스시간 제약이 존재하는 도시부복합교통망을 위한 링크기반의 최단경로탐색 알고리즘, 대한교통학회지, 제18권 제6호, 대한교통학회, pp.111-121
  4. Bellman R. (1957) Dynamic Programming, Princeton University Press, Princeton, New Jersey
  5. De Cea. J. and J.E. Fernandez. (1989) Transit Assignment for Minimal Routes: An Efficient New Algorithm, Traffic Engng. Control, pp.492-494
  6. De Cea. J. and J.E. Fernandez. (1993) Transit Assignment for Congested Public Transport Systems: An Equilibrium Model, Transportation Science Vol.27
  7. Dijkstra E. W. (1959) A Note of Two Problems in Connected with Graphs. Numerical Mathematics. I, pp.269-271
  8. Potts R.B. and Oliver R.M.(1972) Flows in Transportation Networks. Academic Press
  9. Tong C. O. and Richardson A. J.(1984) Computer Model for Finding the Time-Dependent Minimum Path in Transit Systems with Fixed Schedules, Journal of Advanced Transportation 18, pp.145-161 https://doi.org/10.1002/atr.5670180205
  10. Ziliaskopoulos A. and Wardell W. (2000) An Intermodal Optimum Path Algorithm for Multimodal Networks with Dynamic Arc Travel Times and Switching Delays. European Journal of Operational Research 125, pp.486-502 https://doi.org/10.1016/S0377-2217(99)00388-4