Consider the undirected network in the figure below for the subsequent path planning problems. Assume that every link has a length of 1. Please clearly define the decision variables, the objective function, and the constraints. You are supposed to enumerate all constraints rather than using generic link/node indices.
2
14
3
- a) Formulate the MST problem on this network.
- b) Find three distinct MSTs for this network.
- c) Formulate the TSP on this network.
- d) Formulate the CPP on this network.
Problem 2
Consider the undirected network 𝐺 = (𝑁, 𝐸) in the figure below for the subsequent facility location problems. The demands are indicated in the figure. Assume that every link is 10 unit long. Please clearly define the decision variables, the objective function, and the constraints. You are supposed to enumerate all constraints rather than using generic link/node indices.
- a) Suppose that a facility must be located at a node. Specify the distance function 𝑑(𝑥, 𝑖) for all 𝑥∈𝑁 andall 𝑖∈𝑁.
- b) Formulate the 2-median problem on this network in terms of 𝑑(𝑥, 𝑖).
- c) Suppose that every facility can serve up to 15 units of demand within a distance of 10 units.
Develop a formulation to find the minimal number of facilities needed.
Problem 3
Consider the bike sharing rebalancing problem (BRP) on the network below. Node 0 is the depot. The demands as well as the link lengths are indicated in the figure. Suppose that every shipping vehicle can carry no more than 2 bikes. Assume that every vehicle can make only one tour.
- a) Suppose that you have infinitely many vehicles to dispatch. Construct a feasible solution to the BRP.
- b) With the fleet size you used in part a), formulate the BRP; please clearly indicate which formulation you use.
- c) What is the minimal size of the rebalancing fleet? Justify your answer.
- d) (bonus) Find (using any method) the optimal solution to the BRP with the fleet size you
identified in part c).
