## 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

### 146 Responses to “A hawker tour”

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

• Cheap Replica Handbags You guide me by sharing this toolbox i face problem whenever i exploit this promotion reading your blog i am able to easily use.

• The article posted was very informative and useful. You people are doing a great job. Keep going.

• omg! can’t imagine how fast time pass, after August, ber months time already and Setempber is the first Christmas season in my place, I really love it!

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

• ’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!..

• Great job, I was doing a google search and your site came up for homes for sale in Altamonte Springs, FL but anyway, I have enjoyed reading it, keep it up!

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

• I recently found many useful information in your website especially this blog page. Among the lots of comments on your articles. Thanks for sharing.

4. transfert vhs

• really amazing topic

• Visit here says:

Hey, you used to write wonderful, but the last few posts have been kinda boring… I miss your tremendous writings. Past few posts are just a little out of track! come on!

5. 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!

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

7. 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

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

9. 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

10. seo new york says:

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

11. 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

12. Oliver Harries says:

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

Total Curve Herbal Breast Pills

13. Golden Slot says:

Thanks for the good information you give them.

• Hairloss says:

Wonderful write up. Thanks for the information you feed us

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

15. 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!

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

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

18. 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

19. 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

20. Jc says:

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

21. 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

22. 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

23. 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.

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

25. his comment is here says:

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

26. 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

27. 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

28. 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

29. dog insurance says:

30. 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

31. 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

32. 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

33. 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

34. clash royale cheat says:

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

35. 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

36. buy lol elo boost says:

Is it okay to post part of this on my website basically post a hyperlink to this webpage? buy lol elo boost

37. vfx body scam says:

It’s really an incredible to read an article like this.I am searching for a great blog to gather some information for writing an article, and i’m glad i came across your blog. vfx body scam

38. www.ahliasamurat.com says:

I definitely really liked every part of it and i also have you saved to fav to look at new information in your site. http://www.ahliasamurat.com

39. look these up says:

I am always searching online for articles that can help me. look these up

40. hotsboosters says:

I really loved reading your blog. It was very well authored and easy to understand. Unlike other blogs I have read which are really not that good.Thanks alot ! https://hotsboosters.com

41. backpackingThailand says:

Unlike other blogs I have read which are really not that good.Thanks alot ! http://www.backpackingThailand.ca

42. http://lostbeachestravel.blogspot.com says:

I have added and shared your site to my social media accounts to send people back to your site because I am sure they will find it extremely helpful too . http://lostbeachestravel.blogspot.com

You make this data intriguing and locks in. You give perusers a ton to consider and I welcome that sort of composing. http://smartersoloads.tumblr.com

44. related articles 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 related articles

45. Maxican word of the day meme says:

Awesome and interesting article. Great things you’ve always shared with us. Thanks. Just continue composing this kind of post. Maxican word of the day meme

46. Useful information… I am very happy to read this.. thanks for giving us this useful information. Fantastic walk-through.

47. check this url says:

I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. Thanks… check this url

48. roundup pro msds sheet says:

Thankyou for this wondrous post, I am glad I observed this website on yahoo.
roundup pro msds sheet

49. Twana says:

Hawker tour is one of the best and I really love it. Penis Enlargement

50. great post to read says:

This information is magnificent. I understand and respect your clear-cut points. I am impressed with your writing style and how well you express your thoughts. great post to read

51. Nellie says:

Singapore is the best place for visit in summer reason. last longer in bed pills

52. jacklin says:

Another model that is extremely adaptable is expediting or item and administration arbitrage. yandere simulator

53. jacklin says:

Numerous administration suppliers like scholars, developers, web creators, among other people who originate from Third World nations can give modest purchase amazing administration.clash of clans hack

54. jacklin says:

In the event that you can discover cheap administration suppliers, however with much better quality then those offering comparable administrations and items in the USA or your present area, match them up with individuals in the group who require their administrations, expediting or arbitrage might be a decent wellspring of income for you and yours. bus simulator 2016

55. nuning says:

Golden Slot

The information you provide is information that is useful to me, not ever.

56. website says:

This is a truly good site post. Not too many people would actually, the way you just did. website

57. Pheromones Authority says:

Good post but I was wondering if you could write a litte more on this subject? I’d be very thankful if you could elaborate a little bit further. Appreciate it!
Pheromones Authority

