## An Optical Solution For The Traveling Salesman Problem

Optics Express, Vol. 15, Issue 16, pp. 10473-10482 (2007)

http://dx.doi.org/10.1364/OE.15.010473

Acrobat PDF (174 KB)

### Abstract

We introduce an optical method based on white light interferometry in order to solve the well-known NP–complete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non–polynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to *N ^{N}
* for a traveling salesman problem with

*N*cities and that for large numbers of cities the method in practice therefore is limited by the signal–to–noise ratio. The proposed method is meant purely as a gedankenexperiment.

© 2007 Optical Society of America

## 1. Introduction

*N*. It can be shown that once a solution to one NP–complete problem is found it will be possible to map that result (in polynomial time) to any other NP–complete problem[2]. Therefore fast optimum solutions to the TSP are of considerable importance for all NP–complete problems.

*N*cities. The task is to find the shortest tour length through all the cities with the additional constraint to visit each city exactly once. In the classical TSP the trip should end at the same city where it has started. That means we have a round–trip. It is easy to see that for

*N*cities there are (

*N*-1)!/2 possible tours. So even for a moderate number of cities one would have to check an astronomical number of possible tours (e.g. 30 cities lead to 4.4

*x*10

^{30}tours) in order to find the shortest one. For 60 cities we would have more tours than there are atoms in the universe.

4. C. Kirkpatrick, “Optimization by simulated annealing: Quantitative studies,” J. Stat. Phys. **34**, 975–986 (1984). [CrossRef]

6. F. Glover, E. Taillard, and D. de Werra, “A user’s guide to tabu search,” Ann. Oper. Res. **41**, 3–28 (1993). [CrossRef]

7. S. Lin and W. Kernighan, “An effective heuristic algorithm for the traveling salesman problem,’ Oper. Res. **21**, 498–516, (1973). [CrossRef]

8. J. Edmonds, “Matroids and the greedy algorithm,” Math. Program. **1**, 127–136 (1971). [CrossRef]

