RobustShortestPath.jl
Robust Shortest Path Finder for the Julia Language.
This package provides functions to find robust shortest paths. Please see the reference papers below.
Install
julia> Pkg.add("RobustShortestPath")
This will also install LightGraphs.jl, if you don't have it installed in your Julia system already.
To check if works
julia> Pkg.test("RobustShortestPath")
get_robust_path
This function solves the robust shortest path problem proposed by Bertsimas and Sim (2003) and integrates the idea of Lee and Kwon (2014).
get_robust_path_two
This function solves the robust shortest path problem with two multiplicative uncertain cost coefficients proposed by Kwon et al. (2013).
Example
Example network and data from Kwon et al. (2013):
The above network data should be prepared in the column vector form as follows:
data = [
1 4 79 31 66 28;
1 2 59 97 41 93;
2 4 31 21 50 40;
2 3 90 52 95 38;
2 5 9 23 95 59;
2 6 32 57 73 7;
3 9 89 100 38 21;
3 8 66 13 4 72;
3 6 68 95 58 58;
3 7 47 12 56 20;
4 3 14 19 36 84;
4 9 95 65 88 42;
4 8 88 13 62 54;
5 3 44 8 62 53;
5 6 83 66 30 19;
6 7 33 3 7 8;
6 8 37 99 29 46;
7 11 79 54 23 3;
7 12 10 37 35 43;
8 7 95 71 85 56;
8 10 0 95 16 64;
8 12 30 38 16 3;
9 10 5 69 51 71;
9 11 44 60 60 17;
10 13 79 78 16 59;
10 14 91 59 64 61;
11 14 53 38 84 77;
11 15 80 85 78 6;
11 13 56 23 26 85;
12 15 75 80 31 38;
12 14 1 100 18 40;
13 14 48 28 45 33;
14 15 25 71 33 56;
]
start_node = data[:,1] #first column of data
end_node = data[:,2] #second column of data
p = data[:,3] #third
q = data[:,4] #fourth
c = data[:,5] #fifth
d = data[:,6] #sixth
For a single-coefficient case as in Bertsimas and Sim (2003):
using RobustShortestPath
Gamma=3
origin=1
destination=15
robust_path, robust_x, worst_case_cost = get_robust_path(start_node, end_node, c, d, Gamma, origin, destination)
The result will look like:
([1,4,8,12,15],[1,0,0,0,0,0,0,0,0,0 … 0,0,0,0,0,0,1,0,0,0],295)
For a two-coefficient case as in Kwon et al. (2013):
using RobustShortestPath
Gamma_u=2
Gamma_v=3
origin=1
destination=15
robust_path, robust_x, worst_case_cost = get_robust_path_two(start_node, end_node, p, q, c, d, Gamma_u, Gamma_v, origin, destination)
The result should look like:
([1,4,3,7,12,14,15],[1,0,0,0,0,0,0,0,0,1 … 0,0,0,0,0,0,0,1,0,1],25314.0)
See runtest.jl for more information.
get_shortest_path
This package also provides an interface to dijkstra_shortest_paths
of LightGraphs.jl
.
path, x = get_shortest_path(start_node, end_node, link_length, origin, destination)
Contributor
This package is written and maintained by Changhyun Kwon.