8

1

4

2

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

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

02/13/2015

12 days ago

60 commits