travelling salesman problem research paper

A comparative study of Travelling Salesman Problem and solution using different algorithm design techniques

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

• View all journals
• My Account Login
• Explore content
• About the journal
• Publish with us
• Sign up for alerts
• Open access
• Published: 24 April 2024

Energy-efficient superparamagnetic Ising machine and its application to traveling salesman problems

• Jia Si   ORCID: orcid.org/0000-0003-0737-4905 1 , 2 ,
• Shuhan Yang 1 ,
• Yunuo Cen 1 ,
• Jiaer Chen 1 ,
• Yingna Huang 1 ,
• Zhaoyang Yao 1 ,
• Dong-Jun Kim 1 ,
• Kaiming Cai 1 ,
• Jerald Yoo   ORCID: orcid.org/0000-0002-3150-1727 1 ,
• Xuanyao Fong   ORCID: orcid.org/0000-0001-5939-7389 1 &
• Hyunsoo Yang   ORCID: orcid.org/0000-0003-0907-2898 1  

Nature Communications volume  15 , Article number:  3457 ( 2024 ) Cite this article

1724 Accesses

4 Altmetric

Metrics details

• Electrical and electronic engineering
• Magnetic devices

The growth of artificial intelligence leads to a computational burden in solving non-deterministic polynomial-time (NP)-hard problems. The Ising computer, which aims to solve NP-hard problems faces challenges such as high power consumption and limited scalability. Here, we experimentally present an Ising annealing computer based on 80 superparamagnetic tunnel junctions (SMTJs) with all-to-all connections, which solves a 70-city traveling salesman problem (TSP, 4761-node Ising problem). By taking advantage of the intrinsic randomness of SMTJs, implementing global annealing scheme, and using efficient algorithm, our SMTJ-based Ising annealer outperforms other Ising schemes in terms of power consumption and energy efficiency. Additionally, our approach provides a promising way to solve complex problems with limited hardware resources. Moreover, we propose a cross-bar array architecture for scalable integration using conventional magnetic random-access memories. Our results demonstrate that the SMTJ-based Ising computer with high energy efficiency, speed, and scalability is a strong candidate for future unconventional computing schemes.

Similar content being viewed by others

Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar

Combinatorial optimization by weight annealing in memristive hopfield networks

Ferroelectric compute-in-memory annealer for combinatorial optimization problems

Introduction.

The demands for future data-intensive and energy-efficient computing tasks overwhelm the computational power of conventional von Neumann architectures 1 . For example, NP-hard problems are often encountered in combinatorial optimizations 2 , resource allocation 3 , cryptography 4 , finance 5 , image processing 6 , tour planning 7 , and job sequencing 8 , and their computational time and hardware resources increase exponentially with the problem size, which makes them very difficult or impossible to be solved by conventional computers in a finite time. These problems can be mapped to the Ising model, a mathematical model to characterize interactions between magnetic spins 9 . The dynamics of the model is algorithm- based, i.e. by constructing a proper coupling matrix and allowing the system to evolve utilizing an intrinsic convergence property of the Ising model, the ground state could be obtained as a solution to the corresponding problems. However, as the system might be trapped in many local minima, the annealing process has usually been adopted in Ising computers to address such limitations. It is commonly agreed that adding fluctuations prevents the Ising computer from being stuck at the local minima.

Efficient algorithms and hardware systems for finding an optimal or near-optimal solution of an Ising model at a fast speed and low power have been sought. Adiabatic quantum computing (AQC) 10 , 11 and quantum computing 12 , 13 , 14 , 15 based on superconducting qubits are capable of converging the Ising model by tunneling out of local minima to the global minima. A 100-node Maxcut problem was solved using a quantum computer of 2048 spins with huge power consumption 16 . Besides the high cost and complexity of cryogenic temperature, this proof-of-concept system was limited by the sparse connections only between the nearest neighbors, which leads to sub-optimal outcomes 17 . Simulated annealing based on CMOS implementations was exploited for parallel Ising computing, including central processing units (CPU) 18 , 19 , graphics processing units (GPU) 20 , and field-programmable gate array (FPGA) 21 , 22 . These hardware have reported as large as 16,384 spins, however, it requires huge hardware resources for generating random numbers to introduce stochasticity to escape from the local minima 4 , 18 , 23 , 24 . Coherent Ising machine (CIM) is an optical scheme with competitive energy efficiency. However, it requires a long fiber ring cavity and relies on external FPGA for implementing coupling 25 , 26 . The temporal multiplexing process is also time-consuming and hard to expand to large systems. Recently, experiments and simulation works have investigated various devices to emulate the behavior of Ising spins by taking advantage of their intrinsic physics. An 8-spin asynchronous probabilistic computer based on superparamagnetic tunnel junctions for solving integer factorization tasks of values up to 945 was demonstrated 4 . SPICE simulations of 16-city TSP using simulated annealing method were presented 27 . Other works such as 8-spin phase-transition nano-oscillators 28 , multiferroic oxide devices with a high thermal stability 29 , and magnetoresistive random access memory (MRAM) 30 , 31 have also conceptually proved that spin-based devices are suitable for representing Ising units. However, these works have encountered challenges in either partially-connected Ising spins or small scalability which limit the Ising computer from solving practical problems.

TSP discussed in this paper is a well-known problem which is much beyond the limitation of locally connected Ising models. Other combinatorial optimization problems, such as knapsack problems, coloring problems, and number partitioning, need all-to-all connection to satisfy specific constraints 9 . In practice, an additional graph embedding process is often required when mapping to 2-dimensional CMOS circuitry which only considered the coupling between adjacent spins 32 , 33 , 34 . Since the embedding increases the required number of auxiliary spins and causes spin connections to change, the annealing accuracy is degraded significantly, especially when the problem size is large. This means that supporting a fully connected Ising model is highly recommended for dealing with a wide range of problems. Another problem is the rapidly increasing connectivity when considering large-scale systems, which usually results in huge energy consumption and latency. Since the number of spins that a particular annealing processor can handle limit the scale of the problem that can be solved, how to solve complex problems with limited hardware in an energy-efficient way has also drawn significant attention.

In this work, we experimentally report a scalable Ising computer based on 80 SMTJs with all-to-all connections and successfully solve the 4761-node TSP problem. The intrinsic stochasticity in SMTJ enables ultra-fast and low-power Ising annealing without using extra resources for random number generation and Metropolis determining process 7 . By combining global annealing with intrinsic annealing in SMTJ, the convergence of the Ising problem is guaranteed especially in large-scale Ising problems. The method to determine parameters of global annealing is discussed. With an all-to-all connection among Ising spins, the combinatorial optimization of 9-city TSP is solved with the optimal solution. We further develop the algorithm for constrained TSP (CTSP) with no extra auxiliary Ising bits both in algorithm and hardware, indicating the superiority and flexibility of this Ising computer. Furthermore, we propose an optimization strategy based on graph partitioning (GP) and CTSP and experimentally solved a 70-city TSP, which typically needs 4761 nodes, on our 80-node Ising computer with a near-optimal solution. The system can obtain the lowest power consumption of 0.64 mW as well as high energy efficiency of 39 solutions per second per watt among state-of-art Ising annealers. We have experimentally demonstrated that large-scale Ising problems can be solved by small-scale hardware in an energy-efficient way.

SMTJ-based artificial Ising spin

Various NP-hard problems can be solved by constructing corresponding Ising models and observing the ground states during evolution processes. Figure  1a shows an all-to-all connected Ising model, whose Ising Hamiltonian can be written as

where \(H\) is the total energy of the system, \(N\) is the total number of spins, \({s}_{i}\) is the \(\,i\) -th spin with one of two states; “+1” (Ising spin up) or “−1” (Ising spin down), \({J}_{i,j}\) is the coefficient of coupling between the \(i\) -th and the \(j\) -th spins, and \({h}_{i}\) is the external field of the \(\,i\) -th spin. For a fixed configuration of other spins than \({s}_{k}\) , the probability of \({s}_{k}\) staying in the down-state is given by

where \(\Lambda=\frac{\partial H}{\partial {s}_{k}}\) (see Supplementary Note  1 ).

a All-to-all connected 12-spin Ising model with s represents the spin and J 1,6 represents the coupling between s1 and s6. b Sigmoidal fit of probability of AP state ( \({p}_{{AP}}\) ) of an SMTJ under different input currents ( I ). \({p}_{{{{{{\rm{AP}}}}}}}=\frac{1}{1+{e}^{-4.672\times (I-3.905{{{{{\rm{\mu }}}}}}{{{{{\rm{A}}}}}})}}\) . Inset: diagram of an SMTJ. A tunneling barrier layer is sandwiched by a reference layer and a free layer. c Time-dependent resistance of an SMTJ under different input currents ( I ). d Photograph and schematic diagram of SMTJ-based Ising computer. The system contains 8 processing elements (PEs), 4 digital-to-analog converters (DACs), a comparator array, a multiplexer and a microcontroller unit (MCU). Each PE has 10 SMTJ computing units. Each computing unit includes a transistor and a resistor to adjust the property into stochastic. Blue lines and orange arrows represent the control and data flow, respectively.

