Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.40 No.3 pp.99-106
DOI : https://doi.org/10.11627/jkise.2017.40.3.099

New Mathematical Model for Travel Route Recommendation Service

Intae Hwang^*

, Heungseob Kim^**†

^*3rd Flying Training Wing, Air Force
^**Department of Systems Engineering, Air Force Academy

Corresponding Author : heungseob79@gmail.com

Received August 16, 2017 Finally Revised September 8, 2017 Accepted September 11, 2017

Abstract

With the increased interest in the quality of life of modern people, the implementation of the five-day working week, the increase in traffic convenience, and the economic and social development, domestic and international travel is becoming commonplace. Furthermore, in the past, there were many cases of purchasing packaged goods of specialized travel agencies. However, as the development of the Internet improved the accessibility of information about the travel area, the tourist is changing the trend to plan the trip such as the choice of the destination. Web services have been introduced to recommend travel destinations and travel routes according to these needs of the customers. Therefore, after reviewing some of the most popular web services today, such as Stubby planner (http://www.stubbyplanner.com) and Earthtory (http://www.earthtory.com), they were supposed to be based on traditional Traveling Salesman Problems (TSPs), and the travel routes recommended by them included some practical limitations. That is, they were not considered important issues in the actual journey, such as the use of various transportation, travel expenses, the number of days, and lodging. Moreover, although to recommend travel destinations, there have been various studies such as using IoT (Internet of Things) technology and the analysis of cyberspatial Big Data on the web and SNS (Social Networking Service), there is little research to support travel routes considering the practical constraints. Therefore, this study proposes a new mathematical model for applying to travel route recommendation service, and it is verified by numerical experiments on travel to Jeju Island and trip to Europe including Germany, France and Czech Republic. It also expects to be able to provide more useful information to tourists in their travel plans through linkage with the services for recommending tourist attractions built in the Internet environment.

Key Words : Tourism , Travel Route Recommendation , Improved TSP , Tourist Attraction

여행경로 추천 서비스를 위한 최적화 수리모형

황 인태^*, 김 흥섭^**†

^*공군 제3훈련비행단
^**공군사관학교 시스템공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1.서 론

현대인들의 삶의 질에 대한 관심 증가, 주 5일 근무제 시행, 교통편의성 증대 및 경제적․사회적 발전에 따라 국․내외 여행이 보편화되고 있다. 한국관광공사의 국민 여행실태조사 보고서[10]에 따르면 <Figure 1>과 같이 최 근 5년간 국내 여행은 꾸준히 증가하고 있으며, 대표적인 통계로 2016년 기준 여행 경험률은 89.5%, 여행횟수는 1 인당 평균 5.5회로 2006년 대비 2배 증가하였다. 여행일수 도 해마다 증가하여 2016년에는 평균 9.4일, 연간 여행 지 출액은 25.7조 원에 이르고 있다. 또한, 해외여행도 2010년 이후 연평균 10%씩 증가하여 2016년에는 약 2,238만 명이 여행을 목적으로 출국하였으며, 이는 2010년 약 1,249만 명 대비 약 79% 증가한 수치이다. 아울러, 과거에는 전문 여행사의 패키지 상품을 구매하는 경우가 많았으나, 인터 넷의 발전으로 여행지역에 대한 정보의 접근성이 향상되 면서 여행자가 직접 방문지 선정 등 여행을 계획하는 추세 로 변화되고 있다. 2016년의 국내 여행상품 구매율을 살펴 보면, 모든 여행계획을 전문 여행사에게 일임하는 전체 패 키지 상품의 구매율은 20.7%로 해마다 감소하여 왔으며, 교통, 숙박, 차량 임대 등과 같은 부가 서비스만을 구매하 는 부분 패키지 상품이 79.3%를 점유하고 있다는 것은 여 행계획의 주체가 변화하고 있음을 보여준다[10, 11].

자유여행의 증가 추세에 따라 개인이 여행을 계획할 수 있도록 여행경로(Travel route)를 추천해주는 웹사이트 (Website)가 등장하였다. 이러한 웹사이트들 중 인기가 높 은 웹사이트는 스투비 플래너(Stubby planner)[15]와 어스 토리(Earthtory)[2]로 조사되었다. 두 웹사이트의 서비스 특 징을 살펴보면, 스투비 플래너는 이용자가 국가별 도시들 을 선택하면 그 도시들을 최단 시간에 여행할 수 있는 경 로를, 어스토리는 이용자가 임의의 도시 내의 여행지들을 선택하면, 최단 거리의 여행경로를 추천해주고 있었다. 하지만, 두 웹사이트에 대해 분석해본 결과 다음과 같은 제한사항이 나타났다. 스투비 플래너는 도시별 이동계획 을 추천할 뿐 도시 내의 세부 여행지에 대한 방문계획, 숙 소, 교통편 이용을 위한 기차역/공항 등을 고려하지 않고 있었다. 반면, 어스토리는 서비스 지역이 임의의 한 국가 로 제한되어 여러 국가를 방문하는 경우에서는 서비스를 이용할 수 없었다. 또한, 두 웹사이트는 공통적으로 여행 중 수면시간 및 숙소, 교통편 이동가능 시간, 여행지 관광 시간, 그리고 출발지/도착지 등을 고려하지 않은 여행계 획을 추천하고 있었다. 결론적으로, 두 웹사이트 모두 현 실의 여행에서 고려되어야 하는 중요한 요소들이 배제된 여행경로를 추천하고 있었으며, 여행경로 추천 개념은 전형적 인 순회판매원문제(TSPs : Travelling Salesman Problems) 를 따르고 있는 것으로 추정된다.

여행경로 선정 문제는 개념적으로 TSP와 유사하지만, 여행의 특성이 추가적으로 고려되어야 한다. 여행경로 추천 서비스와 관련한 기존 연구들을 살펴보면, Lee and Yang[9] 은 사용자들이 출발지/도착지, 교통편, 관광명소 및 쇼핑 등의 여행목적, 여행지의 범위를 입력하면 여행경로를 추 천하는 서비스를 제안하였으며, 여행경로 생성에는 기존 의 A* 알고리즘과 다익스트라(Dijkstra) 알고리즘을 활용 하였다. Kim et al.[7]은 사전에 밀집도, 날씨, 교통 정보 등을 예상할 수 없는 문제점을 개선하고자 IoT 기반의 실 시간 여행경로 추천 서비스를 제안하였으며, 여행경로는 Greedy 알고리즘을 통해 추천하였다. 하지만, 위의 연구 들에서 여행경로의 생성은 기존 TSP의 개념에 따르고 있 다. Kurashima et al.[8], Oh et al.[14]과 Wen et al.[17]은 여행지 선택기준이 여행지의 지명도와 방문빈도라는 것 에 착안하여 인스타그램(Instagram) 등의 소셜네트워킹 서 비스(SNS : Social Networking Service) 상의 여행사진과 후기들로부터 여행지별 지명도와 방문빈도를 추출하고, 이를 바탕으로 선호도가 높은 여행지를 실시간으로 추천 하는 서비스를 제안하였다. Chen et al.[1]은 계획된 행동 이론(Theory of planned behavior)을 바탕으로 태도, 주관 적 기준 및 인지된 행동 제어가 실시간 정보에 의한 여행 자의 여행경로 변경 의도의 영향 요인임을 확인하고, 이 를 여행자의 여행경로 변경 의도를 예측하는데 활용할 것 을 제안하였다. 결론적으로, 최근의 여행경로와 관련된 연구들은 전자지도 등의 인터넷 기술과의 연계, 인터넷 공간의 정보들을 활용하여 선호도가 높은 여행지를 추천 하는 시스템 개발 분야가 주를 이루고 있으며, 실질적인 여행경로 추천에 있어서는 전통적인 TSP의 개념이 적용 되고 있어 여행자들에게 현실적이고 합리적인 여행경로 를 추천하는데 제한이 따르고 있다.

따라서 본 연구는 여행자들에게 실제적인 여행경로를 추천하기 위해 여행의 특성을 반영하여 기존 TSP 개념을 보완한 최적화 수리모형을 제시한다. 제시되는 수리모형 의 주요 개선사항은 다음과 같다. 첫째, 국․내외 여행지 를 대상으로 하며, 여행경로는 국가 간의 이동을 포함한다. 둘째, 여행자가 지정한 여행일수 동안 숙박(Lodge)까지 고려하여 일자별 여행경로를 제공한다. 셋째, 여행지 간 의 이동을 위한 효율적인 교통편을 추천한다. 넷째, 여행 경비, 여행지별 선호도 및 방문가능 시간 등이 고려된다.

2.문제정의 및 수리모형

2.1.문제정의

개인의 여행계획 수립에 유용한 네트워크 최적화 모형 의 유형으로는 TSPs이 가장 적합하다고 할 수 있다. 하지 만, TSPs은 일반적으로 상품배송, 물류환경 등을 고려하 고 있기 때문에 여행의 고유한 특성을 반영하지는 못한 다. 따라서 본 연구에서는 기존의 TSPs를 기반으로 여행 의 현실적인 특성을 고려하여 개인의 선호에 따른 자유 여행 계획을 지원하는 여행경로 추천 서비스를 위한 최 적화 수리모형을 제시한다. 기본적인 가정사항은 TSPs과 동일하며, 수리모형에 반영되는 여행계획의 주요한 고려 사항들은 다음과 같다.

(1) 선호하는 여행지들은 여행자가 선택하며, 여행일수와 비용에 제한이 따른다.
(2) 실제적인 여행일수와 비용을 고려하기 위해 출발과 복귀지점을 자택(Home)으로 고려한다.
(3) 현실에서 실현 가능한 여행계획을 수립하기 위해서 는 여행기간 중 숙박 등을 고려한 일자별 여행계획 이 필요하다.
(4) 많은 여행지들이 개장․폐장시간과 같은 방문가능한 시간대(Time windows)를 갖는다.
(5) 여행 중 다양한 교통편을 이용하게 되며, 여행지 간 이동에 효율적인 교통편을 선택하여야 한다

2.2.최적화 수리모형

여행의 총 효용, 즉, 방문하는 여행지 선호도 합의 최대 화를 위한 수리모형은 식 (1)부터 식 (13)까지의 혼합정수 계획(MIP : Mixed Integer Programming) 모형으로 제시되며, 표기(Notation)와 결정변수(Decision variables)는 다음과 같다.

<표기>

P : 여행지 노드(Node)의 집합
H : 숙소 노드의 집합
S : 공항/기차역 노드의 집합
{0} : 자택 노드
N : 전체 노드의 집합; N = {0, P, H, S}
d : 여행일자; d = {1, 2, ⋯, D}
K : 교통편의 집합; k∈K이고 차량(k = 1), 열차(k = 2), 항공기(k = 3)
R_i : 여행지 i의 선호도(효용)
t_kij : 교통편 k로 노드 i에서 j로 이동할 때의 소요시간
u_i : 노드 i의 평균 관광시간
M : 일일 여행 가능한 시간
$T_{i}^{s}$ : 노드 i의 개장시간
$T_{i}^{e}$ : 노드 i의 폐장시간
TF : 총 여행경비
$f_{k i j}^{m}$ : 노드 i에서 j로 이동 할 때, 교통편 k의 교통비 (연료비, 열차/항공기 요금)
$f_{i}^{s}$ : 노드 i의 입장료 등 관광비용

<결정변수>

S_di : 노드 i에 도착하는 시간
$x_{d k i j} = {\begin{array}{l} 1, & \begin{array}{l} 여행자가 여행일자 d 에 교통편 k 로 노드 \\ i 에서 j 로 이동하면,, \end{array} \\ 0, & Otherwise \end{array}$

Maximize \sum_{d \in D} \sum_{k \in K} \sum_{i \in N} \sum_{j \in N} R_{i} x_{d k i j}

(1)

\begin{array}{l} subject to : \\ \sum_{d \in D} \sum_{k \in K} \sum_{i \in N} x_{d k i j} \leq 1, \forall j \in P \end{array}

(2)

\sum_{d \in D} \sum_{k \in K} \sum_{i \in N} x_{d k i j} \leq 1, \forall j \in P

(3)

\begin{array}{l} \sum_{i \in N} x_{d k i z} - \sum_{j \in N} x_{d k z j} = 0, \\ 1 \leq d \leq D, \forall z \in N/H, \forall k \in K \end{array}

(4)

\sum_{k \in K} \sum_{j \in N\ {0}} x_{1 k 0 j} = 1

(5)

\sum_{k \in K} \sum_{j \in N\ {0}} x_{D k i 0} = 1

(6)

\sum_{k \in K} \sum_{j \in N\H} \sum_{j \in H} x_{d k i j} = 1

(7)

\begin{array}{l} \sum_{k \in K} \sum_{i \in N/H} x_{d k i \ h} = \sum_{k \in K} \sum_{i \in N/H} x_{(d + 1) k h j}, \\ 1 \leq d \leq D - 1, \forall h \in H \end{array}

(8)

\begin{array}{l} S_{d j} \geq S_{d i} + (t_{k i j} + u_{i}) x_{d k i j} - M (1 - x_{d k i j}), \\ 1 \leq d \leq D - 1, \forall i, j \in N {0}, \forall k \in K \end{array}

(9)

\begin{array}{l} V_{i}^{0} x_{d k j i} \leq S_{d i} \leq V_{i}^{c} x_{d k j i}, \\ 1 \leq d \leq D, \forall i \in N\ {0}, \forall k \in K \end{array}

(10)

\sum_{i \in N} \sum_{j \in N} x_{d k i j} \leq | N | - 1, \forall d \in D, \forall k \in K

(11)

\sum_{d \in D} \sum_{k \in K} \sum_{i \in N} \sum_{j \in N} (f_{k i j}^{m} + f_{i}^{s}) x_{d k i j} \leq T F

(12)

x_{d k i i} = 0, \forall d \in D, \forall k \in K, \forall i, j \in N

(13)

수리모형의 목적함수(Objective function) 식 (1)은 방문 하는 여행지들의 선호도(효용)의 총합을 최대화하는 것 이다. 제약식 (2)와 (3)은 여행기간 중 각 여행지(P)의 방 문은 1회 이하로 제한된다는 의미이다. 즉, 임의의 여행 지는 방문하지 않을 수도 있다. 또한, 숙소(H)와 공항/기 차역(S ) 노드들은 다수 방문을 허용한다. 식 (4)는 일자별 여행경로의 연속성을 보장하기 위한 경로연속성(Route continuity) 제약이며, 이때 식 (8)과 연계하여 여행일자별 숙소가 전일 투석한 숙소와 달라질 수 있기 때문에 숙소 노드(H)는 경로연속성 제약에서 제외된다. 식 (5)와 식 (6) 은 여행의 시작과 종료 지점은 자택(노드 : 0)임을 의미 한다. 즉, 여행 1일차에 자택에서 출발하고, 여행 마지막 일자(D)에 자택으로 복귀하도록 제약하고 있다. 식 (7)은 일자별 여행의 종료 지점은 숙소 노드들(H) 중 하나가 되어야 한다는 의미이며, 식 (8)은 2일차 여행부터는 전 일 투숙한 숙소에서 시작되어야 함을 제약하고 있다. 식 (9)는 노드별 방문하는 시간을 산정하기 위한 제약식으 로, 여행자가 노드 i와 j를 순차적으로 방문할 때, 노드 j에 도착하는 시간은 노드 i에서의 체류시간과 선택된 교통편 k로 이동하는 시간의 합보다 커야한다는 의미이 다. 식 (10)은 식 (9)에서 산정된 노드별 도착시간이 해당 노드의 방문가능 시간대(Time windows)를 준수하여야함 을 제약하고 있다. 식 (11)은 일자별, 차량별 이동경로 상 에 부분순회경로를 방지하기 위한 제약(SECs : Sub-tour Elimination Constraints)[6]이며, 식 (12)는 교통비와 여행 지 관광료의 합, 즉, 총 여행비용이 계획된 여행경비(TF) 를 초과할 수 없음을 제약하고 있다. 식 (13)은 여행자가 임의의 한 노드에 계속 체류하지 않음을 제약하고 있다. 마지막으로, 앞서 명시한 결정변수의 형태와 범위에 대 한 제약은 생략하였다.

여행자가 선택한 여행지들을 최저 비용으로 여행하기 위한 경로계획을 위한 수리모형은 앞서 제시된 효용 최 대화 수리모형에서 목적함수 식 (1)과 제약식 (2)와 (3)이 식 (15), 식 (16)과 같이 변경되며, 제약식 (4)부터 (13)까 지는 동일하게 적용된다. 목적함수 (14)는 교통비와 여행지 입장료 등의 총 여행비용을 최소화하며, 식 (15)와 식 (16) 은 선택된 모든 여행지(P)를 1회 방문하도록 제약하고 있다. 이때도 숙소(H)와 공항/기차역(S )에 대해서는 방문 횟수를 제약하지 않는다.

Minimize \sum_{d \in D} \sum_{k \in K} \sum_{i \in N} \sum_{j \in N} (f_{k i j}^{m} + f_{i}^{s}) x_{d k i j}

(14)

\begin{array}{l} subject to : \\ \sum_{d \in D} \sum_{k \in K} \sum_{i \in N} x_{d k i j} = 1, \forall j \in P \end{array}

(15)

\sum_{d \in D} \sum_{k \in K} \sum_{j \in N} x_{d k i j} = 1, \forall i \in P

(16)

3.수치실험

수치실험은 제 2장에서 제시한 수리모형을 검증하기 위해 수행되었으며, 수치실험에는 두 가지 실험예제가 적 용되었다. 첫 번째는 국내여행 사례로서 제주도 여행을 계획하였으며, 두 번째 실험예제로는 다수 국가를 여행하 는 유럽여행 사례를 적용하였다. 또한, 현실적인 실험예 제 구성을 위해 예제 데이터는 여행 관련 전문 웹사이트의 정보를 활용하였다. 각 실험예제의 최적해(Optimal solution) 는 IBM사의 ILOG CPLEX를 통해 탐색하였다.

3.1.국내(제주도) 여행

국내 여행에 대한 실험예제에서는 여행자가 서울 강남 에 거주하는 것으로 가정하였으며, <Table 1>에 제시된 바와 같이 한라산(Hallasan Mountain) 등 10개소의 여행 지, 호텔 3개소, 공항은 인천과 제주 2개소로 고려하였다. 각 노드 간의 이동 소요시간, 거리, 그리고 차량, 항공기, 열차 등의 교통편별 비용은 지도 웹사이트인 Naver Map [13]에서 제공되는 정보를 활용하였으며, 여행지의 개․ 폐장 시간(Time windows), 요금(Admission fee), 선호도 (Awareness) 등은 여행 전문 웹사이트인 Trip advisor[16] 의 정보를 참고하였다.

제주도를 1박 2일로 여행할 때, 효용 최대화를 위해 추 천되는 여행경로는 <Figure 2>와 같으며, 각 노드에 도착 하는 시간은 <Table 2>와 같다. 단, 하루의 여행시간은 08:00부터 20:00까지로 설정하였으며, <Table 2>의 노드 별 도착시간은 5분 단위로 올림하여 표기하였다. 이때, 여 행기간이 짧아 여행지 총 10개소 중 한라산 등 6개소만을 방문하도록 계획되었으며, 제주도 내에서의 교통편은 렌 트카이다. 1일차에는 자택을 떠나 인천공항에서 항공기로 제주공항으로 이동 후, 오설록티뮤지엄, 한라산, 돌문화 공원을 여행하고 해비치 호텔에서 숙박을 한다. 2일차에 는 해비치 호텔을 출발하여 성산일출봉, 섭지코지, 용두 암의 순서로 여행하고, 제주공항을 통해 인천공항, 자택 으로 복귀한다. 여기서, 이동거리가 증가함에도 성산일출 봉을 섭지코지 보다 먼저 방문하는 것은 성산일출봉의 개 장시간이 빠르기 때문이다.

여행일정을 3박 4일로 연장하면 <Figure 3>과 같이 숙 박장소를 해비치 호텔과 라마다 호텔을 이용하면서 여행 자가 선택한 모든 여행지를 방문할 수 있었으며, 일자별 여행경로와 경로 상의 각 노드에 도착하는 시간은 <Table 3>과 같다. 또한, 일자별 여행경로가 장거리로 설정된 것 은 각 여행지에서의 관광시간(Stay time)이 고려되었기 때 문이다.

3.2.다수 국가 여행 : 유럽(프랑스, 독일, 체코)

국내(제주도) 여행에 대한 수치실험은 현재의 어스토 리 웹사이트 서비스에서 숙박과 교통편의 선택이 개선되 었음을 보였다. 본 절에서는 다수 국가를 여행하는 경우 에 대한 수치실험을 통해 본 연구에서 제안하는 서비스의 개선사항을 종합적으로 보이고자 한다. 국내여행에서와 같이 보다 현실적인 실험예제 구성을 위해 각 노드 간의 이동 소요시간, 거리, 그리고 차량, 항공기, 열차 등의 교 통편별 비용은 지도 웹사이트인 Google Map[3]에서 제공 되는 정보를 활용하였으며, 여행지의 개․폐장 시간(Time windows), 요금(Admission fee), 선호도(Awareness) 등은 Trip advisor[16] 등의 여행 전문 웹사이트의 정보를 참고 하였다.

실험예제의 상황은 다음과 같다. 여행자는 서울 강남 에 거주하고 있으며, 6박 7일 일정으로 독일․프랑스․ 체코를 대상으로 하는 유럽여행을 계획하고 있다. 여행 자는 여행정보서비스 상에서 추천된 여행지들 중 <Table 4>와 같이 프랑스의 에펠탑 등 4개소, 독일의 포츠담광 장 등 4개소, 그리고 체코의 프라하성 등 2개소에 대해 여행을 희망하고 있다. 교통편은 차량, 열차, 항공기로 고 려하였으며, 이중 떼제베(TGV : Train à Grande Vitesse) 와 유로시티(EuroCity) 열차는 여행자들이 선호하는 관광 상품 중의 하나이기 때문에 여행지로써의 선호도(평점) 를 반영하였다. 또한, 하루의 여행은 국내여행 실험예제 와 마찬가지로 08:00부터 20:00까지로 설정하였으며, 해 외여행에서 발생할 수 있는 교통편으로 국가 또는 도시 간 이동 중 날짜가 바뀌는 상황은 여행지 방문시간(Time windows) 제약이 영향을 미치지 않도록 하였기 때문에 실현가능(Feasible)하다.

6박 7일 유럽여행에 대한 실험결과는 <Figure 4>와 같 다. 일자별 여행계획을 정리하면 다음과 같다. 1일차에는 인천공항에서 항공기를 이용해 프라하공항으로 이동 후 프라하 호텔 #1에 숙박하고, 2일차에는 프라하 공항을 통해 프랑스로 이동하여 개선문, 에펠탑, 베르사유 궁전 을 관광한 후 프랑스 호텔 #2에서 숙박한다. 여기서, 1일 차에 바로 프랑스로 이동하지 않은 것에 대해 분석한 결 과, 항공운임 및 숙박료를 고려했을 때 프랑스로 바로 이 동하는 것 보다 체코에서 숙박 후 저가항공을 이용하여 프랑스로 이동하는 것이 여행지를 모두 방문할 수 있으 면서 저렴하기 때문이었다. 3일차에는 몽마르뜨 언덕을 관람 후 파리역에서 떼제베 열차로 독일로 이동하고, 베 를린 호텔 #1에 투숙한다. 4일차에는 포츠담 광장, 슈프 레 강 등 4개소를 관광하고 베를린 역에서 유로시티 열 차로 프라하로 이동하며, 이동 중 날짜가 변경된다. 즉, 여행자는 유로시티 열차에서 숙박을 하게 된다. 프라하 호텔에서 5일차 숙박을 하고, 6일차에 프라하 성과 체스 키를 여행 한 후 프라하공항을 통해 인천공항으로 귀국 한다. 이때도 항공기에서 날짜가 변경되어 한국에 도착 하면서 7일차가 된다.

4.결론 및 향후 연구방향

본 연구는 전통적인 TSP 기반의 여행경로 추천 서비스 의 제한사항과 여행자들의 요구사항(Needs)을 반영하여 개선하여 보다 현실적이고 합리적인 여행계획을 위한 수 리모형을 제시하였으며, 이는 인터넷의 전자지도, 빅데이 터를 활용한 여행지 추천 서비스 등과 연계한다면 여행자 들에게 매우 유용하게 활용될 것으로 기대한다. 제시된 수 리모형의 주요 개선사항으로는, 첫째, 일자별 여행계획을 제공하며, 둘째, 여행경로 상에서 다양한 교통편을 고려하 여 여행지 간 가장 효율적인 교통편을 추천한다. 이때, 열 차, 항공기와 같이 이용할 수 있는 장소까지의 이동소요 (시간, 비용)까지도 고려하도록 설계되었다. 셋째, 여행경비, 여행계획 기간과 여행 중 숙박시설의 이용, 여행지 간의 이 동시간뿐만 아니라 여행지에서의 관광시간(Stay time)과 여 행지별 개장․폐장시간(Time windows) 등 다양한 고려사 항들을 통해 여행계획을 현실화함으로써 여행자들에게 보 다 유용한 정보를 제공한다. 또한, 여행정보시스템(Travel information system) 상에서 구현하는 바에 따라 보다 다양 한 기준(목적함수)에서 여행자의 효용을 극대화할 수 있는 여행계획을 제공할 수 있다. 이와 같은 개선사항들은 국 내․외 여행사례에 대한 수치실험을 통해 검증하였다.

향후 연구로는, 여행경로 추천 서비스가 인터넷 환경 에서 제공되고 있음을 고려할 때, 본 연구에서 적용한 최 적 해법으로는 다수의 여행지에 대한 여행계획 추천에 제한이 따른다. 따라서 합리적인 시간 내에 신뢰할 수 있 는 여행경로를 제시하기 위한 휴리스틱[4, 5, 12]과 같은 해법이 필요하다. 또한, 제시된 수리모형은 여행의 효용 또는 비용만으로 목적함수를 구성하였으나, 여행의 만족 도 향상을 위해 여행자의 여건과 취향에 따라 다수의 기 준을 동시에 고려할 필요가 있다. 즉, 복수의 목적함수를 갖는 목표계획법(Goal programming) 모형 또는 다기준 의사결정법(Multi criteria decision making)에 의한 목적함 수의 구성 등이 고려될 수 있다. 또한, 본 연구의 모형이 국제물류 환경에서의 복합일관운송 시스템 설계에 기본 적 틀을 제공할 수 있을 것으로 기대한다.

Figure

<Figure 1>.

Korea National Tourism Survey(summary)[10]

<Figure 2>.

Trip Plan of Jeju Island for 2 Days

<Figure 3>.

Trip Plan of Jeju Island for 4 Days

<Figure 4>.

Trip Plan of Europe (France, Germany, Czech Republic) for 7 Days

Table

<Table 1>.

Data for Experiment #1 : Jeju Island

No.	Place name	Time Windows	Admissionfee($)	Awareness	Stay time(hour)
0	Home (Gangnam)	24 hour	-	-	-
1	Hallasan Mountain	8:00	17:00	-	9.8	5.0
2	Seongsan Ilchulbong Peak	9:00	18:00	2.0	9.6	2.0
3	Hyeopjae Beach	8:00	20:00	-	8.7	4.0
4	Manjanggul Lava Tube	9:00	18:00	2.0	8.5	3.0
5	Seoubong Beach	8:00	20:00	-	9.1	5.0
6	Eco Land Theme Park	9:00	18:00	12.0	8.3	4.0
7	Yongduam Rock	8:00	20:00	-	9.4	3.0
8	Jeju Stone Park	9:00	18:00	5.0	8.2	2.0
9	Seopjikoji	8:00	20:00	1.0	8.7	2.0
10	Seogwipo olle Market	8:00	20:00	20.0	10.0	2.5
11	Airport	Jeju airport	24 hour	-	-	-
12	Incheon airport	24 hour	-	-	-
13	Accommodations	Kensington hotel	8:00	20:00	228.0	-	-
14	Haevichi hotel	8:00	20:00	210.0	-	-
15	Ramada hotel	8:00	20:00	290.0	-	-

<Table 2>.

Time to Arrive at Each Node

Node	1	2	7	8	9	10	11	12	14	0
1st day	12:20	-	-	17:35	-	10:35	10:00	8:50	20:00	-
2nd day	-	8:20	14:55	-	10:30	-	18:00	19:10	-	20:00

<Table 3>.

Time to Arrive at Each Node

Node	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	0
1st day	-	-	-	-	10:20	-	-	-	-	-	10:00	8:50	-	20:00	-	-
2nd day	-	-	13:50	-	-	-	-	10:55	8:25	18:00	-	-	20:00	-	-	-
3rd day	8:30	-	-	-	-	15:35	-	-	-	-	-	-	-	20:00	-	-
4th day	-	8:20	-	10:45	-	-	14:15	-	-	-	18:00	19:10	-	-	-	20:00

<Table 4>.

Data for Experiment #2 : Europe(France, Germany, Czech Republic)

No.	Place name	Time Windows	Admission fee($)	Awareness	Stay time (hour)
0	France	Home (Gangnam)	24 hour	-	-	-
1	Eiffel Tower	9:30	23:30	15	10.0	2.0
2	Montmartre Hill	8:00	22:00	-	9.6	2.5
3	Versailles Palace	9:00	18:30	20	9.8	2.5
4	Triumphal arch	10:00	22:30	10	9.5	0.5
5	Germany	Berlin Dorm	9:00	20:00	-	9.8	0.67
6	Spree River	8:00	20:00	-	8.5	1.5
7	Checkpoint Charlie	9:00	18:00	-	8.8	1.5
8	Potsdam Square	8:00	18:00	-	9.1	0.67
9	Czech	Prague Castle	9:00	18:00	16	10.0	2.5
10	Cesky	8:00	18:00	10	9.5	5.0
11	Airport &Station	Paris station	24 hour	-	-
12	Berlin stations	24 hour	-	-	-
13	Berlin airport	24 hour	-	-	-
14	Prague station	24 hour	-	-	-
15	Prague airport	24 hour	-	-	-
16	Incheon airport	24 hour	-	-	-
17	Accommodations	Paris hotel #1	8:00	20:00	164	-	-
18	Paris hotel #2	8:00	20:00	63	-	-
19	Berlin hotel #1	8:00	20:00	148	-	-
20	Berlin hotel #2	8:00	20:00	265	-	-
21	Prague hotel #1	8:00	20:00	243	-	-

Reference

Chen Q , Ma R , Jin M , Ren P (2016) Influence of Real-Information to Change Tourists' Travel Route , International Journal of u-and e-Service, Science and Technology, Vol.9 (11) ; pp.337-348
http://www.earthtory.com,
http://maps.google.co.kr,
Ha JM , Moon G (2015) An Application of k-Means Clustering to Vehicle Routing Problems , Journal of Society of Korea Industrial and Systems Engineering, Vol.38 (3) ; pp.1-7
Kang CS , Lee JS (2005) A Heuristic for Fleet Size and Mix Vehicle Routing Problem with Time Deadline , Journal of Society of Korea Industrial and Systems Engineering, Vol.28 (2) ; pp.8-17
Kara I , Laporte G , Bektas T (2004) A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem , European Journal of Operational Research, Vol.158 (3) ; pp.793-795
Kim CW , Boo ES , Park S , Lee E , Ko YB (2017) Real-Time Travel Route Recommendation Service based on IoT , Proceedings of Symposium of the Korean Institute of communications and Information Sciences, ; pp.1084-1085
Kurashima T , Iwata T , Irie G , Fujimura K (2013) Travel route recommendation using geotagged photos , Knowledge and Information Systems, Vol.37 (1) ; pp.37-60
Lee J , Yang J (2014) Efficient Travel Route Recommendation System based on User Moving Route and Tourist Information , Korea Computer Congress, ; pp.1616-1618
(2017) 2016 Korea National Tourism Survey (Analysis),
(2017) 2016 Korea National Tourism Survey (Statistics),
Moon G , Park S (2012) A Possible Heuristic for Variable Speed Vehicle Routing Problem with 4 Time Zone , Journal of Society of Korea Industrial and Systems Engineering, Vol.35 (4) ; pp.171-178
http://map.naver.com,
Oh Y , Kim J , Han Y , Han CG (2016) A Travel Route Recommendation System based on The Number of Stored Travel Photos , Korea Computer Congress, ; pp.2056-2058
http://www.stubbyplanner.com,
http://www.tripadvisor.co.kr,
Wen YT , Yeo J , Peng WC , Hwang SW (2017) Efficient Keyword-aware Representative Travel Route Recommendation , IEEE Transactions on Knowledge and Data Engineering, Vol.29 (8) ; pp.1639-1652

No.	Place name		Time Windows		Admissionfee($)	Awareness	Stay time(hour)
No.	Place name		Open	Close	Admissionfee($)	Awareness	Stay time(hour)
0	Home (Gangnam)		24 hour		-	-	-
1	Hallasan Mountain		8:00	17:00	-	9.8	5.0
2	Seongsan Ilchulbong Peak		9:00	18:00	2.0	9.6	2.0
3	Hyeopjae Beach		8:00	20:00	-	8.7	4.0
4	Manjanggul Lava Tube		9:00	18:00	2.0	8.5	3.0
5	Seoubong Beach		8:00	20:00	-	9.1	5.0
6	Eco Land Theme Park		9:00	18:00	12.0	8.3	4.0
7	Yongduam Rock		8:00	20:00	-	9.4	3.0
8	Jeju Stone Park		9:00	18:00	5.0	8.2	2.0
9	Seopjikoji		8:00	20:00	1.0	8.7	2.0
10	Seogwipo olle Market		8:00	20:00	20.0	10.0	2.5
11	Airport	Jeju airport	24 hour		-	-	-
12	Airport	Incheon airport	24 hour		-	-	-
13	Accommodations	Kensington hotel	8:00	20:00	228.0	-	-
14		Haevichi hotel	8:00	20:00	210.0	-	-
15		Ramada hotel	8:00	20:00	290.0	-	-