Optimizing urban waste collection efficiency : an IoT enabled dynamic vehicle routing system

다국어 초록 (Multilingual Abstract)

Urban waste collection remains one of the most resource-intensive services that a city must provide, and in most municipalities, it is still carried out along fixed routes that take no account of how full the bins actually are. Trucks visit containers that are nearly empty while bins in busier districts overflow before the next scheduled round, wasting fuel, labor, and vehicle hours and leaving residents dissatisfied. The growing availability of low-cost fill-level sensors has made it possible to know the state of every bin in close to real time, yet that information is of little value unless the routing system is able to act on it. This thesis addresses that gap by designing and implementing a dynamic vehicle routing system that continuously adapts collection routes to the live condition of an instrumented bin network.
The system was built as a complete, working application for the Haeundae district of Busan, comprising one hundred bins, four collection trucks operating from four separate depots, and four disposal facilities. At its center is a routing engine that treats the task as a multi-depot capacitated vehicle routing problem and re-plans whenever a bin crosses an eighty-percent fill threshold. To determine which routing strategy is best suited to this setting, ten algorithms were implemented and compared on identical data under a fixed random seed, ranging from simple construction heuristics such as Nearest Neighbour and the Clarke-Wright savings method, through classical metaheuristics including Simulated Annealing, Tabu Search, Genetic Algorithms, Ant Colony Optimization and Large Neighbourhood Search, to the constraint-programming solver provided by Google OR-Tools. Each was evaluated on total travel distance, fuel consumption, and computation time, and the benefit of dynamic re-routing was measured separately against a static plan.
The results show a clear and consistent ordering. On the shared thirty-bin instance the OR-Tools solver produced the shortest routes at 24.66 kilometres, roughly thirty-five percent less than the 37.71 kilometres travelled by the Nearest Neighbour baseline, with a corresponding reduction in fuel from 12.63 to 8.24 litres. Metaheuristics occupied the middle of the ranking, while the pure construction heuristics performed worse, confirming that the additional search effort invested by the stronger methods translates into real savings on this problem. The dynamic experiments demonstrated that re-routing in response to newly full bins allowed the fleet to service fifty percent more containers than a static plan without a proportional increase in distance. Taken together, the work shows that combining an instrumented bin network with a capable routing solver and a dynamic re-planning policy yields a measurable and reproducible improvement in collection efficiency, and that the choice of routing algorithm is itself a decision worth making with care.

국문 초록 (Abstract)

