[논문]승객 수송 문제의 최적화

박준혁; 김병인; 김성배

승객 수송 문제의 최적화
Optimization of Passenger Transportation Problem 원문보기

산업공학 = IE Interfaces, v.23 no.2, 2010년, pp.139 - 146

박준혁 (Department of Industrial and Management Engineering, POSTECH) , 김병인 (Department of Industrial and Management Engineering, POSTECH) , 김성배 (Institute of Information Technology, Inc. (IIT))

Abstract ▼ AI-Helper

In this paper, we present the study of a real passenger transportation system. Passenger transportation problem aims to transport passengers from bus stops to their destinations by a fleet of vehicles while satisfying various constraints such as vehicle capacity, maximum allowable riding time in a bus, and time windows at destinations. Our problem also has special issues such as mixed loading, consideration of afternoon problem together with morning problem, and transferring passengers between vehicles. Our solution approach consists of three serial procedures: bus route generation, bus scheduling, and post optimization. Efficient heuristic algorithms were developed and implemented for the procedures. The proposed solution approach has been successfully applied to several real world problem instances and could reduce about 10% to 15% of buses.

주제어

AI 본문요약
AI-Helper

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

문제 정의

또한 수리 모형을 이용한 경우에도 비교적 간단하고 크기가 작은 문제만을 다뤘다. 따라서 본 연구에서도 exact approach 보다는 휴리스틱 알고리듬을 개발하는데 초점을 맞추었다.
본 연구에서는 다양한 제약 조건을 만족시키는 승객 수송 문제의 가능해(Feasible solution)를 빠른 시간에 만들 수 있는 휴리스틱 알고리듬과 프로그램을 개발하였다. 개발된 프로그램은 큰 사이즈의 문제(예, 4,000개의 승객 승차지점, 200개의 목적지점, 차량 160대 가량)에서도 빠른 시간(예, 30초 이내)에 가능 해를 구할 수 있었으며, 3개의 도시의 승객수송문제에 적용해 본 결과 실제 운영되고 있는 계획에 비하여 약 10～15%의 차량 감소 효과를 거둘 수 있었다.
[Figure 2]는 Step 1에서 구해진 승차지점의 집합 Sp에 대한 가능해(Feasible Solution)의 예이다. 본 연구에서는 차량 경로 결정 문제를 해결하기 위하여 Sweep 알고리듬(Gillett and Miller, 1974)을 변형한 Sweep-based construction 알고리듬을 개발하였다. 차량 경로결정문제에서는 차량 종류의 용량과 최대 승차 시간은 고려되지만 개개의 차량의 가용 여부(Availability)는 고려되지 않는다.
차량 경로 결정 문제와 차량 스케줄링 문제를 통해 얻어진 초기 경로를 개선하기 위해서 본 연구에서는 Post optimization 프로세스를 제안하였다. Post optimization은 크게 경로 재할당과 혼승 재할당의 두 단계로 나뉜다.

가설 설정

본 연구에서는 환승하는 승객들을 메인 알고리듬을 수행하기 전에 Pre-process로 따로 처리하였다. 이때 환승하는 승객의 정보(환승 지점, 환승 횟수 등)은 미리 주어졌다고 가정하였다.

제안 방법

