title: Clustering-Based Improved Ant Colony Optimization for the Multi-Trip Vehicle Routing Problem with Heterogeneous Fleet and Time Windows: An Industrial Case Study
Creators: name: Kim, Beom Sae Shawn
Publisher: name: Graduate Studies
Year: 2025
Subjects: subject: Vehicle Routing Problem (VRP)
subject: Workload Balance
subject: Ant Colony Optimization (ACO)
subject: DBSCAN-Plus
subject: Micro-Clustering
subject: Route Optimization
subject: Geographic Information System (GIS)
subject: Quantum GIS (QGIS)
subject: Artificial Intelligence
subject: Engineering--Industrial
subject: Engineering--Operations Research
subject: Geotechnology

description: The growing complexity of logistics and transportation systems has led to significant interest in solving Vehicle Routing Problems (VRP) with realistic constraints. Real-world VRP extends beyond minimizing transportation costs to include balancing workloads among drivers, managing heterogeneous fleets, and adhering to strict time windows. Addressing these challenges requires advanced methodologies that ensure operational efficiency, fairness, and adaptability to practical constraints. This thesis proposes a Clustering-Based Improved Ant Colony Optimization (CIACO) algorithm, integrating an improved Ant Colony Optimization (IACO) metaheuristic with advanced clustering techniques, including a modified density-based spatial clustering of applications with noise (DBSCAN-Plus) and a Micro-Cluster Fusion Scheme. The framework addresses the multi-trip VRP with heterogeneous fleet and time windows (MTVRPHFTW), focusing on minimizing total travel distance while handling constraints such as travel time, vehicle capacity, heterogeneous fleet configurations, customer-specific time windows, and multitrip scheduling. Additionally, it ensures balanced workload distribution among vehicles while prioritizing the use of smaller, fuel-efficient vehicles to reduce CO2 emissions, supporting both operational efficiency and sustainability goals. This thesis also discusses the development of an interactive Geographic Information System (GIS) visualization system, implemented via custom Quantum Geographic Information System (QGIS) plugins. Designed specifically to enhance the interpretability and application of the CIACO algorithm, this system bridges optimization results with GIS functionality via custom QGIS plugins, providing logistics planners with dynamic visualizations, route overlays with toggling options, advanced filtering capabilities based on metrics such as CO2 emissions, travel time, travel distance, and vehicle types, and an interactive dashboard for real-time analysis and decision-making support. These interactive features enhance the practicality of the proposed framework for real-world logistics applications, making the solutions more adaptable and actionable. The proposed framework was validated using industrial data from a Canadian logistics company, demonstrating its effectiveness in addressing complex VRP. Experimental results show that CIACO outperforms existing methods in minimizing travel distance, achieving balanced workload distribution, and reducing environmental impact. The interactive GIS system amplifies the practicality of the approach by translating optimization outcomes into intuitive visualizations. This thesis advances VRP research by integrating algorithmic optimization with GIS technologies, addressing modern logistical challenges, and offering scalable solutions for industrial applications.