1서 론

카쉐어링 서비스는 일반적으로 렌터카와 달리 사전에 가입된 회원들이 다양하게 분산되어 있는 승용차 공동이 용 차량을 인터넷, 모바일, ARS 등을 통하여 차량 이용 을 예약한 후 필요한 시간만큼 단기간 이용할 수 있는 서 비스로 대중교통의 보완재 역할을 하며, IT 기술의 발달 로 인터넷과 스마트폰 어플을 통해 무인대여소 운영이 가능한 특징이 있다. 국내에는 2009년 최초 서비스가 시 작된 후, <Figure 1>과 같이 회원 수는 205만 명, 차량 수 3,450대의 규모(2015년 10월 기준)로 증가하고 있다[7].

카쉐어링 서비스를 운영방식과 통행관점으로 보면 왕 복통행과 편도통행으로 구분한다. 왕복통행은 대여지점 과 반납지점이 동일한 형태이고 편도통행은 대여지점과 반납지점이 다른 형태이다. 이 서비스의 활성화를 위해서 는 모든 방식의 형태가 제공되어져야 하나 편도통행 방식 의 카쉐어링 서비스는 시간이 지남에 따라 주차장에 저장 되는 차량의 불균형을 유발하기 때문에 서비스 제공을 위 해서는 왕복통행 방식보다 많은 수의 차량을 운영해야 하 는 문제점이 있다[12]. 따라서 효율적인 편도 시스템의 도 입과 운영을 위해서 차량의 재배치는 카쉐어링 시스템에 서 중요한 이슈이다. 하지만 기존 국내의 도입 방식은 왕 복과 재배치가 고려되지 않은 편도 시스템으로 운영되고 있다.

수도권 내 카쉐어링 서비스 대여소의 위치를 나타낸 <Figure 2>와 같이 아직 설치되지 않은 위성도시가 많다. 위성도시에서의 카쉐어링 이용수요는 주변 대도시로의 출근, 여가, 쇼핑 등 편도통행 방식인 경우가 대부분이므 로 왕복통행보다는 편도통행 방식이 적합하다[8, 11]. 따 라서 본 연구는 위성도시의 특징을 반영하여 효율적인 편 도 시스템의 도입과 운영자의 수익을 최대화하기 위한 실 시간 수요와 재배치를 고려한 통합모형을 제시한다.

Correia et al.[2]은 카쉐어링 서비스를 3가지로 구분하 였다. 운영자의 최대의 수익을 위해 수요를 자유롭게 선택 하는 Controlled Service와 모든 수요를 만족시키는 Full Service, 주차장 내 차량이 없을 경우에 수요를 거부하는 Conditional Service로 분류하여 최적 차량 대여소의 입지 및 차량 수와 운영 후 재배치에 대한 모형을 제시하였다. Han[4]는 Correia et al.[2]의 연구에서 재배치로 인해 유지 해야하는 높은 차량 수를 문제로 제기하고 수요를 모두 만족시키는 Full Service에 대해 운영 중 재배치 의사결정 을 위한 해법을 제시하였다. Kim et al.[9]는 효율적인 편 도 시스템을 위한 차량 수, 카쉐어링 존(Zone)별 주차면 수를 결정하였다. 편도통행의 문제를 해소하고자 해당 연구의 시간적 범위를 운영 중과 후로 나누어 재배치 기 간을 단발성과 실시간으로 구분하였다. Ganjar et al.[1]은 편도통행 방식의 카쉐어링 서비스에서 모든 수요를 만족 시키기 위해 최소의 비용으로 차량을 재배치하는 모형을 제시하고 개미 군집 알고리즘으로 해결하였다. Hedayat[15] 은 고객 수요가 결정적(Deterministic)일 때와 확률적(Stochastic) 일 때의 카쉐어링 서비스의 최적화 해법을 위하 여 각각 Mixed Integer Programming(MIP)와 휴리스틱 알 고리즘[5]을 개발하였다.