58. Movies says:

Good post but I was wondering if you could write a litte more on this subject? I’d be very thankful if you could elaborate a little bit further. Appreciate it!
Movies

59. grabe says:

Hello I am so delighted I located your blog, I really located you by mistake, while I was watching on google for something else, Anyways I am here now and could just like to say thank for a tremendous post and a all round entertaining website. Please do keep up the great work.
http://www.grabe.com.br

60. get musically followers says:

This is a truly good site post. Not too many people would actually, the way you just did. get musically followers

61. update status says:

Impressive web site, Distinguished feedback that I can tackle. Im moving forward and may apply to my current job as a pet sitter, which is very enjoyable, but I need to additional expand. Regards.
update status

62. https://www.igotbiz.com/saftland says:

Nice to be visiting your blog once more, it has been months for me. Well this article that ive been waited for therefore long. https://www.igotbiz.com/saftland

63. Pokemon GO Hack says:

This article was written by a real thinking writer. I agree many of the with the solid points made by the writer. I’ll be back.
Pokemon GO Hack

64. find out more says:

This was a really great contest and hopefully I can attend the next one. It was alot of fun and I really enjoyed myself..
find out more

65. liquid diet foods says:

Great knowledge, do anyone mind merely reference back to it
liquid diet foods

66. Vikram says:

you will not be disappointed fast result seo company in noida great service

67. Tommy says:

thanks for sharing such information online email extractor site

68. This tour is going to be awesome.

69. I also like to tour like this.

70. julie says:

71. wevibali says:

Take a short tour of Europe and come back soon.
Young Body Reboot by Drew Allen

72. xukusoyo says:

Go to the island and see people living there.
The Survive In Bed Reviews

73. Felisha says:

I also want to get into this Hawker tour. Tubeloom Plan

74. Indiana says:

I also want to go for Hawker tour. Read More

75. Johnna says:

My friend is on Hawker tour and he is really enjoying it. Read More

76. Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place..

77. Mari Jaus says:

Good article it’s really a great one.

78. Quantum is really important for us. I love it.

79. I want to permit articles integral custom previously the directly appointment to tale for some cashs that ability demand to be made. The qualities of a excellent article on your announce lift to standard the rate.

80. It is really wonderful to see I find it great.

book in it or something

82. it is amazing site i am very impressed your work keep it up dear and sharing a more amazing topic thanks again

83. innoxent says:

This site is very powerful quantum is important for us you should share more good topics thanks

84. IP Hider Pro says:

Fabulous post keep sharing us that type of post.

85. 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!

86. It proved to be Very helpful to me. Thank you so much And I hope that other readers will also experience how I feel after reading your article.

87. The interesting and informative posts inspired me very much. Your post is one of those. You are doing the great job. Keep it up.

88. Thanks so much for sharing this awesome info! I am looking forward to see more postsby you!

90. It was a very helpful information will be expect more of that.

91. Thank you a bunch for sharing this with all of us you actually realize what you are talking about! Bookmarked. Please also seek advice from my site =). We could have a hyperlink change contract between us!

92. You guys like the naruto or anime movie, just see our list good song

93. The biggest topic I have read on the internet. Please keep on posting.

94. I want to learn this kind of style of writing. Please give me hints on how to achieve this.

95. I came onto your blog while focusing just slightly submits. Nice strategy for next, I will be bookmarking at once seize your complete rises

96. I imagine that much obliged for the valuabe data and bits of knowledge you have so given here.

97. Great post full of useful tips! My site is fairly new and I am also having a hard time getting my readers to leave comments. Analytics shows they are coming to the site but I have a feeling “nobody wants to be first”.

98. You’ve got some interesting points in this article. I would have never considered any of these if I didn’t come across this. Thanks!.

99. Amazing details it its truly useful and amazing update us as often as possible with new enhancements

101. I really got into this article. I found it to be interesting and loaded with unique points of interest. I like to read material that makes me think. Thank you for writing this great content.

102. Thanks for sharing these info with us! this is a great site. I really like it. Thank you for the site. May God bless you in all your works.

103. dripex says:

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. If possible, as you gain expertise, would you mind updating your blog with more information? It is extremely helpful for me.

104. asdf says:

sgdhhggrhh

105. If more people that write articles really concerned themselves with writing great content like you, more readers would be interested in their writings. Thank you for caring about your content.

