[논문]정체를 고려한 Personal Rapid Transit 배차 및 경로 계획 알고리즘

한충균; 김백현; 정락교; 하병현

doi:10.5370/kiee.2015.64.11.1578

정체를 고려한 Personal Rapid Transit 배차 및 경로 계획 알고리즘
A Dispatching and Routing Algorithm for Personal Rapid Transit by Considering Congestion 원문보기

전기학회논문지 = The Transactions of the Korean Institute of Electrical Engineers, v.64 no.11, 2015년, pp.1578 - 1586

한충균 (Dept. of Industrial Engineering, Pusan National University) , 김백현 (Korea Railroad Research Institute) , 정락교 (Korea Railroad Research Institute) , 하병현 (Dept. of Industrial Engineering, Pusan National University)

Abstract ▼ AI-Helper

Personal rapid transit (PRT) is getting attention as a new form of transportation. It is energy efficient and provides the high level of passenger service. In this study, the dynamic PRT dispatching and routing problem is dealt with. Passengers request transportation service on a complex network, and an operating system monitors passenger arrivals and coordinates vehicles in real time. A new online dispatching and routing algorithm is proposed, which minimizes the total travel distance of vehicles and the waiting time of passengers. The algorithm dispatches vehicles by considering multiple vehicles' state and multiple passengers at the same time. In particular, finding the shortest-time path is attempted by taking into account the future congestion on lanes. Discrete-event simulation is employed to validate the performance of the proposed algorithm. The results show the algorithm in this study outperforms others.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

하지만 차량 간의 간섭으로 인하여 정체가 발생하는 경우 추정된 EWT와 실제 승객의 대기시간 차이가 커질 수 있다. 따라서 본 연구는 정체를 감안한 최단 소요시간을 추정하여 EWT를 보다 정확하게 산정한다.
본 연구는 PRT 시스템 운영을 위한 동적 수송 문제(dynamic pick-up and delivery problem)를 다룬다. 일반적으로 동적 수송 문제는 차량 배차 단계와 경로 계획 단계로 나누어 접근한다.
본 연구는 PRT 운영 환경에서의 차량 배차 및 경로 계획 문제를 다루었다. 이를 해결하기 위하여 배차와 경로 계획을 함께 고려한 알고리즘을 제시하였다.
본 연구는 시뮬레이션 실험을 통하여 PRT 배차 및 경로 계획 알고리즘을 검증한다. 그림 6은 비교 실험을 위하여 사용된 가상 네트워크이다.
본 연구는 최단 시간 경로를 구하기 위하여 정체를 고려한 conflict-free shortest path finding 알고리즘(CF 알고리즘)을 제시한다. CF 알고리즘은 time window 방법 기반의 알고리즘이다[14-17].
본 연구는 환경적 요소와 승객 서비스 수준을 고려하여 총 차량 이동거리와 승객 대기시간을 최소화를 목표로 한다. 그리고 승객 대기시간에 대하여 평균, 90th percentile, 최대값을 측정하여 서비스 수준을 평가한다.
본 연구에서는 차량 배차와 경로 계획을 함께 고려하는 새로운 PRT 운영 방식을 제안한다. 이를 위해 다수의 PRT 차량과 여러 승객을 동시에 고려하여 체계적인 배차를 수행하는 기존 연구[11]를 확장하고 동시에 time window를 활용하여 정체를 고려한 경로 계획을 수립한다.

제안 방법

