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

• 영문명: A Study on Heuristic Algorithm for Tour-guide Scheduling Problem
• 발행기관: 한국생산관리학회
• 저자명: 배 진(Jin Bae) 서용원(Yong-Won Seo)
• 간행물 정보: 『한국생산관리학회지』韓國生産管理學會誌 第30卷 第3號, 251~266쪽, 전체 16쪽
• 주제분류: 경제경영 > 경영학
• 파일형태: PDF
• 발행일자: 2019.08.30

국문 초록

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

목차

Ⅰ. 서론

Ⅱ. 문헌연구

Ⅲ. 연구모형

Ⅳ. 알고리즘

Ⅴ. 성능 평가 실험

Ⅵ. 결론

키워드

여행 상품 서비스 운영관리 스케쥴링 Interval Scheduling 휴리스틱 알고리즘 Greedy Algorithm 정수 계획법 Tourism Service Operations Management Interval Scheduling Heuristic Algorithm Greedy Algorithm Integer Programming