One natural implementation of this Ising spin is based on a stochastic nanomagnet. The inset of Fig.  1b shows the sketch of an SMTJ, consisting of a tunneling barrier sandwiched by a reference layer and a free layer (see Methods section). Because of the small device diameter (~50 nm), the energy barrier of the free layer between the anti-parallel (AP) and parallel (P) states is low that the retention time of either state is in the range of μs to ms, similar to previous studies 4 , 35 . The SMTJ resistance, measured as a function of time in Fig.  1c , shows preferred AP states at high currents and P states at low currents. When the current ( I ) is ~4 μA, SMTJ shows an equal chance of AP and P states. The probability of the AP state under different input currents over 0.1 s is fitted in Fig.  1b by a sigmoid function:

where \({{{{{\rm{a}}}}}}=4.67 \, {{{{{\rm{and\; b}}}}}}=3.9 \, {{{{{\rm{\mu }}}}}}{{{{{\rm{A}}}}}}.\) In order to emulate Ising spin \({s}_{k}\) with our SMTJ device, we only need to make the probability of the down-state of \({s}_{k}\) to be equal to that for the AP state of SMTJ, namely \({p}{\_}{{{{{{\rm{\_}}}}}}{{{{{\rm{AP}}}}}}}={p}{\_}{{{{{{\rm{\_}}}}}}\downarrow }\) , with two calibration coefficients. Thus, we can derive the form of the current \({{I\_}}_{k}\) injected to SMTJ as (see Supplementary Note  1 ):

where \(c=1/{kT}\) is the effective inverse temperature which can be conducted for global annealing.

Intrinsic annealing in SMTJs-based Ising computer

By integrating 80 SMTJs with a peripheral circuit and a microcontroller unit (MCU), we build an 80-node Ising computer (see Supplementary Note  2 ). Each Ising spin in Eq. ( 1 ) is emulated by an SMTJ with intrinsic randomness, where P (AP) state represents spin-up (down). Figure  1d shows the photograph of the printed circuit board (PCB) and the diagram of the system (see Methods section). The system contains 8 processing elements (PEs); each PE has 10 SMTJ computing units. Each SMTJ computing unit includes a transistor and a resistor to adjust the state of SMTJ into stochastic. During the computing process, an MCU examines the states of all SMTJs by reading the output of comparator arrays through multiplexers and generates new input voltages for digital-to-analog converters (DACs) according to the updating rule in Eq. ( 4 ) (see Supplementary Note  3 for calibration of 80 SMTJ computing units).

During the evolution process, an Ising solver could be easily trapped in a local minimum state. To avoid this non-optimal solution, annealing algorithms such as simulated annealing (SA) or quantum annealing (QA) were developed. The general idea of SA is to make the system evolve from a high temperature to a low temperature gradually 7 . The convergence and relaxation of SA can be mathematically provable 36 . During each iteration, a random number is generated for stochasticity and introduced to determine whether the result in this iteration should be accepted or not. In QA, quantum fluctuations cause quantum tunneling between states 17 . In both SA and QA, stochasticity needs to be introduced into the annealing process. In contrast, our Ising system utilizes the intrinsic stochastic behaviors of SMTJ to perform the Metropolis process of standard SA in hardware, which greatly saves the solution time and hardware resources for generating randomness (see Supplementary Note  4 ). Besides, our Ising computer has an all-to-all connection which has wider application scenarios, as well as a better capability of escaping from local minima.

Ising mapping of N-city TSP and CTSP

We have applied our Ising computer to the TSP problem, one of the combinatorial optimization problems, which applies to various sectors, such as vehicle routing, logistics, planning, and scheduling. The goal is to find the shortest route that visits all listed cities once and only once given distances between the cities in the list. In order to solve this problem, we first map N -city-TSP to an \({N}^{2}\) -spin Ising model, or \({(N-1)}^{2}\) -spin model assuming a fixed starting city. Figure  2a shows the coordinates of 9 cities and Fig.  2b shows the 81-spin Ising model, whose rows indicate the cities and columns indicate the visiting order. We define the binary spin, s , as \({s}_{i,j}\)  = 1 if city i is visited as j -th city or \({s}_{i,j}\)  = −1 otherwise. The total Hamiltonian of TSP is expressed by 9