CF 알고리즘의 실행을 위해 먼저 네트워크 정보, 차량의 경로 정보를 바탕으로 시뮬레이션을 수행하여 점유 기간을 예측한다. 예를 들어, 그림 3(a)와 같이 네트워크와 차량의 경로 정보가 주어지면, 그림 3(b)와 같이 각 노드에 대한 차량의 점유 기간이 구해진다.
PRT 운영 시스템은 승객의 도착 시점과 차량에 탑승 중인 승객이 하차하는 시점에 의사결정을 수행한다. 구체적으로 차량 상태(위치, 경로)와 승객 정보(도착 정류장, 도착시각)를 입력받아 배차 및 경로 계획에 대한 결과를 제시한다.
005)씩 증가하는 것을 의미한다. 그리고 각 도착율에 대해 10번 반복 실험을 수행한다. 안정상태의 성능을 평가하기 위하여 총 24시간의 시뮬레이션 중 초기 2시간을 제외한 통계치를 사용한다.
본 연구는 환경적 요소와 승객 서비스 수준을 고려하여 총 차량 이동거리와 승객 대기시간을 최소화를 목표로 한다. 그리고 승객 대기시간에 대하여 평균, 90th percentile, 최대값을 측정하여 서비스 수준을 평가한다. 또한 차량 이동거리와 승객 대기시간 모두 고려한 다목적(multi-objective)의 관점에서도 알고리즘의 성능을 평가한다.
그리고 승객 대기시간에 대하여 평균, 90th percentile, 최대값을 측정하여 서비스 수준을 평가한다. 또한 차량 이동거리와 승객 대기시간 모두 고려한 다목적(multi-objective)의 관점에서도 알고리즘의 성능을 평가한다.
본 연구는 시뮬레이션 실험에서 배차 규칙과 경로 계획 알고리즘의 성능 차이를 비교한다. 배차 범위 6가지(I, IA, IT, IAP, IAT, IATP)를 고려하고, 경로 계획은 최단 거리 경로, 최단 시간 경로(CF 알고리즘 사용)를 사용하여 총 12가지의 조합에 대해여 비교 실험을 수행한다.
본 연구는 시뮬레이션 실험에서 배차 규칙과 경로 계획 알고리즘의 성능 차이를 비교한다. 배차 범위 6가지(I, IA, IT, IAP, IAT, IATP)를 고려하고, 경로 계획은 최단 거리 경로, 최단 시간 경로(CF 알고리즘 사용)를 사용하여 총 12가지의 조합에 대해여 비교 실험을 수행한다.
하나의 자원은 하나의 작업을 처리할 수 있으며 각 자원이 특정 작업을 처리하는 비용은 정해져있다. 본 연구에서는 이를 PRT 배차에 적용한다. 즉 PRT 차량을 대기 승객에 최소의 총비용으로 할당하는 배차 계획을 찾는다.
특히 단선으로 구성되는 PRT 도로망에서는 정체 구간을 회피하는 것이 중요하다. 이를 위해 기존의 분기 및 합류 지점에서만 점유여부를 판단하는 방법론을 확장하여 차로의 점유여부를 예상하고 경로 계획에 반영한다. 제안된 방법론의 성능을 평가하기 위해 시뮬레이션을 통해 기존 방법론과의 비교 실험을 수행하였다.
본 연구에서는 차량 배차와 경로 계획을 함께 고려하는 새로운 PRT 운영 방식을 제안한다. 이를 위해 다수의 PRT 차량과 여러 승객을 동시에 고려하여 체계적인 배차를 수행하는 기존 연구[11]를 확장하고 동시에 time window를 활용하여 정체를 고려한 경로 계획을 수립한다. 즉 기존의 최단거리 경로대신 정체를 고려하여 이동 시간을 예측하고 경로를 계획한다.
본 연구는 PRT 운영 환경에서의 차량 배차 및 경로 계획 문제를 다루었다. 이를 해결하기 위하여 배차와 경로 계획을 함께 고려한 알고리즘을 제시하였다. 최단 시간 경로를 탐색하는 새로운 경로 계획 알고리즘을 제시하여 기존의 연구가 고려하지 못한 점을 보완하였고, 이를 배차 알고리즘과 통합하여 문제를 해결하였다.
이를 위해 다수의 PRT 차량과 여러 승객을 동시에 고려하여 체계적인 배차를 수행하는 기존 연구[11]를 확장하고 동시에 time window를 활용하여 정체를 고려한 경로 계획을 수립한다. 즉 기존의 최단거리 경로대신 정체를 고려하여 이동 시간을 예측하고 경로를 계획한다. 특히 단선으로 구성되는 PRT 도로망에서는 정체 구간을 회피하는 것이 중요하다.

대상 데이터

표 1은 그림 1의 예제에서 배차 범위가 IA일 때의 비용행렬이다. 즉 Idle 상태에 있는 T1, T5와 Approaching 상태에 있는 T2, T3, T4를 배차 대상 차량으로 고려한다(그림 1에 *로 표시). 본 연구는 할당 문제의 해를 구하기 위하여 Hungarian method를 이용한다.

