A unified Maximum Entropy Principle approach for a large class of routing problems

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.