그런 후에 경로에 포함되지 않은 승차지점 가운데 Index가 가장 작은 지점과 목적지점을 포함하는 경로를 생성한다. 그리고 현재 경로에 포함된 모든 승차지점으로부터 경로에 포함되지 않은 승차지점들까지의 거리를 구하여 최소값을 갖는 승차지점을 경로에 새롭게 포함시키고 외판원문제 (Traveling Salesman Algorithm; TSP) 알고리듬을 적용하여 경로를 구한다. 본 연구에서 사용한 TSP 알고리듬은 삽입 기반의 알고리듬으로 탐욕적으로(Greedy) 승차지점을 경로에 추가한 후에 2-opt 알고리듬을 사용하여 개선하였다.
이 회사가 운영하는 전체 Site에 적용할 준비중인데 실제 적용을 하게 되면 1,000여대의 차량 감소, 약 $150million의 비용 절감이 실현될 것으로 기대한다. 본 논문에서는 승객 수송문제를 소개하였고 문제의 해법을 위한 방법론과 각 문제에 대한 휴리스틱 해법을 제안하고 개략적으로 기술하였다. 제안된 방법론은 시스템화 되어 실제 문제에 적용되어 그 효과를 검증하였다.
그리고 현재 경로에 포함된 모든 승차지점으로부터 경로에 포함되지 않은 승차지점들까지의 거리를 구하여 최소값을 갖는 승차지점을 경로에 새롭게 포함시키고 외판원문제 (Traveling Salesman Algorithm; TSP) 알고리듬을 적용하여 경로를 구한다. 본 연구에서 사용한 TSP 알고리듬은 삽입 기반의 알고리듬으로 탐욕적으로(Greedy) 승차지점을 경로에 추가한 후에 2-opt 알고리듬을 사용하여 개선하였다. 만약 경로가 제약 조건을 만족한다면 다른 승차지점을 추가해보고, 제약 조건을 위반한다면 마지막에 추가된 승차지점을 경로에서 제외시킨 후에 경로를 완성한다.
[Figure 1]은 승객 수송 문제 해결을 위한 알고리듬을 간략히 나타낸 것이다. 본 연구에서 제안한 승객 수송 문제의 해법은 크게 초기해를 얻는 단계(차량 경로 결정 문제, 차량 스케줄링 문제)와 초기해를 개선하는 프로세스인 Post optimization(경로 재할당, 혼승 재할당) 단계로 나뉜다.
본 연구에서는 승객 수송 문제를 하위 문제(Sub-problems)인 차량 경로 결정 문제, 차량 스케줄링 문제, Post optimization으로 세분화하여 해결하였다. 제 2장에서는 승객 수송 문제의 관련 연구들을 소개하고, 제 3장에서는 초기해 생성과 관련된 하위 문제인 차량 경로 결정 문제, 차량 스케줄링 문제를 다룬다.
이 경우는 하교 문제를 등교 문제로 바꾼 후 등교 계획에 사용한 알고리듬을 그대로 사용하여 하교 계획을 세울 수 있다. 본 연구에서는 위에서 언급한 3가지의 하교 계획 방법을 모두 구현하였고, 사용자가 정책에 맞게 선택하도록 하였다. 하교계획 수립 시 등교계획 순이나 역순을 취하는 방법은 개념적으로는 쉬운 방법이나 알고리듬적으로 구현하기는 등교문제나 하교문제의 해를 개별적으로 찾는 것보다 복잡하고 어려워진다.
환승을 하는 승객들은 대부분 교외의 주거 지역에서 시내의 목적지로 이동하는 승객들로서, 환승 지점 (Transfer station)은 주로 시 경계 지역에 위치한다. 본 연구에서는 환승하는 승객들을 메인 알고리듬을 수행하기 전에 Pre-process로 따로 처리하였다. 이때 환승하는 승객의 정보(환승 지점, 환승 횟수 등)은 미리 주어졌다고 가정하였다.
본 논문에서는 승객 수송문제를 소개하였고 문제의 해법을 위한 방법론과 각 문제에 대한 휴리스틱 해법을 제안하고 개략적으로 기술하였다. 제안된 방법론은 시스템화 되어 실제 문제에 적용되어 그 효과를 검증하였다. 하지만 최적해나 lower bound대비 방법론의 효율성 검증에 대한 연구는 앞으로 이루어져야 한다.
본 연구에서는 차량-경로 간의 할당을 Assignment problem(AP)로 나타내었다. 차량의 수와 경로의 수가 다른 경우에는 Dummy 차량이나 Dummy 경로를 생성하였고, Assignment cost는 차량의 현재 위치와 경로의 시작점 간의 거리이며 목적식은 필요 차량 수의 최소화를 우선으로 하고 다음으로 전체 차량 이동거리의 최소화로 하였다. 차량과 경로간의 Cost를 정할 때에 경로 상의 승객 수가 차량의 용량보다 크거나 차량이 정해진 Time Window 안에 승객을 목적지까지 수송할 수 없다면 Cost를 무한대(∞)로 설정한다.

대상 데이터

개발된 프로그램은 큰 사이즈의 문제(예, 4,000개의 승객 승차지점, 200개의 목적지점, 차량 160대 가량)에서도 빠른 시간(예, 30초 이내)에 가능 해를 구할 수 있었으며, 3개의 도시의 승객수송문제에 적용해 본 결과 실제 운영되고 있는 계획에 비하여 약 10～15%의 차량 감소 효과를 거둘 수 있었다. 본 연구에서 개발된 프로그램은 미국 IIT(Institute of Information Technology, Inc.)사의 인터넷 기반 GIS 응용 프로그램의 핵심 엔진으로 사용되고 있으며 현재 미국에서 10,000여대의 버스를 소유하고 있는 승객 수송 회사에 적용되고 있다.

이론/모형

