Bakers Fresh, a local bakery in Brisbane, prides itself on delivering freshly baked products to its loyal customers. As the customer base grows, planning optimal delivery routes for its trucks has become
Written and Programming Assessment Due date: 11:55 pm AEST, Friday of Week 8 (03 May 2024)
Weighting: 25%
Mode: Individual
Length: Maximum 2,000 words (Assessment Report – Max. 1,500
words, and Reflection – Max. 500 words)
Full Mark: 100
Objectives
This assignment is designed to reinforce the knowledge and skills acquired in Week 5 to Week 7. It is an individual assessment to be submitted in Week 8. The assessment task relates to Unit Learning Outcomes 1, 2 and 4, and must be done and submit individually.
Problem Description
Bakers Fresh, a local bakery in Brisbane, prides itself on delivering freshly baked products to its loyal customers. As the customer base grows, planning optimal delivery routes for its trucks has become increasingly challenging. Currently, the bakery relies on a manual process for assigning deliveries to its drivers. This often leads to sub-optimal routes, resulting in longer delivery times that has negatively impacted customer satisfaction.
To address this problem, Bakers Fresh is hiring you to develop a more efficient method for planning the delivery routes. As an example, figure 1 shows how delivery routes may be seen as paths in a graph. The numbers on the edges denote the distances between pairs of locations.
Figure 1. This figure is by an Unknown Author licensed under CC BY-SA-NC
Tasks
Part 1: Modelling and Algorithm Design (25 marks)
1. Problem Modelling (10 marks):
o Explain how the delivery scenario can be modelled as a graph. Identify nodes and edges and their meaning in the context of the problem.
o Consider the choice of data structures for representing nodes and edges. Explain your choice. If the choice of data structures is different for both uninformed and informed search algorithms, explain the difference.
2. Algorithm Design (15 marks):
o Design an algorithm based on A* search to find the shortest delivery route. Include pseudo code with comments explaining the major steps of the algorithm.
o Briefly discuss the heuristic function that you are using in the A* search.
o Choose an uninformed search algorithm you have come across as the candidate to compare with the A* search. Explain this uninformed search algorithm.
Part 2: Implementation (40 marks)
1. Python Implementation (30 marks):
o Implement the A* search algorithm in Python using your chosen data structures.
o Implement the uninformed search algorithm in Python for comparison.
o Ensure your code is well-documented and includes comments explaining your logic.
2. Test Data Design (10 marks):
o Design the test data, including at least 20 delivery locations (discounting the location of Bakers Fresh), for the comparison.
o Include the test data in your Python code.
Part 3: Testing and Analysis (20 marks)
1. Testing (10 marks):
o Test your implemented algorithms (A* and chosen uninformed) with the designed test data.
o Capture screenshots of the test output from your Python program for both algorithms.
2. Analysis (10 marks):
o Compare and analyse the performance of both the A* and the uninformed search algorithm in terms of:
Efficiency (number of nodes explored)
Optimality (shortest route found)
Other relevant performance metrics you can think of
o Discuss which of A* search and the uninformed search performs better in the specific problem of this assignment. Why?
Part 4: Reflection (15 marks)
1. Reflection (15 marks):
o Summarise your learnings from this assignment.
o Reflect on the strengths and limitations of the implemented algorithms.
o Propose potential improvements on either or both algorithms.
Submission
Each student must upload these two files via the Assignment 2 submission link on the COIT20277 HT1,
2
2024 Moodle assessment block by the specified due date. Late submission will incur a penalty as per the university’s Assessment Policy and Procedure.
1. Submit a Jupyter notebook containing your Python code, test data, and analysis with screenshots. 2. Include a separate Word document containing your written report, covering problem modelling, algorithm design, and reflection.
Marking Rubric (maximum 100 marks)
Part 1: Modelling and Algorithm Design (25 marks)
Part 2: Implementation (40 marks)
Part 3: Testing and Analysis (20 marks)
3
Part 4: Reflection (15 marks)