그러나 이들의 연구를 위성도시에 적용하기에는 몇 가 지 한계점이 나타난다. 첫째, 위성도시에서의 카쉐어링 이 용수요는 주변 대도시로의 편도통행 방식인 경우가 대부 분이다. 따라서 Alfian et al.[1]와 Correia et al.[2]에서 제 시된 일정 기간 단위로 실행되는 단발성 재배치 전략은 운영 중에 지역 간 차량의 불균형을 초래하고 결과적으 로 카쉐어링 서비스의 운영자는 높은 차량 수를 유지해 야 한다. 둘째, 기존 연구는 모든 수요를 만족시키기 위 해 최소의 비용으로 재배치를 결정하는 단일 의사결정 모델이다. 운영자의 최대 수익을 위해서는 수요에 따른 이익과 재배치 비용을 함께 고려함으로써 통합적인 의사 결정 모델을 구축해야 한다. 셋째, 기존연구에서 사용된 Mixed Integer Programming(MIP)은 주차장 수의 증가, 재배치 간격의 감소 등 문제의 크기가 커질수록 해결 시 간이 기하급수적으로 증가한다. 그러므로 빠른 시간 안 에 해를 도출하는 방법론이 필요하다.

이러한 카쉐어링 서비스의 최적화 문제는 위성도시에 서의 입지와 초기 차량 수, 주차장 크기, 기간 별 수용하 는 수요량과 재배치량을 구하는 NP-Hard 문제라고 알려 져 있다[15]. 고려하는 지역의 크기가 증가하거나 재배치 를 고려하는 기간이 짧아질수록 해를 찾는 시간이 기하급 수적으로 증가한다. 이는 실시간으로 받아들이는 수요량 과 재배치량에 대한 의사결정에 어려움을 발생시킨다. 따 라서 본 연구는 메타 휴리스틱 기법 중 최근에 가장 많이 적용되고 있는 입자군집 최적화(Particle Swarm Optimiza tion : PSO) 기법을 적용하여 효율적인 해를 구하는 방안 을 제시하고자 한다.

본 연구는 제 2장에서 본 연구에서 다루는 문제를 수 학적으로 모델링을 하고, 입자군집 최적화 방법론을 적 용하여 카쉐어링 문제를 접근하는 방법론은 제 3장에서 서술하고자 하며, 제 4장은 수도권을 중심으로 새로운 입지를 선정할 경우를 대상으로 사례 분석을 실시하고 자 하면, 제 5장은 본 연구에 대한 결론으로 마무리하고 자 한다.

2카쉐어링 수리 모형

본 연구는 편도통행 방식의 카쉐어링 서비스를 위성 도시에 도입하기 위해 운영자의 최대 이익을 위한 기간 별 수요량과 재배치량의 의사결정 모델을 제시하고자 실 시간 재배치를 적용할 수 있는 Correia et al.[2]에서 제시 된 Controlled Service를 기반으로 하고 있다.

편도통행 방식의 카쉐어링 서비스에서 단발성 재배치 는 실시간 재배치보다 많은 수의 차량 유지해야만 가능 하다. 따라서 차량유지 비용을 증가시키며 결과적으로 전체 이익을 감소시킨다고 할 수 있다[4]. 따라서 편도통 행 방식 수요가 대다수인 위성도시에서의 특성을 반영하 기 위해 실시간 재배치를 사용하는 것이 효율적이라 할 수 있다.

모형 수립에 앞서 필요한 변수와 모수들에 대해서 다 음과 같이 정의하고자 한다.

• 집합

N = {1 ⋯ i ⋯N} :

주차지역을 나타내는 집합

T = {1 ⋯ t ⋯T} :

운영시간 동안 시간 간격으로 이루 어진 집합

X = [1₁ ⋯ i_t ⋯ N_t} :

주차지역과 시간 간격의 결합으로 이루어진 네트워크 노드의 집합(X = X₁∪X₂)

X₁ :

기 지정된 주차지역과 시간 간격의 결합으로 이 루어진 네트워크 모델의 노드 집합

X₂ :

