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

I tend to agree with Robert. This sounds to me like a really great candidate for an evolutionary optimisation technique like the Genetic Algorithm implementation that he describes.

I have also had very good success on certain problems with the Particle Swarm Optimisation (PSO).Basically, you can think of each genome as a particle in some multi dimensional space. The coordinates of the particle are the paramters to your calculation (fitness function). Each particle is started of randomly with a random velocity. For each iteration of the simulation, you update the position of each particle with its current travel vector, and then you add components of other vectors like: direction to the best particle so far, direction to the best particle ever, direction to a local group best etc...

It may seem rather daunting at first to implement a GA or PSO but I assure you that it is easy to write a small framework that abstracts the algorithm (GA/PSO) from the actual problem domain that you are trying to optimise. You can always fall back to Wikipedia for details of the algorithms.

Once I have a framework, I normally start with a 2 parameter problem (probably a simplification of your problem, or X and Y locations on an image), so that I can easily visualise and tweak the algorithm so that I get good swarming behaviour. Then I scale it up to more dimensions.

I like this approach because it allows me to easily optimise for problems that have rather complex and intricate parts to the actual problem statement (like the cars and trailers).

Also, why the evolutionary techniques are attractive is because you can dedicate a fixed portion of time to the simulation and take the best answer so far when you decide to stop.

In my experience, you tend to take as much time tweaking the parameters to the GA or PSO (once you have an implementation) as you would writing a hard coded heuristic solution, but the benefit is that to change the strategy for finding the solution typically requires parameter changes only or swapping out very well defined algorithms with another implementation, as opposed to coding a completely different strategy to solving the problem heuristically from scratch.

Please give me a shout if you need guidance on designing the generic frameworks for either of the two algorithms. I must point out, that you get several good free 3rd party frameworks out there too. I sometimes like to code my own because I understand every aspect of the algorithm then and I know where I can adjust the strategy.

Answer 3

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.

Answer 4

Local Search are an alternative to genetic algorithms. In the International Timetabling Competition 2007, local search algorithms (such as tabu search and simulated annealing) clearly beat the genetic algorithm entries (1 to 4th place for LS versus 5th place for GA in track 1 out of about 80 competitors IIRC).

Also, take a look at some of the libraries out there, such as OptaPlanner (Tabu Search, Simulated Annealing, Late Acceptance, open source, java), JGap (genetic algorithms, open source, java), OpenTS (Tabu Search, ...

Answer 5

General Approach:

Since the problem is small, I would suggest an approach where you add cars and trailers until you get a feasible solution rather than trying to minimize cars and trailers.

Solving:

I've had less success on GAs with constraints and even less success on GAs with constraints on integer variables (e.g. the number of trailers in a location). It may be that constraint programming is a better approach since you just want to generate a feasible solution for a given number of cars and trailers rather than trying to minimize distance travelled.

Observation:

You're solving the problem on a network where the last moves may be to relocate an empty trailer.

Good luck !