A delivery planner

The problem

Build a program that plans a day's deliveries: which parcels to load on a van with a weight limit, and the cheapest route to each customer.

Requirements

• The map is read from a file as towns and roads with lengths
• Dijkstra's algorithm finds the shortest route from the depot to each town, and the route itself is printed
• A 0/1 knapsack chooses the parcels that earn the most within the van's weight limit
• The chosen parcels are recovered from the table, not only their total value
• Towns that cannot be reached are reported, and their parcels are not loaded
• Bad input gives a clear message instead of a crash

Technologies

• C
• Graphs
• Dijkstra's algorithm
• Dynamic programming
• File input

Step by step

1. Read the towns and roads into a weight matrix or adjacency lists.
2. Write Dijkstra's algorithm, recording for each town the town it was reached from.
3. Print a route by following those records back from the destination.
4. Read the parcels, leaving out any whose destination cannot be reached.
5. Fill the knapsack table, then walk back through it to find which parcels were taken.
6. Print the load list and the route to each customer.
7. Test with a town that cannot be reached, a van too small for any parcel, and a single parcel.

Expected result

A working planner that gives the best load and the shortest route to every customer.

How it is evaluated

• Every route printed is a shortest route
• The load has the highest possible value within the limit
• Unreachable towns and empty loads are handled calmly
• The code is split into small functions, each with one job

Ways to improve it

• Use a heap to make Dijkstra faster on large maps
• Plan a round trip through a few towns with bitmask dynamic programming
• Add a time window for each customer