106. Thanks so much for this information. I have to let you know I concur on several of the points you make here and others may require some further review, but I can see your viewpoint.

107. I have been checking out a few of your stories and i can state pretty good stuff. I will definitely bookmark your blog

108. It’s appropriate time to make some plans for the future and it is time to be happy. I have read this post and if I could I wish to suggest you few interesting things or advice. Perhaps you could write next articles referring to this article. I desire to read even more things about it!

109. Really impressed! Everything is very open and very clear clarification of issues. It contains truly facts. Your website is very valuable. Thanks for sharing.

110. He left behind the prayer rug so that anyone clever enough would see the pattern and escape. Here are several things you are able to do to prevent these types of situations:.
In certain emergency situations, the availability of an expert locksmith in Delta BC is really helpful for the users.
frankfurt oder restaurant

111. Elder Auto says:

I really thank you for the valuable info on this great subject and look forward to more great posts

112. New site is solid. A debt of gratitude is in order for the colossal exertion.

113. This is my first time i visit here and I found so many interesting stuff in your blog especially it’s discussion, thank you.

114. Hi, I log on to your new stuff like every week. Your humoristic style is witty, keep it up

115. Excellent work done by you once again here. This is just the reason why I’ve always liked your work. You have amazing writing skills and you display them in every article. Keep it going!

pleased, even when it sounded a bit too fantastic to be real, and decided to obtain a review copy
soon. And it was the best decision! I think this
is certainly the course that has helped me quite possibly the most in comprehending the law of attraction the
best and to have the ability to place it to good use, so I truly am grateful to
the creator for placing it together.

117. It is imperative that we read blog post very carefully. I am already done it and find that this post is really amazing.

118. Robinjack says:

I have perused a couple of the articles on your site now, and I truly like your style of blogging. I added it to my top picks blog webpage list and will be returning soon. If it’s not too much trouble look at my site too and let me comprehend what you think. lebanon escort girls

119. We have noticed that credit restoration activity ought to be conducted with techniques. If not, you could possibly obtain yourself endangering your rank. In order to realize your aspirations in fixing your credit rating you must confirm that from this moment in time you pay all of the monthly dues promptly in advance of their planned date. It is significant on the grounds that by not accomplishing that, all other steps that you will decide to try to improve your credit positioning will not be effective. Thanks for expressing your ideas.
hotels frankfurt-oder

120. This knowledge.Excellently written article, if only all bloggers offered the same level of content as you, the internet would be a much better place. Please keep it up.

121. Hi there, I found your blog via Google while searching for such kinda informative post and your post looks very interesting for me

122. Cool you write, the information is very good and interesting, I’ll give you a link to my site.

123. I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post.

124. Thank you for the post. I will definitely comeback.

125. Excellent post. I was checking constantly this weblog and I am impressed! Extremely helpful information specially the final part I take care of such info much.
I used to be looking for this certain info for a very lengthy time. Thank you and good luck.

126. Please let me know if you’re looking for a writer for your site. You have some really great posts and I feel I would be a good asset. If you ever want to take some of the load off, I’d really like to write some articles for your blog in exchange for a link back to mine. Please blast me an email if interested.Cheers!
coimbatore architects list

127. I have a venture that I’m just now operating on, and I have been on the look out for such information.

128. I personally like your post; you have shared good insights and experiences. Keep it up.

129. I am really enjoying the theme/design of your site.
Do you ever run into any internet browser compatibility issues?
A small number of my blog audience have complained about
my site not working correctly in Explorer but looks great
in Safari. Do you have any solutions to help fix this issue?
moviestarplanet hack

130. I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business.

131. Wow, cool post. I’d like to write like this too – taking time and real hard work to make a great article… but I put things off too much and never seem to get started. Thanks though.

132. A simple bookmarking tool that makes it easy to save, organize and share your favorite web pages. Access your bookmarks from any computer, phone or tablet. Listango works on all modern web browsers…

133. Eziday says:

After Reading your post i really impress for this.I personally like your post; you have shared good insights and experiences. Keep it up. thanks for sharing a awesome post.

134. Anum balouch says:

I read your post. i really surprise for this post. i like it .thanks for sharing.
photo-recovery-2017

135. I am so happy to read this. This is the kind of manual that needs to be given and not the random misinformation that’s at the other blogs.