ECE3093 Assignment 4: Melbourne 2050
40 Marks worth 7.5% of the final MTH3330 grade. October 2019
Electronic submission of this assignment is due on Moodle by 5pm on Thursday 24 October 2019.
You are required to submit a single-file report in pdf format based on the template provided, and the source code (Matlab/Python/Julia script). The following files are provided:
1. Ass4-Melb2050.pdf: this set of instructions
2. Ass4-template.docx: the template for your report (answers)
3. Ass4-data.xlsx: An excel spreadsheet with data and sheets for generating the graphs from
the solutions you have computed.
Some notes on requirements: You are not required to use Matlab any particular programming language – but in whatever language you choose to implement this please provide the source code. This is an individual assignment – while it is natural to discuss the assignment with other students, your submission must be your own work.
Motivation
When planning for Melbourne in the year 2050, one thing is clear: urban congestion is going to be a major problem. Trucks moving goods across the greater Melbourne area cause a significant part of this congestion. It might be possible to significantly reduce the congestion by increasing the use of railways to move goods. To do this, a number of intermodal exchanges have to be built in the greater Melbourne area, where containers or goods can be transferred between trains and trucks for the “last mile” movement to the final destination. Where should such IMEXs (Inter-Modal EXchanges) be built? Which suburbs should be served by each IMEX?
Mathematical optimisation allows us to answer such questions. This assignment involves both modelling (that is determining how to translate a problem into mathematics) and implementation of optimisation algorithms to get a solution. We will work through a series of models of increasing complexity. Throughout this assignment, you will be dealing with a single data set that represents a set of locations around Melbourne (based on the Australia Bureau of Statistic’s SL2 statistical areas) and a predicted demand in terms of truckloads.
We will assume that the movement by train
to/from each IMEX is “free” – or more
accurately, that the rail transport costs about
the same irrespective of where we are
locating the centre so that we can ignore the
rail cost. This is not unreasonable as we are
focusing on the congestion from trucks, and
for rail the handling cost for transferring
to/from trucks is more significant than the cost
of moving the containers. Of course, there are
many other issues and costs we could
consider when deciding the locations of
IMEXs. Here we will start simple and slowly
work towards more complex and realistic mathematical models. For the customers we simply have a number of points that represent areas, such as a postcode or in our case an SL2 area.
Notation:
𝑛 = number of locations that have to be served, 𝑁 = {1, … , 𝑛} = set of locations
𝑥𝑖 , 𝑦𝑖 = coordinate of each customer or demand location 𝑖 (in km from an arbitrary zero) 𝑞𝑖 = number of truckloads that have to be moved to or from location 𝑖
pg. 1 MTH3330 Assignment 4 2019
1. Locating a single IMEX in the plane
Here we are going to start simple and work our way up to something more complicated. The simplest location problem is to locate a single IMEX in the plane, given demand at a set of points. Let 𝑥𝑖 , 𝑦𝑖 for 𝑖 = 1,2, … , 𝑛 be the coordinates for a set of locations and 𝑞𝑖 the quantity (number of truckloads) that has to be moved to/from each of these locations. If we assume Euclidean (straight line) distances to a single IMEX located at location (𝑢, 𝑣), then the total travel distance (truck km) incurred in moving goods is given by the function:
𝑛
𝑓̅(𝑢,𝑣)= ∑𝑞𝑖√(𝑢−𝑥𝑖)2+(𝑣−𝑦𝑖)2 𝑖=1
To make this more tractable we are going to start by considering a slightly different objective which is based on the square of the distances (truck km2). This has the added advantage that it discourages long truck trips much more than short ones (doubling the length quadruples the cost). Hence, we have
𝑛
𝑓(𝑢,𝑣)= ∑𝑞𝑖((𝑢−𝑥𝑖)2+(𝑣−𝑦𝑖)2) 𝑖=1
Now the question is: for which location (u,v) is this cost minimised? Or solve: min 𝑓(𝑢, 𝑣) 𝑢,𝑣
a) [1 marks] How many local & global minima does this function have? (Give reasons)
b) [1marks]FindaformulaforcalculatinganoptimalIMEXlocation.
c) [1 marks] Compute a (globally) optimal solution. Insert the answer in the spreadsheet to
generate a plot of this solution and include both the coordinates of the IMEX and the plot in the report.
2. Locating a single IMEX using Manhattan distances
For cities such as Melbourne (or Manhattan, New York) where the streets largely form a grid, using straight-line distances does not really make sense. The distance a truck has to travel is essentially the sum of the distance in the x direction and the distance in the y direction. This type of distance measure is called the Manhattan distance. A nice property of this is that all routes have the same distance, provided trucks never travel away from their destination (why?). Using it we can define a more accurate measure of the truck kilometres that would be incurred from locating a single IMEX at (𝑢, 𝑣):
𝑛
𝑔(𝑢,𝑣)= ∑𝑞𝑖 (|𝑢−𝑥𝑖|+|𝑣−𝑦𝑖|) 𝑖=1
a) [5 marks] Formulate min 𝑔(𝑢, 𝑣) as a linear program. Include a brief explanation of the 𝑢,𝑣
variables and constraints used.
b) [5 marks] Write down the dual of this linear program. Make sure you clearly specify the dual
variables and to which constraints they correspond.
c) [5 marks] Prove that the weighted median is the optimal solution – that is in both the x and y
direction the optimal location can be found by selecting the 𝑥 (resp. 𝑦 ) coordinate so that half 𝑖𝑗
of the demand is associated with locations 𝑥 with 𝑥 ≤ 𝑥 (resp. locations with 𝑦 ≤ 𝑦 ). 𝑘𝑘𝑖 𝑘𝑗
Hint: Your proof should involve constructing a suitable dual solution.
d) [3 marks] Compute the actual optimal location using the data provided and insert the optimal
solution into the first spreadsheet to create a plot. Provide both the coordinates of the optimal location and the plot in the assignment report.
pg. 2 MTH3330 Assignment 4 2019
3. Locating multiple IMEXs in the plane
In practice, of course we want multiple IMEXs to be located in the greater Melbourne area. Now we need to decide both the location of these IMEXs and the how to allocate each customer to these. If we denote with 𝑘(𝑖) the index number, identifying the IMEX to which customer 𝑖 is allocated and 𝑢𝑘,𝑣𝑘 the location of the 𝑘𝑡h IMEX, then the problem of optimally locating 𝑝 such IMEXs becomes:
𝑛
minh(𝒖,𝒗,𝒌)=∑𝑞𝑖 (|𝑥𝑖 −𝑢𝑘(𝑖)|+|𝑦𝑖 −𝑣𝑘(𝑖)|) suchthat 𝑘(𝑖)∈{1,…,𝑝} for𝑖=1,…,𝑛
𝒖,𝒗,𝒌
Your task is to find the best solution (location and allocations for each centre) if 𝑝 = 5.
Observe that for fixed 𝒖, 𝒗 (positions of the IMEX’s) each customer would allocate to the nearest IMEX (based on the Manhattan distance). On the other hand for the fixed 𝒌 (allocations) we can find the best IMEX location in each cluster (set of customers 𝑖 with same (𝑖) ) by solving the location problem from the previous question. Now complete the following tasks:
a) [5 marks] Write code to start with a random allocation vector 𝒌 ∈ {1, … , 𝑝}𝑛 and alternate between
(i) finding the best locations 𝑢, 𝑣 for each group of customers
(ii) changing 𝒌 to allocate each customer to the closest IMEX.
Repeat until the solution remains unchanged. (Remember that your code must be submitted with the assignment and should be written in a readable style.)
b) [4 marks] Analyse the above algorithm by discussing: Is the function h convex? Can the algorithm cycle or is it guaranteed to terminate? Is the final solution optimal? (give reasons). What happens if the algorithm is started with a different random starting point?
c) [4 marks] Report the best solution to the 5 IMEX allocation problem (by inserting the location and allocation into the 3rd sheet of the Excel workbook). Include the coordinates of the 5 IMEXs and the graph in your report.
4. The discrete IMEX location problem
To make the problem slightly more realistic again, we are going to restrict the choice of IMEX locations to a discrete set of possible locations. In practice, these would be chosen based on availability of land, proximity to an existing railway line, links to major roads (freeways or highways), land zoning (commercial vs residential) and other considerations. In the data set provided these potential locations have been semi-randomly generated.
A further complication to be taken into account in this exercise is to limit the capacity (number of trucks) allocated to each IMEX. This limits congestion near the IMEX and allows for physical restrictions on the number of trains and trucks that can be served in a single location by a “standard” sized IMEX. We shall assume that all IMEXs have the same size and use 𝐶 to denote the capacity. For this problem 𝐶 = 260.
Your task now is to find a subset of 𝑝 locations for opening IMEXs, where 𝑝 = 5 from the given set 𝐾 of potential locations and assign customers to these. Customers may be split between multiple IMEXs. This optimisation problem can be written as a non-linear optimisation problem in the form:
𝑖=1
pg. 3 MTH3330 Assignment 4 2019
𝑛5
minh(𝒇,𝒌)=∑∑𝑞 𝑓 (|𝑥 −𝑢 |+|𝑦 −𝑣 |)
𝑖 𝑖𝑗 𝑖 𝑘(𝑗) 𝑖 𝑘(𝑗) 𝑖=1 𝑗=1
𝒌,𝒇
suchthat 𝑘(𝑗)∈{1,…,𝑛} for𝑗=1,…,𝑝
∑ 𝑞𝑓 ≤𝐶 𝑖 𝑖𝑗
𝑖=1,…,𝑛 𝑝
∑𝑓 =1 𝑖𝑗
𝑗=1
𝑓 ≥0 𝑖𝑗
for𝑗=1,…,𝑝
for𝑖=1,…,𝑛 for𝑖=1,…,𝑛, 𝑗=1,…,𝑝
Now that we have both discrete (𝑘) and continuous (𝑓) variables in this problem, and that 𝑢𝑖,𝑣𝑖 are given coordinates of potential IMEXs (𝑖 = 1, … ,24 in the data)
a) [2 Marks] If a fixed choice of 𝑝 IMEX locations is given, write the remaining problem of determining the optimal allocation of customer demand to IMEX’s as a network flow problem (i.e. what are the nodes & arcs with supply/demand for each node and cost & capacity for each arc).
b) [2 marks] An extension to linear programming, that will not otherwise be discussed in this course, allows variables to be constrained to only be binary (0 or 1 but not fractional).
Modify you network flow formulation to allow the optimiser to choose the location of IMEXs, by adding binary variables 𝑧𝑘 ∈ {0,1} for 𝑘 = 1, … ,24 to determine if an IMEX is built at location 𝑘. You will need constraints of the form:
24
𝑓𝑙𝑜𝑤≤𝐶𝑧𝑘 and ∑𝑧𝑘 =𝑝 k=1
c) [2 marks] Solve this problem using the CPLEX or Gurobi solver to get the optimal solution: Hint: In Julia binary variables can be defined by adding ‘,Bin’ as additional optional argument to an ‘@variable’ declaration. In Matlab use binvar(n,m,’full’) to create a 𝑛 × 𝑚 matrix of binary variables and ‘intlinprog’ or gurobi as solver. For python the ‘model.addVars()’ function takes an optional argument ‘vtype=GRB.BINARY’.
Report the optimal solution for the above problem, again using the 4th sheet of the Excel spreadsheet to create an appropriate graph of the solution – here for each location just select an IMEX that has the most flow allocated in column F of the spreadsheet – the picture produced here is somewhat “approximate” as it doesn’t allow for split flows.
Report the best objective value and the location of the 5 IMEXs.
Handing in your work
Please submit your assignment on Moodle by the due date. This must include:
1. A PDF file of the report using the template provided.
2. The complete source code used to create the solutions (perhaps as a notebook). Note that key
parts of the code are to be copied into the report template. The complete version uploaded should include any additional parts such as for reading data, printing solutions etc. Your code should include enough comments and appropriate naming conventions to make it obvious which parts of it were used to answer each of the above questions.
pg. 4 MTH3330 Assignment 4 2019