Package Routing Application

Python application for optimizing package delivery according to time and distance constraints.

Index

1. Application Features
2. User Interface
3. Delivery Constraints
4. Notable Concepts Involved
5. Package Input Data
6. Location Data
7. Algorithm Overview
8. Results

Application Features

• Graphical User interface that animates the delivery process.
• Console readout to provide narrative of each delivery step.
• User can check the status of package at a given time.
• User can add additional packages to any of the defined locations.
• Animations options can be adjusted to the user's preferences.

Back To Top

Notable Concepts

• Space-time complexity is evaluated using Big O notation throughout the entire program (see code).
• A Greedy Algorithm was implemented for determining the next package delivery.
• A hash table was implemented for storing the packages.
• Tkinter was used to develop the GUI.

Back To Top

User Interface

The user interface animatings the delivery process.
It also allows the user to customize the package status checks, add additional packages, and toggle animation options.
The user interface was created using Tkinter.

Back To Top

Delivery Constraints and Assumptions

• 40 Packages must be delivered by the end of the day.
• 2 trucks are available for delivery - they cannot travel more than a combined 140 miles.
• Each truck can only hold 16 packages.
• Each package has a destination that it must be delivered to and a deadline for when it must arrive by.
• Each location has a distance provided to each of the other possible locations available for delivery.
• Each truck drives an average of 18 miles per hour and spends no time loading or unloading packages.
• A package could be delayed, rerouted, or have other packages that it must travel with.

Back To Top

Package Data

All the necessary package information is inputted into the program as the above .csv file.

Back To Top

Location Data

All the necessary location information is inputted into the program as the above .csv file.

Back To Top

Algorithm / Delivery Walkthrough

Delivery Process (Greedy Algorithm)

1. All packages with deadlines are loaded on to the first truck.
2. If there is still room, packages going to the same destination as a loaded package gets loaded on the truck.
3. The current truck location is then analyzed to determine the closest delivery location for a loaded package.
4. The truck travels to the location and unloads the package (Steps 3 and 4 repeat).
5. Once new packages with deadlines are available, the truck returns to the hub to load them.
6. Truck 1 delivers all the remaining packages that it has loaded.
7. Truck 2 begins loading all packages at the hub until it is full.
8. It then uses the earlier described greedy algorithm to delivery its packages.
9. When truck 2 is empty, it returns to the hub for more packages.
10. Once all packages are delivered, the delivery process is complete.

Truck 1 Delivery Route

The result of truck 1's delivery route can be seen above.

Truck 2 Delivery Route

The result of truck 2's delivery route can be seen above.

Status Report at 10:00 AM

The status of all packages at 10:00AM can be seen above.

Status Report at 13:00 PM

The status of all packages at 13:00PM can be seen above.

Back To Top

Results

All constraints are respected, and the total mileage at the end of the delivery process is 115 miles. For a complete narrative of each step of the delivery process, see the following link:

Delivery Application Console Output

Back To Top