BO2L: Two-Layer Bayesian Optimization for Geographical Traveling Salesman Problem

Abstract

Sustainable transportation is a critical concern in today’s rapidly urbanizing world, where optimizing logistics can significantly reduce carbon footprints and enhance operational efficiency. The Traveling Salesman Problem (TSP), particularly with time-dependent constraints, poses considerable challenges in achieving these goals due to costly API response times and complex distance matrices. This paper introduces BO2L (Two-Layer Bayesian Optimization), a novel algorithm designed to optimize delivery routes effectively while incorporating real-time traffic data. BO2L operates by alternating between a continuous vector space of latitude-longitude and a permutation space of delivery order, facilitating a more dynamic response to varying traffic conditions. We validate its effectiveness by comparing BO2L with existing methods, including Combinatorial Efficient Global Optimization (CEGO), Genetic Algorithm (GA), and Random Search (RS), on both synthetic TSP instances and a real-world delivery problem in Bangkok. Our findings reveal that BO2L consistently outperforms these alternatives, particularly under light to moderate traffic conditions. This work not only showcases the potential of Bayesian Optimization for tackling complex TSP challenges but also emphasizes the importance of integrating sustainability into logistical decision-making, paving the way for future research in efficient and environmentally responsible transportation systems.