여행상품 인솔자 스케쥴링 문제에 대한 휴리스틱 알고리즘 연구

A Study on Heuristic Algorithm for Tour-guide Scheduling Problem

본 연구에서는, 여행사에서 운영하는 패키지 여행상품에 효율적으로 인솔자를 배정하기 위한 스케쥴링 문제 및 해법을 제시하였다. 본 스케쥴링 문제의 목적은 일정이 정해진 다수의 여행상품에 대한 인솔자 배정 건수의 최대화이며 제약조건은 다음과 같다. (1) 모든 배정 대상 여행상품의 출발 및 도착 일정은 고정되어 있다. (2) 각각의 여행상품에는 한 명 이하의 인솔자가 배정된다. (3) 한 명의 인솔자는 둘 이상의 여행상품을 동시에 인솔할 수 없다. (4) 인솔자의 등급에 따라 배정 가능한 상품 범위가 제한된다. (5) 배정의 공정성을 기하기 위해 모든 인솔자들의 배정 만족도가 최소치 이상이 되어야 한다. 본 연구에서는 위의 문제에 대한 수리 모형을 만들고, 이를 효율적으로 풀기 위한 휴리스틱 알고리즘을 제안 하였다. 또한, 실제 여행사 데이터에 기반 한 수치 예제를 활용하여 최적해 및 풀이 시간에 대한 성능 실험을 수행하였다. 그 결과 IBM Ilog Cplex 대비 99% 수준의 최적 해를 효율적인 풀이 시간 내에 산출하였다.

This study presents an Integer Programming model (hereafter IP model) and an algorithm for tour-guide scheduling optimization. The model, Tour Guide Interval Scheduling Problem, aims to maximize the number of travel packages, paired with a tour-guide for each, under the following conditions: (1) start and end time for all itineraries are fixed, (2) each guide takes charge of only one tour package at a time, (3) each tour package ought to be assigned to no more than one guide, (4) each guide should be assigned to tour packages under his/her regional accessibility, (5) while meeting the minimum level of the satisfaction level of each guide on the assignment. The model is verified to be NP-hard(Non-deterministic Polynomial time hard). We suggest a heuristic algorithm for the problem and then conduct a computational experiment using data of a tour company to verify efficiency of the algorithm. The result presents more than 99% of optimal solution and notably faster computation time compared to that of IBM Ilog Cplex, implying significant outcome of this study.