The project was deployed at Heroku and active on http://www.alexstrae.nu until april 2023. The code is available in /frontend. Super Deliveries was my very first React project, written in 2022, and contains some subpar solutions like setTimeout instead of useEffect's dependency array. I'm still fond of it and for the time being I want to keep it as it is, as it reminds me of how I have improved since.

Super Deliveries API

The goal of the program is to find the shortest possible delivery route for the highest valuable combination of orders. The program achieves this using the A* search algorithm, a dynamic knapsack solution and other logic. The user may:

1. Add, update or delete a custom order to the database and get all existing orders and 40 addresses from the database.
2. A unique, randomized delivery address is attached to each order. A graph is created from the addresses.
3. Optional: Choose a weight limit, as if you were delivering by bicycle for example, and get the most valuable combination of orders that meets the weight requirement. This is done through a dynamic implementation of the knapsack solution that allows you to get not only a total value, but the order(s) the value come from. POST orders to evaluate and receive the most valuable orders.
4. POST your orders and have the fastest route returned to you with its total distance, as well as the distance for other, simpler to calculate, delivery routes. Compare the distances; was the 'Super Deliveries' method the best?

Third-party libraries

Super Deliveries uses the flask framework and SQLAlchemy. The following third-party library imports are made:

• from flask import Flask, request
• from flask_restful import Api, Resource
• from flask_jsonpify import jsonify
• from sqlalchemy import create_engine, text
• from sorcery import dict_of

End points

Super Deliveries is a REST application. These end points are available:

/orders

All CRUD operations; Create, Read, Update and Delete any order in the database.

• Sending a GET will return a JSON of all rows with columns id, name, weight, value and address in table orders. IMPORTANT: Every time you send a GET to /orders, the orders will have new, randomized delivery addresses in respective 'address' field.
• POSTing requires a JSON with name, weight and value parameters. You can POST several orders in one go. A unique ID will be generated for them. Returns the same JSON.
• PUTting requires a JSON with already existing id, name, weight and value parameters. Returns the same JSON and status 200 if id existed. Returns same JSON and status 403 if not.
• Sending a DELETE requires no JSON - instead, send the request to /orders/{id} , {id} being the id of the order you'd have deleted. Returns null.

/resetOrders

Send a DELETE request to /resetOrders and the database will wipe (truncate) the order table and re-populate it with default orders.

/addresses

Supports GET. Returns all rows with columns id, name, coordinate_x and coordinate_y from table 'addresses'.

/limitingFactor/{factor}

Supports POST. Requires JSON of all orders to be considered and POST to /limitingFactor/{factor}, with {factor} being the weight limit. For example, ~/limitingFactor/22 to set a weight limit of 22 kilos. Returns a new JSON with a combination of orders that in total meets the weight requirement and with the highest total value.

/getRoute

Supports POST. Requires JSON of orders to calculate. Returns new JSON with:

• Calculated distances for all delivery methods. Compare them and see which one was best.
• Location of the logistics office
• The path the program traveled when delivering orders according to the Super Deliveries method
• Counters for total times Super Deliveries provided the best, shortest route and total calculation runs.

In practice:

1. Add, update or delete any orders as you please, then GET all orders
2. If you want, POST a JSON of the orders to the knapsack (limitingFactor endpoint) and have the most valuable combination returned that meets specified weight requirement.
3. GET all addresses. Using the provided coordinates in each address you can populate a table (a 2D-map) of 4 rows and 10 columns of addresses. You now have a table of all addresses, and all destinations since each order have a delivery address attached to it.
4. Get the final results by POSTING JSON of chosen orders to getRoute. Update your table with the final path the program traveled.

Testing

The program have unit tests implemented on the dynamic knapsack solution, the database connection and the A* search algorithm.

How does the 'Super Deliveries' method work?

1. It sorts the deliveries, starting with the direction proceeding a direction void of deliveries (if any). If all directions have deliveries, it starts with the direction with fewest deliveries. Then it travels clockwise on the delivery map.
2. After each delivery, it chooses the next delivery address that is closest to current position, as long as that address is in the same direction.
3. After delivering the last order in the current direction, it chooses the closest delivery address in next clockwise direction, and then repeats the second stage. Unless there are no deliveries left.

• Since the starting direction was proceeding one (or more) directions without deliveries, if any such existed, the route will skip as many empty areas as possible.

4. The route finally returns to base.

This produces a nice, circle-shaped route with few, if any, zig-zag patterns, in about 90% of the cases. See below for 'Can the SP method fail?'

How is the distance calculated using the other methods?

• The distance_by_foot is calculated by delivering the orders one by one, going back and forth from the logistics office.
• The distance_by_shortest is sorted in ascending order, starting with the delivery closest to the office, and ending with the one furthest away. Very effective if deliveries are all in the same direction. Very inefficient if not, as it produces a zig-zag delivery pattern.
• The distance_by_direction is sorted after direction. The program looks in the north direction first and then travels clockwise. Effective overall, but can unnecessarily move over empty areas in order to reach next delivery, and may have to go "back and forth" inside respective direction.
• All routes return to base in the end.
• All routes use the A* algorithm to find the shortest path to the next order in the sorted list. The difference between methods is the way the list is sorted.

Can the 'Super Deliveries' method fail to provide the fastest route?

Yes, it can. Sometimes, when the calculated orders are few, the 'clockwise' or the 'shortest by direction' method can get very favorable randomized addresses. If all addresses are in the same direction, the 'shortest by direction' method is tough to beat. Likewise, if the deliveries are in the North to South-East, the 'Super Deliveries' method gains no advantage over basic clockwise 'sorted by direction' since they both skip the void areas ('sorted by direction' always looks in the North first).

The finding of the closest target can actually result in a longer distance traveled:

Let's say the 'Super Deliveries' method is in the middle of the East district and starts targeting the next delivery. One of them is closer to the office than the other, but they are equally far from the current location. The program then chooses the last address considered and moves further away from the office. It then has to travel back, closer to the office again to reach the last order in the direction area. Then, it turns out the next area of direction (South-East) have orders very far away. The program has to travel out from the center of the map yet again in order to go there.

Since the orders considered were equally far away, it would have been better targeting the innermost order closest to the office first, then the order in between, then the one further out, and lastly move to the next area of delivery orders, already being on the way there. 'Super Deliveries' do not account for this. On the other hand, if the next direction of orders would have been closer to the center of the map, the impact on the total distance would have been less, perhaps even favorable.

Super Deliveries yields the best result in >80% of the time for few orders and 95% of the time for many orders. When it misses, it only miss by a few kilometers compared to the winning method.

Other

• Behind the scenes, the program creates a graph of addresses from addresses in the database. Based on the coordinates of the address, every address is awarded a direction from current logistics office. The logistics office address is in the center of the map.

• The dynamic knapsack solution not only saves a total value inside a 2d-array but a list of the orders this value came from. This is what allows the program to return a JSON with not just a maximum total value number for given weight, but the orders this value is derived from.

• The original Super Deliveries with a form of GUI in Terminal was developed in 5 days. The API version is a rewrite and took a couple more days. Some additional hours have been spent finding and squashing bugs.

• Future versions:

Load a zone from the Google Maps API and have the program use that as its graph/map and source of delivery addresses.

More default orders in the db DONE

A fancy, polished front-end DONE, see below

Adding the factor of storing orders while on the way to the logistics office, for a program more in accordance to JIT-delivery.

The ability to add more than one driver and optimizing deliveries based on delivery zones.