Ⅰ. 연구의 배경 및 목적

최근 교통약자들의 이동성확보와 균등한 기회제 공을 위한 법률이 제정되고 교통약자에 대한 국가 적·사회적 관심이 높아지고 있다. 이러한 교통약자 들을 위한 차량서비스는 dial-a-ride, demand responsive 또는 paratransit으로 불리며 미국의 경우, 전역에 걸 쳐서 7200개가 넘는 단체들에 의해 널리 제공되고 있는 대중교통의 하나이다. 해당 단체들은 이 서비 스를 장애인, 간병인, 동행인이나 노약자에 제한하 고 있다.

교통약자를 위한 차량의 배차와 경로문제 (DARP: Dial-a-Ride Problem)는 NP-hard(non-deterministic polynomial- time hard)로 차량경로와 일정계획 문제(vehicle routing and scheduling problem)의 일반적인 경 우에 속한다[1].

최근 AVL(Automatic Vehicle Location), GPS(Global Position Systems), 텔레커뮤니케이션, 컴퓨터, GIS (Geographical Information System)와 같은 첨단기술 의 발달로 인해 Dial-a-ride 시스템의 효율성과 신뢰 성이 높아지고 있다. 하지만 실제 운영에서 보다 효 율적, 효과적인 경로선정과 일정계획을 위해서 이 러한 첨단기술들을 접목하기 위해서는 통합적인 결 정지원시스템이 필요하다. 또한, 이러한 결정지원시 스템은 넓은 서비스 지역과 많은 대상자들을 포함 하는 실제 운영에서의 경로선정과 일정계획문제를 해결하기 위해서는 보다 계산시간이 빠르고 적절한 알고리즘을 필요로 하게 된다.

하지만, 그동안 대부분의 연구에서 복잡한 문제 를 단순화하기 위해서 단일차고지와 hard time windows(예약시간의 위반이 불가능)가 가정되어 왔 으며 DARP를 위해 제안된 알고리즘을 큰 규모의 실제문제에 적용한 연구가 거의 없었다. 현실적으 로 두 개 이상의 개인회사로부터 서비스가 제공되 는 대도시지역에서는 다수차고지를 포함하며, 실제 운영에서 다수의 예약시간의 위반이 일어나는 것이 사실이다.

따라서 본 연구는 고정적인 수요, 다수차고지, 변 동 가능한 통행시간, 그리고 예약시간의 위반(soft time window)을 고려한 교통약자 차량의 배차와 경 로문제를 해결하기 위해서 Kim과 Haghani(2011)의 연구에서 제안된 선 클러스터-후 경로에 기초한 휴 리스틱 알고리즘에 대한 실제 사례연구에 중점을 두었다.

본 연구의 다음 장에서 관련된 연구를 살펴보고, 3장에서 제안된 모형과 알고리즘을 소개하고, 4장 에서 실제 사례연구로서 MTA의 실제운영과 제안 된 휴리스틱 알고리즘의 적용에 대해서 설명한다. 5장에서 휴리스틱 알고리즘에 의한 실험결과를 제 시하고 그 결과를 MTA의 실제운영과 비교한다. 또 한, 마지막 장에서 본 연구에 대한 결론과 앞으로의 연구방향을 제시한다.

Ⅱ. 관련연구