후보 주차지역과 시간 간격의 결합으로 이루어 진 네트워크 모델의 노드 집합

A= { ⋯ a 1 ( i t , i t + δ i j t ) ⋯ } , i i ∈ X :

집합 X의 각 노드를 연결하는 Arc의 집합

• 의사결정변수

D i t j t + δ i j :

시간 [t, t + δ_ij]사이에 지역 i에서 j으로 사용 되는 차량 수

R i t j t + δ i j :

시간[t, t + δ_ij] 사이에 지역 i에서 j으로 재배 치되는 차량 수

Z_i :

주차지역 i의 크기

S i 0 :

지역 i의 초기차량 수

Y_i :

후보지 i가 선택되었다면 1, 아니면 0을 갖는 이진변수

• 주요모수

C_r :

차량 당 재배치 비용

C_m2 :

주차 공간의 일간 유지비용

C_υ :

일간 차량 감가상각비

δ_ij :

지역 i와 j의 운행 시간

Q i t j t + δ i j :

시간[t, t + δ_ij]에 지역 i와 j의 수요

Q_min :

최소 수요 충족비율

R_max :

최대 재배치 허용량

M :

Big-M

위성도시의 특징을 반영하여 효율적인 편도 시스템의 도입과 운영을 위해 실시간 재배치를 고려한 통합모형을 위의 표기법을 사용하여 나타내면 다음과 같다.

목적함수

제약조건

목적식 (1)은 기간별 수용하는 수요에서 얻는 운영수 익과 재배치 및 차량 관련 비용의 차이인 이익으로 정의 할 수 있다. 운영수익은 시간 당 대여금액(P )과 사용된 차량 수( D i t j t + δ i j )를 이용해 산출하며, 차량 관련 비용은 네 가지 항목으로 이루어져 있다. 첫째, 사용한 차량의 유지 비용으로 차량 운행 시 소모되는 차량의 부품 및 성능에 대한 비용을 나타내고 차량 1대의 유지비용(C_m1)과 사용 된 차량 수( D i t j t + δ i j ) 및 소요시간(δ_ij)을 곱하여 산출한다. 둘 째, 재배치에 대한 비용으로 실시간으로 이뤄지는 재배치 를 고려하여 단위시간당 재배치 비용(C_r )과 재배치되는 차량 수( R i t j t + δ i j ) 및 소요시간(δ_ij)을 곱하여 산출한다. 셋째, 주차 공간에 대해 지불하는 비용이며, 카쉐어링 서비스는 기존의 주차 기반 시설을 이용하기 때문에 공간 대여 비용 (C_m2)을 지불한다. 따라서 대여소 크기( Z_i )와 곱하여 산 출한다. 넷째, 보유하고 있는 모든 차량의 감가상각비용 이다. 차량 1대당 감가상각비용(C_υ)과 전체 차량 수( S i 1) 를 곱하여 산출한다.

식 (2)~식 (9)는 제약조건으로써 카쉐어링의 기본적 인 운영을 조건과 재배치로 인한 추가적인 사항이 포함 되어 있다.

식 (2)은 주차장 i에 t - 1시간에 있던 기존 차량 수를 의미하는 V i t − 1 에서 t기간에 주차장 j로 이용자가 타고 이 동한 차량( ∑ j t ∈ X D i t j t + δ i j )과 재배치된 차량 수( ∑ j t ∈ X R i t j t + δ i j )를 빼고 기간 t에 주차장 j에서 주차장 i로 도착한 차량 수 ( ∑ j t ∈ X D j t + δ i j i t )와 재배치된 차량 수( ∑ j t ∈ X R j t + δ i j i t)를 더하면 S i t 가 되는 것을 의미한다. 식 (3)와 식 (4)는 사용된 차량 수 는 수요를 넘을 수 없으며 주차장 i에서 j로 가는 수요 중 사용된 차량 수의 비율은 최소한의 요구된 수요비율 (Q_min ) 이상을 받아 들여야 한다는 조건이다. 식 (5)은 주 차장 i에서 j로의 재배치된 차량 수는 최대 재배치 차량 수를 넘을 수 없음을 의미한다. 식 (6)은 주차장 i에 저장 되는 차량 수보다 주차 용량이 커야한다는 조건이다. 식 (7)은 후보지에 대여소가 설치되지 않으면 차량 수는 0 대라는 의미이다. 식 (8)은 대여소가 도입된 지역의 주차 장 크기 제약을 의미하며, z_a는 도입된 지역의 대여소의 주차 용량 크기이다. 식 (9)은 도입된 지역의 초기 차량 수( S i 0 )는 t = 0일 때, 차량 수(s_a)와 같다는 의미이다. 또 한, N_a는 선정되는 후보지들의 집합이다.

