Problem 4) Application of Binary Programming in Netork Shortest Path Problem ram

Question

Problem 4) Application of Binary Programming in Netork Shortest Path Problem ramming in Network Problems: from the The following is the road network representation of a cross-country trip origin (Boston) to the destination (Los Angeles) BOSTON, MA CLEVELAND, OH DENVER, co ST. LOUIS, MO LOS ANGELES, CA S ATLANTA, GA HOUSTON, TX The travel time (hours) between every pair of cities is shown in the table below: To Boston Cleveland Denver St. Louis Atlanta Houston L.A 18.5 Boston Cleveland Denver 17 n/a n/a n/a n/a 35 n/a 20.5 n/a n/a n/a 16 n/a 21 n/a n/a n/a n/a 9.5 n/a n/a n/a From St. Louis 1-295 Atlanta Houston L.A. n/a 13 n/a The goal is to minimize is the total travel time from the origin to the destination (know the shortest path problem). We would like to use a variant of the transportation mod binary variables) to formulate this problem. (Problem 4 continued on the next page)

Explanation / Answer

a.

Decision variable:

Xij­ = 1, the route from node i to node j is chosen in the optimal path otherwise Xij­ = 0

Objective Function:

Minimize the total distance travelled:

Min. Z = ?(cij)(Xij)

Where, cij = distance between the ith arc and jth arc
Min Z. = 11X12 + 18.5X14 + 17X15 + 20.5X23 + 35X27 + 16X37 + 11X46 + 29.5X47 + 9.5X54 + 13X56 + 21X67

b.

Constraint:

For shortest route problem, following constraint are to be satisfied,

For origin Node 1, outgoing arc is equal to 1,

X12 + X14 + X15 = 1

For intermediate nodes,

Arc in = arc out

For node 2: X12 = X23 + X27   or X12 – X23 – X27 = 0  

For node 3: X23 = X37   or X23 – X37 = 0

For node 4: X14 + X54 = X47 + X46   or X14 + X54 – X47 – X54 = 0

For node 6: X46 + X56 = X67   or X46 + X56 – X67 = 0

For destination node:

Arc in = 1

For node 7, X37 + X27 + X47 + X67 = 1

Formulation:

Min Z. = 11X12 + 18.5X14 + 17X15 + 20.5X23 + 35X27 + 16X37 + 11X46 + 29.5X47 + 9.5X54 + 13X56 + 21X67

Subject To:

X12 + X14 + X15 = 1

X12 – X23 – X27 = 0  

X23 – X37 = 0

X14 + X54 – X47 – X54 = 0

X46 + X56 – X67 = 0

X37 + X27 + X47 + X67 = 1

c.

If chosen path should be passed through Houston, then following constraint should be added:

X67 = 1

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.