본 연구에서 고려한 문제와 가장 유사한 기존 문제는 스쿨버스 라우팅 문제 (School bus routing problem, 이하 SBRP)이다. SBRP는 여러 지역에 분포되어 있는 학생들을 해당 학교까지 효과적으로 이동시키는 계획을 세워주는 것으로 버스 스탑 결정 문제와 경로 결정 문제, 버스 스케줄링 문제를 포함하고 있다.
차량 스케줄링 문제는 차량 경로 결정 문제에서 구한 경로 들을 서비스 가능한 차량에 할당하는 것을 의미한다. 본 연구에서는 차량-경로 간의 할당을 Assignment problem(AP)로 나타내었다. 차량의 수와 경로의 수가 다른 경우에는 Dummy 차량이나 Dummy 경로를 생성하였고, Assignment cost는 차량의 현재 위치와 경로의 시작점 간의 거리이며 목적식은 필요 차량 수의 최소화를 우선으로 하고 다음으로 전체 차량 이동거리의 최소화로 하였다.
차량과 경로간의 Cost를 정할 때에 경로 상의 승객 수가 차량의 용량보다 크거나 차량이 정해진 Time Window 안에 승객을 목적지까지 수송할 수 없다면 Cost를 무한대(∞)로 설정한다. 이렇게 세워진 AP 모델은 Hungarian Algorithm (Kuhn, 1955)을 사용하여 해를 구하였다.

성능/효과

