We consider several optimization problems in the telecommunication network and logistics subject to data uncertainty. To handle the uncertainty of data efficiently, we adopt the robust optimization methodology. The goal of the robust optimization is to obtain a solution which is feasible for all possible realizations of input data. We present formulations of the problems and propose exact solution algorithms for the robust solution.
First, we consider the network design problem without flow bifurcations. We need to determine the capacity configuration for the edges of the network, which minimizes the sum of total transportation and installation cost while respecting the demand requirements. The demand data are assumed to be uncertain, so we define an uncertainty set for each demand data and a parameter to control the degree of robustness. The goal of the problem is to find an optimal solution which is immune to all possible demand data variations defined by the uncertainty sets and the given parameter. With a mathematical formulation, we propose a solution algorithm for this robust version of the network design problem. We propose a branch-and-price-and-cut algorithm to solve the problem exactly, which enables us to transfer the difficulties arising from data uncertainty to the column generation subproblem. In our algorithm, the column generation subproblem is represented as the robust knapsack problem, and we also present a solution algorithm to solve it. Additionally, we show that we can obtain a complete description of the robust knapsack polytope for each edge of the network. Consequently, we show that the robustness of the solution can be achieved via classical deterministic solution algorithm with small modifications. The results from computational experiments indicate that the robust optimization approach can provide much robust solution at a rather small penalty in the objective value.
Next, we consider a network design problem with flow bifurcations. We assume that the demand data are uncertain, and the uncertainty of demand is expressed as a uncertainty set. The goal is to obtain a minimum cost facilities installation solution on the edges. The solution should be able to deliver any demand requirement in the uncertainty set. We propose an exact solution algorithm based on a decomposition approach. The problem is decomposed into two distinct problems; The first is to design edge capacities, and the second is to check the feasibility of the designed edge capacities with respect to the uncertain demand requirements. The algorithm is a special case of the Benders decomposition method. We show that the robust version of Benders subproblem can be formulated as a linear programming whose size is polynomially bounded. We also propose simultaneous cut generation scheme to accelerate the Benders decomposition algorithm. We report computational results on the real-life telecommunication problems which show viability of proposed algorithm.
And, we consider the vehicle routing problem with time windows and travel time uncertainty. In vehicle routing problem with time window, the time window is imposed on each customer, so that the service for a customer should be taken within the time window. The goal of the problem is to cover given customers at minimum travel distance while respecting time windows and vehicle capacities. Additionally, we consider the case where some unpredictable delays on travel times may happen. Based on the robust optimization methodology, we first present a mixed integer programming formulation, and propose a Dantzig-Wolfe decomposition approach, which enables us to migrate the uncertainty to the column generation subproblem. We propose a dynamic programming algorithm, which can solve the subproblem when the travel time is uncertain. Benefited from the proposed decomposition approach, we show that the robust optimal solution can be obtained via almost the same solution methodology which has been proved to be effective for the non-robust deterministic problems. The computational experiments is conducted on the well-known test instances, and show the robustness of the solution can be greatly improved with quite small penalty in the objective value.
Classical column generation often shows desperately slow convergence. Recently, many acceleration techniques are proposed to improve the convergence. We briefly survey these methods, and propose a new one based on Chebyshev center of dual polyhedron. The Chebyshev center can be obtained by linear programming, so our method can be applied with small modifications on the classical column generation procedure. We also show that the performance can be enhanced by introducing proximity parameters which enable us to adjust the position of the Chebyshev center. Numerical experiments are conducted on the binpacking, vehicle routing problem with time windows, and generalized assignment problem. Computational results show the effectiveness of our method.
본 논문에서는 데이터의 불확실성을 고려하여 통신과 물류분야의 몇몇 최적화 문제들에 대해서 다룬다. 데이터의 불확실성을 효과적으로 다루기 위해서 강건 최적화 방법론을 적용하였다. 강건 최적화의 목적은 불확실한 입력 데이터의 실현 가능한 모든 경우에 대해서도 유효한 최적해를 구하는 것이다. 본 연구에서는 각 문제들에 대해서 강건해를 얻을 수 있는 최적 해법을 제시하려 한다.
먼저, 수요를 나누어 수송할 수 없을 때의 망설계 문제에 대해 다룬다. 본 문제의 목적은 통신망의 주어진 수요량을 모두 소송할 수 있도록 각 호에 설치될 장비의 종류를 결정하는 것이다. 수요량에는 불확실성이 존재한다고 가정하고, 이를 효과적으로 다루기 위해 불확실성 집합을 정의하여 해의 강건한 정도를 조절 할 수 있는 방법을 정의하였다. 이를 바탕으로 강건한 해를 얻을 수 있는 수리식을 제시하고 최적해법을 제시한다. 본 접근 방법의 목적은 불확실한 수요에 대해 유효성을 유지하는 최적해를 찾는 것이다. 본 연구에서는 분지 평가법에 기반한 최적해법을 제시하는데, 이를 통해서 데이터의 불확실성을 전체 최적해법에서 분리하여 열생성 부문제로 전이 할 수 있음을 보인다. 열 생성 부 문제는 강건한 배낭문제의 형태로 주어지는데, 이를 효과적으로 풀 수 있는 방법을 제시한다. 이들 결과들을 이용하여, 각 호에 대해서 강건 배낭문제의 완전기술이 가능하다. 결과적으로, 강건해는 전통적인 최적해법을 약간 수정 함으로써 얻을 수 있을을 보인다. 계산 실험의 결과에 의하면 본 연구에서 제안한 강건 최적해법은 기존의 방법보다 훨씬 강건한 정도를 가지는 최적해를 빠른 시간내에 얻을 수 있었다.
다음으로, 수요량이 분할 가능할 때의 망설계문를 다룬다. 수요량은 불확실하게 주어진다고 가정하고, 이를 불확실성 집합으로 표현한다. 본 문제의 목적은 모든 가능한 불확실성 집합의 수요를 수송할 수 있는 최적 망설계해를 구하는 것이다. 본 연구에서는 이 문제를 망설계 주 문제와 불확실한 수요량의 수송 가능성을 검사하는 부 문제로 분할하는 최적해법을 제시한다. 본 최적해법은 잘 알려진 Benders 분할 방법의 특별한 경우로써, 강건함을 보장하는 부 문제의 수리 모형이 다항시간내에 풀수 있는 형태로 재수립 될 수 있음을 제시한다. 또한, 벤더의 분할 방법의 수행속도를 높이기 위해 동시 위반 절단평면을 효과적으로 생성하는 방법을 제시한다. 실제 사용되는 통신망 문제에 대한 계산 실헙 결과는 본 최적해법이 빠른 시간내에 매우 강건한 최적해를 도출할 수 있을을 명확하게 보여준다.
그리고, 시간 제약이 있는 차량경로문제문제에 대한 이동시간의 불확실성을 고려한 강건 최적해법 알고리즘을 제시한다. 시간 제약이 있는 차량경로문제에서는 각 고객마다 방문가능 시간대가 주어지며 각 차량은 이 시간대 내에 고객을 방문 하여야 한다. 본 문제의 목적은 방문 가능 시간대를 준수하고 차량의 용량을 고려하는 최단 거리 방문 경로를 찾는것이며, 이 최적해는 이동 중에 발생 할 수 있는 예측 불가능한 지연에 대해 강건함을 가지고 있어야 한다. 본 문제에 대한 수리 묘형을 제시한 후, Dantzig-Wolfe의 분할 방법을 바탕으로 불확실성을 열생성 부 문제로 분리 할 수 있는 방법을 제시한다. 불확실성을 가지고 있는 열 생성 부 문제를 풀기 위한 동적 계획 해법을 제시한다. 제안된 분리 방법을 통해 강건한 최적해는 강건하지 않은 전통적인 최적해를 구하는 효과적인 방법을 약간의 수정을 통해 얻을 수 있음을 보인다. 잘 알려진 실험 대상 문제들에 대한 계산 실험의 결과는 본 연구에서 제안된 강건 최적해법을 통해 얻은 최적해는 최적값의 아주 작은 손해만을 가지며 훨씬 더 강건한정도를 가짐을 보여준다.
마지막으로, 전통적인 열생성 방법의 느린 수렴속도를 가속하기 위한 새로운 방법을 제시한다. 최근에 전통적인 열 생성의 성능을 개선시키기 위한 많은 연구들이 보고되고 있다. 본 연구에서는 이들 연구에 대해서 간단히 살펴본 후, Chebyshev 중심에 기반한 새로운 열생성 방법을 제시한다. Chebyshev 중심은 선형 계획법으로 쉽게 구할 수 있으며, 기존의 열생성 방법을 적은 수정만으로 대체 할 수 있다. 또한, Chebyshev 중심의 상대적인 위치를 조절 할 수 있는 방법을 제시하여, 수렴 가능성에 대한 증명을 보인다. 용기할당문제, 차량경로문제 그리고 일반 작업 할당문제들에 대해서 계산 실험을 실시 하였고, 그 결과는 본 방법의 유효함을 보여준다.