3최적화 알고리즘

3.1입자군집 최적화(PSO) 방법론

Kennedy et al.[6]에서 PSO(Particle swarm optimization) 는 Meta heuristic 방법 중 하나로 자연에서 집단행동을 하 는 동물들이 무리를 형성하고, 집단경험에 기반을 두어 해 결책을 발견하는 알고리즘이다[3, 10, 14]. PSO의 구성요 소는 Particle, Swarm, P-best, G-best, Velocity이다. Swarm은 Particle을 포함하는 n차원의 집합이다. Particle은 Swarm 에 속해 있는 하나의 객체이며, 같은 체제 하에 독립적으 로 움직인다. 이는 하나의 해로써 위치는 식 (10)과 같이 n차원의 실수 벡터로 표현된다. P-best는 Swarm을 여러 구 역으로 나누어 해당 구역 내에서 최적의 위치정보를 가진 Particle이다. G-best는 P-best 중에서 가장 최적의 위치를 나타내는 Particle이다. 따라서 주어진 문제의 최적 해는 G-best로 나타나며 Particle의 위치와 속도에 영향을 준다. Velocity는 식 (11)과 같고 Particle 속도를 나타내는 벡터 이다. 각 Particle이 가지는 이동속도와 방향을 의미한다. 구성요소를 변수로 표시하면 최적해 탐색 과정에서 필요 한 구성요소를 변수로 나타내면 다음과 같다.

PSO 알고리즘의 절차는 <Figure 3>과 같다. PSO에서 각 Particle은 문제의 후보 해를 나타내며 Particle은 n차원의 실수 벡터로 구성되어 Swarm안에 놓여진다. 초기 Swarm 내의 각각의 Particle은 설정한 크기에 맞게 무작위로 생성, 배치되어 목적함수에 따라 적합성이 평가되고, P-best로 설정한다. P-best 중 최적의 값은 G-best로 선정된다. 식 (11)에 따라 Velocity가 수정되고, 수정된 Velocity와 위치 가 조절된다. 이후 종료조건에 이르지 않으면, 각 Particle 들은 목적함수의 결과에 의해 다시 평가하여 최적의 해를 도출한다.

카쉐어링 문제는 위성도시에서의 입지와 초기 차량 수, 주차장 크기, 기간 별 수용하는 수요량과 재배치량을 구 하는 NP-Hard 문제이다. 고려하는 지역의 크기가 증가하 거나 재배치를 고려하는 기간이 짧아질수록 해를 찾는 시 간이 기하급수적으로 증가한다. 이는 실시간으로 받아들 이는 수요량과 재배치량에 대한 의사결정에 어려움을 발 생시킨다. 따라서 빠른 시간 안에 수요량과 재배치에 관 한 정수해의 산출이 필요하므로 Meta Heuristic 방법 중 최근에 가장 많이 적용되고 있는 PSO를 이용하였다[13].

3.2초기해의 선정

