MTH3330 Assignment 4: 

Melbourne 2030 40 Marks worth 6% of the final MTH3330 grade. May 2022 50 Marks for postgrad (Honours/Masters) students. Electronic submission of this assignment is due on Moodle by 11:55pm on Friday 27 May 2021. 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-Melb2030.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. (with corresponding .csv files to read data in your code) 4. Some template code in .ipynb notebooks to assist with reading/writing data etc Some notes on requirements: You are not required to use any particular programming language, nor the templates provided, but please provide the source code with your solution. This is an individual and not a group assignment. Motivation When planning for Melbourne in the year 2030, 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 Statistics 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 2022 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) [3 marks] How many local & global minima does this function have? (Give reasons) b) [3 marks] Find a formula for calculating an optimal IMEX location (i.e. = and = ). 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) [10 marks] This questions is for Honours & Masters students only! Show 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: The problem decomposes in the x & y direction. The result can be proven by constructing a dual solution, or in an approximate way by demonstrating that the median is a local minimum. 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 2022 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 IMEXs) 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 an IMEX. Data is provided in the spreadsheet (and corresponding CSV file) for 24 potential IMEX locations and the capacity of the IMEX that could be built at each of these locations. Your task is to find the optimal location the IMEXs and the allocation of customers to IMEXs assuming each customer can only be served by a single IMEX. This requires an extension to linear programming where we restrict variables to only be binary (zero or one). While we do not cover this otherwise in this unit, its a very useful extension and widely used in operations research. The modelling is very similar to linear programming modelling with just the additional binary restriction. To get you started, you should be using: pg. 3 {0,1} to be 1 in the solution if is allocated to the h = 1,...,24 possible IMEX {0,1} to indicate if the h IMEX is built (again 1 means true) MTH3330 Assignment 4 2022 =1 You should write this with a linear objective and linear constraints (just like a normal linear program). The constraints need to include: Build exactly IMEX facilities: Only allow allocation to an IMEX that is built: = 1,...,; = 1,...23 Capacity constraint, with the sum of for all allocated to not exceeding capacity Each customer is allocated to an IMEX The objective h(, ) can be written as a linear objective and computes the same cost as (, , ) except that now the locations of IMEXs are fixed and variables & are used to determine the selection of IMEXs and the allocation of customers to these IMEXs. a) [3 Marks] Write out the complete formulation for this (integer) linear program Hint: The objective function h(, ) can be written entirely in terms of variables, the variables only appear in the constraints. b) [3 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/YALMIP 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. 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 2022