Uber Canberra has identified 10 primary pickup and drop locations for taxi riders in Canberra city. In an effort to minimise travel time and improve customer service and the utilisation of the companys fleet of taxis, management would like the taxi drivers to take the shortest route between locations whenever possible. Using the following network of roads and streets, what path should a driver beginning at location 1 take to reach location 10? The travel times in minutes are shown on the arcs of the network. Note that there are two one-way streets and that the arrows indicate the direction.

a) Formulate a linear programming model (showing the decision variables, objective function and constraints) that can be used to determine the shortest route between locations 1 to 10.

b) Solve the LP model by Excel Solver using the following network of roads and streets, and determine what path a driver should take to begin at location 1 to reach location 10.

c) What will be the shortest travel time for the selected path?