Vehicle Routing Search Optimization For Lpg Gas Delivery

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 to those who submit the video. SUBMISSION FORMAT Your submission must consist of: Important: You should hence carefully plan the content of your video and rehearse and time your presentation, as your mark will only be based on the first 10 minutes of the video. You can also use video editing software when putting it together MARKING CRITERIA The following criteria will be used to assess the assignment: Criteria Comments Available marks (100) Relevant ILO(s) Problem definition, Postulated deployment of Search and Optimisation (S&O) methods Problem definition S&O requirements specification Justification of S&O adopted methods Clarity of objectives 10% 1,2 S&O implementations In-depth knowledge and understanding of S&O approach deployments Implemented solver Completeness Articulated evidence of covered constraints and Improvement of the S&O benchmark approaches 20% 1,3,4 Coding Novelty of coding and good usage of software libraries Embedded challenges and complexities for S&O implementation Efficiency for S&O solver convergence 15% 3,4 Evaluation, validation and lessons learned Appraisal of achievement of project objectives. Appraisal of achievement of good understanding of S&O benchmarking in real-world problems Quality of evaluation, validation and lessons learned. Quality of future recommendations 15% 1,2,4 Project report Document structure and coherence. Literature support and references Scholarship and clarity of narratives 15% 1,2,4 Video Presentation Presentation structure, visual representations, coherence and quality 25% 1,2,3,4 Nov 2021 - v17 Page 5 of 7 APPROVED_L7_COMP7065_21-22_sub_brief The following sections describe what are the expectations for each level of achievement: To achieve a Pass: Attempt to solve both optimisation problems, exceeding benchmark approach in at least one of them. Produce a reasonable report and fully running code which takes advantage of existing implementations or libraries. Deliver a video presentation showing decent understanding of most aspects of the project. Actively participate in the development of the project. To achieve a higher mark: Solve both optimisation problems, exceeding benchmark approach in both of them. Produce an excellent report with details and fully running high quality code implemented by yourselves. Visualize the routing path and key findings in a good format. Compare different optimisation algorithms in terms of mechanism and computational complexity. Deliver a video presentation showing very good or excellent understanding of all aspects of the project. Actively participate in the development of the project. INTENDED LEARNING OUTCOMES (ILOs) This unit assesses your ability to: 1. Demonstrate knowledge and understanding of search and optimisation techniques and their applications. 2. Demonstrate critical awareness of the strengths and limitations of various stochastic search and optimisation techniques. 3. Implement search and optimisation solutions to real-world problems using modern algorithms and software libraries. 4. Design search and optimisation experiments and conduct rigorous statistical analysis of the results. QUESTIONS ABOUT THE BRIEF Please drop an email to jzhang3@bournemouth.ac.uk if you have any question about this assignment brief. Unit Leader Signature Jiankang Zhang Nov 2021 - v17 Page 6 of 7 APPROVED_L7_COMP7065_21-22_sub_brief mailto:jzhang3@bournemouth.ac.uk Help and Support Postgraduate Coursework Assessments If a piece of coursework is not submitted by the required deadline, the following will apply: 1. If coursework is submitted within 72 hours after the deadline, the maximum mark that can be awarded is 50%. If the assessment achieves a pass mark and subject to the overall performance of the unit and the student’s profile for the level, it will be accepted by the Assessment Board as the reassessment piece. The unit will count towards the reassessment allowance for the level; This ruling will apply to written coursework and artefacts only; This ruling will apply to the first attempt only (including any subsequent attempt taken as a first attempt due to exceptional circumstances). 2. If a first attempt coursework is submitted more than 72 hours after the deadline, a mark of zero (0%) will be awarded. 3. Failure to submit/complete any other types of coursework (which includes resubmission coursework without exceptional circumstances) by the required deadline will result in a mark of zero (0%) being awarded. The Standard Assessment Regulations can be found on Brightspace or via https://www1.bournemouth.ac.uk/students/help-advice/important-information (under Assessment). Exceptional Circumstances If you have any valid exceptional circumstances which mean that you cannot meet an assignment submission deadline and you wish to request an extension, you will need to complete and submit the online Exceptional Circumstances Form together with appropriate supporting evidence (e.g. GP note) normally before the coursework deadline. Further details on the procedure and links to the exceptional circumstances forms can be found on Brightspace or via https://www1.bournemouth.ac.uk/students/help-advice/looking-support/exceptional-circumstances. Please make sure that you read these documents carefully before submitting anything for consideration. For further guidance on exceptional circumstances please contact your Programme Leader. Referencing You must acknowledge your source every time you refer to others' work, using the BU Harvard Referencing system (Author Date Method). Failure to do so amounts to plagiarism which is against University regulations. Please refer to https://libguides.bournemouth.ac.uk/bu-referencing-harvard-style for the University's guide to citation in the Harvard style. Also be aware of Self-plagiarism, this primarily occurs when a student submits a piece of work to fulfill the assessment requirement for a particular unit and all or part of the content has been previously submitted by that student for formal assessment on the same/a different unit. Further information on academic offences can be found on Brightspace and from https://www1.bournemouth.ac.uk/discover/library/using-library/how-guides/how-avoid-academic-offences Additional Learning Support Students with Additional Learning Needs may contact the Additional Learning Support Team. Details can be found here: https://www1.bournemouth.ac.uk/als IT Support If you have any problems submitting your assessment please contact the IT Service Desk - +44 (0)1202 965515 - immediately and before the deadline. Disclaimer The information provided in this assignment brief is correct at time of publication. In the unlikely event that any changes are deemed necessary, they will be communicated clearly via e-mail and Brightspace and a new version of this assignment brief will be circulated. Nov 2021 - v17 Page 7 of 7 APPROVED_L7_COMP7065_21-22_sub_brief https://www1.bournemouth.ac.uk/students/help-advice/important-information https://www1.bournemouth.ac.uk/students/help-advice/looking-support/exceptional-circumstances https://libguides.bournemouth.ac.uk/bu-referencing-harvard-style https://www1.bournemouth.ac.uk/discover/library/using-library/how-guides/how-avoid-academic-offences https://www1.bournemouth.ac.uk/als