데이터처리

이를 위해 기존의 분기 및 합류 지점에서만 점유여부를 판단하는 방법론을 확장하여 차로의 점유여부를 예상하고 경로 계획에 반영한다. 제안된 방법론의 성능을 평가하기 위해 시뮬레이션을 통해 기존 방법론과의 비교 실험을 수행하였다. 승객 편의성과 에너지 효율성을 검토하기 위하여 승객의 평균 대기시간과 PRT의 총 이동거리를 성능지표로 비교하였으며, 본 연구에서 제안한 방법론의 우수성을 확인할 수 있었다.

이론/모형

즉 Idle 상태에 있는 T1, T5와 Approaching 상태에 있는 T2, T3, T4를 배차 대상 차량으로 고려한다(그림 1에 *로 표시). 본 연구는 할당 문제의 해를 구하기 위하여 Hungarian method를 이용한다. 표 1에서 최적 배차 결과는 음영으로 표시되어 있으며 이때의 총비용은 109이다.

성능/효과

본 연구에서 제시하는 알고리즘은 다목적(승객의 대기시간-차량의 총 이동거리)에 대한 성능지표에서 우수한 결과를 보여주었다. 구체적으로, 배차 범위에 Transiting 상태가 포함된 경우, 온라인 PRT 배차 및 경로 계획 알고리즘은 공차 이동거리에 대해서 좋은 성능지표를 보여주었다. 그리고 Approaching 상태를 배차 범위에 포함하는 것이 승객의 탑승 요청을 민첩하게 대처하고 승객의 대기시간을 줄일 수 있음을 밝혔다.
구체적으로, 배차 범위에 Transiting 상태가 포함된 경우, 온라인 PRT 배차 및 경로 계획 알고리즘은 공차 이동거리에 대해서 좋은 성능지표를 보여주었다. 그리고 Approaching 상태를 배차 범위에 포함하는 것이 승객의 탑승 요청을 민첩하게 대처하고 승객의 대기시간을 줄일 수 있음을 밝혔다. 또한, 높은 도착율에서 최단 거리 경로를 바탕으로 한 방식이 시스템을 안정화하지 못한 것과 달리, 본 연구에서 제시한 최단 시간 경로를 제시하는 CF 알고리즘은 승객 대기시간에 대하여 더욱 나은 결과를 보여주었다.
그리고 Approaching 상태를 배차 범위에 포함하는 것이 승객의 탑승 요청을 민첩하게 대처하고 승객의 대기시간을 줄일 수 있음을 밝혔다. 또한, 높은 도착율에서 최단 거리 경로를 바탕으로 한 방식이 시스템을 안정화하지 못한 것과 달리, 본 연구에서 제시한 최단 시간 경로를 제시하는 CF 알고리즘은 승객 대기시간에 대하여 더욱 나은 결과를 보여주었다.
본 연구에서 제시하는 알고리즘은 다목적(승객의 대기시간-차량의 총 이동거리)에 대한 성능지표에서 우수한 결과를 보여주었다. 구체적으로, 배차 범위에 Transiting 상태가 포함된 경우, 온라인 PRT 배차 및 경로 계획 알고리즘은 공차 이동거리에 대해서 좋은 성능지표를 보여주었다.
제안된 방법론의 성능을 평가하기 위해 시뮬레이션을 통해 기존 방법론과의 비교 실험을 수행하였다. 승객 편의성과 에너지 효율성을 검토하기 위하여 승객의 평균 대기시간과 PRT의 총 이동거리를 성능지표로 비교하였으며, 본 연구에서 제안한 방법론의 우수성을 확인할 수 있었다.
이는 재배차 결과에 따라 각 차량에 할당된 승객이 바뀌어 공차 이동은 증가할 수 있으나, 이로 인하여 다른 차량은 공차 이동을 시작하지 않고 정류장에서 Idle 상태로 대기할 가능성이 커지기 때문이다. 즉, Approaching 중인 차량의 공차 이동거리는 증가하더라도 시스템 전체 입장에서는 다른 차량의 공차 이동이 줄어들어 총 이동거리 면에서는 더욱 나은 결과를 보여주는 것으로 판단된다.
최단 시간 경로를 사용하고 Approaching이 배차 범위에 포함된 조합(IA-CF, IAP-CF, IAT-CF, IATP-CF)은 높은 도착율(λ=0.115)에서도 시스템이 안정 상태로 유지되었다.
이를 해결하기 위하여 배차와 경로 계획을 함께 고려한 알고리즘을 제시하였다. 최단 시간 경로를 탐색하는 새로운 경로 계획 알고리즘을 제시하여 기존의 연구가 고려하지 못한 점을 보완하였고, 이를 배차 알고리즘과 통합하여 문제를 해결하였다.
090 사이에서는 최단 거리 경로와 최단 시간 경로 간의 차이를 확인하기 어렵다. 하지만 도착율이 증가함에 따라 본 연구에서 제시한 방법론이 승객의 평균 대기시간관점에서 더 좋은 것을 알 수 있다. 승객의 도착율이 증가함에 따라 주요 선로에는 PRT 차량의 통행이 증가하고 정체 현상이 발생한다.
반면에 승객 대기시간의 90th percentile과 총 이동거리를 동시에 고려하는 경우에 IA-CF, IAP-CF, IATP-STP가 Pareto front를 구성한다. 해당 결과는 IATP-CF를 사용할 경우 승객의 대기시간에 대한 편차가 크다는 사실을 확인시켜준다.

