A unified Maximum Entropy Principle approach for a large class of routing problems. (September 2022)

• Record Type: Journal Article
• Authors: Baranwal, Mayank; Marla, Lavanya; Beck, Carolyn; Salapaka, Srinivasa M.
• Is Part Of: Computers & industrial engineering. Volume 171(2022)
• Publication Date: 2022-09
• Subjects: VRP -- Close-enough traveling salesman problem -- Unified heuristics -- Statistical physics -- Maximum Entropy Principle; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108383
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: We present a novel Maximum Entropy Principle (MEP)-based modeling and algorithmic approach, for a large class of routing and scheduling problems including the Capacitated Vehicle Routing Problem (CVRP), the Vehicle Routing Problem with soft time-windows (VRPTW) and the Close-Enough Traveling Salesman Problem (CETSP). The MEP models routing and scheduling as 'equivalent' partitioning or clustering problems with side-constraints, and employs tools from statistical physics for assigning resources (routes/vehicles) to each node such that the resource allocation results in feasible, sub-optimal routes. The MEP can flexibly incorporate side-constraints related to minimum tour-lengths, capacities, schedules and reachability (like CETSP). Analytically, our model results in a second-order non-linear system of complex implicit equations. We show that an iterative approach effectively solves these equations, is equivalent to a gradient descent and converges to a local minimum. Despite the non-linear optimization model, the algorithm converges to an integer optimal solution. Computationally, we compare our approach to Simulated Annealing (SA), the CMT-14 benchmarks for VRP and benchmarks for CETSP. Our approach consistently outperforms SA for multiple variants of routing problems, specifically, the CVRP, VRPTW and CETSP. On the CMT-14 benchmark instances, our approach finds the optimal (when verifiable) number of vehicles, with a cumulative tour distance within 6.2% on average, and in comparable computation times of the best-known solutions (over all approaches for each instance). We also demonstrate the efficacy of our approach on benchmark instances of the CETSP and discuss our results. This demonstrates the potential of our MEP approach to be further embedded into hybridization heuristics for further improved results. Highlights: We introduce a Maximum Entropy Principle-based method for broad routing problems. We improve algorithmically upon existing Elastic Net-type approaches. Our new algorithmic advances are due to principled ways to tune hyperparameters. We prove that our approach is a form of gradient descent and is efficient. We present computational results on benchmark instances and real-world instances.