AI powered Routing Tool
As an Artificial Intelligence intern at Kinematic Foodtech, I worked on a Routing Tool to manage the delivery fleet and create routes to reduce the company's logistics costs.
Tech Stack used:
- Python
- Google OR Tools
- Openrouteservice
- AWS
- Flask
- JavaScript
- HTML
- Shapely
The basic structure of the tool can be divided into two NP-hard problems:
- Capacitated Vehicle Routing Problem with Time Windows and Multiple Depots (CVRPTWMD)
- Facility Location and Allocation Problem
Capacitated Vehicle Routing Problem with Time Windows and Multiple Depots
Minimization Objective: The tools provides option to use two minimization objectives -
- Total cost of travelling for all vehicles
- Total distance traveled by all vehicles
Cost of a vehicle is divided into:
- Fixed Cost per trip
- Running Cost per km.
- Minimum Billing per trip
Different Vehicles have different cost.
Capacity Constraints:
- Each vehicle has a different maximum capacity (number of boxes) they can carry at a time.
Time Window Constraints:
- Each customer has a different time window in which their order can be delivered.
- If some orders cannot be delivered in their time window with the given number of delivery riders, the time window of all orders are increased by a small step (a maximum time increase is set) to ensure that all orders are delivered.
Multiple Depot: There are two types of depots -
- Static depots (or kitchens) - These are the kitchens where food is prepared and the drivers which can leave from here are decided beforehand.
- Dynamic depots (or hubs) - These depots are the facilities created after solving the facility location and allocation problem. A vehicle must deliver the appropriate orders from a static depot to each of the dynamic depots from where other delivery riders would pick their respective orders to further deliver to customers.
Note: There is a start time for depots which tells the earlier any delivery riders can leave from there.
Time spent at delivery location:
- The tool incorporates the time the delivery rider would spend at the delivery location for calling the customer, finding the exact apartment, etc. which creating the dispatch plan.
- Some corporate orders require a team to serve the food to them and thus, only large vehicles can deliver to them.
Facility Location and Allocation Problem
A modified version of k-mean clustering algorithm which uses the distances provided by the Openrouteservice API instead of Euclidean distance for creating facilities/hubs. The position of static hubs is also taken into account while creating the dynamic hubs.
The number of facilities to create is determined by using an automated version of elbow method as described in this article.
The generated hubs are then shown to the operations team to confirm or slightly modify the positions of the dynamic hubs as per their need before they start the route generation.