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

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Article number108383
JournalComputers and Industrial Engineering
Volume171
DOIs
StatePublished - Sep 2022
Externally publishedYes

Keywords

  • Close-enough traveling salesman problem
  • Maximum Entropy Principle
  • Statistical physics
  • Unified heuristics
  • VRP

ASJC Scopus subject areas

  • General Computer Science
  • General Engineering

Fingerprint

Dive into the research topics of 'A unified Maximum Entropy Principle approach for a large class of routing problems'. Together they form a unique fingerprint.

Cite this