Network problems arise in many real-world areas. There has been a great deal of research on the network problems, however, those researches could not cover all the complex network problems. Therefore, more diverse and profound research activities are required. This thesis is concerned with three classes of problems in network delivery systems which are the travelling salesman problem (TSP) with time considerations, the dynamic uncapacitated facility location problem (DUFLP), and the processor selection and task assignment problem.
First, we present a formulation of the TSP with time windows (TSPTW), which is based on the dynamic concept of the TSP and thus has no additional constraints for the time window conditions. In our formulation, TSP is regarded as the minimum cost (one) flow problem with the specified constraints or the constrained shortest path problem. To solve the TSPTW, we use the dual-based procedure. We develop the valid inequalities for the TSPTW that can cut some fractional points of the LP relaxation problem and can be used to reduce the duality gap. The solution procedure is coded, and then computational experiments are carried out. In addition, we present two variants of TSP: the vehicle travel problem (VTP) and the maximum-benefit time-dependent traveling salesman problem (MBTDTSP). The criterion of the VTP is to maximize the sum of the time dependent benefits associated with the travels between two cities in the given time period. In the MBTDTSP, the salesman can visit candidate customers in order to maximize time dependent benefits in the given period, where travel times between two customers are time dependent.
Secondly, we consider the DUFLP in which the facilities can freely enter and leave the system, that is, the facilities can be opened and closed several times. We linearize the quadratic term of the objective function of the DUFLP and present a dual-based solution procedure. A special facet for our DUFLP is presented which is not covered in any previous studies. The solution procedure is coded and tested computationally.
Finally, we consider the processor selection and task allocation problem in a distributed computer and communication system which consists of a collection of candidate processors with capacity option and a set of distributing points. At each distributing point, jobs requesting a service from any processor arrive randomly. In the system, we try to minimize the maximum mean queue length, and produce a general fractional objective function. For solution of the integer linear fractional programming model of our problem, we develop a parametric algorithm that solves a sequence of linear programming problems. In cases that we cannot obtain integer solutions directly, we use the branch and bound method. The performance of solution procedure is tested through computational experiments.
네트웍 문제는 현실 세계에서 많이 나타나고 있는 문제로, 그동안 수많은 학자들이 연구를 하여왔다. 그러나 복잡한 형태의 네트웍 문제에 대한 연구는 아직 부족한 상황이며, 네트웍 문제의 응용 영역은 점점 넓어지고 있다. 따라서 네트웍문제에 대한 다양하고 심도깊은 연구가 더욱 더 필요하다 하겠다.
본 논문에서는 배송망의 형태를 가지고 있는 세가지 종류의 네트웍 문제 인 여행판매원 문제(TSP: Traveling Salesman Problem), 동적설비입지 선정문제(DUFLP: Dynamic Uncapacitated Facility Location Problem), 처리장치선택과 작업할당문제(Processor Selection and Task Allocation)를 대상으로, 각 문제의 모형들을 제시하고 효율적인 해법을 연구하여, 이들 문제들에 대한 연구 확대와 현실상황에의 응용가능성을 높이고자 한다.
여행판매원 문제에서는 방문 순번을 제한하는 경우를 다루었으며, 제한을 의미하는 추가적인 제약식이 없으면서 제한을 나타낼 수 있는 모형을 여행판매원 문제의 동적 개념(Dynamic Concept)를 통해 제시하였는데, 이 모형은 특정제약식을 갖는 최소흐름문제(혹은 최단경로문제)의 형태를 갖게 된다. 문제모형을 풀기 위해 쌍대구조에 바탕을 둔 쌍대해법을 연구하였는데, 원문제와 쌍대문제의 목적함수의 쌍대갭(Duality gab)을 줄이기 위해 원문제의 유효부등식(Valid Inequality)을 개발하여 쌍대 해법의 과정에 반영하였다. 쌍대갭이 발생하는 경우에는 분단탐색법을 통하여 정수 최적해를 찾게 된다. 이러한 해법의 과정을 C언어를 통하여 코딩하여 25가지의 예제를 풀이 하였다.
방문 순번을 제한하는 문제모형의 개념을 이용하여 추가적으로 두 가지 문제를 다루었다. 첫째는 수송선 운항문제(VTP: Vehicle Travel Problem) 로서 선박이나, 비행기 같은 수송선이 일정기간 동안 각 항구나 도시들을 돌아 출발점으로 돌아오는 문제이다. 이 문제에서 운항 수입은 출발시간이나 도착시간에 영향을 받게 되며, 일부 항로는 특정 시간대에 반드시 운항되어야 하는 제약을 갖고 있으나 나머지 항로들에 대한 운항 횟수의 제약은 없다. 둘째는 시간종속 여행판매원문제 (MBTDTSP : Maximum-Benefit Time-Dependent TSP)로 판매원은 일정시간 동안 대상후보 고객들을 최대한 1번 방문하고 출발점으로 돌아오게 되며, 각 고객과 고객을 방문하는데 필요한 이동시간은 이동시의 시각에 따라 달라지게 된다. 이는 대도시에서 매일 고객들을 방문하는 경우에 해당하는 것으로 이동 시간은 러시아워나 그 지역의 특성등에 따라 달라지므로 방문계획을 잘 수립하여 최대한 많은 고객을 방문하여 수익을 최대화하여야 한다. 이들 두 가지 문제들도 쌍대해법을 통하여 풀수있는데, 이 과정들은 방문 순번의 제약이 있는 문제의 해법과 비슷하므로 자세한 과정은 생략하였다.
동적설비입지 선정문제에서는 여러 기간에 걸쳐 설비를 운영하는 문제를 연구하였는데 설비는 상황에 따라서 개설되기도 하고 폐쇄되기도 하며 개설, 폐쇄가 되풀이 될 수 있다. 이 문제는 2차식의 목적함수를 가진 모형으로 정형화 되는데, 본 연구에서는 이 2차식을 새로운 변수와 이와 관계 된 제약식을 통하여 선형화(Linearization) 하였다. 모형을 풀기 위하여 쌍대해법을 연구하였으며 쌍대갭이 생기는 경우에는 분단탐색법을 이용하게 된다. 해법의 과정을 C언어로 코딩하여 25가지 문제를 풀이하고 그 결과를 제시 하였다.
처리장치 선택과 작업할당 문제에서는 각 후보지에서 여러 형태의 용량중의 하나를 택하여 처리 장치를 설치할 수 있는데, 이 처리장치에서는 각 수요처에서 보내온 포아송 확률과정으로 발생한 작업을 처리하게 된다. 이 문제에서는 예산 제약조건을 가지며 각 처리장치의 평균 대기길이의 최대값을 최소화하는 대안을 찾는 것을 목적으로 한다. 이 문제는 정수선 형분수계획법(Integer Linear Fractional Programming) 으로 모형화되며 이 모형을 풀기 위하여 새로운 개념의 매개변수해법을 개발하였는데 정수해를 찾지 못하는 경우에는 분단탐색법을 거쳐 정수 최적해를 찾게 된다. 해법의 과정은 포트란으로 코딩하였으며 25가지 예제를 풀어 보았다.
