Language selection

Government of Canada / Gouvernement du Canada

Search

Clustering-based enhanced ant colony optimization for multi-trip vehicle routing problem with heterogeneous fleet and time windows: an industrial case study

From National Research Council Canada

Download
  1. (PDF, 1.0 MiB)
DOIResolve DOI: https://doi.org/10.1145/3681772.3698216
AuthorSearch for: ORCID identifier: https://orcid.org/0009-0004-6419-1544; Search for: ORCID identifier: https://orcid.org/0000-0002-9938-3560; Search for: 1ORCID identifier: https://orcid.org/0000-0002-2320-954X; Search for: 1ORCID identifier: https://orcid.org/0000-0001-7870-9448; Search for: ORCID identifier: https://orcid.org/0000-0003-3569-2126
Affiliation
  1. National Research Council of Canada. Digital Technologies
FunderSearch for: National Research Council of Canada
FormatText, Article
ConferenceSIGSPATIAL '24: The 32nd ACM International Conference on Advances in Geographic Information Systems, October 29 - November 1, 2024, Atlanta, Georgia, United States
Subjectvehicle routing problem; workload balance; ant colony optimization; DBSCAN+; micro-clustering; route optimization
Abstract
This paper introduces a novel approach to solving a practical variant of the Vehicle Routing Problem (VRP), the multi-trip VRP with heterogeneous fleet and time windows (MTVRPHFTW). The approach integrates an improved Ant Colony Optimization (IACO) metaheuristic, a modified density-based spatial clustering of application with noise (DBSCAN-Plus) clustering, and a Micro-Cluster Fusion Scheme. The proposed framework aims to optimize vehicle routes by minimizing total travelling distance and time while ensuring a fair distribution of workload among the vehicles (drivers). To evaluate the proposed algorithm, referred to as the Ant Colony Optimization (ACO) algorithm with improvement mechanisms (Cluster Improved Ant Colony Optimization, CIACO), real-world data from a logistics company in Canada was utilized. This empirical testing aims to validate the algorithm’s effectiveness in practical applications. The experimental results of CIACO demonstrate that the proposed algorithm outperforms existing methods in terms of reducing traveling distance, minimizing traveling time, optimizing the use of smaller vehicles to reduce CO2 emissions, achieving balanced workloads among drivers, and improving overall route optimization.
Publication date
PublisherACM
In
  • Proceedings of the 17th ACM SIGSPATIAL International Workshop on Computational Transportation Science GenAI and Smart Mobility Session (28 January 2025): 46–55. .
LanguageEnglish
Peer reviewedYes
Export citationExport as RIS
Report a correctionReport a correction (opens in a new tab)
Record identifier6c1a803a-ac77-4602-aa90-9cbe3890b939
Record created2025-02-03
Record modified2025-02-05
Date modified: