University of California Berkeley Small Parcel Delivery Company Worksheet

A small parcel delivery company has its terminal (depot) in downtown Des Moines (node 3) and has sixpackage deliveries to make on a given day (nodes 1, 2, 4, 5, 6, and 7). The Excel template shows the table of distances between all pairs of nodes (in miles).Thecompany wants to find the best route, or the optimal sequence ofvisiting customer nodes, that minimizes the travel distance of thedelivery truck. Your task is to help the company come up with this routeby answering the following questions.

Question 7

How many possible routes are there for this problem?Is this problem symmetric or asymmetric?

Question 8

Currently the driver has been using the route 3-1-2-4-5-6-7-3. What is the distance for this tour?

Question 9

What is the nearest-neighbor heuristic solution to this problem? Note: when you have a tie, choose the node with the smaller node number (for example, if node 1 and node 5 are tie, choose node 1).

Question 10

Determine the optimal traveling salesman tour using the LP method you studied in class. Make sure that you fill the table “Sub-tour elimination constraints” as you solve a series of LPs (follow the example shown in the table, which contain fake data).