Clustering-Based Improved Ant Colony Optimization for the Multi-Trip Vehicle Routing Problem with Heterogeneous Fleet and Time Windows: An Industrial Case Study

Simple item page
dc.contributor.advisorWang, Xin
dc.contributor.authorKim, Beom Sae Shawn
dc.contributor.committeememberWang, Xin
dc.contributor.committeememberKim, Jeong Woo
dc.contributor.committeememberWang, Yunli
dc.contributor.committeememberYang, Hongzhou
dc.date2025-06
dc.date.accessioned2025-01-20T22:28:31Z
dc.date.available2025-01-20T22:28:31Z
dc.date.issued2025-01-16
dc.description.abstractThe 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.
dc.identifier.citationKim, B. (2025). Clustering-based improved ant colony optimization for the multi-trip vehicle routing problem with heterogeneous fleet and time windows: an industrial case study (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.
dc.identifier.urihttps://hdl.handle.net/1880/120513
dc.language.isoen
dc.publisher.facultyGraduate Studies
dc.publisher.institutionUniversity of Calgary
dc.rightsUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
dc.subjectVehicle Routing Problem (VRP)
dc.subjectWorkload Balance
dc.subjectAnt Colony Optimization (ACO)
dc.subjectDBSCAN-Plus
dc.subjectMicro-Clustering
dc.subjectRoute Optimization
dc.subjectGeographic Information System (GIS)
dc.subjectQuantum GIS (QGIS)
dc.subject.classificationArtificial Intelligence
dc.subject.classificationEngineering--Industrial
dc.subject.classificationEngineering--Operations Research
dc.subject.classificationGeotechnology
dc.titleClustering-Based Improved Ant Colony Optimization for the Multi-Trip Vehicle Routing Problem with Heterogeneous Fleet and Time Windows: An Industrial Case Study
dc.typemaster thesis
thesis.degree.disciplineEngineering – Geomatics
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameMaster of Science (MSc)
ucalgary.thesis.accesssetbystudentI do not require a thesis withhold – my thesis will have open access and can be viewed and downloaded publicly as soon as possible.
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ucalgary_2025_kim_beomsaeshawn.pdf
Size:
13.1 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.62 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Open Theses and Dissertations