ECE3093 Assignment 2: Melbourne 2050
50 Marks worth 10% of the final ECE3093 grade. April 2019
Electronic submission of this assignment is due on Moodle by 9am on Monday 6 May 2019. You are required to submit a single-file report in pdf format based on the template provided, and the source code (Matlab script). The following files are provided:
1. Ass2-Melb2050.docx: this set of instructions
2. Ass2-template.docx: the template for your report (answers)
3. Ass2-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 – 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 (statistical level 2 area as defined by the Australian Bureau of Statistics).
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 ECE3093 Assignment 2 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) [2 marks] How many local & global minima does this function have? (Give reasons)
b) [2marks]FindaformulaforcalculatinganoptimalIMEXlocation.
c) [2 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] Compute the actual optimal location (either by solving the primal or dual problem)
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.
d) [5 marks] Bonus question: Can you determine what the optimal primal & solutions are for this
type of problem directly from the data, without solving an LP with the simplex method?
pg. 2 ECE3093 Assignment 2 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:
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) [5 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 𝑝 centres, where 𝑝 = 5 from the given set 𝐾 of potential locations and assign customers to these. Customers may not be split between multiple IMEXs. This optimisation problem can be written as:
𝑛
minh(𝒖,𝒗,𝒌)=∑𝑞𝑖 (|𝑥𝑖 −𝑢𝑘(𝑖)|+|𝑦𝑖 −𝑣𝑘(𝑖)|)
𝑖=1
𝑘(𝑖)∈{1,…,𝑝} for𝑖=1,…,𝑛
(𝑢𝑘(𝑖),𝑣𝑘(𝑖))∈𝐾 for𝑖=1,…,𝑛
∑ 𝑞𝑖≤𝐶 for𝑗=1,…,𝑝 𝑖∶𝑘(𝑖)=𝑗
pg. 3
ECE3093 Assignment 2 2019
𝑛
minh(𝒖,𝒗,𝒌)=∑𝑞𝑖 (|𝑥𝑖 −𝑢𝑘(𝑖)|+|𝑦𝑖 −𝑣𝑘(𝑖)|) suchthat 𝑘(𝑖)∈{1,…,𝑝} for𝑖=1,…,𝑛
𝒖,𝒗,𝒌
Your task is to find the best solution (location and allocations for each centre) if 𝑝 = 5.
𝑖=1
𝒖,𝒗,𝒌
suchthat
Now that we have an entirely discrete problem, it could in principle be answered by simply enumerating all possible choices of IMEX locations and all possible sets of allocations of customers to IMEXs. This motivates the following set of questions:
a) [2 Marks] Imagine that you had written a computer program to enumerate all choices of IMEX locations and all possible allocations of customers to these IMEXs. For each potential solution, it evaluates whether it is feasible (satisfies the capacity constraints) and the cost. Assuming that your computer can evaluate 1 million potential solutions per second, approximately how long will it take the computer to find the optimal solution? Compare this to the age of the universe (approx. 13.8 billion years).
b) [5 marks] Write down an Integer Linear Programming formulation for this problem.
c) Use ILP formulation to obtain an optimal solution to this problem with the data set provided in
the Excel spreadsheet.
Hint: In Matlab with YALMIP you can use binvar(n,m,’full’) to create a 𝑛 × 𝑚 matrix of binary variables and using ‘intlinprog’ as solver.
d) [5 marks] Report the best solution for the above problem, again using the Excel spreadsheet to create an appropriate graph of the solution. Report the best objective value and the location of the 5 IMEXs as well as the total demand allocated to each IMEX.
5. Modelling Extensions
If you were working as a mathematician/modeller for, say, the Victorian Department of Transport, you would of course need to deal significantly bigger data sets. However the types of mathematical models we have discussed above would still valid and could be written in the same (integer) linear programming notation (with simply bigger values for 𝑛, 𝑝, etc). While you would not be using Excel to do this kind of exercise (nor perhaps Matlab), the mathematical modelling skills are exactly the same. We have gone through a series of models of increasing complexity. The final question is regarding what shortcomings remain.
a) [3 marks]: What aspects of the model in Question 4 are still unrealistic? What additional data or model features should be considered in deciding the location of 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. Your Matlab (or other language) source code used to create the solutions as a zip file. The 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 ECE3093 Assignment 2 2019