Clustered Vehicle Routing Problem for Waste Collection Using K-means-Ant Colony Optimization

Abstract

Waste collection is one of the essential tasks in a smart city. The internet of things (IoT) is a promising technology that offers potential solutions for transforming traditional systems. An IoT-based smart bin is a modern technology that offers real-time fill level information to a cleaning authority. However, high uncertainty associated with the smart bin's fill levels and improper operation hinder efficient waste collection. In order to tackle the uncertainty in a smart bin and improve the waste collection operation, the IoT sensor's usage must be combined with optimization procedures. In this thesis, a neighboring bin is utilized to consider the sensor range of IoT. Furthermore, we introduced two operational management approaches to define dynamic optimal routes. We combined ant colony optimization (ACO) with a k-means clustering algorithm to solve the clustered vehicle routing problem for waste collection (CluVRP-WC) on a large scale. The first experiment was conducted in a case study, and comparison results of the operational management approaches were presented. Our hybrid metaheuristic is implemented in the second experiment. CluVRP-WC is a generalization of the capacitated vehicle routing problem (CVRP) in which smart bins are segmented into clusters by a k-means clustering algorithm. Our operational management approaches and proposed heuristic show the potential of building a smart waste collection system considering practical constraints.

폐기물 수거는 스마트 시티의 필수 과제 중 하나이다. 사물 인터넷(IoT)은 기존 시스템을 변환하기 위한 잠재적인 해결책을 제공하는 유망한 기술이다. IoT 기반 스마트 폐기물통은 청소 기관에 실시간으로 폐기물 정보를 제공하는 최신 기술이다. 그러나 폐기물양의 불확실성과 부적절한 수거 방법은 효율적인 폐기물 수거를 방해한다. 스마트 폐기물통의 불확실성을 해결하고 폐기물 수거 방법을 개선하려면 IoT 센서의 사용이 적절한 운영 방법과 결합되어야 한다. 본 연구에서는 동적 최적 경로를 정의하기 위해 두 가지 운영 관리 접근 방식과 인접 폐기물통 개념을 도입했다. 첫 번째 접근 방식은 실제 사례 연구에 적용하고 그 한계를 제시한다. 두 번째 접근 방식에서는 스마트 폐기물통의 불확실성을 해결하기 위해 인접 폐기물통을 사용한다. 본 실험을 위해 개미 군집 최적화와 k-평균 알고리즘을 결합하여 폐기물 수거를 위한 군집 차량 경로 문제를 해결한다.