본 연구에서는 다양한 제약 조건을 만족시키는 승객 수송 문제의 가능해(Feasible solution)를 빠른 시간에 만들 수 있는 휴리스틱 알고리듬과 프로그램을 개발하였다. 개발된 프로그램은 큰 사이즈의 문제(예, 4,000개의 승객 승차지점, 200개의 목적지점, 차량 160대 가량)에서도 빠른 시간(예, 30초 이내)에 가능 해를 구할 수 있었으며, 3개의 도시의 승객수송문제에 적용해 본 결과 실제 운영되고 있는 계획에 비하여 약 10～15%의 차량 감소 효과를 거둘 수 있었다. 본 연구에서 개발된 프로그램은 미국 IIT(Institute of Information Technology, Inc.
현재 미국에서 10,000여대의 버스를 소유하고 있는 승객 수송 회사에서 프로그램을 적용하고 있는데, 이 회사는 한 도시(Site) 당 50~200대의 버스를 운영하고 있으며, 1대의 운영비는 인건비 포함 연간 약 $150,000정도이다. 개발된 프로그램을 3개 Site에 시범 적용한 결과 현재 운영하고 있는 것과 비교하여 약 10%~15%가량의 차량 감소 효과를 거둘 수 있었다. 이 회사가 운영하는 전체 Site에 적용할 준비중인데 실제 적용을 하게 되면 1,000여대의 차량 감소, 약 $150million의 비용 절감이 실현될 것으로 기대한다.

후속연구

하지만 최적해나 lower bound대비 방법론의 효율성 검증에 대한 연구는 앞으로 이루어져야 한다. 또한 각각의 알고리듬에 대한 보다 자세한 기술이나 실험결과에 대해서는 별도의 논문들로 정리하여 발표할 계획이다.
개발된 프로그램을 3개 Site에 시범 적용한 결과 현재 운영하고 있는 것과 비교하여 약 10%~15%가량의 차량 감소 효과를 거둘 수 있었다. 이 회사가 운영하는 전체 Site에 적용할 준비중인데 실제 적용을 하게 되면 1,000여대의 차량 감소, 약 $150million의 비용 절감이 실현될 것으로 기대한다. 본 논문에서는 승객 수송문제를 소개하였고 문제의 해법을 위한 방법론과 각 문제에 대한 휴리스틱 해법을 제안하고 개략적으로 기술하였다.
제안된 방법론은 시스템화 되어 실제 문제에 적용되어 그 효과를 검증하였다. 하지만 최적해나 lower bound대비 방법론의 효율성 검증에 대한 연구는 앞으로 이루어져야 한다. 또한 각각의 알고리듬에 대한 보다 자세한 기술이나 실험결과에 대해서는 별도의 논문들로 정리하여 발표할 계획이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	승객 수송 문제는 어떤 것인가?	승객 수송 문제는 다수의 승객들을 출발지로부터 그들의 목적지까지 수송하는 최적 계획을 세우는 것으로서, 예로는 스쿨버스 라우팅 문제(School bus routing problem), 통근 버스 라우팅 문제(Commuter bus routing problem) 등이 있다. 특히 스쿨버스의 경우 미국에서만 약 44만대가 운영되고 있으며, 2천 4백만 명에 달하는 학생들이 서비스를 이용하는 등 미국 내에서 가장 거대한 공공운송 사업이다.
	승객 수송 문제에는 무엇이 존재하나?	승객 수송 문제에서는 여러 개의 승차지점과 하차지점이 존재하며, 승객들은 승차지점에서 버스에 탑승하여, 자신의 목적지인 하차지점에서 하차하게 된다. 각 승차지점에서는 여러 목적지로 향하는 승객이 탑승 가능하며, 한 대의 버스는 여러 곳의 목적지점을 방문할 수 있다.
	승객 수송 문제에서 사용되는 제약조건은 무엇인가?	승객 수송 문제는 널리 알려진 최적화 문제인 차량 경로 문제(Vehicle routing problem, 이하 VRP)와 유사하나 화물이 아닌 사람의 수송을 다루는 문제이므로 몇 가지 추가적인 제약 조건을 필요로 한다. 일반적으로 사용되는 제약 조건으로는 차량의 용량(Vehicle capacity), 승객이 차량에 머무를 수 있는 최대 시간(Maximum allowable riding time in a bus), 목적지에 도착해야 하는 시간을 지정한 시간 창(Time window) 등이 있다. 또 많은 연구에서 다루지는 않았지만 혼승(Mixed loading)이나 환승(Transfer) 등도 고려될 수 있다.

참고문헌 (19)

Bodin, L. D. and Berman, L. (1979), Routing and scheduling of school buses by computer, Transportation Science, 13, 113-129.

상세보기
Bowerman, R., Hall, B., and Calamai, P. (1995), A multi-objective optimization approach to urban school bus routing : formulation and solution method. Transportation Research Part A, 29(2), 107-123.
Braca, J., Bramel, J., Posner, B., and Simchi-Levi, D. (1997), A Computerized Approach to the New York City School Bus Routing Problem, IIE Transactions, 29, 693-702.

상세보기
Cortes, C. E., Matamala, M., and Contardo, C. (2010), The pickup and delivery problem with transfers : formulation and a branch-and-cut solution method, European Journal of Operational Research, 200, 711-724.

상세보기
Desrosiers, J., Ferland, J. A., Rousseau, J.-M., Lapalme, G., and Chapleau, L. (1986), TRANSCOL : a multi-period school bus routing and scheduling system, TIMS Studies in the Management Sciences, 22, 47-71.
Fugenschuh, A. (2009), Solving a school bus scheduling problem with integer programming, European Journal of Operational Research, 193(3), 867-884.

상세보기
Gavish, B. and Shlifer, E. (1979), An approach for solving a class of transportation scheduling problems, European Journal of Operational Research, 3(2), 122-134.

상세보기
Gillett, B. E. and Miller, L. R. (1974), A heuristic algorithm for the vehicle dispatch problem, Operations Research, 22, 340-349.

상세보기
Kara, I. and Bektas, T. (2006), Integer linear programming formulations of multiple salesman problems and its variation, European Journal of Operational Research, 174(3), 1449-1458.

상세보기
Kuhn, H. W. (1955), The Hungarian Method for the assignment problem, Naval Research Logistics Quarterly, 2, 83-97.

상세보기
Li, L. and Fu, Z. (2002), The school bus routing problem: a case study, Journal of the Operational Research Society, 53, 552-558.

상세보기
Park, J., Tae, H., and Kim, B. (2009), The Effects of Allowing Mixed Loads in the Commuter Bus Routing Problem, Proceedings of the 10th Asia Pacific Industrial Engineering and Management Systems Conference, December 14-16, 2009, Kitakyushu, Japan.
Park, J. and Kim, B. (2010), The School Bus Routing Problem : A Review, European Journal of Operational Research, 202(2), 311-319.

상세보기
Ripplinger, D. (2005), Rural school vehicle routing problem, Transportation Research Record, 1992, 105-110.
Russell, R. A. and Morrel, R. B. (1986), Routing special-education school buses, Interfaces 16(5), 56-64.

상세보기
Schittekat, P., Sevaux, M., and Sorensen, K. (2006), A mathematical formulation for a school bus routing problem, Proceedings of the IEEE 2006 International Conference on Service Systems and Service Management.
Spada, M., Bierlaire, M., Liebling, and Th. M. (2005), Decision-aiding methodology for the school bus routing and scheduling problem, Transporation Science, 39, 477-490.

상세보기
Swersey, A. J. and Ballard, W. (1984), Scheduling school buses, Management Science, 30(7), 844？853.

상세보기
White, G. P. (1982), An improvement in Gavish-Shlifer algorithm for a class of transportation scheduling problems, European Journal of Operational Research 9(2), 190-193.

상세보기

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

연합인증