Truck Routing System

Overview

This project was to create the best route and delivery of several packages for Western Governors University Parcel Service (WGUPS). 40 packages need to be delivered across the Salt Lake City area utilizing two trucks and three drivers throughout a typical workday. The information for the packages contained certain constraints, delays, or errors that needed to be remedied before shipment.

Language

Python 3.7

March 2021 - April 2021

Senario

The Western Governors University Parcel Service (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.

I was tasked is to determine an algorithm, write code, and present a solution where all 40 packages will be delivered on time while meeting each package’s requirements and keeping the combined total distance traveled under 140 miles for both trucks. The specific delivery locations and distances to each location are given. 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.

Keep in mind that 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

Assumptions

• 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 (that 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.

Algorithm

This program utilized a greedy algorithm to optimize the delivery route of each truck. It takes the shorted path possible for each package from where it is currently located and repeats that process until there are no more packages to get delivered for that truck.

Scalability and Adaptability

The program can adapt to different size packages due to the fact that it is mainly linear in space and time complexity. This means that the package size can size up or down without much of an effect in space–time complexity.

Self-Adjusting Data Structures

Self-Adjusting Data Structures and Hash tables are great in the fact that they will always go with the path of the shortest distance. Also, the time complexity of a hash table is consistent no matter how large the data set is, which works well when there are applications that require different data sets that are both large and small. Collisions, however, can be a disadvantage to using hash tables as they can decrease performance.