Introduction
I would like to share with you how I solved Vehicle Routing Problem using genetic algorithm and C#.
Background
The vehicle routing problem (VRP) is the problem of finding a set of minimum-cost vehicle routes which start at a central depot, serve a set of customers with known demands, and return to the depot without any violation of constraints.
We can imagine real life example as – planning delivery of water to customers on next day. Customer’s demands and vehicle capacities are known values.
Current version of solution works only with demand constraints, although at the moment I am working on adding others - time windows, route priorities etc.
Algorithm description
In its core VRP Solver uses parallel genetic algorithm for solving problems.
Each possible solution is represented as chromosome, which can be crossed over with other chromosomes and mutated. In result, child is added to population. Population number is limited and weakest chromosomes are deleted.
In addition, multiple separate populations are maintained. After number of epochs, randomly selected chromosome is added to another population.
Chromosome representation
Each chromosome is represented as array of arrays, where each nested array represent route and all of them represent solution to problem:
Crossovers
Two types of crossovers operations are used – random (RC) and uniform (UC)
Random crossover
Algorithm selects random length part of random route from parent 1, removes all points that present in this route part from parent 2 and inserts part to parent 2, on place which results in minimum total distance.
Uniform crossover
Algorithm calculates density of each route for parent 1 and 2. Then, it selects 1 by 1 route from parents. When adding no new route is possible, points that are left out are added to places to give minimum total distance.
Mutations
Algorithm uses 2 types of mutations – random part mutation and distant customer mutation.
Random part mutation cuts random route part and inserts it to place which gives minimum distance. Distant customer finds most distant customer on random route and moves it to best alternative place.
Local optimizations
After crossover and mutate operations, each algorithm tries to rearrange customers of each route to result in minimum total distance.
Fitness function
Fitness function is calculated as:
Fitness = total distance + route overload*penalty for overload + route under load*penalty for under load
Maintaining unique chromosomes only
For fast convergence only unique chromosomes are added to population
Parallel populations
Number of parallel populations is maintained and after number of epochs migrations are performed.
End of calculation
Calculation is stopped if either maximum number of epochs has been reached or no improvement has been made for last N epochs.
How algorithm parameters were selected
Algorithm settings have 11 parameters. Number of variations with sensible values result in more than 100K options.
For parameters selected separate tool was developed that simulated some kind of tournament for selecting best parameters.
First, it processed test problem using random parameter values and stored results in DB. Then, some kind of semi-final was organized where problems that performed
best within shortest time run 3 times each on bigger list of test problems. In final, best performance parameters were used to run all available (~100) problems.
In result, we have few sets of parameters some of which give best results within acceptable time and vice versa.
Results of algorithm work
Results of work on some of standard problems are listed below. First number in problem name stands for number of points, second – for optimal number of vehicles.
For example, B-n31-k5 means 31 points and 5 vehicles.
Results on 8 core AMD CPU (8350):
Other results can be found on http://nayzer.com/Benchmark-Results.ashx
Solution architecture
Overview
VRP Solver is written in C# and consists from number of services, queues, and DBs:
List of tools/frameworks used:
- .NET 4.5 / C# / WCF / WinService
- Queue: RabbitMQ
- DB: MongoDB
- DI container: Autofac
- Unit tests: MS Test / Rhino Mocks / Fluent assertions
C# lessons learned
- Don’t use properties in performance critical parts of code, public field only
- Minimize use of Lists and Dictionaries and prefer Arrays (add custom Insert and Remove methods where needed)
Next steps
Current version of solution is free for use, you can find details on www.nayzer.com
At the moment I am working on adding new functionality:
- Getting distance between points using their coordinates
- Adding more constraints – by time windows, vehicle to point priority mappings etc.
Literature used
Web contains a lot of material about a problem. Here are some of the articles I have used:
- Solving the Vehicle Routing Problem with Genetic Algorithms http://etd.dtu.dk/thesis/154736/imm3183.pdf
- A hybrid algorithm for the Vehicle Routing Problem with Time Windows http://www2.ic.uff.br/~satoru/conteudo/artigos/PAPER%20IESM2011-SABIR.pdf
- A Route-directed Hybrid Genetic Approach for the Vehicle Routing Problem with Time Windows http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.9531
