Vehicle Routing Problem
Your homework will be to solve the Vehicle Routing Problem using the ant colony optimization. The VRP is just a generalized travelling salesman problem – the goal is to optimize the delivery of parcels for a delivery company. We have depots, each with its own vehicles with a given capacity and a set of shipments that need to be delivered to their owners. The goal is to find a set of delivery routes in such a way that all shipments are delivered to the owners and that the total cost is minimized. More specifically, that the least number of vehicles is used and that the routes are as short as possible.
For the homework, we will use a simplified version of this problem with a single depot that has an unlimited number of vehicles of one type. The input data can be found in the attached zip file. It contains three different inputs in the XML format - 2 small ones and a larger one. Each file contains:
- A list of nodes with x and y coordinates, where the node with type 0 is a depot, and the others with type 1 are customer locations.
- A list of vehicles, in this case we have one type of vehicle that must start and end at the depot and has a maximum capacity of items it can carry.
- A list of requirements, i.e. to which node what needs to be delivered.
In your submission, you should mention how you adapted the source codes from the lesson to solve this particular problem and also show the convergence plots of the algorithm for all three input files. Do not forget to mention the best solution you found.
The deadline for this assignment is May 16, 2023.