This thesis considers layered network design problems for communication and supply chain networks, where the main decision problem is to determine the set of logical tunnels to be established and the logical paths, through which any given demands should be routed. The problems are described in mathematical expressions, for which solution algorithms are developed in the integer programming approaches. In Chapter 2 and Chapter 3, layered communication network design problems for ATM networks and virtual private networks (VPN’s) are considered. Chapter 4 considers a layered supply chain network design problem for cross-docking networks.
Specifically, Chapter 2 considers a combined problem of establishing virtual paths (VP’s) and routing traffic (packet) demands through the virtual paths in ATM networks where each physical link is subject to its capacity constraints. The problem is modeled as a path-based formulation for which a branch-and-price solution algorithm is derived. The solution algorithm is composed of an efficient pricing algorithm and branching rules based on a variable dichotomy which does not destroy the structure of the associated pricing problems. Computational experiments are performed to test the efficiency of the algorithm, which show that the proposed solution algorithm works quite well in finding optimal solutions (for the test instances) within reasonable time. Its immediate application may be made to a centralized ATM network management on mid-term global reconfiguration and long-term VP planning.
Chapter 3 considers a VPN tunnel design problem of establishing VPN tunnels between nodes subject to a VPN tunnel hop count restriction. The relationship between the VPN tunnel design problem and the minimum-cost directed Steiner tree problem is investigated in detail. The problem is modeled as a layered network flow model for which the exact solution is derived based on the path-based branch-and-price methodology with a preprocessing technique incorporated. The associated computational experiments are made, from which it is found that the proposed path-based exact solution algorithm outperforms any standard branch-and-bound algorithm based on the associated arc-flow-based model in terms of effectiveness and efficiency measures.
Chapter 4 considers an integrated service network design problem for cross-docking supply chain networks which is concerned with integration of locating cross-docking (CD) centers and allocating vehicles for the associated direct (transportation) serivces. For the vehicle allocation, direct services (sub-routes) should be determined for the given freight demands, and then the vehicle allocation has to be made in consideration of routing for the associated direct service fulfillment subject to vehicle capacity and service time restriction. The problem is modeled as a path-based formulation for which a tabu-search-based solution algorithm is proposed. To guarantee the performance of the proposed solution algorithm, strong valid inequalities are derived based on the polyhedral characteristics of the problem domain and an efficient separation heuristic is derived for identifying any violated valid inequalities. Computational experiments are performed to test the performance of the proposed solution algorithm and also that of a valid-inequality separation algorithm, which finds that the solution algorithm works quite well and the separation algorithm provides strengthened lower bounds. Its immediate application may be made to strategic (integrated) service network designs and to tactical service network planning for the cross-docking network.
본 논문에서는 통신 및 공급사슬 네트워크 설계를 위한 계층형 네트워크 설계최적화 문제의 정수계획 모델과 이에 대한 해법을 제시하고 있다. 세부적으로는 ATM 망과 가상사설망(VPN)에서의 계층형 통신네트워크 최적설계 문제들과 크로스도킹 배송망에서의 계층형 공급사슬네트워크 최적설계 문제를 다루고 있다.
첫번째 모델은 ATM 망에서 가상경로(VP)를 설정하고, 트래픽들을 가상경로를 통해 전송하는 통합설계문제를 고려하고 있다. 기존의 해법들은 이 통합설계문제를 전송망계층과 논리망계층으로 분리하여 순차적으로 접근하는 휴리스틱 접근법을 적용하였으나 본 논문에서는 전송망계층과 논리망계층을 동시에 고려하는 통합설계모델을 제안하였다. 이 통합설계문제는 각 망계층에서의 경로를 필요에 따라 생성하는 열생성기법 기반 정수계획 모델로 모델링되었고 Branch-and-price 방법론에 기반하여 최적 알고리즘을 제안하였다. 최적 알고리즘은 효율적인 열생성 기법과 열생성 문제의 특성을 고려한 분지방법으로 구성된다. 제안된 알고리즘의 성능을 분석하기 위하여 컴퓨터 실험이 수행되었고 실험결과 제안된 알고리즘이 최적해를 매우 효율적으로 찾는다는 것을 발견할 수 있었다. 본 논문에서 제안된 알고리즘은 중앙집중형 ATM 망 관리 시스템에서 주기적 전역재설계 및 망설계 장기계획에 적용 가능하다.
두번째 모델은 가상사설망에서의 VPN터널 설계 문제를 다루고 있다. 기존의 VPN 터널설계기법들은 Steiner 트리에 바탕을 두고 해를 구하였으나 본 논문에서는 VPN 터널설계문제에 적합한 계층형 망모델을 제시하고, 이에 대한 최적해법을 제안하였다. 최적해법은 정수계획법 모델에 대한 전처리 (Preprocessing) 기법 및 Branch-and-price 방법론에 기반한 최적화 알고리즘으로 구성된다. 컴퓨터 실험 결과 제안된 알고리즘이 상용 정수계획법 프로그램보다 월등히 나은 성능을 보여주는 것으로 나타났다.
세번째 모델은 크로스도킹 기반 공급사슬네트워크에서의 물류센터 위치선정 및 수송서비스별 차량할당 문제에 대한 해법을 제시하고 있다. 크로스도킹 기반 공급사슬 네트워크는 공급사슬관리(Supply Chain Management)의 핵심 수송 기법으로서 대형유통업체의 공급사슬네트워크 및 특급우편배송 등에 활발히 응용되고 있으나 이에 대한 연구는 부족한 상황이다. 본 논문에서는 크로스도킹 공급사슬네트워크 설계 문제에 대해 타부검색(Tabu search) 기법에 기반한 효율적인 휴리스틱 알고리즘을 제안하였다. 그리고 제안된 알고리즘의 성능을 검증하기 위해 주어진 정수계획법 모델에 적합한 유효부등식을 도출하고, 도출된 유효부등식을 효율적으로 추가하는 휴리스틱 해법을 제안하였다. 컴퓨터 실험 결과 제안된 타부검색 기반 휴리스틱 알고리즘은 좋은 해를 빠른 시간 안에 찾을 수 있었고, 추가된 유효부등식에 의해 정수계획완화문제의 해가 상당히 개선되었다는 것을 파악할 수 있었다. 본 논문에서 제안된 알고리즘은 크로스도킹 기반 공급사슬네트워크의 중/장기 설계계획에 효과적으로 적용될 수 있다.
