Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

TR-GY 7013: Urban Transport & Logistics Systems

Fall 2023

Assignment #4

This assignment part is worth 10 points.

Q1. (2 pts) Use the branch and bound algorithm to solve the following MIP. You can use any solver for the associate LPs.

(a) Present a summary of the branching and bounding updates in a table, where each row can be a branch that is solved next, with a column indicating the preceding node (i.e. if L3 follows L1 then L1 would be the predecessor), the LP solution and objective value, and most updated UB/LB.

(b) If you were to stop the algorithm at a gap of 5%, would your solution change? Why or why not?

Q2. (2 pts) Consider a depot located at (0,0) assigned to visit 20 other locations in a rectangular region 3 miles x 5 miles long. (the data is also located on the accompanying spreadsheet “Assignment 4 Worksheet”, tab Q2 & Q3)

a) Find a solution to the 21-node TSP based on minimizing Euclidean distance using Christofides’ heuristic. Plot it on the graph.

b) Solve the TSP using nearest neighbor heuristic. Plot it on the graph and compare the solutions’ tour lengths.

Q3. (3 pts) For the problem in Q2, consider each node now has a demand between 1 – 5 (shown below), and vehicles have a capacity of 6 units.

(a) Use Clarke-Wright savings method to find a solution to a capacitated VRP. Plot it on the graph.

(b) Analyze your solution and propose a second depot location and split your nodes between that second location and the initial depot at (0,0). Recompute the TSP solution for each of the two subproblems using C-W savings again to determine the change in total operating miles – the new depot location would be worth investing if its cost is less than this amount.

Q4. (3 pts) For the Sioux Falls network in Assignment 2, I have specified the demand at each node and the travel times along the shortest paths between each node pair in the accompanying spreadsheet “Assignment 4 Worksheet”, tab Q4. Assume that the travel times are in minutes.

(a) Locate 3 facilities using p-median approach via Teitz & Bart’s greedy heuristic. Plot the solution (facility locations and demand allocations) and the objective value.

(b) Locate 3 facilities using maximal covering location problem with a threshold of 10 minutes. Plot and compare the solution with (a).

(c) For the solution in (a), which facility is most critical? i.e. if it was removed, you would have the remaining facilities in place, and a demand assignment problem to the closest location. Provide a measure of this criticality.