과거 40년 동안 DARP 모형과 알고리즘에 대한 많은 연구들이 있었다. Jaw 외(1986)는 고정적 수요 와 다수차량을 가진 교통약자 차량의 배차와 경로 문제를 위해 ADARTW(Advanced Dial-A-Ride with Time Window)을 제안했고 순차삽입 (sequential insertion)을 이용한 최초의 삽입(insertion) 알고리즘 중의 하나를 개발했다[2]. Ioachim 외(1995)는 다수 차량과 시간제약을 가진 교통약자 차량시스템문제 를 해결하기 위해서 column generation를 이용한 mini-cluster first, route second 방법을 제안했다[3]. Toth와 Vigo(1997)는 도시지역내의 시간제약을 가진 교통약자 서비스를 위한 문제에서 병행삽입(parallel insertion) 방법을 개발했다[4]. Baugh 외(1998)는 다 수차량의 DARP를 해결하기 위한 선 클러스터-후 경로(cluster-first route-second) 방법을 이용한 휴리스 틱 알고리즘을 제시했다[1]. Diana와 Dessouky(2004) 는 기존의 삽입 알고리즘에서 흔하게 나타나는 단 점인 근시안적인 성향 (myopic behavior)을 개선시키 기 위해서 새로운 후회삽입(regret insertion) 휴리스 틱 알고리즘을 제안했다[5]. 또한, Luo와 Schonfeld (2007)는 거절-재삽입 (rejected-reinsertion) 휴리스틱 을 제안했다[6]. 최근에, Kim과 Haghani(2011)는 다 수차고지, 위반 가능한 시간제약, 그리고 변동 가능 한 통행시간을 고려한 DARP에 대해서 순차삽입 (sequential insertion), 병행삽입(parallel insertion), 선 클러스터-후 경로(clustering-first routing-second)에 각각 기초한 3가지의 휴리스틱 알고리즘을 제안했 다[7].

국내의 경우에는 교통약자 차량 서비스를 최적 화하는 연구보다는 교통약자의 유형별 이동특성에 관한 연구(김원호 외, 2008), 교통약자 서비스를 위 한 정보센터 통합방안에 대한 연구(남두희 외, 2010), 교통약자를 고려한 대중교통 환승 알고리즘 에 대한 연구(김응철 외, 2009)가 있었다[8-10].

기존의 연구들을 살펴보면, 복잡한 문제를 단순 화하기 위해서 단일차고지와 hard time windows(예 약시간의 위반이 불가능)이 가정되었으며 DARP를 위해 제안된 알고리즘을 큰 규모의 실제문제에 적 용한 연구가 거의 없었다.

Ⅲ. Dial-a-ride를 위한 모형과 알고리즘

1. 모형

본 연구에서는 서비스예정 하루전날까지의 예약 들에 기초해서 모든 수요는 이미 알려져 있는 것으 로 가정한다. 모든 수요는 서비스 요청시간, 승차/ 하차지점, 그리고, 좌석 수에 대한 정보를 가진다.

매 시간간격(10분)마다 각 링크에 대한 통행속도 가 주어지는 것으로 가정하며 링크 통행속도가 주 어졌을 때, 시간 종속적(time-dependent) 최단경로 알 고리즘을 이용해서 출발지에서 목적지까지의 예상된 통행시간을 계산할 수 있다.

모든 수요를 서비스할 수 있도록 경로계획은 결 정되는데 각 경로에 할당된 차량들은 최대 경로시 간(maximum routing time)을 초과할 수 없다. 또한, 승차지점에서 승차한 고객에 대해 하차하기 전까지 의 승차시간은 주어진 최대 승차시간(maximum ride time)을 초과할 수 없다.

다수의 차고지가 존재하며 각 차고에서 이용 가 능한 전체차량의 대수와 차고의 위치는 이미 알고 있는 것으로 가정한다. 차량 군은 동질적이지 않으 며 각 차량마다 고유의 용량을 가진다. 승객은 3가 지, 즉, ambulatory(일반적인 좌석 이용승객), wheelchair( 일반휠체어 이용승객), 그리고, transferable wheel -chair(동력휠체어 이용승객)로 나뉜다.

Soft time window를 이용함으로써 서비스 예약시 간의 위반이 허용되나, 서비스 지점에서 조기도착 (early arrival)과 연착(delayed arrival)의 경우, 페널티 가 주어짐으로 예약시간의 위반이 최소화되도록 유 지한다. 이는 예약시간의 위반이 허용되지 않는 hard time window 보다 현실적이며 실제운영과도 부합한다. 차량에 승차한 고객이 한 명이라도 있을 경우에는 다음 승차 서비스지점에 예약시간 보다 먼저 도착해서 승차할 고객을 기다리는 것은 허용 되지 않는다.

