95 0

시간 및 비용 제한이 주어진 유지보수 출장경로 탐색

Title
시간 및 비용 제한이 주어진 유지보수 출장경로 탐색
Other Titles
Traveling Maintenance Service Engineer Problem with Time and Cost Constraints
Author
김영훈
Keywords
유지보수 출장 경로 탐색; 탐욕적 알고리즘; Finding path for maintenance service; greedy algorithm
Issue Date
2017-08
Publisher
한국정보과학회
Citation
데이타베이스연구, v. 33, No. 2, Page. 54-65
Abstract
주어진 그래프에서 최소 비용으로 모든 노드를 한번 씩 방문하는 경로를 찾기 위한 외판원 문제는 여행 및 출장 경로를 찾는 응용문제에서 많이 활용이 되어왔다. 그러나 현실의 응용 문제에서는 여행 예산이 한정된 경우, 그리고 모든 노드를 방문하지 않아도 되는 경로를 찾아야 하는 경우가 발생한다. 본 논문에서는 제품의 고장 신고가 들어온 지역을 방문하기 위해 정해진 하루 예산 (i.e., 시간, 비용 등)을 만족하는 출장 경로를찾기 위한 출장 경로 최적화 문제를 다룬다. 또한 최적의 출장경로는 방문한 지역의 총 효용성으로 판단한다. 보다 현실적인 가정을 위해 외판원 문제와 달리 모든 지역을 방문할 필요가 없으며 하루 예산안에서 효용성을 높일 수 있다면 같은 지역을 두 번 방문하여도 관계없는 것이 차이이다. 본 연구에서는 이를 해결하고자 탐욕적(Greedy) 알고리즘을 제안하였으며, 실제 A/S 접수, 방문 날짜와 주소가 기록된 데이터를 기반으로 제안된 알고리즘의 성능을 비교 검증하였다. 그리고 실험을 통해 제안 알고리즘이 실제 A/S 수행에서 사용 된 예산보다 더 적은 예산을 사용하며 더 많은 도시를 방문하는 순회 경로를 찾아내는 것을 확인하였다. Traveling salesperson problem has been utilized for finding minimum-cost cycle touring all nodes with the smallest cost for a given graph and utilized for traveling path or business trip. However, for the real-world application, business budget is limited, and it is not needed to cover all cities. This paper deals with finding optimal business route problem with constraints which are limited budget. i.e., time, costs, etc. In addition, the optimal path is evaluated by the summation of value of visited cities. For more realistic assumption, in distinction from traveling salesperson problem, this problem is not required to visit all cities, and to maximize the total value of the cities, one city can be visited twice. To address this problem, this research suggests greedy algorithm and be evaluated with real maintenance trip data which consists of customer’s request, visit date and address. In conclusion, by the experiments, we verify that this algorithm obtains optimal path which utilizes less cost and more number of cities than real business trip data.
URI
https://www.kci.go.kr/kciportal/ci/sereArticleSearch/ciSereArtiView.kci?sereArticleSearchBean.artiId=ART002254850http://repository.hanyang.ac.kr/handle/20.500.11754/99254
ISSN
1598-9798
Appears in Collections:
COLLEGE OF COMPUTING[E] > COMPUTER SCIENCE(소프트웨어학부) > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE