상세검색
최근 검색어 전체 삭제
다국어입력
즐겨찾기0
149542.jpg
KCI등재 학술저널

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

A Study on Heuristic Algorithm for Tour-guide Scheduling Problem

  • 92

본 연구에서는, 여행사에서 운영하는 패키지 여행상품에 효율적으로 인솔자를 배정하기 위한 스케쥴링 문제 및 해법을 제시하였다. 본 스케쥴링 문제의 목적은 일정이 정해진 다수의 여행상품에 대한 인솔자 배정 건수의 최대화이며 제약조건은 다음과 같다. (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.

Ⅰ. 서론

Ⅱ. 문헌연구

Ⅲ. 연구모형

Ⅳ. 알고리즘

Ⅴ. 성능 평가 실험

Ⅵ. 결론

로딩중