본 문제에서 후보 해를 나타내는 Particle은 고려하는 기간 t동안의 주차장 i에서 주차장 j로의 허용하는 수요량 (D i j t )에 대한 정보를 담고 있으므로 3차원 Matrix로 표현 된다. 초기 해는 각 기간마다 주차장 i에서 주차장 j로 이 동하는 수요량(Q i j t )과 최소로 허용되는 수요량(Q min × Q i j t ) 사이의 임의의 수로 구한다. 최적 해를 탐색할 때, 수리 모형의 목적식을 비교하여 해를 평가한 후 P-best와 Gbest를 산출한다. 그 후 식 (1)과 식 (2)를 이용하여 속도를 갱신한 후 Particle의 다음 위치를 구한다.

3.3교정 작업

X i n와 υ i n을 갱신하며 해를 탐색하다 보면 <Figure 4> 와 같이 가능한 해의 영역을 벗어나 해를 탐색하는 경우 가 발생한다. 가능한 해의 영역을 벗어나 해를 탐색할 경 우, Particle의 위치를 재설정해야 한다.

가능한 해의 영역을 벗어나는 경우는 다음의 2가지이 다. 첫 번째는 X i n에서 D i j t ≥ Q i j t 인 경우이고 두 번째는 X i n에서 D i j t ≤ Q min × Q i j t 인 경우이다. 위와 같이 해의 영 역을 벗어나는 경우 다음의 교정 작업을 실시하였다.

3.4재배치 알고리즘

실시간으로 수요와 차량의 재고에 맞는 재배치될 차량 수를 구해야 한다. PSO에서 Particle이 나타내는 기간 t일 때, 주차장 i에서 주차장 j의 수요량(Q i j t )이 주차장 i에서 이용 가능한 차량 수( S i t − 1)를 초과하여 S i t가 음수가 된다. 이때, 가장 가까운 주차장에서부터 차량의 재배치가 이루 어진다. i_K는 주차장 i에서 K 번째로 가까운 주차장을 의미 하며 재배치 알고리즘을 수행하는 과정은 다음과 같다.

4사례 분석

4.1실험 설계

시간적 범위는 차량 재배치 과정은 최소 운영단위인 10분마다 이루어지며, 실험 기간은 일반적인 특성이 반 영되는 평일(5일)로 설정하였다. 공간적 범위는 수도권인 서울과 경기 지역의 위성도시 중 예상 수요 상위 6곳으로 설정하였다.

위와 같은 범위 설정 및 모수를 위해 입지 후보지, 지 역 간 운행 소요 시간, 지역 간 수요량 그리고 제반 비용 에 대한 정보가 필요하다.

입지후보지는 기존에 도입된 지역과 새로 도입될 지 역을 구분하여 선정하였다. 기존에 도입된 지역의 경우, 일정 수준의 편도 수요를 충족시키기 위해 1~7개의 지 역을 1개의 Zone으로 설정하였다. 현재 카쉐어링 서비스 가 도입된 지역은 서울의 27개 구와 경기 지역의 8개시 이므로 총 8개의 Zone을 생성하였다. 새로 도입될 입지 후보지는 기 도입된 경기지역과의 거리, 인구의 기준으 로 하여 평택시, 남양주시, 화성시, 광주시, 양주시, 가평 군(총 6곳)을 선정하였다.

차량 대여소간 운행 소요시간은 Zone의 중심이 되는 지역의 행정기관(구청 등)에서 입지후보지의 행정기관 사 이의 운행 소요시간이며 <Table 1>와 같다. 동일 구간의 왕복의 경우 2회 편도로 간주하여 20분으로 설정하였다.

시스템 운영비용은 Han[4]에서 사용된 비용으로 설정 하였으며 <Table 2>와 같다.

각 입지에서의 예상 수요는 카쉐어링 서비스의 도입효 과 및 수요를 추정한 Park et al.[11]의 수식을 사용했다. Zone 및 입지 후보지 사이의 쇼핑/여가/배웅/기타, 출퇴근, 업무 등 목적별 통행량을 산출한 후, 카쉐어링 서비스 이 용통행비율과 대중교통 이용비율을 이용하여 예상 수요를 산출하였다. <Table 3>은 편도통행 방식이 가장 활발히 사 용되는 출근 시간대의 10분 단위의 수요 예측 모형이다.

4.2실험 결과

