A transport company must collect and deliver loads from and to various locations along a straight road (call it the x -axis). The truck must start and end each day at the origin (that is at x = 0). Furthermore, the truck can only carry a single load at a time, and must complete one job before carrying out the next one. Suppose in one day there are N jobs with collection and delivery points: (c1; d1); (c2; d2); : : : ; (cN; dN). So, for example, if N = 2 and the jobs are (2; 4) and (1; 5), and the truck dealt with the second job ¯rst, its path would be: 0, 1, 5, 2, 4, 0. Whereas, if the first job was done first, the path would be: 0, 2, 4, 1, 5, 0. Note that the total distances travelled are 14 and 16, respectively.

We must decide how to sequence the jobs to minimize the total distance travelled.

1. Model this problem as an integer linear program, and more specifically as an example of a travelling salesperson problem. Your solution should include precise definitions of your decision variables, constraints and objective function. For example: let xij = 1 if load j is processed immediately after load i and xij = 0 otherwise.

2. Construct a small numerical example, and use your model and Excel Solver to generate a travel plan for your example. Your assignment submission should be in pdf format and should include the model for part 1, details of the Solver model for part 2 and the numerical solution.