*N*>100) very good solutions can be found today in reasonable time using conventional computers[

*9*]. Ref. [10] gives a good overview. Polynomial time algorithms are available if one is satisfied with obtaining good solutions where one can even set upper bounds for the deviation from global optimality[9

9. S. Arora, “Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems,” J. ACM **45**, 753–7872 (1998). [CrossRef]

11. T. Hogg and D. Portnov, “Quantum optimization,” Inf. Sci . **128**, 181–197 (2000). [CrossRef]

13. N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP–complete problems,” Appl. Opt. **46**, 711–724 (2007). [CrossRef] [PubMed]

13. N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP–complete problems,” Appl. Opt. **46**, 711–724 (2007). [CrossRef] [PubMed]

*N*is still not possible by conventional computing[9

9. S. Arora, “Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems,” J. ACM **45**, 753–7872 (1998). [CrossRef]

*N*

^{2}complexity. We achieve this by using white light interferometry (WLI)[14

14. G. S. Kino and S. C. Chi, “Mirau correlation microscope,” Appl. Opt. **29**, 3775–3783 (1990). [CrossRef] [PubMed]

## 2. Basic idea

*N*connected cities and finally might exit at the final (=initial) city. If the optical path length through the network corresponds to the reference path length, interference at the detector will be observed.

*d*. It should be noted that by using fibers we can implement an arbitrary distance metric as well as asymmetric connections between the cities (so called asymmetric TSP). The input signals from other cities to the exit(=initial) city are connected directly to the white light interferometer.

_{ij}*N*input and

*N*output channels. A photon entering one of the input channels will travel through a fiber optical delay line before entering a fan–out element that outputs the photon to one of the output channels. In the quantum mechanical particle model the choice of the output port is given purely randomly. In the wave-optical model of course we have a splitting of the wave to the

*N*output channels. Different methods (e.g. Y-couplers[15

15. V. A. Kozlov, J. Hernandez-Codero, and T. F. Morse, “All-fiber coherent beam combining of fiber lasers,” Opt. Lett. **24**, 1814–1816 (1999). [CrossRef]

*correct*interferences (step 3). To this end a careful choice of the delays within the cities is mandatory. For the TSP we chose (other choices are possible) for city number i the length

*D*of the delay line

_{i}*N*-1 and with a small

*d*in the range of tens of microns. The reason for this choice will become clear in section 3. The constant

*α*is chosen such that it is considerably larger than

*N*times the largest distance max(

*d*) between two cities.

_{ij}*N*cities this setup time will be proportional to

*N*

^{2}.

*L*is at least

*P*being the overall path length traveled between the cities:

*α*(2

*-1)+*

^{N}*Nd*which is the sum of all delay lines in the cities.

*α*(2

*-1)+*

^{N}*Nd*exactly equals the minimum path length that the salesman has to travel during his trip.

*N*– 1 remaining cities (see Fig. 2 (b)). For city i we have to reduce the length of the reference arm by

*N*-2 remaining cities.

*N*

^{2}. Therefore we have reduced the NP–complete problemto a problemwith cost proportional

*N*

^{2}. For the example at the beginning with N=30 we have to perform 900 comparisons which is negligible compared to the original cost proportional to 10

^{30}.

## 3. Filtering out the correct interference

*R*and the wave packet that corresponds to the correct solution by

*C*. We have to keep in mind, that there might be multiple global solutions

*C*present at the same time (see also below), therefore we have to use ∑

_{i}

^{#C}

_{i}*C*for the analysis of the interference. #

_{i}*C*denotes the number of global solutions.

*C*with wave packets that have the same overall path length

_{i}*L*but might not traveled through all the cities exactly once. We denote these wave packets by

*WC*and the number of these wave packets by #

_{j}*W*.

*L*. If we have #

*K*different superpositions each with #

*H*wave packets we might denote this term by

_{k}*I*

_{1}-

*I*

_{2}therefore is

*WC*.

_{j}*d*as well as

_{ij}*α*(see Eq. 1) in multiples of 1 mm. Consequently, it follows that

*P*then is also a multiple of 1 mm:

*G*.

*d*)=1 m. That means the resolution of our problem is 1:1000 (e.g. 1 km for a trip with maximum inter city distances of 1000 km) which is enough for non-artificial problems for finding the best trip but of course other choices — with a better resolution — are possible. The computational cost does not depend on the chosen resolution.

_{ij}*d*is chosen larger than twice the coherence length of the light source. E.g. we might chose

*d*=10

*µ*m.

*N*≥2.

*WC*for the chosen delays.

_{j}*WC*with exactly

_{j}*N*cities?

*N*cities would be replaced by another one. But that would mean that the overall delay within the cities is changed by at least

*α*. Since

*α*>

*P*we can’t cancel that change by a different way through the cities because any change would be too strong. Therefore we will not achieve interference with the reference.

*WC*with less than

_{j}*N*cities?

*N*cities we again would have to cancel the loss of one (or more) cities by visiting one city with a large delay multiple times. This is also not possible with the chosen Delays

*D*.

_{i}*Nd*within the delay. Due to Eq. 12 we can only visit very special numbers

*N′*of cities in order to achieve this delay, namely

*d*=10

*μ*m and e.g.

*N*=10) this would lead to

*N′*=10,110,210,310. In practice only the first possible value of

*N′*, which corresponds to case A, is detectable at all. The ratio between the intensities of the two first possible solution for

*N*=10, namely

*N′*=10 and

*N′*=110 is 10

^{10}/10

^{110}=10

^{100}which is definitely far beyond any possibility for detection (compare section 4).

*WC*with more than

_{j}*N*cities?

*N′*cities according to Eq. 14 are possible. And again the extreme difference in intensities leads to the situation that the probability of getting only one wrong photon is beyond any practical limit.

*WC*disturbing any measurement if we chose the setup as described above.

_{j}*C*=0 by randomly increasing some (randomly chosen) distances between cities by a very small amount (e.g. λ/5) that is performing phase shifting.

_{i}*α*(2

*-1)+*

^{N}*Nd*the first solution that we will find is the global solution to the TSP.

## 4. Signal-to-Noise Ratio

*N*cities we have to use fan–out elements with

*N*connections. That means that the intensity of a wave packet entering the network will be attenuated by a factor of (1/

*N*)

*before being detected by the interferometer.*

^{N}*N*)

^{N/2}and the interference with the reference (which should have a large amplitude, we take here 2) leads to an interference of

*N*

^{-N/2}.

16. B. E. A. Saleh and M. C. Teich, *Fundamentals of Photonics*, (Wiley, 1991). [CrossRef]

*s*of the photon number is directly proportional to the square root of the total photon number

_{dev}*N*, that is

_{g}*M*and the total number of photons (dominated by the reference light) by

*N*.

_{g}*µ*m the energy per photon is

*E*=

*hν*≈ 2×10

^{-19}J. With a 1 W light source we therefore would achieve 5×10

^{18}photons per second and we should be able to solve problems with about 16 cities (detector integration 1 s). Using millimeter waves (λ=1 mm) and waveguides we gain a factor of 1000 but even together with raising the power to 1 kW this would lead only to a small improvement concerning the maximum number of cities to about 20 (see Fig. 4).

## 5. Is this a quantum computer?

## 6. Conclusions

*N*! to

*N*

^{2}by optical means. To this end we employed white light interferometry and a fiber optic model of the network of cities that the salesman should travel through.

*N*(problem size) is fundamentally limited by the number of photons. Problems with

*N*=20 cities can be solved if 1 kW of power is available (1 s integration time per individual measurement). Since for practical (non-pathological) problems by purely electronic means very good solutions to even large size problems can be found, our proposed method is not meant to solve real–world traveling salesman problems but rather as a gedankenexperiment to show how photons and the laws of physics can considerably reduce the computational complexity of difficult mathematical problems.

## References and links

1. | G. Laporte, A. Asef-Vaziri, and C. Sriskandarajah, “Some applications of the generalized travelling salesman problem,” J. Oper. Res. Soc. |

2. | T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, |

3. | C. Vourdouris and E. Tsang, “Guided local search and its application to the traveling salesman problem,” Eur. J. Oper. Res. |

4. | C. Kirkpatrick, “Optimization by simulated annealing: Quantitative studies,” J. Stat. Phys. |

5. | J. J. Hopfield and D. W. Tank, “Neural’ computation of decisions in optimization problems,” Biol. Cybern. |

6. | F. Glover, E. Taillard, and D. de Werra, “A user’s guide to tabu search,” Ann. Oper. Res. |

7. | S. Lin and W. Kernighan, “An effective heuristic algorithm for the traveling salesman problem,’ Oper. Res. |

8. | J. Edmonds, “Matroids and the greedy algorithm,” Math. Program. |

9. | S. Arora, “Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems,” J. ACM |

10. | D. S. Johnson and L. A. McGeochE. Aarts and J. K. Lenstra,“The traveling salesman problem: a case study in local optimization,” in |

11. | T. Hogg and D. Portnov, “Quantum optimization,” Inf. Sci . |

12. | S. Y. Shin, B. T. Zhang, B.T., and S. S. JunP. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, “Solving traveling salesman problems using molecular programming,” eds., (IEEE Press, 1999), pp 994–1000. |

13. | N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP–complete problems,” Appl. Opt. |

14. | G. S. Kino and S. C. Chi, “Mirau correlation microscope,” Appl. Opt. |

15. | V. A. Kozlov, J. Hernandez-Codero, and T. F. Morse, “All-fiber coherent beam combining of fiber lasers,” Opt. Lett. |

16. | B. E. A. Saleh and M. C. Teich, |

17. | A. F. Fercher, W. Drexler, C. K. Hitzenberger, and T. Lasser, “Optical coherence tomography — principles and applications,” Reports on Progress in Physics |

**OCIS Codes**

(120.3180) Instrumentation, measurement, and metrology : Interferometry

(200.0200) Optics in computing : Optics in computing

(200.4740) Optics in computing : Optical processing

(260.3160) Physical optics : Interference

**ToC Category:**

Optics in Computing

**History**

Original Manuscript: June 5, 2007

Revised Manuscript: July 3, 2007

Manuscript Accepted: July 3, 2007

Published: August 3, 2007

**Citation**

Tobias Haist and Wolfgang Osten, "An Optical Solution For The Traveling Salesman Problem," Opt. Express **15**, 10473-10482 (2007)

http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-15-16-10473

Sort: Year | Journal | Reset

### References

- G. Laporte, A. Asef-Vaziri, and C. Sriskandarajah, "Some applications of the generalized travelling salesman problem," J. Oper. Res. Soc. 47, 1461-1467 (1996).
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, (MIT Press, 2001).
- C. Vourdouris and E. Tsang, "Guided local search and its application to the traveling salesman problem," Eur. J. Oper. Res. 113, 80-110 (1998).
- C. Kirkpatrick, "Optimization by simulated annealing: Quantitative studies," J. Stat. Phys. 34, 975-986 (1984). [CrossRef]
- J. J. Hopfield and D. W. Tank, "Neural’ computation of decisions in optimization problems," Biol. Cybern. 52, 381-384 (1985).
- F. Glover, E. Taillard, and D. de Werra, "A user’s guide to tabu search," Ann. Oper. Res. 41, 3-28 (1993). [CrossRef]
- S. Lin and W. Kernighan, "An effective heuristic algorithm for the traveling salesman problem,’Oper. Res. 21, 498-516, (1973). [CrossRef]
- J. Edmonds, "Matroids and the greedy algorithm," Math. Program. 1, 127-136 (1971). [CrossRef]
- S. Arora, "Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems," J. ACM 45, 753-7872 (1998). [CrossRef]
- D. S. Johnson, and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization," in Local Search in Combinatorial Optimization," E. Aarts and J. K. Lenstra, eds., (Princton University Press, 2003).
- T. Hogg and D. Portnov, "Quantum optimization," Inf. Sci. 128, 181-197 (2000). [CrossRef]
- S. Y. Shin, B. T. Zhang, B.T., and S. S. Jun, "Solving traveling salesman problems using molecular programming," in Proceedings of the Congress on Evolutionary Computation, P. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, eds., (IEEE Press, 1999), pp 994-1000.
- N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, "Optical solution for bounded NP-complete problems," Appl. Opt. 46, 711-724 (2007). [CrossRef] [PubMed]
- G. S. Kino and S. C. Chi, "Mirau correlation microscope," Appl. Opt. 29, 3775-3783 (1990). [CrossRef] [PubMed]
- V. A. Kozlov, J. Hernandez-Codero, and T. F. Morse, "All-fiber coherent beam combining of fiber lasers," Opt. Lett. 24, 1814-1816 (1999). [CrossRef]
- B. E. A. Saleh and M. C. Teich, Fundamentals of Photonics, (Wiley, 1991). [CrossRef]
- A. F. Fercher, W. Drexler, C. K. Hitzenberger, and T. Lasser: "Optical coherence tomography — principles and applications," Reports on Progress in Physics 66, 239-303 (2003). [CrossRef]

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

OSA is a member of CrossRef.