Author Topic: Travelling Salesman, Chinese Postman... real world data sources?  (Read 723 times)

0 Members and 1 Guest are viewing this topic.

Offline InfravioletTopic starter

  • Super Contributor
  • ***
  • Posts: 1185
  • Country: gb
I've been looking up some stuff about various geographically themed problems in mathematics (Traveling salesman, visit each roundabout) (Chinese Postman, cover all lengths of street) (this sort of thing https://www.chrispanza.com/blog/shortest-route-cover-all-roads or https://www.geeksforgeeks.org/traveling-salesman-problem-tsp-implementation/)and wondering about what it would be like to try on real-world rather than made-up road networks.

Does anyone know if there are freely available datasets of this kind for UK roads? Or have any idea how one might convert from something like open street map in to a data format which could then be run in to the many algotihms available to try to solve rtavelling salesman and chinese postman style problems.

Clearly this sort of thing is done behind the scenes on any route-planning website, but is there an available data souce to do it for yourself for real-world routes?

Thanks
 

Offline InfravioletTopic starter

  • Super Contributor
  • ***
  • Posts: 1185
  • Country: gb
Re: Travelling Salesman, Chinese Postman... real world data sources?
« Reply #1 on: January 05, 2023, 07:44:27 pm »
Does anyone have thoughts on this?
Thanks
 

Offline EggertEnjoyer123

  • Frequent Contributor
  • **
  • Posts: 335
  • Country: us
Re: Travelling Salesman, Chinese Postman... real world data sources?
« Reply #2 on: January 05, 2023, 07:59:42 pm »
https://www.openstreetmap.org/
https://wiki.openstreetmap.org/wiki/Downloading_data

Try this

Also I'm pretty sure commercial GPS systems use heuristics (go to small road -> big road -> freeway -> big road -> small road)
 

Offline sokoloff

  • Super Contributor
  • ***
  • Posts: 1799
  • Country: us
Re: Travelling Salesman, Chinese Postman... real world data sources?
« Reply #3 on: January 05, 2023, 08:08:55 pm »
Related, maybe useful tool:
https://citystrides.com/

Related video of a guy who did this in Pittsburgh:
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf