A hawker tour

by


My father is coming to visit Singapore next week.  Of course one thing I have to do is take him to sample some of the great food at the hawker centres here.  Say we are very ambitious and want to visit 18 of the best hawker centres on the island…in order to intelligently engage in the raging debate on which stall has the best char kway teow.  As my Dad’s stay is limited, we want the shortest tour visiting all these hawker centres.

Here is a google map of the 18 chosen hawker centres.  What do you think the shortest tour is?

18 of the best Singaporean hawker centres: ABC brickhouse, Amoy St, Changi Village, Chinatown Complex, Chomp Chomp, East Coast Lagoon, Geylang Serai, Ghim Moh, Golden Mile Complex, Hong Lim, Lau Pa Sat, Maxwell Rd, Newton, Old Airport Rd, Tampines Roundhouse, Tekka Centre, Tiong Bahru, Whampoa

This is an instance of the traveling salesman problem (TSP), the most celebrated problem in computer science.  Easy to state and visualize, it has a catchy story to boot: a salesman wants to visit a set of cities and return to his starting point.  What is the shortest tour possible?

TSP is an NP-hard problem and we do not know of any efficient way to solve it in general.  In this post, I will talk about some algorithmic approaches using linear programming, and use them to find the shortest hawker tour for our example.

The algorithms that have been developed for TSP are very impressive, and optimal tours have been found for real-life questions involving hundreds of thousands of cities.

Here is a 100,000 city TSP problem created by Robert Bosch to "draw" the Mona Lisa. The optimal tour is still open---with a $1000 prize---though the current best upper and lower bounds differ by only 0.0019%.

We will content ourselves with the the 1954 state of the art, following the approach Dantzig, Fulkerson, and Johnson used to solve a 49-city TSP problem of cities in the US.  This was by far the largest problem solved at the time—remember they did this without a computer!  This paper introduced the cutting-plane method, which has been extremely influential not just for TSP but many optimization problems.

Say we have a vector \(c_{i,j}\) indicating the distance between city \(i\) and \(j\).  We assume that the distance between city \(i\) and \(j\) is the same as between \(j\) and \(i\), so this will be a vector of length \(n \choose 2\), and I will refer to entries of \(c\) with indices \(i < j\).  In the hawker example, I used distances from Google maps driving distances.  These distances are not actually symmetric due to one way streets and the like, so I first symmetrized the distances.

We can also encode a tour as a boolean vector \(x_{i,j}\) with \(i < j\) where \(x_{i,j}=1\) if the tour goes from city \(i\) to city \(j\) and is \(0\) otherwise.  Thus the total cost is \(c^t x\).

The full TSP optimization problem can thus be written as

\[ \begin{aligned} \mbox{minimize} & c^t x \\ &x \in S \end{aligned}\]

where \(S\) is the set of all valid tours.  The set \(S\) of all tours is pretty complicated, and we do not know how to efficiently optimize over it.  So we instead consider a problem we can solve: optimizing the same objective function subject to constraints given by linear  inequalities \(Ax \le b\), resulting in a linear program

\[ \begin{aligned} \mbox{minimize} & c^t x \\ & Ax \le b \end{aligned}\]

We want this linear program to be a relaxation of TSP meaning that we should choose constraints such that \(\{x:Ax \le b\}\) contains the set of valid tours \(S\).  One property that any tour \(x \in S\) must satisfy is that \(\sum_{j} x_{i,j}=2\), that is every vertex has degree 2.  This is the basic relaxation that Dantzig, Fulkerson, and Johnson start with:

\[ \begin{aligned} \mbox{minimize} & c^t x \\ & \sum_{j} x_{i,j}=2 \mbox{ for all } i \\ & x \ge 0 \end{aligned}\]

In the hawker problem, we get the following solution to this linear program.  Luckily, the solution turns out to be integral and so it is easy to draw it on the map.

Here is what the solution does in Chinatown

This solution has several problems.  First off, there are double lines, \(x_{i,j} =2\), which never happens in a true tour.  Secondly, this solution has small cycles like we see here in Chinatown, also not possible in a true tour.  Here is where the cutting-plane method comes in.  We add linear constraints, violated by this solution but true for any tour, in order to eliminate this spurious solution.  To address the first fault of this solution we can add what are known as degree constraints that \(x_{i,j} \le 1\).  If there are \(n\) cities there are \(O(n^2)\) many such constraints so we could add all of them and still have a polynomial size linear program.  For the second problem we add what are known as subtour constraints.  These constraints say that for any subset \(T\) of hawker centres (not including all of them), \(\sum_{i<j \in T} x_{i,j} \le |T|-1\).  This is another constraint you can see will be satisfied by any true tour.  Notice that there are exponentially many subtour constraints, one for each subset of cities.

Following Dantzig, Fulkerson, and Johnson—who after all were reasoning about these linear programs by hand—we try to eliminate false tours by adding just a few strategic constraints of the above two types.  The east (Changi Village) and west (Ghim Moh) outlying hawker centres both have double edges in the first solution.  This is fairly natural as the second closest city to each of these is much further away than the closest one.  We add degree constraints to eliminate these double lines.  We also add a degree constraint in Chinatown between Amoy St and Lau Pa Sat.  Notice that in the first solution there is not even a double edge here, but it pops up later on so we squash it now.

When we solve the linear program with these degree constraints added, the solution fortunately again has integral weights so it is easy to draw.  But we are not lucky enough to get a tour yet.

Solution we obtain after adding degree constraints

In Chinatown there is still a double edge between Chinatown Complex and Hong Lim, and a triangle between Maxwell Road, Amoy St, and Lau Pa Sat, which are all very close together.

