WGUPS Delivery Optimization Program

1. 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. Here’s why it’s a good fit:

• 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.
• It prioritizes efficiency by aiming to minimize total distance traveled.

1. 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.

1. Program Overview:
2. Algorithm Logic (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)

Use code with caution.

content_copy

2. Programming Environment:

• Software: Python 3.x (widely used and well-suited for this task)
• Hardware: Standard computer with sufficient processing power and memory

3. 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.

4. 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.

5. 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.

6. 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).

7. Justification for Key Choice: Package ID

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.