Using Graph Theory in Vehicle Routing Problem

Question

I am working on a Vehicle Routing Problem with a single depot. The problem definition is as follows. There are n vechiles that need to travel to m number of sites. Each site has its specific constraints like only vehicles with certain capacity can serve the site, some sites need to be served at a particular time of the day. Also the vehicles will be of different capacity and will have different start and finish times.

The idea is to minimize the travel time for the vehicles from the depot.

I am in the process of constructing the cost matrix for the problem. Though not an expert in Graph theory, I know that I could use the Hamiltonian Cycle to solve the problem if it fell into a classical Travelling Salesman problem. However, because it falls into a multiple travelling salesman problem I want to know how I can address the problem using Hamiltonian cycles, or if there is another process specifically designed to target problems as such?

Any help would be much appreciated.

Answer 1

The constraint of sites needing vehicles of a certain capacity make this problem also analogous to the knapsack problem. See here: knapsack problem on wikipedia

This problem seems pretty unique so I would think you'll need a combination of techniques used to solve the knapsack problem and shortest path problem. First, figure out which vehicles to assign to each site (knapsack). Then figure out if the shortest path of vehicles to their site intersect with the path of other vehicles, in descending order of capacity, and reassign responsibilities as necessary.