[논문]실시간 재배치를 통한 카쉐어링 서비스 최적화에 관한 연구 : PSO 방법론 기반으로

이건영; 이형석; 홍요한; 고성석

doi:10.11627/jkise.2016.39.2.028

실시간 재배치를 통한 카쉐어링 서비스 최적화에 관한 연구 : PSO 방법론 기반으로
The Optimization of One-way Car-Sharing Service by Dynamic Relocation : Based on PSO Algorithm 원문보기

Journal of Korean Society of Industrial and Systems Engineering = 한국산업경영시스템학회지, v.39 no.2, 2016년, pp.28 - 36

이건영 (건국대학교 산업공학과) , 이형석 (건국대학교 산업공학과) , 홍요한 (건국대학교 산업공학과) , 고성석 (건국대학교 산업공학과)

Abstract ▼ AI-Helper

Recently, owing to the development of ICT industry and wide spread of smart phone, the number of people who use car sharing service are increased rapidly. Currently two-way car sharing system with same rental and return locations are mainly operated since this system can be easily implemented and maintained. Currently the demand of one-way car sharing service has increase explosively. But this system have several obstacle in operation, especially, vehicle stock imbalance issues which invoke vehicle relocation. Hence in this study, we present an optimization approach to depot location and relocation policy in one-way car sharing systems. At first, we modelled as mixed-integer programming models whose objective is to maximize the profits of a car sharing organization considering all the revenues and costs involved and several constraints of relocation policy. And to solve this problem efficiently, we proposed a new method based on particle swarm optimization, which is one of powerful meta-heuristic method. The practical usefulness of the approach is illustrated with a case study involving satellite cities in Seoul Metrolitan Area including several candidate area where this kind systems have not been installed yet and already operating area. Our proposed approach produced plausible solutions with rapid computational time and a little deviation from optimal solution obtained by CPLEX Optimizer. Also we can find that particle swarm optimization method can be used as efficient method with various constraints. Hence based on this results, we can grasp a clear insight into the impact of depot location and relocation policy schemes on the profitability of such systems.

주제어

AI 본문요약
AI-Helper

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

문제 정의

이는 실시간으로 받아들이는 수요량과 재배치량에 대한 의사결정에 어려움을 발생시킨다. 따라서 본 연구는 메타 휴리스틱 기법 중 최근에 가장 많이 적용되고 있는 입자군집 최적화(Particle Swarm Optimiza tion : PSO) 기법을 적용하여 효율적인 해를 구하는 방안을 제시하고자 한다.
위성도시에서의 카쉐어링 이용수요는 주변 대도시로의 출근, 여가, 쇼핑 등 편도통행 방식인 경우가 대부분이므로 왕복통행보다는 편도통행 방식이 적합하다[8, 11]. 따라서 본 연구는 위성도시의 특징을 반영하여 효율적인 편도 시스템의 도입과 운영자의 수익을 최대화하기 위한 실시간 수요와 재배치를 고려한 통합모형을 제시한다.
수도권 지역 위성도시에 카쉐어링 서비스의 최적화를 위하여 재배치 차량 수, 초기차량 수, 주차장 크기, 선정입지 등을 산정하고자 본 연구를 수행하였다. PSO 알고리즘을 활용함으로서 보다 빠른 해 탐색이 가능하고 운영단위 시간에 따라 실시간으로 수요와 재배치를 반영하는 통합모형을 사용하였다.

제안 방법

