Constrained parallel tempering in traveling-salesman problems with circular neighborhoods

This paper is a contribution to the Physical Review Applied collection titledPhysics-Inspired Computing. Combinatorial optimization problems such as the traveling-salesman problem (TSP) are central to many applications ranging from physics to mechanical engineering, such as toolpath planning, robotic navigation, and drone routing. In this work, we propose the concept of constrained parallel tempering (CPT), an energy-minimization algorithm implemented on probabilistic Ising machines (PIMs) with probabilistic bits (p-bits) tailored for constrained problems. CPT separates the constraint and target components of the encoding into distinct energy terms with independent sampling temperatures, improving convergence and reducing computational overhead compared with traditional parallel tempering. We demonstrate the effectiveness of CPT on a benchmark of a TSP instance and extend the method to a more general formulation, the TSP with circular neighborhoods (TSPCNs), where each node is defined as a region, not a point. This model reflects real-world flexibility in robotic and drone-based applications. A hybrid deterministic–Monte Carlo refinement is then used to handle the continuous solution space of TSPCNs. Additionally, we present a hardware-friendly approach to generate Gaussian-distributed random numbers using a PIM with p-bits. Our results suggest that CPT-PIM frameworks offer an approach with better scalability and potentially low-power implementation for embedding intelligent decision-making into edge computing applications.