This dissertation focuses on multi-period inventory/distribution planning in two-level inventory systems consisting of a warehouse and many geographically dispersed retailers. Products are distributed from the warehouse to the retailers by a fleet of vehicles. We determine vehicle routes and schedules and delivery quantities for retailers with the objective of minimizing transportation costs for product delivery and inventory holding costs at retailers over a given planning horizon. In this dissertation, we consider the following three problems related to inventory and distribution planning of the system.
First, we consider a multi-period vehicle scheduling problem (MPVSP) in a transportation system where a fleet of homogeneous vehicles delivers products of a single type from a central depot to multiple (N) retailers. For the MPVSP, a two-phase heuristic algorithm is suggested based on a k-th shortest path algorithm. In the first phase of the algorithm, the MPVSP is decomposed into N single-retailer problems by ignoring the number of vehicles available. The single-retailer problem is formulated as the shortest path problem and several good delivery schedules are generated for each retailer using the k-th shortest path algorithm assuming the exact requirement policy is used in the system. In the exact requirement policy, replenishments occur only when the inventory level is zero. In the second phase, a set of vehicle schedules is selected from those generated in the first phase. The vehicle schedule selection problem, which is a generalized assignment problem, is solved by a heuristic based on the k-th shortest path algorithm.
Secondly, we consider a multi-period inventory/distribution planning problem (MPIDP) in a one-warehouse multi-retailer distribution system where a fleet of heterogeneous vehicles delivers products from a warehouse to several retailers. It is assumed that vehicles can make several round trips between the warehouse and the retailers in a time period. The MPIDP is formulated as a mixed integer program and solved by a Lagrangian relaxation approach in which sets of complicated constraints are relaxed. The relaxed problem is decomposed into a linear programming problem and several integer knapsack problems. A subgradient optimization method is used to find optimal values for Lagrangian multipliers, and a Lagrangian heuristic is suggested to find good feasible solutions for the MPIDP in a reasonable amount of time.
Finally, we consider a multi-period inventory routing problem (MPIRP) to determine delivery routes of vehicles and delivery quantities to be delivered to the retailers in each period with the objective of minimizing transportation distances of vehicles while satisfying demand of the retailers. The MPIRP is formulated as a set partitioning problem, in which retailers are grouped into sub-regions and retailers in a sub-region are served by a vehicle. We suggest an algorithm for the MPIRP based on the column generation method. The column generation algorithm suggested here embeds a sub-region generation procedure which enumerates all possible sub-region groupings and a method for making a delivery schedule for retailers in a sub-region. In addition to the column generation, a heuristic based on simulated annealing (SA) approach is developed to group retailers into sub-regions. In the column generation algorithm, all possible sub-region groupings are implicitly enumerated, while a subset of possible sub-region groupings is considered in the search heuristic.
Performances of all solution procedures are evaluated through series of computational tests on test problems generated in such a way that the resulting problem data reflect the real situations well. Results of the computational tests show that the solution procedures developed in this dissertation give very good solutions in a reasonable amount of computation time.
본 논문에서는 하나의 창고와 다수의 소매점들로 이루어진 2단계 재고 시스템에서의 다기간 운송 계획 문제를 다루고 있다. 여러 지역에 분산되어 위치한 소매점들의 수요를 만족시키기 위하여, 최소의 비용으로 제품을 공급할 수 있도록 기간별 제품 운송량과 차량의 운행 계획 및 운송 경로를 결정할 수 있는 수리 모형들과 해법들을 개발하였다.
본 논문에서는 기존의 차량의 운송 경로 결정, 제품 공급 및 재고 관리와 관련된 연구들에서 고려하지 못한 제품 공급과 관련되어 현실적으로 고려해야 하는 사항들을 고려하였다. 첫째, 운송비용과 재고 비용을 동시에 고려함으로써, 더욱 경제적인 차량 운송 계획과 제품 공급 계획을 수립할 수 있도록 하였다. 둘째, 여러 기간 동안의 동적인 제품 수요를 고려함으로써 문제의 사실성을 높였다.
먼저, 논문의 2장에서는 소매점으로의 운송기간이 한 기간 이상인 장거리 운송의 경우에 대한 문제를 다루었다. 계획 기간동안에 소매점에서의 재고 유지 비용과 제품 공급을 위한 차량 운행 비용의 합을 최소화하는 문제를 해결하기 위하여 k번째 최소 경로 기법(k-th shortest path algorithm)을 이용한 2단계 휴리스틱 알고리즘을 개발하였다. 알고리즘의 첫번째 단계에서는 전체 문제를 여러 개의 단일 소매점 문제로 분해하여 각 소매점들에 대한 여러 개의 공급계획 대안을 수립하였고, 두 번째 단계에서는 자원제약이 있는 최소 경로문제를 이용하여 전체 문제에 대한 공급계획을 수립하였다.
다음으로, 논문의 3장에서는 한 기간 내에 소매점으로 여러 번의 운송이 가능한 근거리 운송의 경우에 대한 문제를 다루었다. 계획 기간 동안의 소매점에서의 제품 수요와 차량의 적재 용량을 고려한 혼합 정수 선형 모형(Mixed integer linear program)을 제안하였고, 제안된 수리 모형에 대한 휴리스틱 알고리즘을 라그랑지안(Lagrangian) 완화 기법을 사용하여 개발하였다. 제안된 수리 모형 및 알고리즘을 통하여 제품의 재고 유지 비용과 차량의 운행 비용의 합을 최소화 하는 제품의 공급 계획 및 차량 운행 계획을 생성할 수 있다.
마지막으로, 논문의 4장에서는 차량이 창고를 떠난 후 다시 돌아올 때까지 여러 소매점들을 방문하는 경우에 대한 문제를 다루었다. 차량의 운행 비용을 최소화하는 차량의 운행 경로 및 소매점들에 대한 제품 공급량을 결정하기 위하여, 고려하는 문제를 집합 분할 문제(set partitioning problem)로 수리 모형화하고 열 생성 기법(column generation approach)을 이용한 휴리스틱 알고리즘을 개발하였다. 또한, 빠른 시간 내에 큰 문제를 해결하기 위하여 담금질 기법(simulated annealing)을 이용한 휴리스틱도 개발하였다.
본 논문에서 개발된 수리 모형들과 알고리즘들은 실제 현장의 상황을 반영할 수 있도록 생성된 실험 문제들을 이용하여 평가 되었다. 평가로부터 현실적인 시간 내에 논문에서 다루고 있는 중앙창고와 소매점들로 이루어진 2단계 재고 시스템에서 기간별 제품 공급 계획과 차량의 운행 계획에 대한 우수한 해들을 찾을 수 있음을 확인하였다.