[11]의 수식을 사용했다. Zone 및 입지 후보지 사이의 쇼핑/여가/배웅/기타, 출퇴근, 업무 등 목적별 통행량을 산출한 후, 카쉐어링 서비스 이용통행비율과 대중교통 이용비율을 이용하여 예상 수요를 산출하였다. [Table 3]은 편도통행 방식이 가장 활발히 사용되는 출근 시간대의 10분 단위의 수요 예측 모형이다.
다음으로 사용된 차량 수와 재배치된 차량 수를 비교하였다. [Figure 7]와 같이 사용된 차량 수는 차이가 없는 반면, 재배치된 차량 수는 [Figure 8]과 같이 차이가 있다.
둘째, 재배치에 대한 비용으로 실시간으로 이뤄지는 재배치를 고려하여 단위시간당 재배치 비용(Cr)과 재배치되는 차량 수(R#) 및 소요시간(δij)을 곱하여 산출한다.
본 연구에서 활용한 PSO 알고리즘을 통해 구한 해와 IBM ILOG CPLEX Optimizer를 통해 얻은 해와 비교를 통해 본 연구에서 제시한 PSO 알고리즘의 유용성을 검증하였다. 먼저 PSO 알고리즘을 통해 얻은 결과는 [Table 6]의 결과와 같이 약 4%의 오차를 나타내었지만 연산 속도는 PSO 알고리즘이 CPLEX에 비해 약 8배 빠른 결과를 보였다.
시간적 범위는 차량 재배치 과정은 최소 운영단위인 10분마다 이루어지며, 실험 기간은 일반적인 특성이 반영되는 평일(5일)로 설정하였다. 공간적 범위는 수도권인 서울과 경기 지역의 위성도시 중 예상 수요 상위 6곳으로 설정하였다.
[2]은 카쉐어링 서비스를 3가지로 구분하였다. 운영자의 최대의 수익을 위해 수요를 자유롭게 선택 하는 Controlled Service와 모든 수요를 만족시키는 Full Service, 주차장 내 차량이 없을 경우에 수요를 거부하는 Conditional Service로 분류하여 최적 차량 대여소의 입지및 차량 수와 운영 후 재배치에 대한 모형을 제시하였다. Han[4]는 Correia et al.
식(11)에 따라 Velocity가 수정되고, 수정된 Velocity와 위치가 조절된다. 이후 종료조건에 이르지 않으면, 각 Particle들은 목적함수의 결과에 의해 다시 평가하여 최적의 해를 도출한다.
첫째, 사용한 차량의 유지비용으로 차량 운행 시 소모되는 차량의 부품 및 성능에 대한 비용을 나타내고 차량 1대의 유지비용(Cm1)과 사용된 차량 수(D#) 및 소요시간(δij)을 곱하여 산출한다.
초기 해는 각 기간마다 주차장 i에서 주차장 j로 이동하는 수요량(Q#)과 최소로 허용되는 수요량(Q_min × Q#) 사이의 임의의 수로 구한다. 최적 해를 탐색할 때, 수리모형의 목적식을 비교하여 해를 평가한 후 P-best와 Gbest를 산출한다. 그 후 식 (1)과 식 (2)를 이용하여 속도를 갱신한 후 Particle의 다음 위치를 구한다.
[9]는 효율적인 편도 시스템을 위한 차량 수, 카쉐어링 존(Zone)별 주차면 수를 결정하였다. 편도통행의 문제를 해소하고자 해당 연구의 시간적 범위를 운영 중과 후로 나누어 재배치 기간을 단발성과 실시간으로 구분하였다. Ganjar et al.

대상 데이터

시간적 범위는 차량 재배치 과정은 최소 운영단위인 10분마다 이루어지며, 실험 기간은 일반적인 특성이 반영되는 평일(5일)로 설정하였다. 공간적 범위는 수도권인 서울과 경기 지역의 위성도시 중 예상 수요 상위 6곳으로 설정하였다.
[Table 4]은 사용된 차량 수와 재배치 차량 수와 비용에 대한 결과이다. 사용 차량 수는 일정한 규칙을 보이며 약 35,900대가 사용되었다. 또한 재배치 차량 수는 일별로 산발적인 형태를 띠고 있으며 실험 기간 동안 4,049회의 재배치가 일어났다.
현재 카쉐어링 서비스가 도입된 지역은 서울의 27개 구와 경기 지역의 8개 시이므로 총 8개의 Zone을 생성하였다. 새로 도입될 입지 후보지는 기 도입된 경기지역과의 거리, 인구의 기준으로 하여 평택시, 남양주시, 화성시, 광주시, 양주시, 가평군(총 6곳)을 선정하였다.
입지후보지는 기존에 도입된 지역과 새로 도입될 지역을 구분하여 선정하였다. 기존에 도입된 지역의 경우, 일정 수준의 편도 수요를 충족시키기 위해 1∼7개의 지역을 1개의 Zone으로 설정하였다.

이론/모형

수도권 지역 위성도시에 카쉐어링 서비스의 최적화를 위하여 재배치 차량 수, 초기차량 수, 주차장 크기, 선정입지 등을 산정하고자 본 연구를 수행하였다. PSO 알고리즘을 활용함으로서 보다 빠른 해 탐색이 가능하고 운영단위 시간에 따라 실시간으로 수요와 재배치를 반영하는 통합모형을 사용하였다.
각 입지에서의 예상 수요는 카쉐어링 서비스의 도입효과 및 수요를 추정한 Park et al.[11]의 수식을 사용했다. Zone 및 입지 후보지 사이의 쇼핑/여가/배웅/기타, 출퇴근, 업무 등 목적별 통행량을 산출한 후, 카쉐어링 서비스 이용통행비율과 대중교통 이용비율을 이용하여 예상 수요를 산출하였다.
이는 실시간으로 받아들이는 수요량과 재배치량에 대한 의사결정에 어려움을 발생시킨다. 따라서 빠른 시간 안에 수요량과 재배치에 관한 정수해의 산출이 필요하므로 Meta Heuristic 방법 중 최근에 가장 많이 적용되고 있는 PSO를 이용하였다[13].

성능/효과

CPLEX를 이용한 최적해와 비교해본 결과, 재배치 차량 수와 주차장 크기 부분에서 차이가 있는 것으로 분석되었으나 초기 차량의 수나 사용된 차량의 수 등은 비슷한 결과를 보여 주었으며 8배 이상의 연산 속도를 보여 줌으로써 본 연구에서 제안한 알고리즘을 유용성이 충분히 검증될 수 있었다.
[1]와 Correia et al.[2]에서 제시된 일정 기간 단위로 실행되는 단발성 재배치 전략은 운영 중에 지역 간 차량의 불균형을 초래하고 결과적으로 카쉐어링 서비스의 운영자는 높은 차량 수를 유지해야 한다. 둘째, 기존 연구는 모든 수요를 만족시키기 위해 최소의 비용으로 재배치를 결정하는 단일 의사결정 모델이다.
따라서 대여소 크기(Z_i)와 곱하여 산출한다. 넷째, 보유하고 있는 모든 차량의 감가상각비용이다. 차량 1대당 감가상각비용(C_v)과 전체 차량 수(S#)를 곱하여 산출한다.
본 연구에서 활용한 PSO 알고리즘을 통해 구한 해와 IBM ILOG CPLEX Optimizer를 통해 얻은 해와 비교를 통해 본 연구에서 제시한 PSO 알고리즘의 유용성을 검증하였다. 먼저 PSO 알고리즘을 통해 얻은 결과는 [Table 6]의 결과와 같이 약 4%의 오차를 나타내었지만 연산 속도는 PSO 알고리즘이 CPLEX에 비해 약 8배 빠른 결과를 보였다.
운영자의 최대 수익을 위해서는 수요에 따른 이익과 재배치 비용을 함께 고려함으로써 통합적인 의사 결정 모델을 구축해야 한다. 셋째, 기존연구에서 사용된 Mixed Integer Programming(MIP)은 주차장 수의 증가, 재배치 간격의 감소 등 문제의 크기가 커질수록 해결 시간이 기하급수적으로 증가한다. 그러므로 빠른 시간 안에 해를 도출하는 방법론이 필요하다.
둘째, 재배치에 대한 비용으로 실시간으로 이뤄지는 재배치를 고려하여 단위시간당 재배치 비용(C_r)과 재배치되는 차량 수(R#) 및 소요시간(δ_ij)을 곱하여 산출한다. 셋째, 주차 공간에 대해 지불하는 비용이며, 카쉐어링 서비스는 기존의 주차 기반 시설을 이용하기 때문에 공간 대여 비용 (C_m2)을 지불한다. 따라서 대여소 크기(Z_i)와 곱하여 산출한다.
주차장 크기는 실험 기간 동안 주차된 차량 수 중 가장 큰 값에 따라 결정되었으며, 남양주가 가장 높게 나타났다. 전체 비용 중 차량 유지비용이 약 47%로 가장 높게 나타났으며, 재배치 비용이 37%로 다음으로 높게 나타났다.
[Table 5]는 주차장 크기와 입지별 초기차량 수에 대한 결과이다. 주차장 크기는 실험 기간 동안 주차된 차량 수 중 가장 큰 값에 따라 결정되었으며, 남양주가 가장 높게 나타났다. 전체 비용 중 차량 유지비용이 약 47%로 가장 높게 나타났으며, 재배치 비용이 37%로 다음으로 높게 나타났다.

후속연구

그러나 카쉐어링 시스템의 다양한 환경 및 기능에 대한 고려 즉 수요의 거절과 시스템 도입 등에 따라 추가적으로 발생하는 비용 및 지역에 따른 교통상황 등을 반영하지 못하는 한계점을 가지고 있다. 이러한 한계점은 지속적인 연구를 통해 카쉐어링 서비스의 고객서비스 향상, 수익성 증대 그리고 다른 위성도시에의 활용까지 가능할 것으로 생각된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	통행관점에서 카쉐어링 서비스를 운영방식은 어떻게 구분되나?	카쉐어링 서비스를 운영방식과 통행관점으로 보면 왕복통행과 편도통행으로 구분한다. 왕복통행은 대여지점과 반납지점이 동일한 형태이고 편도통행은 대여지점과 반납지점이 다른 형태이다.
	카쉐어링 서비스의 역할은?	카쉐어링 서비스는 일반적으로 렌터카와 달리 사전에 가입된 회원들이 다양하게 분산되어 있는 승용차 공동이용 차량을 인터넷, 모바일, ARS 등을 통하여 차량 이용을 예약한 후 필요한 시간만큼 단기간 이용할 수 있는 서비스로 대중교통의 보완재 역할을 하며, IT 기술의 발달로 인터넷과 스마트폰 어플을 통해 무인대여소 운영이 가능한 특징이 있다. 국내에는 2009년 최초 서비스가 시작된 후, [Figure 1]과 같이 회원 수는 205만 명, 차량 수 3,450대의 규모(2015년 10월 기준)로 증가하고 있다[7].
	카쉐어링 서비스에서 왕복통행과 편도통행이 갖는 특징은?	카쉐어링 서비스를 운영방식과 통행관점으로 보면 왕복통행과 편도통행으로 구분한다. 왕복통행은 대여지점과 반납지점이 동일한 형태이고 편도통행은 대여지점과 반납지점이 다른 형태이다. 이 서비스의 활성화를 위해서는 모든 방식의 형태가 제공되어져야 하나 편도통행 방식의 카쉐어링 서비스는 시간이 지남에 따라 주차장에 저장되는 차량의 불균형을 유발하기 때문에 서비스 제공을 위해서는 왕복통행 방식보다 많은 수의 차량을 운영해야 하는 문제점이 있다[12].

참고문헌 (15)

Alfian, G., Farooq, U., and Rhee, J., Ant Colony Optimization for Relocation Problem in Carsharing, Journal of 2013 KIIE Spring Conference, 2013, pp. 1859- 1866.
Correia, G. and Antunes, A., Optimization approach to depot location and trip selection in one-way carsharing systems, Transportation Research Part E : Logistics and Transportation Review, 2012, Vol. 48, No. 1, pp. 233-247.

상세보기
Del Valle, Y., Venayagamoorthy, G.K., Mohagheghi, S., and Hernandez, J.-C., Particle Swarm Optimization, Basic Concepts, Variants and Applications in Power Systems, IEEE Transactions on Evolutionary Computation TEC, 2008, Vol. 12, No. 2, pp. 171-195.

상세보기
Han, J.H., One-way Carsharing system Optimization through Real-time relocation of vehicle, Journal of 2014 KIIE Fall Conference, 2014, pp. 44-58.
Jung, I.S., Yeo, S.J., Bae, J.H., and Wang, G.N., An Approach of heuristic rule for the quay assignment, Journal of the Korean Institute of Plant Engineering, 2008, Vol. 13, No. 3, pp. 59-66.
Kennedy, J. and Everhart, R.C., Particle Swarm Optimization, Proc. of the IEEE Int. Conf. on Neural Networks, 1995, pp. 1942-1948.
Kim, J.S., Park, K.C., and Ko, J., Socio-economic Effects of Carsharing, Issue and Analysis, 2015, Vol. 183, pp. 1-25.
Kim, S.H., Jung, H.J., and Bea, S.H., Development of a Vehicle Relocation Algorithm for the Promotion of One-way Car Sharing Service, Journal of Korean Society of Transportation, 2014, Vol. 32, No. 2, pp. 239-247.

원문보기 상세보기
Kim, S.H., Lee, K.J., and Choi, K.J., Preferences Factors Analysis for Car-sharing, Journal of The KSCE, 2014, Vol. 34, No. 4, pp. 1241-1249.

원문보기 상세보기
Park, B.J., Oh, S.K., Kim, Y.S., and An, T.C., Comparative Study on Dimensionality and Characteristic of PSO, Journal of Institute of Control, Robotics and Systems, 2006, Vol. 12, No. 4, pp. 328-338.
Park, J.S. and Moon, J.H., Demand Estimation and Impact Analysis of Car-Sharing Service, Journal of Transport Research, 2013, Vol. 20, No. 2, pp. 59-75.
Park, J.S. and Moon, J.H., Estimation of the Demand for Car-Sharing Service, The Korea Transport Institute Spot Research Report, 2012, Vol. 24, pp. 1-149.
Talukder, S., Mathematical Modelling and Applications of Particle Swarm Optimization, Master's Thesis Mathematical Modelling and Simulation Thesis, 2011.
Yim, D.-S., Particle Swarm Optimizations to Solve Multi- Valued Discrete Problems, Journal of the Society of Korea Industrial and Systems Engineering, 2013, Vol. 36, No. 3, pp 63-70.
Zarkoob, H., Optimizaing One-Way Car Sharing Systems, [master's thesis]. [Burnaby, Canada] : SIMON FRASER University, 2015.

저자의 다른 논문 :

표제어: 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

연합인증