역방향 로지스틱스에서 폐기품 수거 망 설계 및 차량경로 문제에 관한 연구

Abstract

This dissertation focuses on the refuse collection network design and vehicle routing problems in reverse logistics. The network design problem determines the number, locations and capacities of collection points as well as the allocations of refuses at each demand points to the opened collection points under the capacity and maximum allowable distance constraints, while the vehicle routing problem determines the number and routes of collection vehicles starting and terminating at the depot while satisfying the returned demands at collection points and vehicle capacity. In this dissertation, we first consider the two static and two dynamic network design models. Then, the integrated network design, capacity planning and vehicle routing problem is considered, together with reporting a case study on a Korean municipal refuse collection system. In Chapter 2, two static collection network design models are suggested. The first one is the static problem that determines the locations of collection points and allocation of refuses at demand points to the opened collection points under the capacity and the maximum allowable distance constraints at each collection point. After formulating the problem mathematically, an optimal and two heuristic algorithms are suggested for the objective of minimizing the sum of fixed costs to open collection points and variable costs to transport refuses at demand points to collection points. The second one is the static collection network design and capacity planning problem. The capacity planning determines the capacities of collection points. Here, the additional capacity planning problem is an important consideration in collection network design since it provides flexible responses to changes in collection demands and cost savings from reducing surplus collection capacities. To represent the problems mathematically, we develop an integer programming model. Then, due to the problem complexities, two heuristic algorithms are suggested. To show the performances of the algorithms developed for each of the two static problems, computational experiments were done on various instances, and the test results are reported. In Chapter 3, two dynamic collection network design models are suggested to cope with fluctuating demands commonly occurred in refuse collection systems. The first one is a restricted dynamic collection network design problem in which the locations are fixed, but the allocations are changed over a given planning horizon. This is because it is highly unlikely to change collection points due to large fixed costs to open or close them and larger total costs due to frequent changes in the locations of collection points. The problem is formulated as an integer programming model for the objective of minimizing the sum of fixed costs and variable costs, and then, due to the problem complexity, two heuristic algorithms are suggested. As in the static models, the second one is the restricted dynamic network design and capacity planning problem. To represent the problem mathematically, an integer programming model is developed. Then, due to the problem complexity, two heuristics are suggested. To show the performances of the algorithms developed for each of the two dynamic problems, computational experiments were done on various test instances, and the results are reported. In particular, we show from an additional test that the dynamic approach significantly outperforms the static one when the refuse demands change over time. In Chapter 4, an integrated model is suggested for network design, capacity planning and vehicle routing. The network design and capacity planning problems are to determine the static locations and capacities of collection points as well as the dynamic allocations of demand points to the opened collection points over a planning horizon, and the vehicle routing problem is to determine the number and routes of vehicles in such a way that each collection point must be visited exactly once by one vehicle starting and terminating at the depot while satisfying the refuse demands at collection points and the vehicle capacity. The objective is to minimize the sum of fixed costs to open collection points and to acquire vehicles as well as variable costs to transport refuses at demand points to the opened collection points and travel the opened collection points by vehicles. To solve the integrated problem, two types of tabu search algorithms, hierarchical and integrated ones, are suggested. To show the performances of the tabu search algorithms, computational experiments were done on various test instances, and the results are reported. In particular, we show that the integrated approach outperforms the hierarchical one significantly. Also, a case study is reported for a Korean municipal refuse collection system.|본 논문은 역방향 로지스틱스에서 폐기품 수거 망 설계 및 차량경로 문제를 고려하고 있다. 역방향 로지스틱스에서 수거 시스템의 설계와 관련된 의사결정 문제는 수거지점의 수, 위치, 용량 및 수요 지의 수요를 수거지점에 할당하는 것을 결정하는 문제이며, 차량경로와 관련된 의사결정 문제는 수거차량의 수와 경로를 결정하는 문제로 한대의 차량이 차고 또는 수거관련 시설을 출발하여 오직 하나의 수거지점을 방문하여 수거지점에 할당되어 모인 수요를 수거하여 돌아오는 문제이며, 이때 수거지점의 모든 수요는 수거해야 하며 차량의 용량제약을 고려해야 한다는 특성을 가지고 있다. 따라서 본 논문에서는 수거 망 설계의 가장 기본적인 형태인 정적 모형과 수요 지의 수요변동을 고려하여 확장한 동적 모형을 제안하였다. 특히, 정적 및 동적 모형 각각에 대하여 수거지점의 용량을 결정하는 용량계획 문제를 추가적으로 고려하여 확장하였다. 마지막으로, 수거 망 설계 문제와 차량경로 문제를 통합하여 수거 망 설계 및 용량계획과 차량경로의 통합문제를 제안하고 관련 사례연구를 수행 하였다. 먼저, 가장 기본적인 형태인 수거 망 설계 문제의 정적 모형은 수거지점의 위치와 수요 지의 수요를 수거지점에 할당하는 것을 결정하는 것이며 수거지점의 용량과 최대 수거가능 거리 제약을 고려하였다. 본 장에서는 이와 관련하여 수리모형을 개발하고 최적 알고리듬인 분지 한계법과 두 가지 형태의 발견적 알고리듬을 개발하였다. 또한, 본 장에서 제안한 정적 모형에 수거지점의 용량을 결정하는 용량계획 문제를 추가적으로 고려하여 수거 망 설계 및 용량계획 문제를 제안하였다. 수거지점의 용량계획 문제의 경우 각 수거지점에 가장 최적화된 용량을 선택하여 수거지점을 위치 시킬 수 있도록 함으로써 각 수거지점의 잉여 용량을 줄여 수거 망 설계에 관한 비용을 줄일 수 있다. 본 장에서는 확장문제에 대해서도 수리모형을 개발하고 확장문제의 난이도로 인하여 두 가지 형태의 발견적 알고리듬을 제안하였다. 또한, 수거 망 설계의 기본적인 형태인 정적 모형과 확장문제에서 제안한 알고리듬을 평가하기 위하여 계산실험을 수행하였으며 그 결과를 보였다. 다음으로, 두 번째 장에서는 앞서 제안한 정적 모형에 수요지의 수요가 매 기간 변동하는 경우를 고려하여 확장한 동적 모형을 제안하였으며, 본 장에서 제안한 동적 모형은 전체 계획기간에 걸쳐 수거지점의 정적인 위치를 결정하고 동시에 수요지의 수요를 수거지점에 매 기간 동적으로 할당하는 제한적인 동적 모형을 제안하였다. 본 장에서도 앞선 정적 모형과 마찬가지로 동적 모형에 용량계획 문제를 추가적으로 고려하여 수거 망 설계 및 용량계획 문제를 제안하였으며, 관련 수리모형을 개발하고 문제의 난이도로 인하여 두 가지 형태의 발견적 알고리듬을 제안하였다. 또한, 동적 모형과 확장문제에서 제안한 알고리듬을 평가하기 위하여 계산실험을 수행 하였으며 그 결과를 보였다. 특히, 본 장에서는 정적 모형과 동적 모형의 비교를 통해 수요지의 수요가 변동하는 경우 동적 모형이 정적 모형과 비교하여 효율적인 해를 줄 수 있음을 보여 주었다. 마지막으로, 세 번째 장에서는 수거 망 설계 및 용량계획과 차량경로 문제를 통합한 수거망 설계 및 차량경로 문제를 제안하였다. 통합문제에서 수거 망 설계 및 용량계획 문제의 경우 전체 계획기간에 걸쳐 수거지점의 정적인 위치 및 용량계획을 결정하며 동시에 수거지점에 수요지의 수요를 매 기간 동적으로 할당하는 것을 결정하는 문제이며, 차량경로 문제는 수거차량의 수와 경로를 결정하는 문제로 한대의 차량이 차고 또는 수거관련 시설을 출발하여 오직 하나의 수거지점을 방문하여 수거지점에 할당되어 모인 수요를 수거하는 문제이며, 수거지점의 모든 수요는 수거하여야 하며 차량의 용량제약을 고려하여야 한다는 특성을 가지고 있다. 제안한 통합문제를 해결하기 위하여 본 장에서는 두 가지 형태의 타부서치 알고리듬을 제안하였고, 제안한 알고리듬을 평가 하기 위하여 계산 실험을 수행 하였으며 그 결과를 보였다. 또한, 통합문제에 대하여 현실 적용가능성의 판단 및 현실 수거 시스템의 개선을 위하여 사례 데이터를 수집하고 사례 연구를 수행 하였다. 사례연구 결과 제안한 알고리듬이 기존 수거 망 설계 및 운영 방법에 비하여 많은 개선을 줄 수 있음을 확인 하였다.; This dissertation focuses on the refuse collection network design and vehicle routing problems in reverse logistics. The network design problem determines the number, locations and capacities of collection points as well as the allocations of refuses at each demand points to the opened collection points under the capacity and maximum allowable distance constraints, while the vehicle routing problem determines the number and routes of collection vehicles starting and terminating at the depot while satisfying the returned demands at collection points and vehicle capacity. In this dissertation, we first consider the two static and two dynamic network design models. Then, the integrated network design, capacity planning and vehicle routing problem is considered, together with reporting a case study on a Korean municipal refuse collection system. In Chapter 2, two static collection network design models are suggested. The first one is the static problem that determines the locations of collection points and allocation of refuses at demand points to the opened collection points under the capacity and the maximum allowable distance constraints at each collection point. After formulating the problem mathematically, an optimal and two heuristic algorithms are suggested for the objective of minimizing the sum of fixed costs to open collection points and variable costs to transport refuses at demand points to collection points. The second one is the static collection network design and capacity planning problem. The capacity planning determines the capacities of collection points. Here, the additional capacity planning problem is an important consideration in collection network design since it provides flexible responses to changes in collection demands and cost savings from reducing surplus collection capacities. To represent the problems mathematically, we develop an integer programming model. Then, due to the problem complexities, two heuristic algorithms are suggested. To show the performances of the algorithms developed for each of the two static problems, computational experiments were done on various instances, and the test results are reported. In Chapter 3, two dynamic collection network design models are suggested to cope with fluctuating demands commonly occurred in refuse collection systems. The first one is a restricted dynamic collection network design problem in which the locations are fixed, but the allocations are changed over a given planning horizon. This is because it is highly unlikely to change collection points due to large fixed costs to open or close them and larger total costs due to frequent changes in the locations of collection points. The problem is formulated as an integer programming model for the objective of minimizing the sum of fixed costs and variable costs, and then, due to the problem complexity, two heuristic algorithms are suggested. As in the static models, the second one is the restricted dynamic network design and capacity planning problem. To represent the problem mathematically, an integer programming model is developed. Then, due to the problem complexity, two heuristics are suggested. To show the performances of the algorithms developed for each of the two dynamic problems, computational experiments were done on various test instances, and the results are reported. In particular, we show from an additional test that the dynamic approach significantly outperforms the static one when the refuse demands change over time. In Chapter 4, an integrated model is suggested for network design, capacity planning and vehicle routing. The network design and capacity planning problems are to determine the static locations and capacities of collection points as well as the dynamic allocations of demand points to the opened collection points over a planning horizon, and the vehicle routing problem is to determine the number and routes of vehicles in such a way that each collection point must be visited exactly once by one vehicle starting and terminating at the depot while satisfying the refuse demands at collection points and the vehicle capacity. The objective is to minimize the sum of fixed costs to open collection points and to acquire vehicles as well as variable costs to transport refuses at demand points to the opened collection points and travel the opened collection points by vehicles. To solve the integrated problem, two types of tabu search algorithms, hierarchical and integrated ones, are suggested. To show the performances of the tabu search algorithms, computational experiments were done on various test instances, and the results are reported. In particular, we show that the integrated approach outperforms the hierarchical one significantly. Also, a case study is reported for a Korean municipal refuse collection system.