This thesis considers two distribution optimization problems and a procurement optimization problem with vehicles allocated in supply chain networks. Chapter 2 and Chapter 3 present two optimization problems to design supply chain distribution networks with the cross-docking(CD) distribution strategy adapted, which has recently received much attention from the real field, but has not been studied much yet. Chapter 4 presents an optimization problem to make a procurement plan with supplier selection, lot-sizing and transportation (vehicle allocation) considered together.
Specifically, Chapter 2 proposes an exact branch-and-price algorithm for the single-period cross-docking supply chain network design problem introduced by Sung and Song (2003). The objective is to optimally locate cross-docking(CD) centers and allocate vehicles for direct transportation services from the associated origin node to the associated CD center or from the associated CD center to the associated destination node so as to satisfy a given set of freight demands at minimum cost subject to the associated service(delivery) time restriction. A set-partitioning-based formulation is derived for the problem for which some solution properties are characterized. Based on the properties, a branch-and-price algorithm is derived. The properties can also be used in deriving any efficient local search heuristics with the move operation (neighborhood search operation) of modifying assignment of some freight demands from current CD centers to other CD centers. The associated numerical experiments show that the proposed algorithm is effective and efficient and also that the solution properties contribute to improve the efficiency of the local search heuristics.
Chapter 3 proposes a Lagrangian heuristic for a multi-period vehicle lease planning problem in a CD supply chain network where short-term-leased and long-term-leased vehicles are to be allocated for each direct service. The objective is to allocate the two kinds of leased vehicles optimally for direct transportation services from the associated origin node to the associated CD centre or from the associated CD centre to the associated destination node so as to satisfy a given set of period-to-period freight demands over a given planning horizon at total minimum vehicle allocation cost subject to demand-dependent transportation time restriction. For the problem, a formulation is derived as an integer programming model. The problem is proven to be NP-hard in a strong sense, so that the Lagrangian relaxation method is applied to find a good solution efficiently. The associated numerical experiments show that the proposed Lagrangian heuristic may give good lower and upper bounds within reasonable time.
Chapter 4 proposes a Lagrangian heuristic for an integrated procurement planning problem with supplier selection, lot-sizing and vehicle allocation considered together. In a situation where a buyer purchases multiple products from multiple supplier candidates, the objective is to select suppliers, determine ordering time and ordering amount, and allocate heterogeneous vehicles so as to satisfy given period-to-period products` demands over a given planning horizon at the total minimum cost. The total cost is composed of purchasing cost, ordering cost, inventory holding cost and vehicle allocation cost. For the problem, a formulation is derived as an MIP (Mixed Integer Programming) model. The problem is proven to be NP-hard in a strong sense, so that a Lagrangian heuristic is proposed to find a good solution efficiently. The associated numerical experiments show that the proposed algorithm works quite well.
본 논문에서는 공급사슬망에서 차량할당을 고려한 두 가지 분배 최적화 문제와 한 가지 조달 최적화 문제에 대하여 연구하였다. 2장과 3장은 최근 현장에서 많은 관심을 받고 있으나, 연구가 많이 수행되지 않은 크로스 도킹 분배 전략을 사용하는 공급사슬 분배망을 설계하기 위한 최적화 문제들을 다룬다. 4장은 공급자 선정, lot-sizing 및 수송 (차량 할당)을 동시에 고려하여 조달 계획을 세우기 위한 최적화 문제를 다룬다.
구체적으로, 2장에서는 Sung and Song (2003)이 처음 연구했던 일 기간 크로스 도킹 공급사슬망 설계 문제에 대하여 최적해를 찾는 branch-and-price 알고리즘을 제안하였다. 본 문제의 목적은 서비스(배달) 시간 제약을 만족하면서, 최소 비용으로 주어진 화물 운송 요구들을 만족시키기 위한 크로스 도킹 기지들의 위치를 선정하고 화물 운송 시작지점에서 크로스 도킹 기지 혹은 크로스 도킹 기지에서 화물 운송 도착지점간의 직수송 서비스를 하기위해 필요한 차량들을 할당하는 것이다. 본 문제를 풀기 위하여, 집합 분할 모형(set-partitioning-based formulation)으로 모델링 되었으며 여러 문제의 특성들이 규명되었다. 규명된 특성들을 기반으로, 최적해를 찾는 branch-and-price 알고리즘이 개발되었다. 또한, 규명된 특성들은 어떤 화물 운송 요구들을 담당하는 크로스 도킹 기지들을 변경하는 move operation들을 이용하는 효율적인 local search 근사해법을 개발하는데 사용될 수 있다. 제안된 알고리즘의 성능을 분석하기 위하여 수행된 컴퓨터 실험 결과, 제안된 알고리즘은 효과적이며 효율적으로 최적해를 찾는다는 것과 규명된 특성들은 위에서 언급한 local search 근사해법의 효율성을 개선시킨다는 것을 알 수 있다.
3장에서는 크로스 도킹 공급사슬망에서 각 직 배송 구간에 단기 리스 차량들과 장기 리스 차량들을 할당하는 단기간 차량 리스 계획 문제를 해결하기 위해서 라그랑지안 근사해법을 제안하였다. 본 문제의 목적은 주어진 계획 기간에서 기간마다 변하는 화물 운송 요구들을 최소 비용으로 만족시키기 위해서 화물 운송 시작지점에서 크로스 도킹 기지 혹은 크로스 도킹 기지에서 화물 운송 도착지점간의 직 수송 서비스를 하기위한 이 두 가지 유형의 차량들은 할당하는 것이다. 제안된 문제는 정수 계획 모형으로 모델링 되었다. 또한, 본 문제는 pseudo-polynomial 알고리즘조차 존재하지 않을 것으로 판단되는 NP-hard 문제임을 증명하였다. 따라서, 좋은 근사해를 효율적으로 찾을 수 있는 근사해법을 개발하기 위하여 라그랑지안 완화 기법을 적용하였다. 제안된 알고리즘의 성능을 분석하기 위하여 수행된 컴퓨터 실험에서 제안된 라그랑지안 근사해법은 합리적인 시간 안에 최적해에 대한 좋은 하한과 상한을 준다는 것을 알 수 있다.
4장에서는 공급자 선정, lot-sizing 및 차량할당을 통합적으로 결정하기 위한 조달 계획 문제에 대한 라그랑지안 근사해법을 제안하였다. 본 문제의 목적은 한 명의 구매자가 다수의 공급자들로부터 다수의 제품들을 구매하는 상황에서, 주어진 계획기간에 대하여 기간마다 변하는 제품들의 수요를 최소비용으로 만족시키기 위해 제품 공급자들을 선정하고, 주문 시점과 주문량을 결정하며 수송 적재량이 다른 여러 가지 차량들을 할당하는 것이다. 비용은 구매 비용, 주문 비용, 재고 유지비용, 차량 할당 비용으로 구성된다. 제안된 문제는 혼합 정수 계획 모형으로 모델링 되었다. 또한, 본 문제는 pseudo-polynomial 알고리즘조차 존재하지 않을 것으로 판단되는 NP-hard 문제임을 증명하였다. 따라서, 좋은 근사해를 효율적으로 찾을 수 있는 라그랑지안 근사 해법을 제안하였다. 제안된 알고리즘의 성능을 분석하기 위하여 수행된 컴퓨터 실험 결과로부터, 제안된 라그랑지안 근사해법은 효과적이며 효율적으로 잘 작동한다는 것을 알 수 있다.