모형의 목적함수는 서비스 제공자의 비용과 고 객들의 불편비용으로 이루어진 전체비용을 최소화 하는 것이다. 서비스 제공자의 비용은 이용된 전체 차량 대수에 대한 비용, 차량들의 전체 통행시간 비 용, 그리고 차량의 대기시간 비용을 포함한다. 반면 에, 고객들의 불편비용은 초과 승차시간 비용과 서 비스지연 비용을 포함한다. 본 모형의 제약 식들은 크게 5가지의 그룹, 차고(depot), 차량의 용량(capacity), 선행과 연결(precedence and coupling), 경로(routing), 그리고 시간제약(time window)으로 나뉜다. 이러한 모형식과 제약식은 Kim과 Haghani(2011)의 연구를 참조하였다[7].

2. 휴리스틱 알고리즘(HCR)

선 클러스터-후 경로방법에 기초한 휴리스틱 알고 리즘(Heuristic algorithm based on Cluster-first Routingsecond) 은 크게 구축단계와 개선단계로 나뉜다.

1) 구축단계(Construction phase)

구축단계에서 선 클러스터-후 경로방법에 기초한 <그림 1>과 같은 과정을 통해서 실행 가능한 최소 의 경로들이 구축된다.

2) 개선단계(Improvement phase)

구축단계에서 실행 가능한 초기해가 만들어진 후, <그림 2>와 같이 4개의 step들로 이루어진 개선단계를 통해서 초기해는 개선된다.

(1) Step Ⅰ: 허용 가능한 대기지연 시간

본 모형에서 예약시간의 위반이 허용되는 반면에, 최대허용 대기지연 시간(Maximum acceptable waiting and delay time, 이하 MaxWD)에 의해 서비스 질의 조 정이 가능하다.

(2) Step Ⅱ: 삭제 후 삽입

지역 해를 탐사하는 개선절차로서 삽입연산자 (trip insertion operator)가 적용되어 선택된 대상 경 로에서 일부분의 이동(trip)을 제거한 후 다른 경로 의 최적 위치에 삽입한다.

(3) Step Ⅲ: 경로병합

Step II를 거친 후, 아주 적은 수의 서비스 지점들을 가진 경로들이 존재할 수 있다. 이러한 경로들은 제약 식들을 위반하지 않으면서 그 경로에 할당된 고객들 을 서비스 할 수 있는 다른 경로에 병합될 수 있다.

(4) Step Ⅳ: 차량 출발시간 조정

각 경로에서 차량의 출발시간은 한계시간(marginal time)을 이용해서 조정가능하다. 한 서비스 지점에 서 한계시간은 나머지 다음 서비스 지점들에서의 시간제약을 위반하지 않으면서 현재 서비스 지점에 서 가능한 최대 서비스 지연시간으로 정의된다.

Ⅳ. Dial-a-ride 사례연구

1. MTA의 Dial-a-ride 서비스

사례연구를 위한 실제자료는 Maryland 주 Baltimore city에 위치한 Maryland Transit Administration (MTA)로 부터 제공되었다. MTA는 일반적인 버스노선의 3/4 마일 안에 위치한 Baltimore city, Baltimore county 와 Anne Arundel county내에서 고정된 경로를 서비 스하는 대중교통을 사용할 수 없는 장애인들을 위 한 특별화된 수요대응적인 대중교통 서비스를 제공 하는데 중요한 역할을 하고 있다.

실제 서비스는 MTA 소유의 차량들, 그리고 MTA와 계약된 두 개의 사립회사인, MV와 Yellow Transportation 소유의 차량들을 통해 제공되며 모든 차량들은 MTA에 위치한 컴퓨터 기반의 중앙 운행 관리원의 지시를 받는다.

MTA의 Trapez 데이터베이스로부터 2004년 9월 24 일 하루의 운영자료를 추출했으며 전체 예약된 수요 들 중에서 총 4,726개의 수요들이 서비스 되었다. 전체 차량 편은 Yellow Transportation 소유의 103대, MTA 소유의 56대, 그리고 MV 소유의 103대로 이루어졌다.

<그림 3>은 전체 4,726개의 수요에 대한 서비스 요청시간대의 분포를 보여주고 있다. 대부분의 수 요가 오전7시와 10시 사이 그리고 오후 2시와 5시 사이에 집중돼 있음을 알 수 있다. 시간제약의 폭은 30분이며, 실제 승 하차지점은 도로 네트워크 내에 서 가장 근접한 교차지점으로 가정한다.

