FIT5216 Modelling Discrete Optimization Problems - Assignment 3: Ferry Loading
FIT5216: Modelling Discrete Optimization Problems Assignment 3: Ferry Loading
1 Overview For this assignment, your task is to write a MiniZinc model for a given problem specification. •Submit your work to the MiniZinc auto grading system (using the submit button in the MiniZinc IDE). •Submit your model (copy and paste the contents of the .mzn file) and report using the Moodle assignment. You have to submit by the due date (28th May 2023, 11:59pm), using MiniZinc and using the Moodle assignment, to receive full marks. You can submit as often as you want before the due date. Late submissions without special consideration receive a penalty of 10% of the available marks per day. Submissions are not accepted more than 7 days after the original deadline. This is an individual assignment . Your submission has to be entirely your own work . We will use similarity detection software to detect any attempt at collusion, and the penalties are quite harsh . You may not use any generative AI software in the completion of this assignment. If in doubt, contact your teaching team with any questions!
2 Problem Statement Your task is manage the loading of a ferry that transports vehicles. The ferry is made up multiple lanes for the vehicles. Usually vehicles fit in one lane, but some wide vehicles require using two adjacent lanes, since the lanes are only wide enough of standard cars. The vehicles start on the dock lined up in lanes, and vehicles are loaded one by one by driving onto the ferry. The aim is to load the most value onto the ferry for each trip (meaning that highly valued customers are not waiting as long, and each trip maximizes the value of ferry tickets served). Input data is given in MiniZinc data format: for the ferry ferrylanes = ⟨The number of lanes on the ferry ⟩; ferrylength = ⟨The length of the ferry in meters ⟩; flen = ⟨The length of each lane in the ferry ⟩; fstart = ⟨The starting position of the lane, 0 = ramp ⟩; Consider the ferry data defined by ferrylanes = 4; ferrylength = 20; flen = [12,20,20,12]; fstart = [4,0,0,4]; 1 lane1lane4lane2lane3 048121620 lane1lane4lane2lane3 048121620 car1lane3lane3car3truck1truck2crane1truck3camper1semi1 semi2car2 lane1lane4lane2lane3 048121620 car1lane3lane3car3truck1truck2 crane1truck3camper1semi1semi2 car2(a) (b) (c) Figure 1: (a) An empty ferry layout. (b) A simple packing (c) A packing on the ferry. defines a ferry with layout shown in Figure 1, with a ramp on lanes 2 and 3. Note we are guaranteed that ferry lanes start positions decrease on the left hand side of the ramp, and increase on the right hand side of the ramp. Input data is given in MiniZinc data format: for the loading lanes and vehicles loadinglanes = ⟨The number of loading lanes ⟩; sided = ⟨% difference in weight allowed on sides ⟩; halfd = ⟨% difference in weight allowed front/back ⟩; VEHICLE = ⟨The set of vehicles to be loaded ⟩; len = ⟨Length in meters of each vehicle ⟩; width = ⟨Width in lanes of each vehicle, 1 or 2 ⟩; weight = ⟨Weight of each vehicle in tonnes ⟩; llane = ⟨Loading lane where each vehicle starts ⟩; plane = ⟨Position in loading lane of each vehicle, 1 = first ⟩; value = ⟨value of loading each vehicle ⟩; Here is a sample data set (given in ferry0.dzn ): ferrylanes = 4; ferrylength = 20; 2 flen = [12,20,20,12]; fstart = [4,0,0,4]; loadinglanes = 3; sided = 10; halfd = 200; VEHICLE = { CAR1, CAR2, CAR3, TRUCK1, TRUCK2, SEMI1, SEMI2, CRANE1, CAMPER1, TRUCK3}; len = [2,2,2,3,3,8,8,4,4,6]; width = [ 1,1,1,1,1,2,2,2,1,1]; weight = [1,1,1,2,2,5,5,4,3,3]; llane = [1,1,1,2,2,3,3,2,1,3]; plane = [1,2,3,1,2,1,2,3,4,3]; value = [1,1,1,2,2,5,5,5,2,2]; This data requires loading as many of the 10 vehicles onto the ferry as possible. The decisions of the model are: which lane to put each vehicle (for double width vehicle this is the leftmost (least) lane); how far into the ferry to place the back end of the vehicle; whether the vehicle is loaded at all; and in which order vehicles are loaded. set of int: FLANE = 1..ferrylanes; set of int: POS = 0..ferrylength; set of int: ORDER = 1..card(VEHICLE); array[VEHICLE] of var FLANE: flane; % lane (leftmost for wide) where vehicle is parked array[VEHICLE] of var POS: fpos; % position of vehicle rear, 0 = ramp end of ferry array[VEHICLE] of var bool: loaded; % is the vehicle loaded arrry[VEHICLE] of var ORDER: order; % order of loading The assignment is in parts, please attempt them in order. Note that if you do not complete all parts you cannot get full marks. Part A - Basic packing Until part D we will assume all vehicles are loaded. Your model should leave the loaded variables unconstrained until then. Similarly we will ignore the order variables until part E. Create a model ferry.mzn that takes data in the format specified above and packs all the vehicles in a space of width ferrylanes and height ferrylength , assuming all vehicles are loaded, making sure no vehicles overlap. Try to use global constraints if possible. An example solution for ferry0.dzn defined by decisions flane = [CAR1: 4, CAR2: 3, CAR3: 3, TRUCK1: 3, TRUCK2: 3, SEMI1: 1, SEMI2: 1, CRANE1: 1, CAMPER1: 3, TRUCK3: 3]; fpos = [CAR1: 0, CAR2: 18, CAR3: 16, TRUCK1: 13, TRUCK2: 10, SEMI1: 12, SEMI2: 0, CRANE1: 8, CAMPER1: 6, TRUCK3: 0]; is shown in Figure 1(b). Notice how nothing overlaps, and everything fits in the box but some vehicles, like CAR1, SEMI1, and SEMI2 are outside the boundaries of the ferries area.
Part B - Ferry Packing Fix the packing constraints so that only the actual available area of the ferry is available to pack onto. Try to use global constraints if possible. An example solution for ferry0.dzn defined by decisions flane = [CAR1: 4, CAR2: 4, CAR3: 3, TRUCK1: 3, TRUCK2: 2, SEMI1: 3, SEMI2: 1, CRANE1: 1, CAMPER1: 2, TRUCK3: 3]; fpos = [CAR1: 14, CAR2: 12, CAR3: 12, TRUCK1: 0, TRUCK2: 16, SEMI1: 4, SEMI2: 8, CRANE1: 4, CAMPER1: 0, TRUCK3: 14]; is shown in Figure 1(c). Notice how nothing overlaps, and everything fits in the boundary of the ferry area.
Part C - Weight Balance The ferry has to be loaded in a balanced manner so it is safe to traverse the sea. The rule is that the total weight of vehicles on the left and right side of the ferry can differ by at most sided %. And the total weight of vehicles on the front end and back end can differ by at most halfd %. Note that 10 and 13 differ by 30%, but 7 and 10 do not, they differ by 3/7 = 42.86%. If the ferry has an even number of lanes, then the first half are on the left side and the second half on the right side. If the ferry has an odd number of lanes, then the lanes left of the middle lane are the left side, and the lanes right of the middle are the right side. Note that a width two vehicle straddles a boundary (i.e. overlaps the middle of the ferry with an even number of lanes, or sits partially on the middle lane for a ferry with an odd number of lanes) then it gives half its weight (rounded down for simplicity) to each side it straddles. If we examine the solution of the previous part (Figure 1(c)): the left side is lanes 1 and 2, and the total weight there is from TRUCK2, SEMI2, CRANE1, CAMPER1 giving 2 + 5 + 4 + 3 = 14; the right side is lanes 3 and 4 with total weight from CAR1, CAR2, CAR3, TRUCK1, SEMI1, TRUCK3 giving 1 + 1 + 1 + 2 + 5 + 3 = 13. Since these number are within 10% of each other the weight balance constraint holds. The ferry layout shown in Figure 3(b) has middle lane, lane 3. The left side is lanes 1 and 2, the right side is lanes 4 and 5. A double width vehicle parked in lane 3 would give half of its weight (rounded down) to the right side, and none to the left side. Any vehicle loaded entirely in a position at least half way down the ferry length is added to the front weight. Any vehicle loaded entirely in a position no more than half way down the ferry length is added to the backweight. Any vehicle straddling the middle of the ferry length is not added to either weight. The loading shown in Figure 1(c) has TRUCK2, TRUCK3, CAR1, CAR2, and CAR3 loaded after position 10 for a total front weight of 2 + 3 + 1 + 1 + 1 = 8; while CRANE1, CAMPER1 and TRUCK1 are loaded completely before position 10 for a total back weight of 9. Note that SEMI1 and SEMI2 are counted to neither weight, as they straddle the mid point. The front back weight constraint is satisfied since the difference in weights is less than 200%
Part D - Load optimisation Until now we have assumed all vehicles are loaded. In fact the critical choice is which vehicles are loaded onto the ferry. Now your model needs to constrain the loaded variables. Note a vehicle that is not loaded can have any value for its flane andfpos variables. Add to your model an objective of maximizing the total value of the vehicles that are loaded. Note that the loading lanes constrain which vehicles can be loaded. We cannot load a vehicle without also loading all vehicles ahead of it in the loading lane. Add a constraint to your model to enforce this. The objective for the solution shown in Part C is 26, the total value of all vehicles. Given all the vehicles in the loading zone are loaded for the solution the loading lane constraint is automatically satisfied. car1car3truck1truck2crane1truck3camper1semi1 semi2car2loadinglane1loadinglane2loadinglane3 lane1lane4lane2lane3 048121620 car1lane3lane3car3truck1truck2 crane1truck3camper1semi1semi2car2 lane1lane4lane2lane3 048121620car1lane3lane3car3truck1truck2crane1truck3camper1semi1 semi2car2 (a) (b) (c) Figure 2: (a) The loading lanes. (b) An ordered packing. (c) An ordered packing satisfying marshalling constraints.
Part E - Load ordering In reality the vehicles are loaded on one by one, and we have to have a clear driving space to get each vehicle to where it goes. Now your model needs to constrain the order variables. The vehicles loaded must be given order numbers which are different, vehicles which are not loaded can get any order number.
The loaded vehicles have to respect the loading lane, that is no vehicle can be loaded ahead of a vehicle that is in front of it in the loading lane. Similarly any vehicle loaded before another must either be in ferry lanes to the left of it, or ferry lanes to the right of it, or appear further from the loading ramp (larger position value). The packing shown in Figure 1(c) does not meet these
constraints since for example SEMI1 must be loaded before TRUCK3 since it appears earlier in loading lane 3, but appear closer to the ramp in (ferry) lane 3. The loading lanes for ferry0.dzn are shown in Figure 2(a). The solution satisfying the ordering constraints below: flane = [CAR1: 4, CAR2: 4, CAR3: 3, TRUCK1: 3, TRUCK2: 2, SEMI1: 3, SEMI2: 1, CRANE1: 1, CAMPER1: 2, TRUCK3: 3]; fpos = [CAR1: 6, CAR2: 4, CAR3: 0, TRUCK1: 16, TRUCK2: 16, SEMI1: 8, SEMI2: 8, CRANE1: 4, CAMPER1: 0, TRUCK3: 2]; order = [CAR1: 3, CAR2: 4, CAR3: 9, TRUCK1: 1, TRUCK2: 5, SEMI1: 2, SEMI2: 6, CRANE1: 8, CAMPER1: 10, TRUCK3: 7]; is shown in Figure 2(b). Note how the ordering TRUCK1, SEMI1, CAR1, CAR2, TRUCK2, SEMI2, TRUCK3, CRANE1, CAR3, CAMPER1 satisfies the constraints on loading. Part F - Marshalling constraints The vehicles must be marshalled onto the ferry from the loading lanes. There are two rules that must be applied. Two vehicles cannot be loaded one after the other from the same loading lane, i.e. if the 3rd vehicle loaded comes from loading lane 3 the 4th vehicle loaded must come from a different loading lane. Secondly we cannot load two width 2 vehicles one after the other, we must load a width 1 vehicle between them. The solution shown in Figure 2(b) does not satisfy the marshalling constraints, since CAR1 and CAR2 from the same loading lane are loaded one after the other. A solution satisfying these constraints is flane = [CAR1: 1, CAR2: 1, CAR3: 1, TRUCK1: 1, TRUCK2: 1, SEMI1: 2, SEMI2: 2, CRANE1: 2, CAMPER1: 4, TRUCK3: 4]; fpos = [CAR1: 8, CAR2: 6, CAR3: 4, TRUCK1: 13, TRUCK2: 10, SEMI1: 12, SEMI2: 0, CRANE1: 8, CAMPER1: 6, TRUCK3: 10]; order = [CAR1: 4, CAR2: 6, CAR3: 8, TRUCK1: 1, TRUCK2: 3, SEMI1: 2, SEMI2: 7, CRANE1: 5, CAMPER1: 10, TRUCK3: 9]; is shown in Figure 2c), where we load in order TRUCK1, SEMI1, TRUCK2, CAR1, CRANE1, CAR2, SEMI2, CAR3, TRUCK3 and CAMPER1.
Part G - Ramp constraints Warning this stage is much more difficult than previous stages. You may not wish to attempt it, you can get most of the marks without doing so. The load ordering is also constrained by the ramp. Note how in the solution of Part F (Fig- ure 2(c)), SEMI1 is loaded before TRUCK3 and CAMPER1, but clearly it blocks the entire ramp onto the ferry so there is no way for these vehicles to get to their position. There is always a ramp to the ferry, a lane lwith fstart[l] = 0. There may be multiple ramp lanes. We are guaranteed the fstart positions before a ramp are non-increasing, and the fstart position after a ramp are non-decreasing. In order to allow vehicles to load on board we also require a path from a ramp to the beginning of the lane(s) where they will park, at the time of loading. For a single width vehicle we allow it to
lane1lane4lane2lane3 048121620car1lane3lane3car3truck1truck2crane1camper1semi1 semi2car2 lane1lane4lane2lane3 048121620 lane3lane3lane5 lane1lane4lane2lane3 048121620 lane3lane3lane5(a) (b) (c) Figure 3: (a) Packing satisfying ramp constraints (b) Ramp constraint examples for single width vehicles. (c) Ramp constraint examples for double width vehicles. move to a lane if the first two meters of the lane are free and the lane its currently on is free up to the start position of that lane plus two meters. For example, in Figure 3(b) a single width vehicle loading onto lane 1 must have the grey area free when it loads to get to lane 1. Similarly to get to lane 5, it must have the entire purple area free. For a double width vehicle it must have the two lanes it is coming from free up until the start position of the lane it is moving (half) into plus two meters. For example in Figure 3(c) a double with vehicle moving to lane 1 must have the grey and pink and green boxes free at the time of loading. While to park in lane 4 (which means half of it is in lane 5) it needs the pink, green and purple boxes to be free. A solution satisfying the ramp constraints below is: flane = [CAR1: 1, CAR2: 4, CAR3: 1, TRUCK1: 4, TRUCK2: 4, SEMI1: 2, SEMI2: 2, CRANE1: 2, CAMPER1: 1, TRUCK3: 4]; fpos = [CAR1: 14, CAR2: 11, CAR3: 12, TRUCK1: 13, TRUCK2: 8, SEMI1: 12, SEMI2: 0, CRANE1: 8, CAMPER1: 6, TRUCK3: 20]; order = [CAR1: 1, CAR2: 3, CAR3: 6, TRUCK1: 2, TRUCK2: 5, SEMI1: 4, SEMI2: 9, CRANE1: 7, CAMPER1: 8, TRUCK3: 1]; and is illustrated in Figure 3(a). Note that there is a better one where we fit all vehicles.
Part H - Assertions In order for the input data to be correct, it must meet some requirements. In your model write MiniZinc assertions to check that the input data satisfies the following conditions: •The start positions of each ferry lane are non-negative; •The lengths of each ferry lane are non-negative; •The end of each ferry lane is no longer than the ferry length; •A ramp exists; •The side difference is non-negative; •The half difference is non-negative; •The lengths of all vehicles are positive; •The weights of all vehicles are positive; •The values of all vehicles are positive; •No two vehicles have the same loading lane and position in that lane; •The positions in each loading lane are numbered from 1 to the number of vehicles in that lane; and •The start positions of lanes are non-increasing before the ramp, and non-decreasing after- wards. Make sure that your assertions produce clear error messages when the assertions are violated. Make sure the error message pinpoints exactly where the data goes wrong. For each condition above, explain what your model is likely to do if the condition was violated and the model ran anyway. Explain in the report how you test each of the last three conditions. Create three small sample input files that violate the last three conditions. Include the three sample input files in your report, and show the output from your model when applied to these models. Note that none of these conditions is violated by the given input data or the hidden test data. If you are having difficulty with this part, leave the assertions out of the MiniZinc model submitted via the IDE, but ensure they are in the MiniZinc model submitted through Moodle with your report. 3 Instructions Edit the provided mznmodel files to solve the problems described above. You are provided with some sample data files to try your model on. Your implementations can be tested locally by using theRun+check icon in the MiniZinc IDE. Note that the checker for this assignment will only test whether your model produces output in the required format, it does not check whether your solutions are correct. The checker on the server will give you feedback on the correctness of your submitted solutions and models.
