I start to work with stochastic TSPTW. I have no experience with it (and with stochastic programming/probability world even I like this field). My advisor suggested that I should start with a formulation that has some discrete probability.

I found a paper The Fastest Path through a Network with Random TimeDependent Travel Times that fits what I am looking for at this step; they have an example saying that there are two paths between A and B. The first one is with the probability of 0.5, and travel time 90, The second one is with the probability of 0.5, and travel time 120, etc.

I will continue my searching/reading, however, I would like your suggestions and comments about some papers having mathematical formulations of shortest-path problems (or TSP/TSPTW) with probability constraints as the above. (The paper I cited prior does not have the formulation) It would help me much.

asked 19 Oct '16, 16:23

Duc%20Minh%20Vu's gravatar image

Duc Minh Vu
accept rate: 0%

You question reminded me 'Canadian Travelers problem', the road(arc) can be blocked by snowfall but you will no know until you arrive there.

However, if you google "stochastic Traveling salesmen Problem (Time Windows)" you can find a lot of articles.


answered 23 Oct '16, 19:49

ksphil's gravatar image

accept rate: 14%

Many thanks, I take a step back by reading stochastic vehicle routing problem. Regarding stochastic TSP, almost problems are belong to probabilistic ones (the one with probability of visiting each customer), and there is no (good) review. However, by reading stochastic VRP, I have a better view on the model steps (chance constraint models/recourse models) with stochastic travel times, and then how one evaluates/handles the expected terms.

(24 Oct '16, 18:52) Duc Minh Vu
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 19 Oct '16, 16:23

Seen: 550 times

Last updated: 24 Oct '16, 18:52

OR-Exchange! Your site for questions, answers, and announcements about operations research.