Now we start adding constraints to eliminate some of these subtours.  We add constraints to kill the triangle you see on the west side between Ghim Moh, ABC Brickhouse, and Tiong Bahru.  We also kill the east side triangle between Changi Village, East Coast Lagoon, and Tampines Round Market.  Finally, we kill the Chinatown triangle between Maxwell Road, Amoy St, and Lau Pa Sat.

With these 3 additional constraints added, the minimum cost solution is no longer integral, but all edges have weight either 1 or 1/2 (or zero).  In the pictures below the thick lines represent edges of weight 1 and the thin lines edges of weight 1/2.

And things get interesting in Chinatown…

What can we identify that is wrong with this solution?  An equivalent way to phrase the subtour constraints \(\sum_{i,j \in T} x_{i,j} \le |T|-1\), saying that there cannot be too many edges within a set, is that there must be at least two edges leaving any set (that does not contain all the vertices).  The picture below shows two sets which violate this constraint—each only has edges of total weight 1 leaving the set.

Two violated subtour inequalities

If we add these two subtour constraints our optimization returns a true tour!  In total we wound up using 26 constraints for the 18 hawker tour.  To solve the linear programs I used the freely available software Octave.  If you want to try it yourself, the code is available on github.

The optimal tour: 88.764 kilometers

The optimal tour through Chinatown

 

35 Responses to “A hawker tour”

  1. [...] a previous post, we solved a small instance of the traveling salesman problem (TSP) around Singapore’s hawker [...]

  2. I recently found many useful information in your website especially this blog page. Among the lots of comments on your articles. Thanks for sharing.
    how to get views on youtube fast

  3. This was really an interesting topic and I kinda agree with what you have mentioned here!
    youtube views

  4. You know your projects stand out of the herd. There is something special about them. It seems to me all of them are really brilliant!

  5. Thank you very much for the sharing! COOL..

  6. Im no expert, but I believe you just made an excellent point. You certainly fully understand what youre speaking about, and I can truly get behind that.
    Design Craft Exhibition

  7. This is a brilliant blog! I’m very happy with the comments!..
    discount codes

  8. vouchers codes says:

    I’ve been searching for some decent stuff on the subject and haven’t had any luck up until this point, You just got a new biggest fan!..
    vouchers codes

  9. seo new york says:

    Great survey, I’m sure you’re getting a great response.
    seo new york

  10. Thank you for some other informative blog. Where else could I get that type of information written in such an ideal means? I have a mission that I’m just now working on, and I have been at the look out for such information.
    Commission Black Ops review

  11. Oliver Harries says:

    Singapore is the great place and I love to visit it again and again.

    Total Curve Herbal Breast Pills

  12. Golden Slot says:

    Thanks for the good information you give them.

  13. My father visited Singapore and he tell me this is the great place in Asia.

  14. That is a really good tip particularly to those new to the blogosphere. Short but very accurate info… Many thanks for sharing this one. A must read post!

  15. This is a very well written and useful article. keep up the good work

  16. It is great to see your father chooses Singapore for his journey.

  17. here are the findings says:

    The way you write your articles is just mindblowing. Without a doubt, there is not a single person better at this job than you right now. Keep giving the great stuff. here are the findings

  18. Steven Wyer says:

    I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job!Steven Wyer

  19. Jc says:

    Singapore is the great place and I am glad your father chooses Singapore to start his journey. Erectile Dysfunction Conqueror Review

  20. blood thinning medicine lawsuit says:

    That is a really good tip particularly to those new to the blogosphere. Short but very accurate info… Many thanks for sharing this one. A must read post!blood thinning medicine lawsuit

  21. cheap futons says:

    That is a really good tip particularly to those new to the blogosphere. Short but very accurate info… Many thanks for sharing this one. A must read post! cheap futons

  22. I really believe the reality with this consider that You have the efficiency of modifying in that way, that soon Your blog site web page will be the most research of everyone. Now my friends appreciate Your career.

  23. I love Singapore and love to visit it again and again.

  24. his comment is here says:

    Love what you’re doing here guys, keep it up!..
    his comment is here

  25. Andrew says:

    There I found your blog using msn This is a really well written article Ill make sure to bookmark it and return to read more of your useful information Thanks for the post I will definitely comeback. Andrew

  26. look at here now says:

    admit, I have not been on this web page in a long time… however it was another joy to see It is such an important topic and ignored by so many, even professionals. professionals. I thank you to help making people more aware of possible issues. look at here now

  27. Lords mobile hack says:

    I am always searching online for articles that can help me. There is obviously a lot to know about this. I think you made some good points in Features also. Keep working, great job!Lords mobile hack

  28. dog insurance says:

    Great info. I love all the posts, I really enjoyed, I would like more information about this, because it is very nice. Thanks for sharing. dog insurance

  29. male enhancement pills says:

    That is a really good tip particularly to those new to the blogosphere. Short but very accurate info… Many thanks for sharing this one. A must read post! male enhancement pills

  30. freeangrybirdsgame says:

    I’m excited to uncover this page. I need to to thank you for ones time for this particularly fantastic read!! http://www.freeangrybirdsgame.org

  31. concrete-contractors says:

    professionals. I thank you to help making people more aware of possible issues.https://www.hirerush.com/TX:Austin/service/concrete-contractors

  32. app developers says:

    I have understood everything in this article, and I need more on this to complete my study on the topic, thanks to provide such nice details. app developers

  33. clash royale cheat says:

    Love what you’re doing here guys, keep it up!.. clash royale cheat

  34. broken iphone repair says:

    Useful info. Lucky me I discovered your web site by accident, and I am stunned why this accident didn’t took place earlier! I bookmarked it. broken iphone repair

Leave a Reply