Vehicle Routing in a Refuse Collection System : A Case Study

Abstract

본 연구는 서울시 성동구청 관할지역 내 폐기물 수거 망의 차량경로 결정에 관한 것이며, 기존의 방식보다 차량의 이동거리를 최소화하여 수거 시스템의 효율성을 향상시키는 것을 본 연구의 최종 목적으로 한다. 쓰레기 수거 작업은 수거작업의 시간대와 날짜, 그리고 위치에 따라 쓰레기의 양이 현저히 달라지는 특성을 갖고 있다. 또한 기존 수거 시스템에서는 각 수거지점의 쓰레기 양을 현장에 도착하지 않고는 예측할 수 없다는 한계가 있다. 이 때문에 기존 수거 방식에서는 경우에 따라 수거차량 한대의 용량을 초과하는 상황이 발생하게 된다. 수거 차량의 적재용량이 초과되면 쓰레기 수거 작업은 중단될 수 밖에 없고 차량은 적재된 쓰레기를 집하장에 버리기 위해 회차하게 된다. 이러한 과정을 "라우트 실패"라고 하는데 이 “라우트 실패” 비율이 높을수록 차량의 이동거리는 증가하게 된다. 본 논문에서는 라우트 실패를 최소화하면서 동시에 많은 수거지점의 쓰레기 집하장으로 이동시킬 수 있는 휴리스틱을 제안하였다. 첫째, 간단한 3가지의 휴리스틱 알고리즘을 사용하여 결정적인 방법과 통계적인 방법에 적용하였다. 둘째, 제안한 휴리스틱 방법의 수행평가를 위해 시뮬레이션 실험을 실시하여 증명하였다. 셋째, 결정적인 방법과 통계적인 방법을 사용하여 기존 쓰레기 수거 망의 차량경로보다 수거 효율이 향상된 것을 실험을 통해 증명하였다.; This thesis addresses a case study on the vehicle routing problem for a refuse collection activity in Seoul, South Korea. Unlike existing deterministic versions of the vehicle routing problem, this research considers a stochastic version of the vehicle routing problem to determine collection vehicle routes that satisfy the stochastic demand at each collection point for the objective of minimizing the total distance travelled. Due to the stochasticity of demand at each collection point, the vehicle capacity may be violated at random, called a route failure in this thesis. Two types of simple heuristics; deterministic and stochastic ones are suggested. To show the performances of the heuristics, simulation experiments were done on the real data, and the results show that deterministic and stochastic heuristics suggested in this thesis outperforms the conventional method used in the current refuse collection activity.