Sites.ualberta.ca



MGSTC 461 – Quiz 2

November 18, 2008

Time: 90 minutes

Instructions:

1. Download the data from the course homepage. Immediately save this sheet onto a thumbdrive and give it a name that allows me to identify whose it is (eg “quiz2_lastname.xls”). I highly recommend working from a thumbdrive or your AFS disk space, since if there is a problem with your computer you can easily move to another machine and continue working with minimal interruption.

2. The spreadsheet file has one worksheet named “answers.” All of the answers I ask you to provide should go on this sheet, in the spaces provided. Any additional work you want to present for part marks should be left on your original “working” sheet.

3. When you are finished, save a copy of the file for yourself and upload a copy to the course dropbox. Remember that if you “add” the file, you must then “send” it. I will confirm that the file has made it to the dropbox before you leave the room.

4. There is NO COMMUNICATION of any kind allowed between students, electronic or otherwise. The only applications you should have open on your computer are a web browser (pointing to the course homepage) and Excel.

5. All questions can be answered by referring to MGTSC 461 course notes and/or the notes you have taken during lecture. The use of outside sources (e.g. Google searches, etc) is permitted but discouraged.

6. Allocate your time accordingly. A rough guide is to allot one minute per point, so you can be done at about the 75 minute mark. At the 90 minute mark I will require all students to have uploaded to the course webpage and will not consider further submissions.

7. SAVE OFTEN!

Problem 1: Multiple Choice Questions [10 pts]

1. When compared to the travelling salesman problem with n nodes, vehicle routing problems with n nodes are:

a. Computationally easier to solve, since each tour in the VRP has fewer nodes than the TSP.

b. Computationally the same, since there is an equal number of customer nodes.

c. Computationally harder, since you must determine both who is on which tour and how to build the tours.

d. Computationally the same or harder, depending on the tour constraints.

2. The Hakimi Property states that

a. If we restrict our search to nodes only, the best we can guarantee is an answer within (2/N) percent of optimal, where N is the number of nodes

b. The only optimal solution to the P-median problem is one where all facilities are located at nodes

c. One of the potentially multiple optima has facilities located solely at nodes

d. None of the above

3. A feasible tour for a travelling salesman problem with 45 cities (including the “home” city) has

a. 27 arcs

b. 44 arcs

c. 45 arcs

d. 990 arcs

4. Complete enumeration of an uncapacitated, cost-minimizing 10-Median problem with 40 candidate facility locations requires how many solution evaluations?

a. 3,075,990,524,006

b. 847,660,528

c. 8.15915 * 1047

d. Impossible to tell without knowing the number of customers

5. Having a unimodular matrix in your problem means that

a. There is only one optimal solution to the problem

b. You can break the problem down (modular) and employ a “divide and conquer” approach

c. Integer inputs result in integer outputs

d. The problem is unicyclical

Problem 2: P-Median [15 pts]

Let Xj be a binary variable that takes the value 1 if a facility is located at j and 0 otherwise. Let Yij be a binary variable that takes the value 1 if customer i is served by facility j and 0 otherwise. Let hi be the demand at customer i. Let tij be the distance from customer i to facility j. Assume for this problem that the monthly fixed cost of locating facilities is the same for all locations.

a) Say you have three customers (1, 2, and 3), and four candidate facilities (A, B, C, and D). Write out the objective function for the linear p-median problem. For example, “XA * t12 * Y13 + XB * hB5 * XA2 + …” (note: the example is not correct). How many changing cells will you have for the problem? You don’t have to worry about subscripts here; I’ll assume that YA3 is YA3.

b) Write out the constraint that ensures customer 3 is served by a single facility.

c) If you have m customers and n candidate locations, how many changing cells will you have in your problem? How many linking constraints (which prohibit assigning customers to unopened facilities)? How many assignment constraints?

d) Suppose you eliminate the constraint that a customer must be served by a single facility. Instead, assume that a customer can be supplied from more than one facility. What changes would you have to make to the objective function, changing cells, or constraints? You need only describe your answer, not implement it.

Problem 3: Travelling Salesman Problem [25 pts]

The following diagram shows a completed tour resulting from an unknown tour construction heuristic (left-hand side):

[pic]

Information about the X and Y coordinates of each node is given in the sheet marked “Problem 3” of the quiz data set. Distances are rectilinear with k = 2. The distance matrix is symmetric.

a) What is the length of the tour shown above?

b) We will perform a 3-opt improvement heuristic on arcs BD, CE, and AH. Start by removing the three arcs listed. What is the total length of the three arcs you removed? (Note – this might be a good time to draw the 5 remaining arcs on the blank network on the right hand side.)

c) List all the possible ways to reconnect the graph to make a feasible tour. For example, “BD CE AH” is one possible reconnection; it’s the one you just removed. There are a total of eight possible reconnections, including the tour you started with. For ease of marking, list each possibility on one line in the answer sheet, as a triplet of letter pairs like I have above.

d) For each of the seven “new” reconnections, report the total length of the three arcs you’re adding, and whether or not the new reconnection is better than the tour you started with in part 1. Report the full route of the reconnection that results in the lowest total route length.

Problem 4: Vehicle Routing Problem [25 pts]

The U of A’s mail services branch has heard about our work in MGTSC 461 and has asked us to find efficient delivery routes for intercampus mail delivery to 37 offices around the campus. They have provided office location coordinates (in meters) based on a campus map maintained in ArcGIS. You can find these coordinates in the sheet “Problem 4” from your Excel workbook. The main post office is located at (132, 49). Each office has an estimated number of kilograms of mail, which is specified in the “quantity” column. Distances are rectilinear.

There are some constraints imposed into the tour formation: first, occupational health and safety dictates delivery people can carry at most 20 kg in their bags at any one time. Moreover, each delivery person visits at most 8 offices per trip. There is no specific constraint on the tour length.

a) The worksheet “Problem 4” has a partial list of the potential savings achieved by combining one-node tours (depot – node – depot) together. How many potential savings calculations would have to be made for this problem?

b) Calculate the savings achieved by combining a tour from the depot to office 12 and back, with a tour from depot to office 36 and back. Explain, based on the coordinates for the depot and nodes 12 and 36, why this savings amount is the highest. (hint: a quick sketch of the three nodes helps here, though I do not need to see the sketch.)

c) The two constraints (number of stops and bag weight) help us to identify a lower bound on the number of tours that will be created. Calculate the lower bound for each constraint and explain which is the lower bound for the overall problem.

d) I have started implementing the Clarke-Wright savings algorithm for the problem, and interim progress is shown on the sheet “Problem 4.” For the first 17 tour combinations considered, I have shaded the row in BLUE if the combination was accepted and RED if the combination was rejected. For the next four savings on list, determine whether or not to accept or reject the combination. If you accept, explain what you do. If you reject, explain why.

e) The worksheet also shows the tours after 497 possible savings have been considered. Do we need to continue checking for further savings? Explain why or why not.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download