후속연구

본 연구 결과는 유사한 특성을 가지는 다른 환경에도 적용 가능할 것으로 예상된다. 예를 들어 다양한 산업에서 중요한 역할을 담당하고 Automated Guided Vehicle (AGV)의 경우 과거 단순한 배치에 한정된 수의 차량만 운영되는 것이 일반적이었다.
따라서 생산성 향성을 위해 보다 효율적인 운영 정책의 개발이 요구되고 있다[21]. 본 연구에서 제안하는 방법론은 이와 같은 AGV의 운영에도 효과적으로 적용될 수 있을 것으로 기대된다. 또한 생활과 밀접하게 관련된 택시 배차 및 경로 계획 문제에 활용하여 승객 만족도와 에너지 사용 효율을 높일 수 있다.
향후 연구로 서비스가 끝난 차량을 승객의 발생 패턴에 따라 재배치하는 연구가 필요할 것으로 여겨진다. 그리고 PRT 운영 환경에 적합한 주기적인 경로 재탐색의 수행하는 경우 승객 서비스 수준을 보다 향상할 수 있을 것으로 기대된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	PRT가 차세대 대중교통 수단으로 주목받는 이유는?	Personal Rapid Transit (PRT)는 전기를 동력으로 하는 소형 무인 궤도 차량이다. 일반적인 대중교통 수단에 비해 PRT는 무게가 가볍고 에너지 효율이 높으며 수요 응답형(on-demand)으로 운영할 수 있어 차세대 대중교통 수단으로 주목받고 있다. 버스와 전철은 많은 수의 승객이 함께 탑승한다.
	PRT가 효율적으로 운영하는 것이 가능한 이유는?	PRT는 전용 선로 상에서 운행되며 정류장이 주행 차로에서 떨어져 있어(off-lane) 무정차(non-stop) 서비스를 제공할 수 있다. 또한 통합 운영 시스템에서 차량 경로를 계획하고 통제하므로 교통 혼잡을 예측하여 보다 효율적으로 운영하는 것이 가능하다[1].
	Personal Rapid Transit란?	Personal Rapid Transit (PRT)는 전기를 동력으로 하는 소형 무인 궤도 차량이다. 일반적인 대중교통 수단에 비해 PRT는 무게가 가볍고 에너지 효율이 높으며 수요 응답형(on-demand)으로 운영할 수 있어 차세대 대중교통 수단으로 주목받고 있다.

참고문헌 (21)

K. Mueller and S. P. Sgouridis, "Simulation-based analysis of personal rapid transit systems: service and energy performance assessment of the Masdar City PRT case", Journal of advanced transportation, vol. 45, No. 4, pp. 252-270, 2011.

상세보기
UK Tram, "Advice Note for Promoters Considering Personal Rapid Transit (PRT)", 2012
P. J. Egbelu and J. M. A. Tanchoco, "Characterization of automatic guided vehicle dispatching rules", International Journal of Production Research, vol. 22, No. 3, pp. 359-374, 1984.