도시 폐기물 수거는 도시가 제공해야 하는 가장 자원 집약적인 공공 서비스 중 하나이지만, 대부분의 지방자치단체에서는 여전히 수거함이 실제로 얼마나 찼는지와 관계없이 고정된 경로를 따라 수행되고 있다. 그 결과 거의 비어 있는 수거함을 방문하는 데 연료와 인력, 차량 운행 시간이 낭비되는 한편, 통행량이 많은 지역의 수거함은 정해진 수거일 이전에 넘쳐 주민 불편을 야기한다. 최근 저비용 적재량 감지 센서의 보급으로 모든 수거함의 상태를 실시간에 가깝게 파악할 수 있게 되었으나, 경로 산정 시스템이 이러한 정보를 활용하여 능동적으로 대응하지 못한다면 그 가치는 제한적이다. 본 논문은 계측된 수거함 네트워크의 실시간 상태에 따라 수거 경로를 지속적으로 조정하는 동적 차량 경로 지정 시스템을 설계하고 구현함으로써 이러한 문제를 다룬다.
제안한 시스템은 부산 해운대구를 대상으로 100개의 수거함, 4개의 차고지에서 운행하는 4대의 수거 차량, 4개의 처리 시설로 구성된 완전한 응용 프로그램으로 구축되었다. 시스템의 핵심은 수거 문제를 다중 차고지 용량 제약 차량 경로 문제（Multi-Depot Capacitated Vehicle Routing Problem）로 정식화하고, 수거함의 적재량이 80% 임계값을 초과할 때마다 경로를 재계획하는 경로 산정 엔진이다. 본 연구는 이 환경에 가장 적합한 경로 산정 전략을 규명하기 위하여, 최근접 이웃（Nearest Neighbour） 및 클라크-라이트 절약（Clarke-Wright Savings）과 같은 단순 구성 휴리스틱부터, 모의 담금질（Simulated Annealing）, 타부 탐색（Tabu Search）, 유전 알고리즘（Genetic Algorithm）, 개미 군집 최적화（Ant Colony Optimization）, 대형 이웃 탐색（Large Neighbourhood Search）과 같은 고전적 메타휴리스틱, 그리고 구글 OR-Tools의 제약 프로그래밍 솔버에 이르기까지 총 열 가지 알고리즘을 고정된 난수 시드 하에서 동일한 데이터로 비교하였다. 각 알고리즘은 총 이동 거리, 연료 소비량, 계산 시간을 기준으로 평가되었으며, 동적 재경로 산정의 효과는 정적 계획과 별도로 비교 측정되었다.
실험 결과는 명확하고 일관된 순위를 보여주었다. 동일한 30개 수거함 인스턴스에서 OR-Tools 솔버는 24.66킬로미터로 가장 짧은 경로를 산출하였으며, 이는 최근접 이웃 기준선의 37.71킬로미터보다 약 35% 짧은 수치로, 연료 소비량 또한 12.63리터에서 8.24리터로 감소하였다. 메타휴리스틱은 순위의 중간을 차지하였고 순수 구성 휴리스틱은 가장 저조한 성능을 보였는데, 이는 더 강력한 기법이 투입한 추가적인 탐색 노력이 실제 비용 절감으로 이어짐을 확인해 준다. 동적 실험에서는 새롭게 가득 찬 수거함에 대응하여 경로를 재산정함으로써, 거리의 비례적 증가 없이도 정적 계획 대비 50% 더 많은 수거함을 처리할 수 있음을 입증하였다. 종합하면 본 연구는 계측된 수거함 네트워크와 성능이 우수한 경로 산정 솔버, 그리고 동적 재계획 정책을 결합함으로써 측정 가능하고 재현 가능한 수거 효율 향상을 달성할 수 있으며, 경로 산정 알고리즘의 선택 자체가 신중하게 내려야 할 의사결정임을 보여준다.

목차 (Table of Contents)

• I. Introduction 1
• 1 Research Background 1
• 2 Importance 2
• 3 Research Motivation and Significance 3
• II. Literature Review 6
• 1. The Origin and Structure of Vehicle Routing 6
• 2. Construction Heuristics and Their Limitations 7
• 3. Metaheuristics for Routing 9
• 4. Modern Solvers and the OR-Tools Library 10
• 5. IoT-Enabled and Dynamic Waste Collection 12
• 6. Evaluation Practice and Benchmark Instances 13
• 7. Research Gap 14
• III. Methodology 15
• 1. System Design and Architecture 15
• 2. Problem Formulation 16
• 3. Distance, Time, and Fuel Models 18
• 4. The Ten Routing Algorithms 20
• 5. Static and Dynamic Modes 23
• 6. Data Collection and Dataset 24
• 7. Evaluation Metrics and Experimental Constraints 26
• IV. Implementation and experimental setup 28
• 1. Technology Stack and Backend 28
• 2. Frontend and Visualization 30
• 3. Real-Time Communication and the Algorithm Registry 31
• 4. Experimental Setup 32
• 5. Database Schema and Data Model 33
• 6. Achieving Reproducibility in Practice 34
• V. Results and analysis 35
• 1. Static Comparison of Ten Algorithms 35
• 2. Improvement Over the Baseline 37
• 3. Performance by Algorithm Category 38
• 4. Computation Time and the Quality–Time Trade-off 40
• 5. The Configuration of the Independently Implemented Metaheuristics 41
• 6. The Relationship Between Distance and Fuel 43
• 7. Dynamic Re-routing Proof 43
• 8. Discussion and Interpretation 45
• 9. Why the Selected Strategy Is Appropriate 47
• VI. Conclusion 48
• 1. Summary of Findings 48
• 2. Contributions of Research 48
• 3. Future Work 49
• VII. References 51
• VII. Appendix 54
• 1. The OR-Tools Routing Solver 54
• 2. The Load-Sensitive Fuel Model 55
• 3. The Dynamic Re-routing Trigger 55
• 국문초록 57