Shortest path

The Shortest Path
Problem

The Shortest Path Problem
We have all had some occasion to look at a road
map and try to plan the best route to our
destination.
We usually want to find the route of shortest
distance considering the cost of traveling.
Our objective is to find the shortest path from a
starting point to a destination.
Such problems are called shortest path problems.

TheShortest Path Problem
In the shortest path problem, There are n nodes
beginning with the start node 1 and ending with
the terminal node n.
It differs from the traveling salesman problem in
two ways:
In the shortest path problem,
(1) not every node need to be included on the
selected path, and
(2) we do not return to the start node

The Shortest Path Problem
Example:
Fairway Van LinesCompany is a nationwide
household mover in U.S.
One of its current jobs is to move goods from a
house in Seattle (in Washington) to El Paso (in
Texas).

The Shortest Path Problem
Node
12
13
14
27
28
34
35
47
56
5 10
67
78
7 11
7 12
89
9 12

Node
City
Seattle
Seattle
Seattle
Butte
Butte
Portland
Portland
Boise
Sacramento
Sacramento
Reno
Salt Lake City
SaltLake City
Salt Lake City
Cheyenne
Denver

City
Butte
Portland
Boise
Salt Lake City
Cheyenne
Boise
Sacramento
Salt Lake City
Reno
Bakersfield
Salt Lake City
Cheyenne
Las Vegas
Albuquerque
Denver
Albuquerque

Distance (km)
599
432
497
420
691
432
602
345
138
291
526
440
432
621
102
452

The Shortest Path Problem
Node
10 11
10 13
11 14
11 15
11 16
12 1512 19
13 14
13 16
13 17
14 15
16 18
16 19
17 18
18 19

Node
City
Bakersfield
Bakersfield
Las Vegas
Las Vegas
Las Vegas
Albuquerque
Albuquerque
Los Angeles
Los Angeles
Los Angeles
Barstow
Phoenix
Phoenix
San Diego
Tucson

City
Las Vegas
Los Angeles
Barstow
Kingman
Phoenix
Kingman
El Paso
Barstow
Phoenix
San Diego
Kingman
Tucson
El Paso
Tucson
El PasoDistance (km)
280
114
155
108
290
469
268
138
386
118
207
116
403
425
314

The Shortest Path Problem

The Shortest Path Problem
Management would like to determine the route
of minimum distance from Seattle to El Paso.
This problem can be formulated and solved by
using a standard linear programming module.
Binary decision variables Xij represent utilization
of the highwayfrom city i to city j.

The Shortest Path Problem
Xij is 1 if the truck travels on the highway from city i to
city j. It is 0 if it does not.
The objective is to minimize the total distance that will
be traveled from Seattle to El Paso, Which is found by
summing all the distances (dij) of the highways traveled.
Therefore, the objective function is: Minimize Σ dij
Xij.
The constraintsfor the shortest path model require
that, for each city (excluding starting and ending cities)

The Shortest Path Problem
(The number of highways used to travel INTO
the city) =
(The number of highways traveled WHEN
LEAVING the city).
For example, the constraint for Boise (City 4) is
as formed follows:
X14 + X34 + X74 = X41 + X43 + X47

The Shortest Path Problem
This implies that, IfBoise were on the selected route,
The number of highways traveled when entering into
Boise would be 1, and the number of highways traveled
when leaving Boise would also be 1.
Similarly, If Boise were NOT on the selected route,
The number of highways traveled when entering into
Boise would be 0, and the number of highways traveled
leaving Boise would also be 0.

The Shortest Path ProblemIn addition, we must ensure that the number of highways
traveled out of Seattle (the starting node) is 1, And
That the number of highways traveled into El Paso (ending
node) is 1.
This can be accomplished by adding the following
constraints to the model:
X12 + X13 + X14 = 1 (For the starting city, Seattle)
And
X12,19 + X16,19 + X18,19 = 1(For the ending City, El
Paso).

The Shortest...