상세보기
S. Lee, "The role of centrality in ambulance dispatching", Decision Support Systems, vol. 54, No. 1, pp. 282-291, 2012.

상세보기
U. Bilge, G. Esenduran, N. Varol, Z. Ozturk, B. Aydin and A. Alp, "Multi-attribute responsive dispatching strategies for automated guided vehicles", International Journal of Production Economics, vol. 100, No. 1, pp. 65-75, 2006.

상세보기
Y. Ho and H. Liu, "A simulation study on the performance of pickup-dispatching rules for multiple-load AGVs", Computers & Industrial Engineering, vol. 51, No. 3, pp. 445-463, 2006.

상세보기
B. Zhicheng, M. Weijian, Y. Xiaoming, Z. Ning and M. Chao, "Modified Hungarian Algorithm for Real-Time ALV Dispatching Problem in Huge Container Terminals", Journal of Networks, vol. 9, No. 1, pp. 123-130, 2014.
A. C. Regan, H. S. Mahmassani and P. Jaillet, "Evaluation of Dynamic Fleet Management System: A Simulation Framework", Transportation Research Board, 1998.
B. Kim, J. Shin, S. Jeong and J. Koo, "Effective overhead hoist transport dispatching based on the Hungarian algorithm for a large semiconductor FAB", International Journal of Production Research, vol. 47, No. 10, pp. 2823-2834, 2009.

상세보기
P. K. Sheridan, E. Gluck, Q. Guan, T. Pickles, B. Balcioglu and B. Benhabib, "The dynamic nearest neighbor policy for the multi-vehicle pick-up and delivery problem", Transportation Research Part A vol. 49, pp. 178-194, 2013.
C. Han, B. Kwon, B. Kim, R. Jeong, H. Lee and B. Ha, "An Online Personal Rapid Transit Dispatching Algorithm Based on Nearest Neighbor Dispatching Rule", Journal of the Korean Society for Simulation, vol. 23, No. 4, pp. 97-109, 2014.

원문보기 상세보기
K. Bartlett, J. Lee, S. Ahmed, G. Nemhauser, J. Sokol and B. Na, "Congestion-aware dynamic routing in automated material handling systems", Computers & Industrial Engineering, vol. 70, pp. 176-182, 2014.

상세보기
B. R. Sarker and S. S. Gurav, "Route planning for automated guided vehicles in a manufacturing facility." International Journal of Production Research, vol. 43, No. 21, pp. 4659-4683, 2005.

상세보기
C. Kim and J. M. A. Tanchoco, "Conflict-free shortest-time bidirectional AGV routeing", International Journal of Production Research, vol. 29, No. 12, pp. 2377-2391, 1991.

상세보기
R. H. Mohring, E. Kohler, E. Gawrilow and B. Stenzel, "Conflict-free real-time AGV routing", Operations Research Proceedings, 2004.
N. Smolic-Rocak, S. Bogdan, Z. Kovacic and T. Petrovic, "Time Windows Based Dynamic Routing in Multi-AGV Systems", Automation Science and Engineering, IEEE Transactions on, vol. 7, No. 1, pp. 151-155, 2010.

상세보기
S. Rajotia, K. Shanker and J. L. Batra, "A semidynamic time window constrained routeing strategy in an AGV system", International Journal of Production Research, vol. 36, No. 1, pp. 35-50, 1998.

상세보기
C. Oboth, R. Batta and M. Karwan, "Dynamic conflictfree routing of automated guided vehicles", International Journal of Production Research, vol. 37, No. 9, pp. 2003-2030, 1999.

상세보기
Y. Tanaka, T. Nishi, and M. Inuiguchi, "Dynamic Optimization of Simultaneous Dispatching and Conflictfree Routing for Automated Guided Vehicles", Journal of Advanced Mechanical Design, Systems, and Manufacturing, Vo. 4, No. 3, pp. 701-715, 2010.

상세보기
T. Nishi, Y. Hiranaka and I. E. Grossmann, "A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles", Computers & Operations Research, vol. 38, No. 5, pp. 876-888, 2011.

상세보기
I. F. A. Vis, "Survey of research in the design and control of automated guided vehicle systems", European Journal of Operational Research, vol. 170, No. 3, pp. 677-709, 2006.

상세보기

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증