Vehicle Routing / Resource Scheduling Algorithm Design

Question

My first post here – hoping you can help me with designing an algorithm that I’ve been considering for a little while now – not sure what approach to take (VRPTW or resource scheduling or something else entirely!?)

To put it into a real word example, we have a whole lot of garden waste at a small number of locations (usually less than 5). The waste must all be transported to other locations within given time frames. To move the garden waste we have trailers, which must be towed by cars. Garden waste can only be dropped at the waste depot at certain times (time windows). At some sites we can drop off the trailer to be filled up or emptied by people there, but at other locations the driver of the car has to do it himself and the car must remain there. All timings can be calculated (i.e. loading / unloading times, transit times etc). Cars can move between sites without a trailer, trailers can be towed empty but trailers cannot move themselves between locations.

Our objective is to ensure all trailer loads of waste are transported whilst

• minimising the number of trailers and cars in use
• meeting all time windows for dropping off waste
• “balancing” the trailers – i.e. at the end of the day we have as many trailers at each location as were there at the start of the day

I thought of approaching this as a resource scheduling algorithm but I’m unsure how to handle the “balancing” of trailers.

One other method I considered was to consider the cars first. I could then select the earliest task and build a graph of all feasible tasks after that. If I then picked the longest path through the graph that would service the maximum number of trailer loads. I could then remove these tasks from the list of tasks and repeat until all tasks were serviced. I would then need to run over these list of trailer loads to work out the number of trailers required.

Any thoughts as to approach would be appreciated!

Answer 1

I agree with Jiri...you want a heuristic algorithm that gets reasonably close with an acceptable solution quickly and then refines from there.

I've worked at companies before that had delivery routing software and the approach they took was to use a genetic algorithm to solve very similar, though much larger scale, problem. Take a look here if you're not familiar with the approach. From that site:

1. [Start] Generate random population of n chromosomes (suitable solutions for the problem)
2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population

3. [New population] Create a new population by repeating following steps until the new population is complete

   [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)

   [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.

   [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).

   [Accepting] Place new offspring in a new population

4. [Replace] Use new generated population for a further run of algorithm
5. [Test] If the end condition is satisfied, stop, and return the best solution in current population
6. [Loop] Go to step 2

The trick to this is encoding your constraints into a "chromosome" and writing the "fitness" function. The fitness function has to take inputs of the results of a potential solution and spit out a score of how good a solution that is or throw it out if it violates any of the constraints.

As mentioned by Jiri, the advantage of this solution is that it comes up with a workable, though maybe not the best, answer very quickly and the longer you let it run, the better the solution gets.

Answer 2

We are talking a NP complete algorithm here for sure, beyond some number of cars and trailers this is not gonna be a task where you would get a best solution out of all possible solutions and then be able to discard that and go again to avoid the longest path as you suggest. If you design your algorithm in that way, its very likely that one day you add a bit more cars and trailers and it will never finish computing the solution.

You probably want to go with algorithm that can reasonably fast generate good enough solution of the problem. Make sure you create a metric for quality of the solution, you get a good way to estimate the value of the metric for an ideal solution, then set yourself some % within which you'd like your solution to be from an ideal solution and simply take the first solution that has metric within the bounds. This has the added benefit of if this algorithm is taking too long to compute and you abort it, you can still use the solution with the lowest computed metric, even if it is not in your expected bounds.

I'm not sure what approach to take the solving the problem itself though. I would suggest to read few articles after searching on acm portal. I would assume UPS and Fedex probably have similar problems, if you add them as keywords to a search in google, you could get some more useful results.