where the first term is a constraint that represents only one city is visited at the j -th visit, and the second term represents one city is visited only one time. \(w\) is a constant small enough ( \(0 \, < \, w \, < \, 1\) ) not to violate the two constraints of the TSP cycle. \({d}_{i,{i{{\hbox{'}}}}}\) is the distance between city \(i\) and city \({i{{\hbox{'}}}}\) . According to Eqs. ( 1 ) and ( 5 ), coupling matrix \(J\) of 81 spins could be obtained, as shown in Fig.  2c (see Supplementary Note  5 ). It shows that spins in the same row or column have strong coupling, as indicated by the first two terms in Eq. ( 5 ).

a Coordinates of all 9 cities used in this problem which are the first 9 cities in the dataset Burma14 from TSPLIB. b Ising spin representation for 9-city TSP (81 spins). Rows indicate names of cities and columns indicate the visiting order. Each spin can be 1 (visited) or −1 (not visited) in each iteration. c Color map of the coupling matrix J TSP of 9-city TSP, and the color bar represents an effective energy with the unit of kT . Here, k is the Boltzmann constant and T is the temperature. d Constrained TSP (CTSP) with a fixed vising sequence from city 2 to city 7 or from city 7 to city 2. The arrows represent the visiting sequence. e The Ising spin representation for CTSP with the fixed visiting sequence in d . Arrows represent possible vising sequences. f Color map of the difference of coupling matrix between TSP (J TSP ) in a and CTSP (J CTSP ) in d . Arrows represent the fixed vising sequences from city 2 to city 7 or from city 7 to 2.

We define CTSP as the visiting orders of some cities are enforced during the traveling. This is quite useful in real-life scenarios. For example, a delivery man collects food and drinks at shop A and must deliver hot drinks to B first even though the total cost is higher than optimal. We propose an algorithm for solving CTSP by adding negative “distance” to the Hamiltonian. For example, suppose that city A and city B are required to be connected in the CTSP as city 2 and city 7 shown in Fig.  2d , and then we add the term

such that the energy of a path, where city A and city B are connected, is always lowered by \(\theta .\) When \(\theta\) is sufficiently large, the optimal path must have city 2 and city 7 connected. Thus, the total Hamiltonian of the CTSP is expressed by

Constructing an Ising model for CTSP is exactly the same as TSP except for extra allowed visiting sequences, as shown in Fig.  2e . This would lead to a modification of the coupling matrix of \(J\) according to Eq. ( 7 ) (see the deduction of \({J}_{{CTSP}}\) in Supplementary Note  6 ). From Fig.  2f we can clearly see the differences between \({J}_{{CTSP}}\) and \({J}_{{TSP}}\) . This algorithm of CTSP fits for arbitrary constraints of visiting sequences as well as their combinations.

Experimental demonstration of 9-city TSP

We first run a 9-city TSP in the 80 SMTJ-based Ising computer at a relatively low but non-zero effective temperature to examine the intrinsic annealing in SMTJ. The iteration time is set comparable to the longest retention time of SMTJs to avoid reading previous spin states. In our experiments, we set the iteration time as 0.1 ms. As shown in Fig.  3a , as the effective inverse temperature ( c ) is increased quickly to 0.5, the system converges rapidly to a low energy state within 50 iterations and reaches the ground state after 4000 iterations. It should be noted that the intrinsic stochasticity in SMTJs helps the system escape from local minima without an extra annealing process, as shown in the right inset of Fig.  3a . Figure  3b illustrates the evolution of 9 spins out of 81 spins. The evolution of all 81 spins can be found in Supplementary Note  7 .

a Total energy transition of 9-city TSP with 5000 iterations (the optimal solution with the energy of 18.23 corresponds to the dashed horizontal line). Insets: effective inverse temperature ( c ) and total energy within 3500–4500 iterations. b Evolution of 9 representative SMTJ states in 5000 iterations. An offset is used in the y -axis to show each SMTJ clearly. c Visiting routes of state A, B, C, and D in a . d Corresponding Ising spins of state A, B, C, and D in a . The yellow squares represent ‘visited ( \({s}_{i,j}=1\) )’ and the purple squares represent ‘not visited ( \({s}_{i,j}=-1\) )’. e Total energy transition with increasing c from 0.2 to 1.8. Left inset: zoom-in view of total energy transition with increasing c from 0.392 to 0.52. Right inset: transition of c with iterations. The red dashed line represents the optimal path (success). f Success probability of solving TSP with varying the node size. The data points and shadows represent the median value and the interquartile range (IQR), respectively.

We choose four states in Fig.  3a to inspect the traveling path in Fig.  3c and their Ising spins, namely \({s}_{i,j}\) , as shown in Fig.  3d . The yellow square in Fig.  3d represents \({s}_{i,j}=1\) (visited) and the blue square represents \({s}_{i,j}=-1\) (not visited). In an initial state A, the spin states are randomly set and then converge to a relatively low energy at state B. State C is an intermediate solution during the annealing process. State D is the optimal solution satisfying two constraints of the TSP. Because we anneal the system to a relatively low but non-zero temperature so that the convergence to a sub-optimal state could be guaranteed, and at the same time, the intrinsic randomness in SMTJ helps the system to escape from local minima and find a ground state quickly. We test 10 different random initial states each with 5000 iterations and find that in all cases the system can obtain a relatively small energy, as shown in Supplementary Note  8 . However, there is a probability that the system jumps out of the ground state because of the non-zero temperature. If we continue to observe the evolution in a large timescale, the system would move back to the global minimum state. In some cases, where the speed and near-optimal solution matter but the accurate optimal solution is not, the number of iterations can be chosen to be small.

Further global annealing of the system to a lower effective temperature may guarantee the convergence of the computation. Here we use linear annealing as an example to examine the convergence of this algorithm in a very large-iteration limit. The initial temperature should be chosen sufficiently high to ensure that the thermal energy exceeds any energy barrier ( \(\Delta H{=H}_{\max }-{H}_{\min }\) ) within the system, while still adhering to the fundamental constraints of the specific Ising model. For a given N-city TSP, \({H}_{\max }\) in Eq. ( 5 ) can be estimated as \(w\times N\times \bar{d}\) , assuming that the distance between any two cities is the same as the average distance \(\bar{d}\) . Similarly, \({H}_{\min }\) can be estimated as \(w\times N\times {d}_{\min }\) . Therefore, the initial \(c\) of 9-city TSP in our experiment can be estimated as \({c}_{{{{{{\rm{initial}}}}}}}\, \sim 1/\Delta H=0.07\) , where \(w=0.5\) , \(N=9\) for a total of 9 cities, \(\bar{d}=4\) and \({d}_{\min }=0.8\) for the average and shortest distance of each two cities, respectively in Fig.  3c . We then choose \({c}_{{{{{{\rm{initial}}}}}}}\)  = 0.2 which is sufficiently safe for annealing. As the temperature linearly decreases, the dynamical system gradually stabilizes. The final temperature should be low enough i.e., \({c}_{{{{{{\rm{final}}}}}}} \, \gg \, 1/\Delta H\) , to freeze all possible fluctuations. Here we set \({c}_{{{{{{\rm{final}}}}}}}=1.8\) which is at least one order larger than \(1/\Delta H\) . This can also be verified by observing randomly generated states under \({c}_{{{{{{\rm{final}}}}}}}\) for long iterations. Regarding the annealing speed, if several changes in the spin configuration are observed under each value of c , then this annealing speed is valid. Plenty trials are required to find the proper annealing speed (details in Supplementary Note  8 ).

In Fig.  3e we can find the first global minimum energy appears after 16,500 iterations, and converge to the ground state after 40,000 iterations. Temperature schedules can be optimized to reduce iteration numbers, e.g. increase the effective temperature in the first few time steps, and then decrease gradually, or learned by the reinforcement learning method 37 . In practice, we use one memory to store the minimum energy state during the computation, and another memory to record the final energy state. We take the minimum value of these two results as the solution. Figure  3f shows the success probability (defined as finding the optimal path) of TSP with various node sizes. The success probability of 9-city TSP reaches 95% after 10 4 iterations. The success probability with the parameter \(w\) in Eq. ( 5 ) which determines the relative strength of the constrain term and distance term is also discussed. If the \(w\) is too large, then the probabilities of violations, namely the invalid path, would increase, as shown in Supplementary Note  8 . If \(w\) is too small, then the effect of the distance term is small, which results in a slower convergence to the ground state.

The advantages of this annealer are threefold: (1) Selective working modes by using different temperature schemes. One is the probabilistic sampling mode working at a constant temperature, which is similar to an asynchronous probabilistic computer 4 ; the other is the annealing mode conducted by reducing the effective temperature. (2) Fast speed and low power consumption to find the ground state because of the intrinsic annealing properties in SMTJ. (3) Global annealing outperforms probabilistic sampling in achieving efficient convergence, especially for large-scale problems.

We have implemented a synchronous design with a lower requirement on the speed of peripheral circuits. This design also effectively mitigates issues such as leakage, sneak currents, and parasitic resistances which might encountered in asynchronous hardware with a memristive (or resistive) crossbar array.

Compressing 70-city TSP to 80-node Ising computer

Generally, the number of spins required for an N -city TSP is ( N -1) 2 , which limits the scalability of TSP on state-of-the-art computing systems. Here, we propose a graph Ising compressing algorithm based on CTSP that can significantly reduce the number of spins and interactions for solving a TSP. Figure  4a is an example of how we apply this algorithm to our 80-node SMTJ Ising computer for solving a 70-city TSP (4761 nodes, st70 data set from TSPLIB 38 ). The major steps of this algorithm can be described as follows: (a) divide the cities into several smaller groups until the number of cities in each group is less than 10 by GP method; (b) solve TSP within each group separately; (c) integrate neighboring groups to obtain an initial path of the whole group; and (d) optimize the path in (c) by a CTSP window sliding over the whole map.

a Optimization algorithm for 70-city TSP. b Number of required SMTJs for various problems using different methods. Burma14, berlin52, eil76, and eil101 are TSP of 14, 52, 76, and 101 cities, respectively. c Comparison of total Ising energy (path) and total clock cycles for final solution with different SA-based algorithms, including symbiotic organisms search 40 , ant colony optimazation 41 , multi-offspring genetic algorithm 42 , and gene-expression programming 7 . Our method is tested on our Ising system and others are tested on Intel Core-i7 PC. In this comparison, our system runs at a main frequency of 10 kHz.

It is worth mentioning that GP is also an Ising problem. When converting a global TSP into local TSPs, using GP would be more hardware-friendly for our Ising computer compared to other clustering algorithms. It is based on the idea that the original graph can be separated into multiple sub-graphs depending on the Euclidean distance. The number of spins required for solving GP is ~ N and thus, GP is quite efficient for local TSPs since the problem size can be reduced to ~ \({\left(N-1\right)}^{2}/a\) , where \(a\) is the number of groups, and each TSP can be optimized independently (see GP mapping in Supplementary Note  9 ).

The final step (d) is based on CTSP, where a rectangular window slides over the path and cuts it into several disconnected lines, among which the two longest lines are chosen and the edge cities are connected as a circular path (Supplementary Note  10 ). The CTSP is solved within each window for sub-area optimization without changing the visiting order of edge cities. After this, the two lines at the edge cities are opened and CTSP is carried out again after sliding to the next window. GP-CTSP-based optimization algorithm provides an efficient way of finding near-optimal solutions for large-scale TSP on limited hardware resources.

Figure  4b shows the comparison of numbers of spins for different TSPs by a conventional Ising method 9 , cluster Ising method 39 , and our method. The required number of spins in our method is relatively unchanged for various TSPs, while that of other methods increases substantially with the scale of the problem. Figure  4c shows the total path of 70-city TSP as a function of iteration number using different SA-based algorithms, including symbiotic organisms search 40 , ant colony optimization 41 , multi-offspring genetic algorithm 42 , and gene-expression programming 7 . Finally, we obtain the near-optimal path with a total energy of 700.71, which is slightly higher than the optimal solution of 675. However, the iteration number for an optimized solution is 4.9 \(\times\) 10 6 by our method, which is two to three orders lower than that of SA-based algorithms running on Intel Core-i7 CPU 7 with the main frequency of 3 GHz, as shown in Fig.  4c .

Ising computer scaling and cross-bar architecture

The above experimental demonstration shows our Ising computer with 80 SMTJs is capable of finding a near-optimal solution to a medium-scale NP-hard problem. We then explore the performance with increasing from 70 to 200 cities. The simulation of complete TSP task is carried out using MATLAB, incorporating a stochastic model of the SMTJ employed in our experiment (details in Supplementary Note  11 ). The solution quality is defined as

Figure  5a illustrates the solution quality of the best results obtained for each TSP task (Supplementary Note  12 for the best solutions). Notably, as the number of SMTJ (M) increases, higher quality solutions can be attained. It is worth emphasizing that the shortest path obtained for the 101-city TSP is 640.9755 in our study, surpassing the optimal path of 642.3095 provided by TSPLIB (Eil101.opt.tour). This outcome serves as evidence of the superiority of our method. The utilization of more SMTJs solving TSP per sliding window leads to improved optimization of CTSP annealing, resulting in an enhanced solution quality, as depicted in Fig.  5b . Consequently, the time to convergence s would also increase with the use of more SMTJS. When dealing with a fixed hardware capacity, an appropriate number of SMTJs for CTSP optimization can be assigned, taking into account both the solution quality and convergence speed. Figure  5c showcases the success rate (defined as achieving 95% solution quality) as the problem size increases. The success probability of 200-city TSP, whose complexity is ~40,000 nodes, can reach as high as 90%, demonstrating the scalability of our method compared to typical TSP (without GP and CTSP) 9 .

a Solution quality of various problems using different number of SMTJs (M) in the array. The datasets used are St70, Eil101 and KroA200, for 70, 101 and 200 cities, respectively. b Total length of KroA200 TSP at different convergence speeds using different number of SMTJs. The dashed line represents the best demonstrated solution. c Success probability of different TSP algorithm (without/with GP and CTSP) as the number of cities increases after running for 50 times. A total of 512 SMTJs are used. Here we define the success as achieving the solution quality of 95%. d SMTJ cross-bar array which contains row decoder, SMTJ, select transistor and read sense amplifier (RSA). BL represents bit line, WL represents word line, Vin, Vout and Vdd represent the input voltage, output voltage and supply voltage of RSA. e Circuit of one RSA which contains a current mirror, voltage equalization circuit (VEC, with a control signal of EQ which initializes the voltages in Q and QB points, under a reference voltage of Vdd/2), voltage sense amplifier (VSA, with a control signal of SEN), reference resistance ( \({{{{{\rm{Rref}}}}}}=\frac{1}{2}({{{{{\rm{Rap}}}}}}+{{{{{\rm{Rp}}}}}})\) , Rap and Rp represent SMTJ’s resistance in AP and P state respectively), and control transistors. f Signals of writing/reading two adjacent SMTJ cells in one BL, selected by WL0 and WL1 in sequence. All signals are defined in e and f .

We also propose a cross-bar architecture for large-scale Ising computer implementation, which can be integrated by using modern MRAM and CMOS technologies. The core part of this architecture consists of SMTJ bit cells organized as a cross-bar array, integrated with row decoders and read sense amplifiers (RSA), as shown in Fig.  5d . Each SMTJ bit cell contains one select transistor and one SMTJ (1T1SMTJ), whereas the gate of the select transistor is driven by word lines (WL), and the source of all bit cells are connected to the ground. Each bit line is assigned with an RSA. The current flows through SMTJ can be continuously adjusted by Vin of RSA, and the state of SMTJ can be read by RSA at the same time. Figure  5e illustrated the circuit of RSA, in which two clamp transistors control the current flow through the bit cell path and reference path by the gate voltage (Vin), and a current mirror is used to guarantee the same current of the above two paths. Then different voltages would show in the Q and QB point when the resistance of SMTJ is higher or lower than the reference resistor (Rref). By utilizing an enabled voltage sense amplifier (VSA), the voltages at the Q and QB points are sensed, allowing the SMTJ state to be determined as either Vdd (P state) or 0 V (AP state). Particularly, a voltage equalization circuit (VEC) is designed for initializing VSA to avoid incorrect readout. Electrical coupling through a resistance change 43 is evaluated to have neglectable effects (details in Supplementary Note  11 ). Figure  5f shows the signals to control and read bit cells. In phase 0 (PH0), one row of SMTJs is selected by WL, and Vin prepared by peripheral circuit is applied to the corresponding RSA. EQ is set high to initialize Q, QB and Vout as Vdd/2. In phase 1 (PH1), the SMTJ fluctuates from the falling edge to next rising edge of EQ. Finally, in phase 2 (PH2), RSAs read the data of one row in parallel at the falling edge of SEN. After the first row has been retrieved, the partial sum starts to be computed. Meanwhile, the same process for the second row can be started, so and so forth. To avoid reading the previous state, the duration of PH1 is preferred to be comparable with the retention time of SMTJ, which limits the main frequency of the system (see details in Supplementary Note  11 ).

We compare our system with other state-of-art Ising solvers, including CMOS annealer (Intel Core i7 processor) 7 , quantum annealer (D-Wave 2000Q) 16 , 17 , CIM with FPGA 26 , memristor Hopfield neural networks (mem-HNN) 44 , and phase-transition nano-oscillators (PTNO) 28 in solving 4761-node TSP70, as shown in Table  1 . We use the experimental data for benchmarking from literature, and two kinds of SMTJs for comparison. One is our perpendicular anisotropy SMTJ device and the other is assuming recently reported in-plane anisotropy SMTJ with a retention time of 8 ns 45 , 46 . The major attributes are the main frequency (defined as 1/iteration time), power, time-to-solution as well as energy efficiency (defined as solutions per second per watt). As quantum computers, CIM, mem-HNN, and PTNO only demonstrated ~100-node max-cut problems, we estimate the time-to-solution for solving TSP70 by assuming that the algorithm and the total number of spins to find a near-optimal solution is the same as our work (details in Supplementary Note  13 ). Here, we set 80-spin Ising computer as a standard and fix the number of iterations of 400,000 for a good solution to TSP70. Only Ising computing parts are calculated for power consumption.

In Table  1 , although the main frequency of CPU is the highest among all candidates, the energy efficiency is lower than our SMTJ-based approach. This is due to the redundant logic and data transfer delay between the memory and PEs in a conventional von-Neumann architecture. The SMTJ-based approach currently outperforms the quantum annealer both in the power consumption as well as time to solution. The power of quantum annealer is huge which needs to be optimized further for real applications. CIM is another promising architecture with a fast speed and acceptable power consumption. Current CIM systems are proof-of-concept systems which are not at present optimized for energy efficiency. Mem-HNN has a relatively fast speed assuming the 180-nm CMOS technology. However, the required number of devices is large, which limits the integrated density. The PTNO approach uses capacitors or resistors to mimic spin coupling, whose main frequency would be limited by the system scale and parasitic effects. It is reported that the ideal main frequency would decrease from 500 to 87 MHz when the system scale increases from 8-node to 100-node 28 . Our SMTJ-based Ising computer outperforms other approaches with low power consumption with 0.64 mW (details in Supplementary Note  13 ).

We experimentally demonstrate perpendicular MTJs with a retention time of ~0.1 ms and solve TSP70 Ising problems at an energy efficiency of 39 solutions per second per watt. Furthermore, we simulate an Ising computer with 4 Kb SMTJs using 40 nm commercial CMOS technology. The simulated energy efficiency for solving TSP70 by using the same SMTJ can reach 68 solutions per second per watt. By using reported in-plane SMTJ 45 and advanced CMOS, the system could obtain the highest energy efficiency of \(5.4\times {10}^{3}\) , which shows several orders of magnitude improvement over other approaches. This result suggests that an SMTJ-based Ising computer can be a good candidate for solving dense Ising problems in a highly energy-efficient and fast way.

In summary, we have experimentally demonstrated an intrinsic all-to-all Ising computer based on 80 SMTJs, and solved 9-city TSP with the optimal solution. Furthermore, a compressing strategy based on CTSP and GP is proposed to experimentally solve 4761-node 70-city TSP on an 80-node system with a near-optimum solution as well as ultra-low energy consumption. A cross-bar architecture is then proposed for large-scale Ising computers and the 200 city TSP task is simulated. Our system provides a feasible solution to fast, energy-efficient, and scalable Ising computing schemes to solve NP-hard problems.

Sample growth and device fabrication

Thin film samples of substrate/[W (3)/Ru (10)] 2 /W (3)/Pt (3)/Co (0.25)/Pt (0.2)/[Co (0.25)/Pt (0.5)] 5 /Co (0.6)/Ru (0.85)/Co (0.6)/Pt (0.2)/Co (0.3)/Pt (0.2)/Co (0.5)/W (0.3)/CoFeB (0.9)/MgO (1.1)/CoFeB (1.5)/Ta (3)/Ru (7)/Ta (5) were deposited via DC (metallic layers) and RF magnetron (MgO layer) sputtering on the Si substrates with thermal oxide of 300 nm with a base pressure of less than \(2\times {10}^{-8}\) Torr at room temperature. The numbers in parentheses are thicknesses in nanometers. To fabricate the superparamagnetic tunnel junctions, bottom electrode structures with a width of 10 µm were firstly patterned via photolithography and Ar ion milling. MTJ pillar structures with a diameter of ~50 nm for the superparamagnetic behavior were patterned by using e-beam lithography. The encapsulation layer of Si 3 N 4 was in-situ deposited after ion milling without breaking vacuum by using RF magnetron sputtering, and top electrode structures with a width of 10 µm were patterned via photolithography and top electrodes of Ta (5 nm)/Cu (40 nm) were deposited by using DC magnetron sputtering.

MTJ characterization by probe station

The setup includes a source meter (Keithley 2400) for supplying DC bias currents and a data acquisition card (NI-DAQmx USB-6363) for the read operation. A single SMTJ operation cycle comprises two steps (i.e. bias and read). A small DC input current with an amplitude of 1–20 μA is applied to SMTJ. Simultaneously, the DAQ card reads the voltage signal across the SMTJ at a maximum sampling rate of 2 MHz. The MTJ switching probability varies in accordance with the amplitude of applied currents. The retention time of MTJ is determined from random telegraph noise measurements over 250 ms. The expectation values of event time τ is determined by fitting an exponential function to the experimental results.

80 SMTJ arrays and peripheral circuits are integrated on a 12 cm × 15 cm PCB, controlled by an MCU (Arduino Mega 2560 Rev3). Four 12-bit rail-to-rail DACs (AD5381) with 160 output channels in total are used to generate analog DC inputs for PE and comparator arrays. Half of the DAC output channels are used to provide stimulation to the gate terminal of NMOSs (2N7002DW-G), and others are used to provide reference voltages to comparators (AD8694). The drain voltages of NMOS are compared with reference voltages and generate outputs in parallel. Outputs of comparator arrays are read by MCU through four multiplexers (FST16233) and then are calculated to obtain new inputs for DACs. The supply voltage of the PCB board and SMTJs is 5 V and 0.8 V, respectively. The value of resistors in each computing unit can be designed to adjust the center of sigmoidal curves.

Data availability

The data generated during this study are available within the article and the  Supplementary Information file.  Source data are provided with this paper.

Code availability

The codes that support this study can be available from the corresponding author upon request.

Theis, T. N. & Wong, H. S. P. The End of Moore’s Law: A New Beginning for Information Technology. Comput. Sci. Eng. 19 , 41–50 (2017).

Article   Google Scholar  

Shim, Y., Jaiswal, A. & Roy, K. Ising computation based combinatorial optimization using spin-Hall effect (SHE) induced stochastic magnetization reversal. J. Appl. Phys. 121 , 193902 (2017).

Article   ADS   Google Scholar  

Tindell, K. W., Burns, A. & Wellings, A. J. Allocating hard real-time tasks: An NP-Hard problem made easy. J. Real.-Time Syst. 4 , 145–165 (1992).

Borders, W. A. et al. Integer factorization using stochastic magnetic tunnel junctions. Nature 573 , 390–393 (2019).

Article   ADS   CAS   PubMed   Google Scholar  

Tatsumura, K., Hidaka, R., Yamasaki, M., Sakai, Y. & Goto, H. A Currency Arbitrage Machine Based on the Simulated Bifurcation Algorithm for Ultrafast Detection of Optimal Opportunity. in 2020 IEEE International Symposium on Circuits and Systems (ISCAS) 1–5 (IEEE, 2020). https://doi.org/10.1109/ISCAS45731.2020.9181114 .

Cohen, E., Carmi, M., Heiman, R., Hadar, O. & Cohen, A. Image restoration via ising theory and automatic noise estimation. In 2013 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting (BMSB) 1–5 (IEEE, 2013). https://doi.org/10.1109/BMSB.2013.6621708 .

Zhou, A.-H. et al. Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming. Information 10 , 7 (2018).

Garza-Santisteban, F. et al. A Simulated Annealing Hyper-heuristic for Job Shop Scheduling Problems. In 2019 IEEE Congress on Evolutionary Computation (CEC) 57–64 (IEEE, 2019). https://doi.org/10.1109/CEC.2019.8790296 .

Lucas, A. Ising formulations of many NP problems. Front. Physics 2 , 5 (2014).

Albash, T. & Lidar, D. A. Adiabatic quantum computation. Rev. Mod. Phys. 90 , 015002 (2018).

Article   ADS   MathSciNet   Google Scholar  

Dickson, N. G. & Amin, M. H. S. Does Adiabatic Quantum Optimization Fail for NP-Complete Problems? Phys. Rev. Lett. 106 , 050502 (2011).

Article   ADS   PubMed   Google Scholar  

Heim, B., Ronnow, T. F., Isakov, S. V. & Troyer, M. Quantum versus classical annealing of Ising spin glasses. Science 348 , 215–217 (2015).

Article   ADS   MathSciNet   CAS   PubMed   Google Scholar  

Kadowaki, T. & Nishimori, H. Quantum annealing in the transverse Ising model. Phys. Rev. E 58 , 5355–5363 (1998).

Article   ADS   CAS   Google Scholar  

Martoňák, R., Santoro, G. E. & Tosatti, E. Quantum annealing of the traveling-salesman problem. Phys. Rev. E 70 , 057701 (2004).

Okuyama, T., Hayashi, M. & Yamaoka, M. An Ising Computer Based on Simulated Quantum Annealing by Path Integral Monte Carlo Method. In 2017 IEEE International Conference on Rebooting Computing (ICRC) 1–6 (IEEE, 2017). https://doi.org/10.1109/ICRC.2017.8123652 .

Hamerly, R. et al. Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer. Sci. Adv. 5 , eaau0823 (2019).

Article   ADS   PubMed   PubMed Central   Google Scholar  

Johnson, M. W. et al. Quantum annealing with manufactured spins. Nature 473 , 194–198 (2011).

Yamaoka, M. et al. A 20k-Spin Ising Chip to Solve Combinatorial Optimization Problems With CMOS Annealing. IEEE J. Solid State Circuits 51 , 303–309 (2016).

Yamaoka, M. et al. 24.3 20k-spin Ising chip for combinational optimization problem with CMOS annealing. In 2015 IEEE International Solid-State Circuits Conference - (ISSCC) Digest of Technical Papers 1–3 (IEEE, 2015). https://doi.org/10.1109/ISSCC.2015.7063111 .

Davendra, D., Metlicka, M. & Bialic-Davendra, M. CUDA Accelerated 2-OPT Local Search for the Traveling Salesman Problem. In Novel Trends in the Traveling Salesman Problem (eds. Davendra, D. & Bialic-Davendra, M.) (IntechOpen, 2020). https://doi.org/10.5772/intechopen.93125 .

Tatsumura, K., Dixon, A. R. & Goto, H. FPGA-Based Simulated Bifurcation Machine. In 2019 29th International Conference on Field Programmable Logic and Applications (FPL) 59–66 (IEEE, 2019). https://doi.org/10.1109/FPL.2019.00019 .

Tatsumura, K., Yamasaki, M. & Goto, H. Scaling out Ising machines using a multi-chip architecture for simulated bifurcation. Nat. Electron 4 , 208–217 (2021).

Mathew, S. K. et al. μ RNG: A 300–950 mV, 323 Gbps/W All-Digital Full-Entropy True Random Number Generator in 14 nm FinFET CMOS. IEEE J. Solid-State Circuits 51 , 1695–1704 (2016).

Pervaiz, A. Z., Sutton, B. M., Ghantasala, L. A. & Camsari, K. Y. Weighted p-Bits for FPGA Implementation of Probabilistic Circuits. IEEE Trans. Neural Netw. Learn. Syst. 30 , 1920–1926 (2019).

Article   PubMed   Google Scholar  

McMahon, P. L. et al. A fully programmable 100-spin coherent Ising machine with all-to-all connections. Science 354 , 614–617 (2016).

Inagaki, T. et al. A coherent Ising machine for 2000-node optimization problems. Science 354 , 603–606 (2016).

Sutton, B., Camsari, K. Y., Behin-Aein, B. & Datta, S. Intrinsic optimization using stochastic nanomagnets. Sci. Rep. 7 , 44370 (2017).

Dutta, S. et al. An Ising Hamiltonian solver based on coupled stochastic phase-transition nano-oscillators. Nat. Electron 4 , 502–512 (2021).

Sharmin, S., Shim, Y. & Roy, K. Magnetoelectric oxide based stochastic spin device towards solving combinatorial optimization problems. Sci. Rep. 7 , 11276 (2017).

Faria, R., Camsari, K. Y. & Datta, S. Implementing Bayesian networks with embedded stochastic MRAM. AIP Adv. 8 , 045101 (2018).

Zand, R., Camsari, K. Y., Datta, S. & DeMara, R. F. Composable Probabilistic Inference Networks Using MRAM-based Stochastic Neurons. J. Emerg. Technol. Comput. Syst. 15 , 1–22 (2019).

Choi, V. Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process 7 , 193–209 (2008).

Article   MathSciNet   Google Scholar  

Sugie, Y. et al. Minor-embedding heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes. Soft Comput 25 , 1731–1749 (2021).

Cai, J., Macready, W. G. & Roy, A. A practical heuristic for finding graph minors. Preprint at http://arxiv.org/abs/1406.2741 (2014).

Chaves-O’Flynn, G. D., Wolf, G., Sun, J. Z. & Kent, A. D. Thermal Stability of Magnetic States in Circular Thin-Film Nanomagnets with Large Perpendicular Magnetic Anisotropy. Phys. Rev. Appl. 4 , 024010 (2015).

Mitra, D., Romeo, F. & Sangiovanni-Vincentelli, A. Convergence and finite-time behavior of simulated annealing. Adv. Appl. Probab. 18 , 747–771 (1986).

Mills, K., Ronagh, P. & Tamblyn, I. Finding the ground state of spin Hamiltonians with reinforcement learning. Nat. Mach. Intell. 2 , 509–517 (2020).

MP-TESTDATA - The TSPLIB Symmetric Traveling Salesman Problem Instances. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/ (2013).

Dan, A., Shimizu, R., Nishikawa, T., Bian, S. & Sato, T. Clustering Approach for Solving Traveling Salesman Problems via Ising Model Based Solver. In 2020 57th ACM/IEEE Design Automation Conference (DAC) 1–6 (IEEE, 2020). https://doi.org/10.1109/DAC18072.2020.9218695 .

Ezugwu, A. E.-S., Adewumi, A. O. & Frîncu, M. E. Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem. Expert Syst. Appl. 77 , 189–210 (2017).

Mohsen, A. M. Annealing Ant Colony Optimization with Mutation Operator for Solving TSP. Comput. Intell. Neurosci. 2016 , 1–13 (2016).

Wang, J., Ersoy, O. K., He, M. & Wang, F. Multi-offspring genetic algorithm and its application to the traveling salesman problem. Appl. Soft Comput. 43 , 415–423 (2016).

Talatchian, P. et al. Mutual control of stochastic switching for two electrically coupled superparamagnetic tunnel junctions. Phys. Rev. B 104 , 054427 (2021).

Cai, F. et al. Power-efficient combinatorial optimization using intrinsic noise in memristor Hopfield neural networks. Nat. Electron 3 , 409–418 (2020).

Hayakawa, K. et al. Nanosecond Random Telegraph Noise in In-Plane Magnetic Tunnel Junctions. Phys. Rev. Lett. 126 , 117202 (2021).

Safranski, C. et al. Demonstration of Nanosecond Operation in Stochastic Magnetic Tunnel Junctions. Nano Lett. 21 , 2040–2045 (2021).

Download references

Acknowledgements

This work was supported by National Research Foundation (NRF), Prime Minister’s Office, Singapore, under its Competitive Research Programme (NRF-000214-00 to H.Y.), Advanced Research and Technology Innovation Center (ARTIC to H.Y.), the National University of Singapore under Grant (project number: A-0005947-19-00 to H.Y.), and Ministry of Education, Singapore, under Tier 2 (T2EP50123-0025 to H.Y.). We thank Yuqi Su, and Chne-Wuen Tsai from National University of Singapore and Zhi-Da Song from Peking University for useful discussions.

Author information

Authors and affiliations.

Department of Electrical and Computer Engineering, National University of Singapore, Singapore, Singapore

Jia Si, Shuhan Yang, Yunuo Cen, Jiaer Chen, Yingna Huang, Zhaoyang Yao, Dong-Jun Kim, Kaiming Cai, Jerald Yoo, Xuanyao Fong & Hyunsoo Yang

Key Laboratory for the Physics and Chemistry of Nanodevices and Center for Carbon-based Electronics, School of Electronics, Peking University, Beijing, China

You can also search for this author in PubMed   Google Scholar

Contributions

J.S. and H.Y. conceived and designed the experiments. J.S. designed, fabricated, and coded the hardware system. D.K., and S.Y. fabricated the devices. J.S., S.Y., and K.C. performed device measurements. Z.Y. bonded the components on PCB. J.S. designed SMTJ-based Ising system. J.S., J.C., Y.C., Y.H. and X.F. developed the optimization algorithm and performed simulations. J.S., S.Y., Y.C., J.Y., X.F. and H.Y. analyzed the data. J.S. and H.Y. wrote the manuscript. H.Y. proposed and supervised this work. All authors discussed the results and revised the manuscript.

Corresponding author

Correspondence to Hyunsoo Yang .

Ethics declarations

Competing interests.

The authors declare no competing interests.

Peer review

Peer review information.

Nature Communications thanks the anonymous reviewers for their contribution to the peer review of this work.

Additional information

Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary information

Supplementary information, source data, source data, rights and permissions.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Cite this article.

Si, J., Yang, S., Cen, Y. et al. Energy-efficient superparamagnetic Ising machine and its application to traveling salesman problems. Nat Commun 15 , 3457 (2024). https://doi.org/10.1038/s41467-024-47818-z

Download citation

Received : 16 June 2022

Accepted : 11 April 2024

Published : 24 April 2024

DOI : https://doi.org/10.1038/s41467-024-47818-z

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

By submitting a comment you agree to abide by our Terms and Community Guidelines . If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.

Quick links

• Explore articles by subject
• Guide to authors
• Editorial policies

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.

Subscribe to the PwC Newsletter

Join the community, add a new evaluation result row, traveling salesman problem.

68 papers with code • 1 benchmarks • 1 datasets

Benchmarks Add a Result

Most implemented papers, neural combinatorial optimization with reinforcement learning.

Despite the computational expense, without much engineering and heuristic designing, Neural Combinatorial Optimization achieves close to optimal results on 2D Euclidean graphs with up to 100 nodes.

Differentiation of Blackbox Combinatorial Solvers

Achieving fusion of deep learning with combinatorial algorithms promises transformative changes to artificial intelligence.

Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Mode

Heuristics are indispensable for tackling complex search and optimization problems.

Triplet Interaction Improves Graph Transformers: Accurate Molecular Graph Learning with Triplet Graph Transformers

We also obtain SOTA results on QM9, MOLPCBA, and LIT-PCBA molecular property prediction benchmarks via transfer learning.

Donkey and Smuggler Optimization Algorithm: A Collaborative Working Approach to Path Finding

Charan619/Get-me-there • 19 Apr 2019

These are the Smuggler and Donkeys.

Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

Furthermore, to approximate solutions to constrained combinatorial optimization problems such as the TSP with time windows, we train hierarchical GPNs (HGPNs) using RL, which learns a hierarchical policy to find an optimal city permutation under constraints.

Exploring the Loss Landscape in Neural Architecture Search

In this work, we show that (1) the simplest hill-climbing algorithm is a powerful baseline for NAS, and (2), when the noise in popular NAS benchmark datasets is reduced to a minimum, hill-climbing to outperforms many popular state-of-the-art algorithms.

Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer

Moreover, the positional features are embedded through a novel cyclic positional encoding (CPE) method to allow Transformer to effectively capture the circularity and symmetry of VRP solutions (i. e., cyclic sequences).

Backpropagation through Combinatorial Algorithms: Identity with Projection Works

Embedding discrete solvers as differentiable layers has given modern deep learning architectures combinatorial expressivity and discrete reasoning capabilities.

A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem

raissaccorreia/genetic_algorithm • 14 Mar 2012

Genetic algorithm includes some parameters that should be adjusting so that the algorithm can provide positive results.

the traveling salesman problem Recently Published Documents

Total documents.

• Latest Documents
• Most Cited Documents
• Contributed Authors
• Related Sources
• Related Keywords

A list-based simulated annealing algorithm with crossover operator for the traveling salesman problem

Artificial electric field algorithm with greedy state transition strategy for spherical multiple traveling salesmen problem.

AbstractThe multiple traveling salesman problem (MTSP) is an extension of the traveling salesman problem (TSP). It is found that the MTSP problem on a three-dimensional sphere has more research value. In a spherical space, each city is located on the surface of the Earth. To solve this problem, an integer-serialized coding and decoding scheme was adopted, and artificial electric field algorithm (AEFA) was mixed with greedy strategy and state transition strategy, and an artificial electric field algorithm based on greedy state transition strategy (GSTAEFA) was proposed. Greedy state transition strategy provides state transition interference for AEFA, increases the diversity of population, and effectively improves the accuracy of the algorithm. Finally, we test the performance of GSTAEFA by optimizing examples with different numbers of cities. Experimental results show that GSTAEFA has better performance in solving SMTSP problems than other swarm intelligence algorithms.

Improving the state-of-the-art in the Traveling Salesman Problem: An Anytime Automatic Algorithm Selection

Penerapan bat algorithm dalam penyelsaian kasus travelling salesman problem (tsp) pada internship program.

This optimization is an optimization case that organizes all possible and feasible solutions in discrete form. One form of combinatorial optimization that can be used as material in testing a method is the Traveling Salesman Problem (TSP). In this study, the bat algorithm will be used to find the optimum value in TSP. Utilization of the Metaheuristic Algorithm through the concept of the Bat Algorithm is able to provide optimal results in searching for the shortest distance in the case of TSP. Based on trials conducted using data on the location of student street vendors, the Bat Algortima is able to obtain the global minimum or the shortest distance when compared to the nearest neighbor method, Hungarian method, branch and bound method.

A Microlearning path recommendation approach based on ant colony optimization

This paper presents the technical proposal of a novel approach based on Ant Colony Optimization (ACO) to recommend personalized microlearning paths considering the learning needs of the learner. In this study, the information of the learner was considered from a disciplinary ICT perspective, since the characteristics of our learner correspond to those of a professor with variable characteristics, such as the level of knowledge and their learning status. The recommendation problem is approached as an instance of the Traveling Salesman Problem (TSP), the educational pills represent the cities, the paths are the relationships between educational pills, the cost of going from one pill to another can be estimated by their degree of difficulty as well as the performance of the learner during the individual test. The results prove the approach proposal capacity to suggest microlearning path personalized recommendation according to the different levels of knowledge of the learners. The higher the number of learners, the behavior of the algorithm benefits in terms of stability.

A Collaborative Neurodynamic Optimization Algorithm Based on Boltzmann Machines for Solving the Traveling Salesman Problem

Some contributions of ailsa h. land to the study of the traveling salesman problem, using fuzzy inference to evaluation suppliers in diyala general electric industries company.

The research aims to evaluate the suppliers at Diyala general electric industries company conducted in an environment of uncertainty and fuzzy where there is no particular system followed by the company, and also aims to use the problem of traveling salesman problem in the process of transporting raw materials from suppliers to the company in a fuzzy environment. Therefore, a system based on mathematical methods and quantity was developed to evaluate the suppliers. Fuzzy inference system (FIS) and fuzzy set theory were used to solve this problem through (Matlab) and the problem of the traveling salesman in two stages was also solved by the first stage of eliminating the fuzzing of the environment using the rank function method, while the second stage used the method of the nearest neighbor to solve the traveling salesman problem (TSP) by drawing a path that facilitates the process of transporting raw materials in the least time where the programming (Winqsb) was used. The most important thing that was reached is the mechanism of evaluating the suppliers by giving a percentage to each supplier and also their ranking where the supplier (Japanese company) got the first place and it was (87.3) ... etc. The raw materials process was used in the least time and obtained at the lowest time of the transfer, which is 292 minutes

Enhanced Self-Organizing Map Solution for the Traveling Salesman Problem

Usando um método aprimorado de Mapa Auto-Organizável, fornecemos soluções abaixo do ideal para o Problema do Caixeiro Viajante. Além disso, empregamos o ajuste de hiperparâmetros para identificar os recursos mais críticos do algoritmo. Todas as melhorias no trabalho de benchmark trouxeram resultados consistentes e podem inspirar esforços futuros para melhorar este algoritmo e aplicá-lo a diferentes problemas.

Sustainable Urban Delivery: The Learning Process of Path Costs Enhanced by Information and Communication Technologies

Today, local administrations are faced with the presence of greater constraints in terms of the use of space and time. At the same time, large amount of data is available to fleet managers that can be used for controlling their fleets. This work is set in the context defined by sustainable city logistics, and information and communication technologies (ICTs), to formalize the three themes of the smart city (transport, ICTs and energy savings) in a single problem. Following this, the main purpose of the study is to propose a unified formulation of the basic problem of fleets, i.e., the traveling salesman problem (TSP), which explicitly includes the use of emerging information and communication technologies (e-ICTs) pointing out the learning process of path costs in urban delivery. This research explores the opportunity to extend the path cost formation with a within-day and day-to-day learning process, including the specification of the attributes provided by e-ICTs. As shown through a real test case, the research answers to queries coming from operators and collectivities to improve city liveability and sustainability. It includes both economic sustainability for companies/enterprises and environmental sustainability for local administrations (and collectivities). Besides contributing to reduce the times and kms travelled by commercial vehicles, as well as the interference of freight vehicles with other traffic components, it also contributes to road accident reduction (social sustainability). Therefore, after the re-exanimation of TSP, this paper presents the proposed unitary formulation and its benefits through the discussion of results obtained in a real case study. Finally, the possible innovation guided by e-ICT is pointed out.

Export Citation Format

Share document.

Two metaheuristics approaches for solving the traveling salesman problem: an Algerian waste collection case

• Original paper
• Published: 01 November 2019
• Volume 21 , pages 1641–1661, ( 2021 )

Cite this article

• Khalid Mekamcha 1 ,
• Mehdi Souier 1 , 2 ,
• Hakim Nadhir Bessenouci 1 &
• Mohammed Bennekrouf 1 , 3  

755 Accesses

7 Citations

Explore all metrics

Waste collection remains a very important research area in waste management to deal with environmental degradation and health risks caused by daily waste quantities of the population. However, due to financial resources limitations, there is an increasing trend towards developing waste collection systems able to meet the different requirements related to the performance of the global collection cost, the tour scheduling and the capacity of each truck, the collection times, the fuel consumption and the overall traveled distance. In this work, we investigate the waste collection problem in Tlemcen City in Algeria. The problem is represented as a traveling salesman problem. Owing to the complexity of this real-life problem, two classes of metaheuristics known as powerful approaches are used to provide useful solutions for the addressed case. A Tabu Search algorithm and a simulated annealing (SA) algorithm are integrated in a decision-making graphical interface developed to help decision makers to plan their tours. The proposed algorithms are validated using data retrieved from all areas in Tlemcen. The results show that the SA performs the best to minimize the traveled distance in the vast majority of cases.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

A Simulated Annealing Algorithm for Solving a Routing Problem in the Context of Municipal Solid Waste Collection

A novel model for sustainable waste collection arc routing problem: Pareto-based algorithms

Simulated Annealing Metaheuristic Approach for Municipal Solid Waste Collecting Route Problem in the Historical Center of a Mexican City

Abdelaziz FB, Mir H (2016) An optimization model and tabu search heuristic for scheduling of tasks on a radar sensor. IEEE Sens J 16(17):6694–6702

Article   Google Scholar  

Abdeljaoued MA, Saadani NEH, Bahroun Z (2018) Heuristic and metaheuristic approaches for parallel machine scheduling under resource constraints. Oper Res. https://doi.org/10.1007/s12351-018-0412-3

Abdellafou KB, Hadda H, Korbaa O (2018) Heuristic algorithms for scheduling intrees on m machines with non-availability constraints. Oper Res. https://doi.org/10.1007/s12351-018-0432-z

Agatz N, Bouman P, Schmidt M (2018) Optimization approaches for the traveling salesman problem with drone. Transp Sci 52(4):965–981

Akbari M, Molla-Alizadeh-Zavardehi S, Niroomand S (2017) Meta-heuristic approaches for fixed-charge solid transportation problem in two-stage supply chain network. Oper Res. https://doi.org/10.1007/s12351-017-0332-7

Alidaee B, Ramalingam VP, Wang H, Kethley B (2018) Computational experiment of critical event tabu search for the general integer multidimensional knapsack problem. Ann of Oper Res 269(1–2):3–19

Archetti C, Speranza MG, Hertz A (2006) A tabu search algorithm for the split delivery vehicle routing problem. Transp Sci 40(1):64–73

Arribas CA, Blazquez CA, Lamas A (2010) Urban solid waste collection system using mathematical modelling and tools of geographic information systems. Waste Manag Res 28(4):355–363

Bautista J, Fernández E, Pereira J (2008) Solving an urban waste collection problem using ants heuristics. Comput Oper Res 35(9):3020–3033

Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3):209–219

