A carbon aware ant colony system for the sustainable generalized traveling salesman problem

According to the United States Environmental Protection Agency, transportation accounts for 28% of total U.S. emissions which is 8 billion tons of carbon dioxide, making it the largest contributor to the nation's greenhouse gas emissions. In an era where sustainability is becoming increasingly crucial, we introduce a novel Carbon-Aware Ant Colony System (CAACS) Algorithm that addresses the Generalized Traveling Salesman Problem while minimizing carbon emissions. We mathematically formulated the sustainable GTSP and developed an innovative approach that leverages the natural efficiency of ant colony pheromone trails to optimize routes, balancing both environmental and economic objectives. We discover new pathways achieving greater improvements in carbon emissions compared to the tradeoff in cost. Through our research, we developed several key concepts and correlations, including: a generalizable carbon emission heuristic that is adaptable to other carbon sources, the correlation that more ants improve solution quality and reduce runtime up to a threshold, and empirical proof of linear time complexity. The CAACS Algorithm identifies routes with carbon emissions less than or equal to the expected amount for 98% of instances in the benchmark datasets and in UPS Package Delivery we found a 0.02 % decrease in cost and 1.07 % decrease in carbon which can scale to millions of tons of carbon dioxide conserved in transportation. To the best of our knowledge, this is the first sustainable algorithm developed for the GTSP since the problem's introduction in 1969. By integrating sustainability into transportation models, the CAACS Algorithm is a powerful tool for real-world applications, including network design, delivery route planning, and commercial aircraft logistics. Our algorithm's unique bi-objective optimization represents a significant advancement in sustainable transportation solutions strategically balancing cost and carbon emissions to reduce energy consumption and promote environmental responsibility.