Service for solving Vehicle Routing Problem using genetic algorithms and C#

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 

1. Don’t use properties in performance critical parts of code, public field only
2. 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:

1. Getting distance between points using their coordinates
2. 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:

1. Solving the Vehicle Routing Problem with Genetic Algorithms http://etd.dtu.dk/thesis/154736/imm3183.pdf
2. A hybrid algorithm for the Vehicle Routing Problem with Time Windows http://www2.ic.uff.br/~satoru/conteudo/artigos/PAPER%20IESM2011-SABIR.pdf
3. 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