Beliën J, De Boeck L, Van Ackere J (2012) Municipal solid waste collection and management problems: a literature review. Transp Sci 48(1):78–102

Beltrami EJ, Bodin LD (1974) Networks and vehicle routing for municipal waste collection. Networks 4(1):65–94

Benjamin AM, Beasley JE (2010) Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities. Comput Oper Res 37(12):2270–2280

Bing X, de Keizer M, Bloemhof-Ruwaard JM, van der Vorst JG (2014) Vehicle routing for the eco-efficient collection of household plastic waste. Waste Manag 34(4):719–729

Bosch R, Herman A (2004) Continuous line drawings via the traveling salesman problem. Oper Res Lett 32(4):302–303

Bourgeois M, Laporte G, Semet F (2003) Heuristics for the black and white traveling salesman problem. Comput Oper Res 30(1):75–85

Changdar C, Mahapatra GS, Pal RK (2016) A modified genetic algorithm-based approach to solve constrained solid TSP with time window using interval valued parameter. Int J Oper Res 26(4):398–421

Chaurasia SN, Sundar S, Singh A (2017) Hybrid metaheuristic approaches for the single machine total stepwise tardiness problem with release dates. Oper Res 17(1):275–295

Google Scholar  

Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2(4):393–410

Doppstadt C, Koberstein A, Vigo D (2016) The hybrid electric vehicle–traveling salesman problem. Eur J Oper Res 253(3):825–842

