최근린 배차 규칙 기반 온라인 Personal Rapid Transit 배차 알고리즘

• 영문명: An Online Personal Rapid Transit Dispatching Algorithm Based on Nearest Neighbor Dispatching Rule
• 발행기관: 한국시뮬레이션학회
• 저자명: 한충균(Chung-Kyun Han) 권보배(Bo Bea Kwon) 김백현(Baek-Hyun Kim) 정락교(Rag-Gyo Jeong) 이훈(Hoon Lee) 하병현(Byung-Hyun Ha)
• 간행물 정보: 『한국시뮬레이션학회 논문지』제23권 제4호, 97~109쪽, 전체 13쪽
• 주제분류: 공학 > 기타공학
• 파일형태: PDF
• 발행일자: 2014.12.30

국문 초록

Personal Rapid Transit (PRT)는 차세대 대중교통 수단으로 에너지 효율적이며 높은 수준의 고객 서비스를 제공한다. 정류장에 동적으로 도착한 고객이 운송 서비스를 요청하면 PRT 시스템은 차량을 배차한다. 본 연구에서는 PRT 시스템을 위한 새로운 온라인 배차 알고리즘을 제시하였다. 제시된 알고리즘은 최근린(nearest neighbor) 배차 규칙을 기반으로 개발되었으며, 이분 매칭(bipartite matching)을 사용하여 다수의 PRT 차량과 고객을 동시에 고려하여 배차를 결정한다. 이 경우 전체 차량 중 배차 대상 차량의 선택 범위가 성능지표에 영향을 줄 수 있다. 따라서 본 연구에서는 차량의 상태를 고려하여 체계적으로 배차 차량을 선택하는 방법을 제시한다. 성능지표로 공차 이동거리와 고객 대기시간을 고려하였으며, 시뮬레이션 기법을 사용하여 배차 선택 범위에 따른 성능지표의 차이를 확인하였다. 그리고 기존의 배차 규칙과 비교하여 본 연구에서 제시하는 방법론이 우수하며 PRT 시스템에 적합한 것을 확인하였다.

영문 초록

Personal rapid transit (PRT) is a new transportation system, which is energy efficient and brings high quality of customer service. Customers arrive dynamically at stations and request transportation service. In this paper, we propose a new online PRT dispatching algorithm for pickup and delivery of customers. We adopt the nearest neighbor dispatching rule, which is known as performing well in general. We extend the rule with bipartite matching in order to deal with multiple vehicles and customers at the same time. We suggest a systematic way for selecting vehicles that will be considered to be dispatched, since the scope with which vehicles are selected may affect the system performance. We regard the empty travel distance of vehicles and the customer waiting time as the performance measures. By using simulation experiments, it has been examined that the scope of dispatching affects the system performance. The proposed algorithm has been validated by comparing with other dispatching rules for transportation services. We have shown that our algorithm is more suitable for PRT operating environment than other dispatching rules.

목차

1. 서론

2. 문제정의

3. 온라인 PRT 배차 알고리즘

4. 시뮬레이션 실험

5. 결 론

References

키워드

Personal rapid transit (PRT) 동적 수송 온라인 알고리즘 차량 배차 최근린 배차 규칙 Personal rapid transit (PRT) Dynamic pickup and delivery Online algorithm Vehicle dispatching Nearest neighbor dispatching rule