Shortest path problem with Excel

Use the solver in Excel to find the shortest path from node S to node T in an undirected network (less constraints in a directed network).

Formulate the problem

To formulate this shortest path problem, answer the following three questions.

  • What are the decisions to be made? For this problem, we need Excel to find out if an arc is on the shortest path or not (Yes=1, No=0). For example, if SB is part of the shortest path, cell F5 equals 1. If not, cell F5 equals 0. (in yellow)
  • What are the constraints on these decisions? The Net Flow (Flow Out – Flow In) of each node should be equal to Supply/Demand. Node S should only have one outgoing arc (Net Flow = 1). Node T should only have one ingoing arc (Net Flow = -1). All other nodes should have one outgoing arc and one ingoing arc if the node is on the shortest path (Net Flow = 0) or no flow (Net Flow = 0). (in light blue)
  • What is the overall measure of performance for these decisions? The overall measure of performance is the total distance of the shortest path, so the objective is to minimize this quantity. (in dark blue)

LP45

Name the following ranges:

Range Name Cells
From B4:B21
To C4:C21
Distance D4:D21
Go F4:F21
NetFlow I4:I10
SupplyDemand K4:K10
TotalDistance F23

And insert the following functions:

LP46

Solve the model

Enter the solver parameters:

LP47

The optimal solution:

LP48

Publicités