This thesis is concerned with the targeting problem and the fire sequencing problem. The main decision process of firing consists of two phases. Initially, we decide the weapon-target allocation by solving the targeting problem. Then, we schedule the firing sequence so as to minimize the timespan. Two phase approachgives flexibility to the plan officers. That means the plan officers can handle each problem separately under various tactical and operational constraints.
We consider the problem of assigning weapons to targets so that the total cost is minimized while satisfying various tactical and operational constraints. Given a set of weapon systems and a set of targets, we need to assign weapons to targets and determine the number of rounds that each weapon may fire on the targets. A target may be fired on by more than one weapon systems and a weapon may fire on more than one targets. The constraints include the amount of ammunition available for each weapon, the desired destroy level on each target, restriction on the number of targets that a weapon system can fire, and the upper bound on the number of rounds that can be fired for each weapon-target pair.
The targeting problem can be modeled as a nonlinear integer programming problem, which can be transformed into a linear integer programming problem by linearizing the nonlinear constraints. Even though targeting problem is NP-hard, we try to solve the problem to optimality within a reasonable amount of time.
In the basic targeting problem, we consider the minimum tactical and operational restrictions required to plan the targeting operation. To solve the basic targeting problem, we apply the Lagrangian relaxation and the branch-and-bound method. In the Lagrangian relaxation, a primal heuristic is developed so as to obtain the feasible solution from the infeasible solution obtained by solving the relaxed problem. Three different branching strategies are adopted and evaluated in the branch-and-bound method.
We extend the basic targeting problem by introducing extra constraints for the proper concentration and distribution of firepower. Preliminary tests showed that the conventional branch-and-bound approach based on the linear programming relaxation performed poorly on this problem. So, using the target impact configuration variables, we reformulate the problem that provides a bound at least as strong as the bound provided by the conventional formulation. To solve the reformulated problem, the delayed column generation technique and the branch-and-price algorithm are used. A hybrid branching strategy is developed in the implementation of the branch-and-price algorithm.
The aim point selection problem is another extended model, which considers indirect firing as well as the direct firing considered in the extended targeting model. To solve the problem, we reformulate the problem into a binary integer programming problem and apply the cutting plane algorithm to the reformulated problem. A separation procedure to find the violated valid inequalities and a heuristic method to strengthen the minimal general-upper-bound knapsack cover inequality are developed.
With the results of targeting problem as input data, the fire sequencing problem seeks to minimize the firing timespan under various tactical and operational constraints. We show that the fire sequencing problem is strongly NP-hard even if the number of weapon system is two. Preliminary tests showed that the branch-and-bound approach based on the linear programming relaxation performs poorly on this problem. Therefore, we develop a heuristic method for the fire sequencing problem. The heuristic method tries to allocate available targets at specific time slot as many as possible. That means we want the weapon systems not to be idle when the weapon systems are available. This strategy is based on greedy method.
The approaches to solve the targeting and the fire sequencing problems considered in this thesis can provide a guideline to develop a computerized control system for tactical firing direction. The models also can be used as reference models which can be extended to more sophisticated models for fire control.
무기체계-표적 할당문제는 주어진 무기체계와 표적의 집합에서 전술적, 운영적 제약 조건을 만족시키면서 최소 비용으로 가용 무기체계를 할당하는 문제이다. 사격순서 결정문제는 무기체계-표적 할당 문제에서 구한 결과를 바탕으로 전술적, 운영적 제약 조건을 만족시키면서 가장 빠른 시간 내에 사격을 완료할 수 있는 사격순서를 결정하는 일정계획 문제이다.
본 논문에서는 적 위협치 최소화 목적에 상응하는 표적의 요망 파괴 수준을 만족하는 제약식을 상정하고 이러한 제약하에서 비용을 최소화 시키는 비선형 정수계획법을 구성하였다. 이러한 접근법은 무기체계의 비용 뿐만 아니라 잔존적 위협 최소화를 동시에 추구하는 접근방법이다.
첫째, 기본적 무기체계-표적 할당문제는 야전에서 요구되는 통제보급률과 표적 요망파괴수준 그리고 사격통제를 위한 제약식으로 구성되어 있다. 이 문제를 해결하기 위해 비선형 정수 계획 모형을 선형 정수계획 모형으로 변환하여 Lagrangian 완화 기법과 분지한계법을 사용하여 최적 해를 구하는 해법을 제시하였다. 선택된 변수를 분지할 때는 3가지 분지 전략을 사용하였으며 분지방법에 따른 실험 결과를 비교하였다.
둘째, 앞에서 설정한 기본모형에 작전간 무기체계가 사격할 수 있는 표적의 수를 제한한 확장된 모형을 설정하였다. 이러한 제약사항의 추가는 화력의 집중과 분산이라는 효과를 달성하고 전술적 요구조건을 만족시키기 위한 것이다. 본 논문에서는 이 문제가 일반적인 선형계획법 완화 및 분지 한계법으로는 잘 해결되지 않는 문제라는 것을 보이고 문제를 표적이 피격되는 형태변수로 정의한 0-1 정수계획법으로 재구성하여 열 생성기법과 branch-and-price방법으로 최적 해를 구하는 해법을 제시하였다.
셋째, 조준점 선정 문제는 표적들이 일정 지역내 밀집해 있을 때 적절한 조준점에 사격을 함으로써 표적을 파괴하여 고가의 무기체계를 적절히 운용할 수 있는 무기체계-표적 할당 문제의 일종이다. 이 문제를 해결하기 위해 각 무기체계의 발사 형태를 변수로 정의하여 0-1 정수계획 모형으로 재구성하고 일반 상한 다면체의 절단평면을 이용하여 목적함수의 하한값을 증가시키는 절단 평면 해법과 분지 한계법을 적용하였다. 절단평면 해법을 적용하기 위한 유효부등식의 분리문제를 구성하여 절단평면을 찾았고 유효부등식을 강화할 수 있는 문제의 해법을 제시하였다.
마지막으로, 전술적 기습과 운영적 제약사항을 만족하는 사격 순서 결정 문제를 정수계획 모형으로 구성하고 이 문제가 무기체계의 수가 2 이상이면 의사 다항 시간 내에 해결하는 해법이 알려지지 않은 강력한 NP-hard 문제인 것을 증명하였다. 따라서 가능 해를 구하기 위해 발견적 방법을 개발하였다. 발견적 방법은 일정한 시각에 표적에 사격이 가능하면 가용한 무기체계를 전부 운영하여 빠른 시간내에 계획된 표적을 다 사격할 수 있는 방법으로 구성되어 있다.
