Python Project
WGUPS needs to determine an efficient route and delivery distribution for their daily local deliveries (DLD) because packages are not currently being consistently delivered by their promised deadline. The Salt Lake City DLD route has three trucks, two drivers, and an average of 40 packages to deliver each day. Each package has specific criteria and delivery requirements that are listed in the attached WGUPS Package File.
Your task is to determine an algorithm, write code, and present a solution where all 40 packages will be delivered on time while meeting each packages requirements and keeping the combined total distance traveled under 140 miles for all trucks. The specific delivery locations are shown on the attached Salt Lake City Downtown Map, and distances to each location are given in the attached WGUPS Distance Table. The intent is to use the program for this specific location and also for many other cities in each state where WGU has a presence. As such, you will need to include detailed comments to make your code easy to follow and to justify the decisions you made while writing your scripts.
The supervisor should be able to see, at assigned points, the progress of each truck and its packages by any of the variables listed in the WGUPS Package File, including what has been delivered and at what time the delivery occurred.
Each truck can carry a maximum of 16 packages, and the ID number of each package is unique.
The trucks travel at an average speed of 18 miles per hour and have an infinite amount of gas with no need to stop.
There are no collisions.
Three trucks and two drivers are available for deliveries. Each driver stays with the same truck as long as that truck is in service.
Drivers leave the hub no earlier than 8:00 a.m., with the truck loaded, and can return to the hub for packages if needed.
The delivery and loading times are instantaneous (i.e., no time passes while at a delivery or when moving packages to a truck at the hub). This time is factored into the calculation of the average speed of the trucks.
There is up to one special note associated with a package.
The delivery address for package #9, Third District Juvenile Court, is wrong and will be corrected at 10:20 a.m. WGUPS is aware that the address is incorrect and will be updated at 10:20 a.m. However, WGUPS does not know the correct address (410 S. State St., Salt Lake City, UT 84111) until 10:20 a.m.
The distances provided in the WGUPS Distance Table are equal regardless of the direction traveled.
The day ends when all 40 packages have been delivered.
TASK:
A. Identify a named self-adjusting algorithm (e.g., nearest neighbor algorithm, greedy algorithm) that could be used to create your program to deliver the packages.
B. Identify a self-adjusting data structure, such as a hash table, that could be used with the algorithm identified in part A to store the package data.
1. Explain how your data structure accounts for the relationship between the data components you are storing.
C. Write an overview of your program in which you do the following:
1. Explain the algorithms logic using pseudocode.
2. Describe the programming environment you will use to create the Python application, including both the software and hardware you will use.
3. Evaluate the space-time complexity of each major segment of the program and the entire program using big-O notation.
4. Explain the capability of your solution to scale and adapt to a growing number of packages.
5. Discuss why the software design would be efficient and easy to maintain.
6. Describe both the strengths and weaknesses of the self-adjusting data structure (e.g., the hash table).
7. Justify the choice of a key for efficient delivery management from the following components:
delivery address
delivery deadline
delivery city
delivery zip code
package ID
package weight
WGUPS Delivery Optimization Program
A. Algorithm: Savings Algorithm (Self-Adjusting)
The Savings Algorithm is a well-suited choice for this program. It's a self-adjusting algorithm from the family of Cluster-First Route Planning algorithms. It iteratively analyzes potential pairings of undelivered packages, calculating the "savings" achieved by merging deliveries into a single truck route. This self-adjusting nature allows the algorithm to adapt to package locations and priorities.
B. Data Structure: Hash Table
A Hash Table is a good choice for storing package data due to its efficient retrieval based on unique keys.
- Relationship between Data Components: The package ID will be the key for the Hash Table. Each entry in the Hash Table will be a custom class containing all the other package data (delivery address, deadline, etc.) This allows for quick access to specific package information using the unique ID.
C. Program Overview:
- Pseudocode:
Python
# Initialize variables
packages = read_package_data() # Read package data from file
trucks = [Truck(capacity=16) for _ in range(3)] # Create 3 trucks
unallocated_packages = packages.copy() # Copy all packages for tracking
# Savings Algorithm loop
while unallocated_packages:
# Calculate savings for all undelivered package combinations
savings_matrix = calculate_savings(unallocated_packages)
# Find the pair with the highest savings
best_pair, best_savings = find_best_saving_pair(savings_matrix)
# Check if valid (within capacity and deadline)
if is_valid_merge(best_pair, trucks):
# Add packages to chosen truck route
merge_routes(trucks[best_pair[0]], trucks[best_pair[1]], best_pair)
# Remove packages from unallocated list
unallocated_packages.remove(best_pair[0])
unallocated_packages.remove(best_pair[1])
# Dispatch trucks and track progress (implementation details omitted)
dispatch_trucks(trucks)
track_progress(trucks)
- Programming Environment:
- Software: Python 3.x (widely used and well-suited for this task)
- Hardware: Standard computer with sufficient processing power and memory
- Space and Time Complexity:
- Space Complexity: O(n) - The Hash Table and truck data structures scale linearly with the number of packages (n).
- Time Complexity:
- Overall Program: O(n^2) - The Savings Algorithm involves calculating savings for all package pairs (potentially n^2 calculations).
- Major Segments:
calculate_savings: O(n^2) - Nested loop iterates through all package pairs.find_best_saving_pair: O(n^2) - Iterates through the savings matrix.is_valid_merge: O(1) - Constant time operation for checking capacity and deadline.
- Scalability:
The program adapts to a growing number of packages. While the time complexity increases with more packages, the core logic remains efficient for route planning with moderate numbers of deliveries (hundreds). For very large datasets, alternative algorithms with lower time complexity (e.g., Genetic Algorithms) might be explored.
- Software Design Efficiency and Maintainability:
- Modular design with clear functions promotes maintainability.
- Using a Hash Table for data storage allows for efficient access and updates.
- Well-commented code improves readability and future modifications.
- Hash Table Strengths and Weaknesses:
- Strengths:
- Efficient average-case retrieval based on the key (package ID).
- Relatively simple to implement and use.
- Weaknesses:
- Potential for collisions (same hash value for different keys). This can be mitigated by good hash function selection and collision resolution techniques.
- Not ideal for frequent insertions and deletions, as these can affect performance. (In our case, insertions happen at program start, and deletions are infrequent).
- Justification for Key Choice:
Package ID is the most efficient key for delivery management. It's a unique identifier that allows for direct retrieval of all relevant package information without needing additional comparisons or calculations. Other options like delivery address would require additional processing to identify packages at specific locations.