This thesis addresses the routing of planetary surface rover considering two important aspects associated with space exploration. The problem can be formulated as the vehicle routing problem with profits (VRPP). Given the base (landing location) and the set of sites that can be potentially explored, the VRPP determines the routes of a rover starting from a base, visiting selected sites to collect profits, and returning to the base, to maximize the sum of collected profits obtained at visited sites under constraints on a single route and the whole exploration mission. In the traditional VRPP framework, two important issues for the routing problem associated with space exploration - the coupling between the routes and rover’s layout trade-off and the various perspectives of multiple stakeholder groups - additionally considered.
In the first part of the thesis, the routing optimization of planetary surface rover considering the core composition of the rover, which is one of its key design decisions. The rover system is simplified as two core subsystems having important functional trade-off - the mobility/operation subsystem and the science subsystem. A double-loop solution methodology that can determine the best weight distribution of two subsystems as well as the optimal routing for the given exploration map is proposed. Case studies for two sets of surface exploration instances having different characteristics are conducted to demonstrate the validity of the proposed optimization procedure.
The second part of this thesis proposes a routing problem that involves the perspectives of multiple stakeholder groups. To reflect various benefit types obtainable from the planetary exploration, the concept of profit vector - rather than a scalar - assigned on a site. Each element of the vector represents the assessment of the site provided by a specific stakeholder. The objective for the routing optimization with vector profit is to maximize the sum of profits for the least satisfied stakeholder - sequentially in a lexicographical sense. A mixed-integer linear programming (MILP) formulation of the proposed problem referred to as the Vehicle Routing Problem with Vector Profit (VRPVP) is presented. A column generation based solution methodology that can find near-optimal solution for the VRPVP with optimality gap is developed. Two case studies - a planetary surface exploration and a Rome tour case - are presented to demonstrate the effectiveness of the proposed formulation and solution procedure.
본 논문은 행성 표면 탐사 로버의 경로 결정 문제에 두 가지 관점을 결합한 내용을 다루고 있다. 연구에서 다룬 문제는 이익을 고려한 차량 경로 문제(the vehicle routing problem with profits, VRPP)의 한 종류로 공식화되었다. 이익을 고려한 차량 경로 문제는 베이스(착륙지) 및 탐사 후보지들의 위치가 정해진 경우, 주어진 제약 조건 하에서 베이스를 출발하여 탐사지들을 방문하여 획득하는 이익을 최대화하고 베이스로 돌아오는 경로를 찾는 문제이다. 전통적인 VRPP 문제에서 다음과 같은 두 가지 관점 - 경로와 로버 레이아웃의 트레이드오프 관계 및 다양한 이해관계자들이 존재하는 경우의 경로 결정 - 이 본 연구에서 추가적으로 다루어졌다.
논문의 첫 번째 파트에서는 로버 설계의 핵심 사항인 로버 서브시스템들이 전체 시스템에서 차지하는 비율을 로버의 탐사 경로와 함께 최적화하는 경로 결정 문제를 제시하였다. 로버의 시스템을 두 개의 핵심 서브시스템인 이동/운영 서브시스템과 과학 서브시스템으로 간소화하였다. 로버 서브시스템들의 최적 무게 분배 및 그에 따른 최적 경로를 찾기 위한 이중 루프 문제 해결 기법을 제시하였다. 제시한 문제 해결 방법론의 검증을 위해서는 서로 다른 특성을 가지는 두 가지 사례 연구를 분석하여 그 결과를 제시하였다.
두 번째 파트에서는 경로 결정 과정에 다수의 이해관계자들이 참여하는 경우에 대한 문제를 제시하였다. 다양한 관점을 고려하기 위해서는 탐사 후보지에 할당되는 이익 값을 스칼라가 아닌 벡터 이익을 적용하였다. 벡터 이익에서 각각의 요소는 해당 탐사 후보지에 대한 개별 이해관계자의 관점을 의미한다. 문제의 목적 함수는 탐사를 통해 획득하는 이익 값이 가장 낮은 이해관계자의 이익 값을 최대화하고, 그다음 낮은 값을 순차적으로 최대화하는 것으로 하였다. 문제는 혼합 정수 선형계획법(mixed-integer linear programming, MILP)으로 공식화되었으며, 벡터 이익을 고려한 차량 경로 문제(the vehicle routing problem with vector profit, VRPVP)로 명명되었다. 제시한 VRPVP 문제의 근사 해를 찾기 위한 열 생성 기법 기반 문제 해결 기법이 제시되었고, 방법론을 검증하고자 행성 표면 탐사 및 로마 여행 경로 최적화의 두 가지 사례 연구를 수행하였다.
