Return to Index
Operations Research Models and Methods
Problems Section
Network Flow Programming Models
 - Variations on the Shortest Path Problem

The picture below shows a traffic network. The arrows indicate directions of allowed travel. Each arc has a travel time t(i, j). These times are known, but are not shown on the network. You have a minimum cost flow algorithm that has the parameters (lower bound, upper bound, cost) for the arcs, and [fixed external flow] for the nodes. Show the network models that will solve the problems given below (one model for each part).

a. Find the shortest time route from node 1 to node 16

b. You want to send two vehicles from 1 to 16, but the two must take entirely different paths. The two paths must not use the same nodes or the same arcs. The total time for the two vehicles is to be minimized.

c. Each arc has a capacity c(i, j), which is the number of vehicles that can travel on that arc. In addition, every node except node 16 has a supply of vehicles, where b(i) is the number of vehicles at node i. Show the model that would determine the maximum number of vehicles that could be delivered to node 16 without exceeding the capacities on the arcs or the vehicles available at the nodes.

d. As in part a, you want to direct a single vehicle through the network from 1 to 16. The goal is to minimize total time of travel. In addition, we have the constraint that the path taken by the vehicle must use at least five arcs. Show the mathematical programming model (objective function and constraints) that will find this solution.

Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2001 - All rights reserved