Homework



MGTSC 461 Assignment 3

Due: Friday, November 14, 11:59 PM

Submit via Digital Dropbox on Course Webpage

70 points total

Problem 1 [20 points]

a) Using the data set provided in worksheet “Problem 1” of the data file, set up the 3-Median model in a spreadsheet. All 60 nodes are customers, but only those nodes whose index is a multiple of 6 (node 6, 12, 18, etc) are potential facility locations. Distances are Euclidean, and k=1 will give you kilometer distances. Assume that customers are assigned to their nearest facility. The fixed cost of locating at a facility is equal to $2 multiplied by that location’s population, and transportation costs are $0.40 per km traveled. Ignore return trip distance.

Using {6, 18, 42} as a starting solution, perform two iterations of the Teitz-Bart heuristic. The first iteration should fix the second and third nodes, and attempt all swaps of the first node with nodes not already in the solution. Accept whatever swaps improve the solution. The second iteration should start with the best solution you got from iteration 1. Fix the first and third nodes and attempt swapping out the second node. Report your selected facilities and cost for the initial solution, the best solution after the first iteration, and the best solution after the second iteration.

b) Suppose that each facility has an upper limit of 115,000 customers assigned. You now need to come up with a more sophisticated method for assigning customers to facilities. Your solution should assign customers to a single facility. This constraint makes it much more difficult to solve a problem to optimality.

Devise and explain a policy for allocating customers to facilities without violating the capacity constraints. Your method should focus either on minimizing total cost or balancing workloads across facilities. Implement your method for the candidate solution {18, 36, 54}. Report the number of customers served by each facility and the total cost of transportation.

Problem 2 [15 points]

The data given in the worksheet “Problem 2” of the data file is the same data that was used to create the handout from the October 28 class. Find the best possible solution you can to the TSP with this data. You can plot the problem on a piece of paper, trace out a solution that looks good to you, and record the route you’ve chosen. Alternatively, you can use one of the construction or improvement heuristics we covered in class, or download and use Concorde.

The grade you receive for your solution will be based on how far you are from the optimal solution. You get full marks if within 1% of optimal, 12/15 if within 3% of optimal, 9/15 if within 5% of optimal, and 4/15 if within 50% of optimal. Solutions that are not proper tours, or which are more than 50% away from the optimal solution, receive 0 points. Explain what techniques you used to arrive at your solution.

Please submit your best tour as a sequence of node numbers that start from 1 and end with a return to node 1. Your list should be easy to copy-paste into Excel.

Problem 3 [35 points]

You have been approached by CrazyFruit, a BC-based fruit grower’s cooperative. They’re launching a brand new hybrid fruit – the plappear – to Edmonton region stores, and they have asked for your help to make some key supply decisions.

CrazyFruit has secured valuable shelf space at 18 high-end grocery stores and market stalls in the Edmonton region. They have also scouted out 10 local growers who are willing to stock plappears and distribute the fruit.

Each store has a yearly demand for plappears (in bushels), and each grower has a yearly supply capacity (also in bushels) based on available physical space. Note that stocking a grower means you must provide the capacity requested; think of these figures as both an upper bound on physical space and a minimum volume that the grower will accept. CrazyFruit has not approached these growers to hear their terms, but has estimated some yearly fixed costs based on market research.

You have been provided with the following data:

• A set of nodes with X and Y coordinates (coordinates are in kilometers);

• A link list describing the road network connecting the nodes (links are bidirectional, so if A-B is in the list, B-A is also possible);

• A list of nodes where stores are located, with yearly demand (in bushels); and

• A list of potential growers, with yearly supply capacity and estimated fixed costs (in hundreds of dollars).

Transportation costs (which will be borne by CrazyFruit) are $50 per bushel per kilometre. This cost includes return travel.

a) Set up a transportation problem like the oranges-to-groves example we looked at in the first lecture. To do this you will need to use the X-Y coordinates to establish arc lengths, then use Dijkstra’s Algorithm to find shortest paths from each potential grower to each store. Use Euclidean distances and whatever value of k gives you distances in kilometres. Remember that arcs are bidirectional. Report the distance of the arc from 6 to 15, and the shortest path (and shortest path length) between node 42 and 43.

b) Find the optimal solution to the problem that minimizes total travel cost. Assume all growers have signed contracts for CrazyFruit, so you don’t have to decide which should open and which should not. Stores WILL NOT ACCEPT more plappears than what is demanded. Report the total transportation cost, as well as the origin(s) and number of bushels flowing into node 32. Also, calculate the total amount of unused supply.

Hint: Make sure you check Solver messages carefully. There is a “bug” in the Excel Solver which occasionally returns a “could not find feasible solution” message even though the solution is feasible. Usually, re-running solver (without changing settings) will resolve this. You may want to increase the number of iterations in the Solver options menu as well.

c) CrazyFruit does not want to over-supply the market, which would happen if all growers were contracted to provide plappears. Modify and solve the model so that it chooses both which growers to sign contracts with and the optimal transportation solution. Report which growers are chosen and which aren’t, as well as the fixed costs and transportation costs of the solution. Again, calculate the amount of unused supply.

d) To this point we have assumed that unshipped plappears do not cost CrazyFruit any money. However, because the makeup of the plappear is an industrial secret, CrazyFruit must dispose of any additional supply, at a cost of $100 per bushel. Modify your model to include this cost and solve again, reporting the selection of growers, total fixed costs, total transportation costs, and total disposal costs.

e) What happens to your solution as the total cost of disposal increases? Solve the model and report the total number of bushels that are surplus for the following two cases:

i. Disposal is $300 per bushel;

ii. Disposal is $1000 per bushel.

Can you find a solution where there is no wasted supply?

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

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

Google Online Preview   Download