I'm trying to solve the $\alpha$-reliable shortest path problem with correlated time variables (travel time per arc), i.e. the shortest path subject to the constraint that the probability of arriving before a maximum time $T$ is greater than $\alpha$. I was thinking of modeling all the arc times as a multivariate normal distribution; however I would like to know what are the best practices to do this or literature regarding this subject.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Do you mean "greater than or equal to" not "less than"in "probability of arriving before a maximum time T is less than α." $\endgroup$– Mark L. StoneSep 14 at 13:59
-
$\begingroup$ @MarkL.Stone Already corrected the typo, thx! $\endgroup$– Mathematician....Sep 14 at 14:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Disclaimer: My response is not meant to be an exhaustive list of relevant directions \ publications for the $\alpha$-reliable shortest path problem, but here are a few papers on related problems that can be suggestive of best practices.
I believe your constraint on the arrival time is reminiscent of a chance constraint, dealing with correlated random arc duration variables is however challenging. Under such a setting, the most common approach I have seen is to frame the problem as a Sample Approximation problem with Chance constraints, take a look at [1] for reference. Here, random i.i.d samples from the joint distribution of the arc variables are drawn and then the chance constraint is reformulated using the i.i.d samples. This approach gives rise to some nice probabilistic guarantees on the solution quality. You can also perhaps frame your problem through the lens of Distributionally robust optimization as well which similar to Stochastic Approximation draws samples and provides many useful probabilistic guarantees. Unfortunately, I was unable to locate the most relevant publication for you at this time.
Apart from work in the OR community, there is some work in the AI scheduling community which may be relevant, see [2], [3]. Although the objective in scheduling problems is generally the longest path problem (credits Makespan objective), nevertheless if you are interested in heuristic approaches then the approaches in those papers may give you some ideas. [2] & [3] assume that the arc durations are i.i.d random durations. [2] assumes those r.v.s are Normally distributed while [3] makes fewer assumptions on each r.v. (just assumes the mean and variance and nothing about the distribution).
References
- James Luedtke and Shabbir Ahmed, A Sample Approximation Approach for Optimization with Probabilistic Constraints
- Beck and Wilson, Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations
- Fu, N., Lau, H. C., Varakantham, P., & Xiao, F. (2012). Robust local search for solving rcpsp/max with durational uncertainty.