1) 도로 네트워크 자료

서비스 지역에 대한 도로 네트워크 자료는 상용 패키지인 ArcLogistics으로부터 추출되었으며 가장 중요한 네트워크의 연결성 확인 작업을 거쳤다. 네 트워크상에 총 63,356의 노드, 8,446개의 링크, 그리 고 142,483개의 방향성을 가진 아크가 존재한다. <그 림 4>는 서비스 지역의 위치를 보여주고 있다.

링크는 그들의 기능에 따라서 3가지 유형으로 나뉜 다. 즉, 첫 번째 유형인 highway는 60mph, 두 번째 유 형인 main road는 40mph, 그리고 세 번째 유형인 minor road는 30mph의 링크속도를 가진다.

2. 제안된 알고리즘의 사례연구 적용

적정한 시간 내에 문제에 대한 해를 구하기 위해 서 원래의 문제는 5개의 시간대로 나누어진다. 5개 의 시간대(즉, 오전0시~오전7시, 오전7시~오전10시, 오전10시~오후2시, 오후2시~오후5시, 오후5시~오전 0시)는 <그림 3>과 같은 수요들의 서비스요청시간 대 분포에 기초해서 만들어진다. HCR의 적용절차 는 다음 <그림 5>와 같다.

3. 매개변수(parameter) 설정

최대경로시간은 540분, 고정된 차량비용에 대한 매개변수는 $200/대, 차량통행비용에 대한 매개변수 는 $1/분, 차량의 대기비용, 서비스지연 비용, 그리 고, 초과승차 시간비용에 대한 매개변수는 $0.5/분으 로 설정한다. 승객들의 승하차시 서비스 소요시간은 일반적인 승객의 경우에는 2분, 동력 휠체어를 사용 하는 승객들의 경우에는 4분, 그리고 일반 휠체어를 사용하는 승객들의 경우에는 6분으로 가정한다.

알고리즘은 C++로 코딩 되었으며 컴퓨터 실험은 Window 7환경 내에서 2.93GHZ Intel Core i7 CPU와 8GB 메모리를 가진 데스크탑 컴퓨터에서 이루어졌다.

Ⅴ. MTA의 실제운영과 제안된 알고리즘의 결과 비교

1. 실험 시나리오

MTA의 DB로부터 전체 4,726개의 수요들 중에서 4,604개의 수요들에 대해서만 운영 자료를 구할 수 있 었다. 따라서 4,604개의 수요들만이 실험대상이 된다.

또한, HCR 알고리즘 내에서 시간 종속적 통행시 간 대신에 고정된 통행시간이 사용되었다. MTA의 운영에서 이용된 실제 링크통행시간에 대한 정보를 구할 수 없었기 때문에 MTA의 운영결과와 HCR의 결과를 비교하기 위해 링크속도에 대한 두 가지의 시나리오를 제시한다. 첫 번째 시나리오에서는 실 제 링크속도가 제한속도에 기초하여 설정된 링크속 도보다 25% 느린 것으로 가정한다. 이 경우에는, 속도인자 값은 0.75이다. 두 번째 시나리오에서는 실제 링크속도가 원래 설정된 링크속도와 같은 것 으로 가정된다. 이 경우에는, 속도인자 값은 1.0이다

HCR에서는 전체비용에 차량대기 비용, 서비스 지연 비용, 그리고 초과승차 시간 비용이 포함됨에 비해서, 실제 MTA의 운영 자료에는 차량 대기시간, 서비스 지연시간, 그리고 초과 승차시간에 대한 정 보가 없다. 따라서 HCR에서 차량대기, 서비스지연, 그리고 초과 승차시간들의 단위비용 변화에 따른 전체비용분석이 필요하다. 따라서 <표 1>과 같이 주요 파라미터들에 대한 시나리오를 적용하여 <표 2>와 같이 총 24가지의 실험 시나리오를 제시한다.

2. 실험결과

<그림 6>은 HCR의 결과와 MTA의 실제운영의 비교를 보여준다. 비교를 위해서, HCR의 목적함수 값에서 차량대기 비용, 서비스지연 비용, 그리고 초 과승차 시간비용은 포함되지 않는다. 전체적으로 HCR의 결과가 MTA의 실제운영에 비해서 21.4~ 48.2%의 비용절감을 보였으며, HCR의 결과와 MTA 운영 사이의 이러한 큰 차이는 MTA의 경로배정 방 법에 기인한다. 자료획득 당시, MTA는 각 회사로부 터 이용된 차량수의 균형을 맞추기 위해서 경로들 을 먼저 생성한 후 각각의 경로에 번호를 부여하고 일정범위의 번호를 가진 경로에 특정회사의 차량을 배정했다. MTA의 경로배정 방법은 전체비용을 최 소화하기에는 비합리적인 것으로 나타났다. 또한, 제안된 모형에서 시간제약의 위반이 가능해짐으로 써 고객들 간 동승의 기회가 더 많아지게 된다. 따 라서 제안된 알고리즘을 이용할 경우, MTA의 실제 운영보다 필요한 차량의 수는 적다.

<그림 7>은 속도인자, 단위시간비용, MaxWD의 변화에 따른 목적함수 값의 변화를 보여준다. 속도 인자가 증가함에 따라 전체비용은 증가하며, 차량 대기 시간, 서비스지연 시간, 초과승차 시간에 대한 단위비용이 증가함에 따라 전체비용은 다소 증가하 는 것으로 나타났다. 또한, 최대 허용 대기지연 시 간(MaxWD)이 증가함에 따라 전체비용은 감소하는 것으로 나타났다.

모든 경우에 대한 평균계산시간은 225.7분으로 적당한 수준이다. 만약에 예약수요의 경로와 일정 에 대한 컴퓨터작업이 오후 5시에 시작되면 모든 작업은 밤 9시 이전에 끝나고 다음날 서비스(자정 시작)를 준비할 수 있는 시간의 여유가 충분하다.

Ⅵ. 결론 및 향후 연구

본 연구는 교통약자 차량서비스의 경로와 일정문 제에 관한 것으로 다수차고지와 예약시간의 위반을 고려한다. 본 연구에서는 선 클러스터-후 경로방법에 기초한 휴리스틱 알고리즘(HCR)을 Maryland 주 Baltimore city에 위치한 MTA로부터 제공된 실제 dial-a-ride 서비스에 적용하였다.

실험결과에 의하면 모든 실험경우에 대해 HCR 에 의한 목적함수의 값이 MTA 실제운영에 의한 목 적함수 값보다 나은 것으로 나타났다. 제안된 모형 에서 예약시간의 위반이 가능해짐으로써 고객들 간 동승의 기회가 더 많아지게 된다. 따라서 제안된 알 고리즘을 이용할 경우, MTA의 실제운영보다 필요 한 차량의 수가 적다. 이 결과는 본 연구에서 제안 된 휴리스틱 방법을 통해서 실제 운영시 효율성을 향상시킬 수 있음을 보여준다.

최근 교통약자들의 이동성확보와 균등한 기회제 공을 위한 법률이 제정되고 교통약자에 대한 국가 적·사회적 관심이 높아지면서 교통약자 차량서비스 에 대한 관심도 같이 높아지고 있다. 따라서 기존 해외 사례 연구를 통해서 우리 실정에 맞는 교통약 자 차량 서비스에 대한 연구가 이루어져야 할 것이 다. 교통약자 차량 서비스의 특성상 저렴한 요금으 로 인해 비용측면에서 많은 부분의 정부지원이 필 수적인데 이에 대한 준비가 필요할 것이다. 따라서 교통약자 차량서비스의 주체도 민간보다는 공공섹 터가 되어야 할 것이다. 즉, 정부나 지방자치단체가 직접 이를 운영하거나 아니면 민간에게 위탁하고 운영비를 지원해야 할 것이다.

교통약자 차량서비스는 차량군(fleet)과 승무원 (crew)에 의해 지원되기 때문에 앞으로 이와 관련된 승무원 일정 문제(crew scheduling problem)에 대한 고려가 필요하며, 본 연구에서 초기 해를 개선시키 는 단계에서 유전자알고리즘(genetic algorithms), 타 부 서치(tabu search), 하모니 서치(harmony search)와 같은 메타휴리스틱(meta-heuristic) 방법들이 적용될 수 있다.