Assignment 5, Q5

5. (20 marks) A furniture store at location 0 has deliveries to make to customers at locations 1, 2, 3, and 4. The time in minutes that it would take a truck to travel from one location to another is given in the following table. Because of one-way streets and places where no left-turn are allowed, or are difficult to make, the table is not symmetric. From To 0 1 2 3 4 O 0 22 34 42 30 25 0 16 32 18 29 17 0 28 22 45 36 30 0 15 28 20 25 14 0 The objective is to minimize the total travel time. (a) Give the algebraic model of this situation, omitting the sub-tour constraints. (b) Use LINGO or the Excel Solver to solve this (partial) model. Show that this solution is not a tour, and state the two sub-tours. (c) Give a constraint that would, if added to the formulation of (b), prevent this specific situation from arising. Re-solve the computer model, and state whether or not this new solution is a tour