선형 독립적이고 자원 제약이 있는 k번째 최소 경로 문제

국문 초록 (Abstract)

선형 독립적이고 자원 제약이 있는 k번째 최소 경로 문제(Linearly Independent and Resource Constrained k-th shortest Path Problem; LI-RCKSPP)란 최소 경로 집합에 선형 독립적이고 자원 제약 조건을 만족하는 k번째 최소 경로를 찾는 문제이다. 최소 경로 집합이란 1번째 최소 경로부터 k-1번째 최소 경로까지의 k-1개의 최소 경로들의 집합을 의미한다. 본 논문은 LI-RCKSPP를 처음으로 정의하고 이 문제의 최적 해를 구할 수 있는 생성 기반 알고리즘을 소개한다. 벤치마크 데이터에서의 실험을 통해 제안된 알고리즘의 한계와 그 개선 방향을 제안한다.

다국어 초록 (Multilingual Abstract)

Linearly independent and resource constrained k-th shortest path problem (LI-RCKSPP) is the problem of finding the k-th shortest path that is linearly independent to the shortest path set and satisfies resource constraints. The shortest path set means a set of k-1 paths from the first to the k-1-th shortest path. This paper first defines LI-RCKSPP and introduces an enumerative algorithm to find the optimal solution. The computational experiments on the benchmark data shows the performance of the algorithm and the improvement direction.

목차 (Table of Contents)

• 1. 서론
• 2. LI-RCKSPP에 대한 정의
• 3. 생성 기반 알고리즘
• 4. 실험 결과
• 5. 결론
• 참고문헌