Ezugwu AES, Adewumi AO, Frîncu ME (2017) Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem. Expert Syst Appl 77:189–210

Ghiani G, Laporte G, Semet F (2006) The black and white traveling salesman problem. Oper Res 54(2):366–378

Glover F (1989) Tabu search: part I. ORSA J Comput 1(3):190–206

Gouveia L, Leitner M, Ruthmair M (2017) Extended formulations and branch-and-cut algorithms for the Black-and-White traveling salesman problem. Eur J Oper Res 262(3):908–928

Hannan MA, Akhtar M, Begum RA, Basri H, Hussain A, Scavino E (2018) Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm. Waste Manag 71:31–41

Hasegawa M (2011) Verification and rectification of the physical analogy of simulated annealing for the solution of the traveling salesman problem. Phys Rev E 83(3):036708

Hong S, Padberg MW (1977) A note on the symmetric multiple traveling salesman problem with fixed charges. Oper Res 25(5):871–874

Huang GH, Baetz BW, Patry GG (1995) Grey integer programming: an application to waste management planning under uncertainty. Eur J Oper Res 83(3):594–620

Ioannou G, Kritikos MN, Prastacos GP (2008) An assignment-based heuristic for vehicle routing with time windows. Oper Res 8(3):219–233

Javad MOM, Karimi B (2017) A simulated annealing algorithm for solving multi-depot location routing problem with backhaul. Int J Ind Syst Eng 25(4):460–477