<Table 4>은 사용된 차량 수와 재배치 차량 수와 비용 에 대한 결과이다. 사용 차량 수는 일정한 규칙을 보이며 약 35,900대가 사용되었다. 또한 재배치 차량 수는 일별 로 산발적인 형태를 띠고 있으며 실험 기간 동안 4,049 회의 재배치가 일어났다.

<Table 5>는 주차장 크기와 입지별 초기차량 수에 대 한 결과이다. 주차장 크기는 실험 기간 동안 주차된 차량 수 중 가장 큰 값에 따라 결정되었으며, 남양주가 가장 높게 나타났다. 전체 비용 중 차량 유지비용이 약 47%로 가장 높게 나타났으며, 재배치 비용이 37%로 다음으로 높게 나타났다.

4.3민감도 분석

<Figure 5>는 운영수익과 재배치 비용에 따른 이익의 변화를 나타냈던 것으로 재배치 비용보다 운영수익의 변 화에 더 큰 변동이 있음을 알 수 있다. 이는 매 회 재배 치량이 R_max 이하로 발생하는 것이 주요 요인으로 분석 할 수 있다.

또한 주차장 비용과 차량유지비용에 대한 목적함수 값 (이익)의 변화는 <Figure 6>과 같다. 주차장 비용의 영향 보다 차량 유지비용에 의한 변동이 더 큰 것을 알 수는 있는데, 이는 앞의 결과와 같이 총 비용 중 차량 유지비 용의 중요도를 알 수 있다.

5.4성능 평가

본 연구에서 활용한 PSO 알고리즘을 통해 구한 해와 IBM ILOG CPLEX Optimizer를 통해 얻은 해와 비교를 통해 본 연구에서 제시한 PSO 알고리즘의 유용성을 검증 하였다. 먼저 PSO 알고리즘을 통해 얻은 결과는 <Table 6>의 결과와 같이 약 4%의 오차를 나타내었지만 연산 속 도는 PSO 알고리즘이 CPLEX에 비해 약 8배 빠른 결과 를 보였다.

또한 주차장 크기는 <Table 7>의 결과와 같으며, 큰 차이가 없음을 알 수 있다. 따라서 문제에 반영되는 지역 의 수가 증가한다면 실시간으로 운영되는 편도통행 방식 에 PSO 알고리즘의 적용이 효율적이라 할 수 있다.

다음으로 사용된 차량 수와 재배치된 차량 수를 비교 하였다. <Figure 7>와 같이 사용된 차량 수는 차이가 없 는 반면, 재배치된 차량 수는 <Figure 8>과 같이 차이가 있다. 이는 PSO 알고리즘은 운영 단위 시간마다 수요와 재배치량을 반영하여 가장 가까운 주차장에서부터 순차 적으로 재배치가 결정되는 재배치 알고리즘에 기인한 것 으로 분석된다. 그러나 CPLEX를 활용한 최적 해의 경우 모든 기간에 주차장의 차량 수를 고려하여 거리가 먼 주 차장의 재고까지 고려하여 재배치를 결정하기 때문에 재 배치 차량 수의 차이가 존재한다.

5결 론

수도권 지역 위성도시에 카쉐어링 서비스의 최적화를 위하여 재배치 차량 수, 초기차량 수, 주차장 크기, 선정 입지 등을 산정하고자 본 연구를 수행하였다. PSO 알고 리즘을 활용함으로서 보다 빠른 해 탐색이 가능하고 운 영단위 시간에 따라 실시간으로 수요와 재배치를 반영하 는 통합모형을 사용하였다.

CPLEX를 이용한 최적해와 비교해본 결과, 재배치 차 량 수와 주차장 크기 부분에서 차이가 있는 것으로 분석 되었으나 초기 차량의 수나 사용된 차량의 수 등은 비슷 한 결과를 보여 주었으며 8배 이상의 연산 속도를 보여 줌으로써 본 연구에서 제안한 알고리즘을 유용성이 충분 히 검증될 수 있었다.

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