Search optimization
APPROVED_L7_COMP7065_21-22_sub_brief Faculty of Science and Technology Department of Computing & Informatics Unit Title: Search and Optimisation (COMP7065) Assessment Title: Algorithm Design and Comparison for an Optimisation Problem Unit Level: 7 Assessment Number: 1 of 1 Credit Value of Unit: 20 Date Issued: 01/11/2021 Unit Leader: Jiankang Zhang Submission Due Date: 14/01/2022 Time: 12:30 PM Other Marker(s): Kevin Wilson Submission Location: Brightspace Quality Assessor (QA): Hamid Bouchachia Feedback Method: Brightspace This is a group assignment which carries 100% of the final unit mark. ASSESSMENT TASK This is a group assignment with an individual element. Your group should have 4-5 members, and you must enroll to your group on Brightspace by 12/11/2021. After this deadline you will be assigned to a group randomly. BACKGROUND In this assignment you will address a real-world problem of delivery planning for the LPG (Liquefied Petroleum Gas) distributor. In the areas where mains gas for heating purposes is not available, LPG is the best alternative solution. LPG distribution companies source the fuel from major oil refineries and deliver it to the bulk customers by a fleet tanker lorry like the one in Figure 1. Figure 1. Tanker lorry. You have been employed by SaO Gas Ltd as data scientists. You are to produce delivery schedules for the fleet of 25 tanker lorries operating from 5 depots in the country of Optilandia. The tank capacity and the delivery cost are summarized in Table 1, where the cost is calculated using pound sterling (£). Furthermore, the lorries’ distribution in the depots is shown in Table 2. The speed of tank lorry is 50 miles/hour on average by considering safety, regardless of the lorry’s capacity. There are multiple objectives of the delivery schedules to be considered, including minimizing the overall dispatch time used, minimizing the overall cost of delivery for the distributor, whilst certain constraints may be applied to the objectives, which will be detailed in the optimization problems. Tanker type Capacity [tonnes] Cost per mile [£] Cost per mile per tonne [£] Small 5 1.00 1.50 Medium 12 1.60 1.00 Large 22 2.20 0. 50 Table 1. Tanker lorries operated by SaO Gas Ltd. Nov 2021 - v17 Page 1 of 7 APPROVED_L7_COMP7065_21-22_sub_brief As an example of the cost calculating, a large tanker can be loaded with up to 22 tonnes of LPG at one of the depots (you can assume that depots never run out of gas). It costs the distributor £2.2 per mile to use the large tanker (even if it is empty) plus £0. 50 per mile for every tonne of LPG the tanker carries. So, a large tanker with 10 tonnes of LPG travelling 20 miles costs: 20 [miles] x (2. 2 [£] + 10 [tonnes] x 0. 50[£]) = 144 [£]. However, after dropping 2 tonnes of LPG at a customer, the next 20 miles travelled will cost less as the lorry is now lighter: 20 [miles] x (2.2 [£] + 8 [tonnes] x 0.50 [£]) = 124 [£]. As an example of the dispatch time calculating, the loading time at depot can be omitted (not included as dispatch time), however, the travel time and offloading time will be included into the dispatch time. The offloading time consists of constant fixing time of 5 minutes at a customer, and 10 minutes per tonne for dropping the gas from tank to customer. With above mentioned large tank with 10 tonnes of LPG travelling 20 miles to drop 2 tonnes to a customer, the dispatch time imposed is (20 [miles] / 50 [miles/ hours] ) x 60 ( x 60 is to change to minutes) + 2 tonnes * 10 [minutes/tonne] + 5 minutes = 49 minutes. SaO Gas Ltd operates from five depots as shown in Table 2. The road network of Optilandia has been depicted in Figure 2, with the red dots denoting locations of the five depots, and the green dots denoting locations of SaO Gas customers. Depot Location ID Small tankers Medium tankers Large tankers 1 #523 2 2 1 2 #124 1 3 1 3 #373 2 2 1 4 #167 3 1 1 5 #127 2 2 1 Table 2. SaO Gas depots. Figure 2. Road network of Optilandia. Nov 2021 - v17 Page 2 of 7 APPROVED_L7_COMP7065_21-22_sub_brief OPTIMISATION PROBLEMS There are two problems you should address: 1. Winter is coming, so fully fill all customers’ tanks is urgent. Schedule LPG delivery to all customers in order to fully fill their tanks while minimising the overall dispatch time. There are no additional constrains apart from the tanker lorry capacity, and the overall delivery cost is not a concerned objective. 2. Schedule LPG delivery in order to maximise the cost efficiency, where the cost efficiency is defined as Cost efficiency = total gas delivered to all customers / overall cost of delivery, while observing the following constraints in addition to tanker lorry capacity: a. Each lorry must stop for 20 minutes for a rest after 2 hours continuous driving b. The lorry with small tank can only stop up to 4 times, the lorry with medium tank can only stop up to 8 times, the lorry with medium tank can only stop up to 16 times, this only includes customer deliveries. c. Each lorry can refill and end its journey at any depot. d. At the end, all customers should have more than 50% of gas in their tanks, or the Gas Ltd will receive complaint from the customer, and will incur a penalty of £1,000 for each such customer. You are required to design and implement at least two optimisation schemes to address the LPG delivery scheduling problems (that is two schemes in total, not two per each problem). One of these schemes can be simple e.g. Dijkstra's algorithm, a random or greedy scheduler, but you need to make sure that the approach is able to generate valid solutions i.e. not violating the given constraints. The other one is expected as an efficient one in terms of computational complexity and convergence. You can use any combination of methods covered in class (e.g. Genetic Algorithms, Ant Colony Optimisation) as well as methods you have found during your independent study or which you came up with yourself. Your implementation should be in Python. You are allowed to use existing Python optimisation libraries or implementations if you need to, but you should aim to implement as much as possible from scratch yourself. You must apply your implementations to the two LPG delivery scheduling problems and critically evaluate the results, comparing and contrasting performance, strengths and weaknesses of the approaches you have used in terms of quality of the solution, running time etc. DATASET The dataset for this assignment consists of three files: 1. SaO_Optilandia_locations.csv 2. SaO_Optilandia_links.csv 3. SaO_Optilandia_depot_lorries.json The SaO_Optilandia_locations.csv file contains the following columns: id – Location ID x,y – coordinates of a location; Optilandia lives on a flat version of Earth, so the Euclidean distance between two locations is what you should use (no need to use Haversine for example); the Euclidean distance is expressed in miles is_depot – True if a location is one of the five depots is_customer – True if a location is one of the customers capacity – capacity of the tank in tonnes (only for locations where is_customer ==True) level – current gas level in the tank in tonnes (only for locations where is_customer ==True) A small sample of the SaO_Optilandia_locations.csv file has been given in Table 3. You can think of the locations as nodes of a graph. Nov 2021 - v17 Page 3 of 7 APPROVED_L7_COMP7065_21-22_sub_brief Table 3. Locations dataset sample. The SaO_Optilandia_links.csv file contains the following columns: id1,id2 – Location IDs connected by a road segment A small sample of the SaO_Optilandia_links.csv file has been given in Table 4. You can think of the locations as edges of a graph. Nov 2021 - v17 Table 4. Links dataset sample. The SaO_Optilandia_ depot_lorries.json file contains information about the types and capacities of tanker lorries in each depot as given in Table 1 and Table 2. SOLUTION FORMAT The file SaO_Optilandia_example_solution.json contains an example solution. A solutions file contains a list of lorry journeys, where each journey includes the lorry identifier and a list of tuples consisting of location identifier and the amount of gas loaded to the tanker (positive number) or dropped off at a customer (negative number) at this location. An example journey is given below: { 'lorry_id': '124-0', 'loc': [(124,5),(14,-0.33),(36,-0.81),(124,0)] } where the interpretation of loc is as follows: (124,5) – load 5 tonnes of LPG at location 124 (depot) (14,-0.33) – go to next location (14 – customer) and drop off 0.33 tonnes of LPG (36,-0.81) – go to next location (36 – customer) and drop off 0.81 tonnes of LPG (124,0) – go back to depot (location 124 – customer) Page 4 of 7 APPROVED_L7_COMP7065_21-22_sub_brief 1. Report in the shape of a Jupyter notebook (Brightspace, Group), that contains the following sections: Front matter, Problem definition, Methodology (all steps), Experiments & discussion, Conclusion and References. The report must be a combination of text and working code, relevant figures (e.g. evolution of the objective function values over time), tables and anything else you deem useful in communicating your work (e.g. interactive visualisations or animations). You must make sure that your notebook executes from top to bottom without any intervention in the Google Colab environment. 2. PDF version of your Jupyter notebook (Brightspace/Turnitin, Group). This can be produced by simply printing your notebook to a .pdf file. The feedback will be provided via Turnitin on this very document. 3. Two solution files (Brighspace, Group) representing your best solutions to the two optimisation problems. The files should follow the format of the SaO_Optilandia_example_solution.json file. 4. Peer-assessment of the group members (Brightspace, Individual) Each member of each group will be asked to anonymously assess the contributions to the task of all the other members in their respective group via Brightspace. It is very important that you’re honest in your assessment. The final mark will be weighted by your contribution. For example, if in a group of 4 you all contributed equally, your final mark will be the same. We will use the uGrade system for the peer assessment, details will be posted on Brightspace. 5. Video presentation (Panopto, Individual) of your group’s submission, which should be between 7 and 10 minutes in total. The video should include a short walkthrough of the report including screen capture rather than just a “talking head”. This element is mandatory, and marks will only be awarded