Kaboudani Y, Ghodsypour SH, Kia H, Shahmardan A (2018) Vehicle routing and scheduling in cross docks with forward and reverse logistics. Oper Res. https://doi.org/10.1007/s12351-018-0396-z

Kara I, Bektas T (2006) Integer linear programming formulations of multiple salesman problems and its variations. Eur J Oper Res 174(3):1449–1458

Karadimas NV, Kouzas G, Anagnostopoulos I, Loumos V (2005) Urban solid waste collection and routing: the ant colony strategic approach. Int J Simul 6(12–13):45–53

Khaksar W, Hong TS, Sahari KSM, Khaksar M, Torresen J (2019) Sampling-based online motion planning for mobile robots: utilization of Tabu search and adaptive neuro-fuzzy inference system. Neural Comput Appl 31(2):1275–1289

Khambhampati S, Calyam P, Zhang X (2018) A tabu search algorithm for a capacitated clustering problem. Int J Oper Res 33(3):387–412

Kim KH, Park YM (2004) A crane scheduling method for port container terminals. Eur J Oper Res 156(3):752–768

Kim BI, Kim S, Sahoo S (2006) Waste collection vehicle routing problem with time windows. Comput Oper Res 33(12):3624–3642

Kim H, Yang J, Lee KD (2009) Vehicle routing in reverse logistics for recycling end-of-life consumer electronic goods in South Korea. Transp Res Part D Transp Environ 14(5):291–299

Kinable J, Smeulders B, Delcour E, Spieksma FC (2017) Exact algorithms for the equitable traveling salesman problem. Eur J Oper Res 261(2):475–485

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680

Kuo RJ, Wibowo BS, Zulvia FE (2016) Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time. Appl Math Model 40(23–24):9990–10001

Laporte G, Nobert Y (1980) A cutting planes algorithm for the m-salesmen problem. J Oper Res Soc 31(11):1017–1023

Larki H, Yousefikhoshbakht M (2014) Solving the multiple traveling salesman problem by a novel meta-heuristic algorithm. J Opt Ind Eng 7(16):55–63

Leggieri V, Haouari M (2017) Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems. Eur J Oper Res 263(3):755–767

Lin Y, Bian Z, Liu X (2016) Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing–tabu search algorithm to solve the symmetrical traveling salesman problem. Appl Soft Comput 49:937–952

Louveaux FV, Salazar-González JJ (2018) Exact approach for the vehicle routing problem with stochastic demands and preventive returns. Transp Sci 52(6):1463–1478

Malek M, Guruswamy M, Pandya M, Owens H (1989) Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Ann Oper Res 21(1):59–84

Marinakis Y, Migdalas A (2007) Annotated bibliography in vehicle routing. Oper Res 7(1):27–46

Mekamcha K, Bennekrouf M, Souier M (2018) Improvement of the municipal waste collection: the real case of city center of Tlemcen, Algeria. In: 2018 International colloquium on logistics and supply chain management (LOGISTIQUA), IEEE, pp 140–145

Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087–1092

Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulations and traveling salesman problems. J ACM (JACM) 7(4):326–329

Mourão MC, Almeida MT (2000) Lower-bounding and heuristic methods for a refuse collection vehicle routing problem. Eur J Oper Res 121(2):420–434

Murakami K (2018) Formulation and algorithms for route planning problem of plug-in hybrid electric vehicles. Oper Res 18(2):497–519

Muter I (2015) A new formulation and approach for the black and white traveling salesman problem. Comput Oper Res 53:96–106

Muttiah RS, Engel BA, Jones DD (1996) Waste disposal site selection using GIS-based simulated annealing. Comput Geosci 22(9):1013–1017

Orloff CS (1974) Routing a fleet of M vehicles to/from a central facility. Networks 4(2):147–162

Osamy W, El-sawy AA, Khedr AM (2019) SATC: a simulated annealing based tree construction and scheduling algorithm for minimizing aggregation time in wireless sensor networks. Wirel Pers Commun. https://doi.org/10.1007/s11277-019-06440-9

Rajabi-Bahaabadi M, Shariat-Mohaymany A, Babaei M, Vigo D (2019) Reliable vehicle routing problem in stochastic networks with correlated travel times. Oper Res. https://doi.org/10.1007/s12351-019-00452-w

Riahi V, Kazemi M (2018) A new hybrid ant colony algorithm for scheduling of no-wait flowshop. Oper Res 18(1):55–74

Ruland KS, Rodin EY (1997) The pickup and delivery problem: faces and branch-and-cut algorithm. Comput Math Appl 33(12):1–13

Ryan JL, Bailey TG, Moore JT, Carlton WB (1998) Reactive tabu search in unmanned aerial reconnaissance simulations. In: 1998 Winter simulation conference proceedings (Cat. No. 98CH36274), IEEE, vol 1, pp 873–879

Sharma SK, Routroy S, Yadav U (2018) Vehicle routing problem: recent literature review of its variants. Int J Oper Res 33(1):1–31

Silva MR, Cunha CB (2017) A tabu search heuristic for the uncapacitated single allocation p-hub maximal covering problem. Eur J Oper Res 262(3):954–965

Song CH, Lee K, Lee WD (2003) Extended simulated annealing for augmented TSP and multi-salesmen TSP. In: 2003 IEEE proceedings of the international joint conference on neural networks, vol 3, pp 2340–2343

Taillard É, Badeau P, Gendreau M, Guertin F, Potvin JY (1997) A tabu search heuristic for the vehicle routing problem with soft time windows. Transp Sci 31(2):170–186

Tayal A, Singh SP (2018) Integrating big data analytic and hybrid firefly-chaotic simulated annealing approach for facility layout problem. Ann Oper Res 270(1–2):489–514

Tirkolaee EB, Mahdavi I, Esfahani MMS (2018) A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew’s working time. Waste Manag 76:138–146

Viotti P, Polettini A, Pomi R, Innocenti C (2003) Genetic algorithms as a promising tool for optimisation of the MSW collection routes. Waste Manag Res 21(4):292–298

Wang H (2017) Routing and scheduling for a last-mile transportation system. Transp Sci 53(1):131–147

Wang S, Rao W, Hong Y (2018) A distance matrix based algorithm for solving the traveling salesman problem. Oper Res. https://doi.org/10.1007/s12351-018-0386-1

Yahyaoui H, Kaabachi I, Krichen S, Dekdouk A (2018) Two metaheuristic approaches for solving the multi-compartment vehicle routing problem. Oper Res. https://doi.org/10.1007/s12351-018-0403-4

Zaidan AA, Atiya B, Bakar MA, Zaidan BB (2017) A new hybrid algorithm of simulated annealing and simplex downhill for solving multiple-objective aggregate production planning on fuzzy environment. Neural Comput Appl 2017:1–12

Zhao Y, Leng L, Zhang C (2019) A novel framework of hyper-heuristic approach and its application in location-routing problem with simultaneous pickup and delivery. Oper Res. https://doi.org/10.1007/s12351-019-00480-6

Download references

Acknowledgements

The authors warmly thank the municipality of Tlemcen City for their collaboration. Special thanks to the waste management team for their daily involvement and support in helping us achieve sound results.

Author information

Authors and affiliations.

Manufacturing Engineering Laboratory of Tlemcen (MELT), University of Tlemcen, PB 230, 13000, Tlemcen, Algeria

Khalid Mekamcha, Mehdi Souier, Hakim Nadhir Bessenouci & Mohammed Bennekrouf

High School of Management of Tlemcen, PB 1085, 13000, Tlemcen, Algeria

Mehdi Souier

High School of Applied Sciences of Tlemcen, PB 165, 13000, Tlemcen, Algeria

Mohammed Bennekrouf

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Mehdi Souier .

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Mekamcha, K., Souier, M., Bessenouci, H.N. et al. Two metaheuristics approaches for solving the traveling salesman problem: an Algerian waste collection case. Oper Res Int J 21 , 1641–1661 (2021). https://doi.org/10.1007/s12351-019-00529-6

Download citation

Received : 17 December 2018

Revised : 08 October 2019

Accepted : 28 October 2019

Published : 01 November 2019

Issue Date : September 2021

DOI : https://doi.org/10.1007/s12351-019-00529-6

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Traveling salesman problem
• Tabu search
• Simulated annealing
• Waste collection
• Find a journal
• Publish with us
• Track your research

> cs > arXiv:2405.01997

Current browse context:, change to browse by:, references & citations, computer science > computation and language, title: exploring combinatorial problem solving with large language models: a case study on the travelling salesman problem using gpt-3.5 turbo.

Abstract: Large Language Models (LLMs) are deep learning models designed to generate text based on textual input. Although researchers have been developing these models for more complex tasks such as code generation and general reasoning, few efforts have explored how LLMs can be applied to combinatorial problems. In this research, we investigate the potential of LLMs to solve the Travelling Salesman Problem (TSP). Utilizing GPT-3.5 Turbo, we conducted experiments employing various approaches, including zero-shot in-context learning, few-shot in-context learning, and chain-of-thoughts (CoT). Consequently, we fine-tuned GPT-3.5 Turbo to solve a specific problem size and tested it using a set of various instance sizes. The fine-tuned models demonstrated promising performance on problems identical in size to the training instances and generalized well to larger problems. Furthermore, to improve the performance of the fine-tuned model without incurring additional training costs, we adopted a self-ensemble approach to improve the quality of the solutions.

Submission history

Link back to: arXiv , form interface , contact .