Comparative Study of GA, Simulated Annealing And Hybrid of Both Strategies on a CVRP


Meta heuristic algorithms are often used to produce good approximations to NP-hard combinatorial optimization problems within an acceptable time frame. This work measures statistical difference between applying two of such algorithms on a Capacitated Vehicle Routing Problem (CPVRP).

In CPVRP, there are two objectives to be optimized: number of vehicles and total distance covered by all vehicles. The work first conducts an independent multi-objective experiment of either algorithm on a CVRP dataset. However both algorithms are known for their strengths and weaknesses therefore, a new approach that combines both strategies is used to overcome their disadvantages. Using the hybrid approach, a population based search algorithm (Genetic Algorithm (GA)) is used to optimize both objectives using Weighted Sum (WS) fitness measure, by placing a bigger weight on the number of vehicles. This biases the search towards optimizing number of vehicles. Routes for the best-evolved solution produced by GA are further optimized using a local search algorithm (Simulated Annealing (SA)) as a post optimizer to move distance discovered by each vehicle in GA to its local optima. When compared to GA and SA, the hybrid strategy recorded improved solutions however was statistically insignificant using a t-test with confidence level 0.05.

I developed the entire system was developed in Java

see source code on:
https://www.github.com/aawuley/evolutionary-computation



  1. Comparative Study of GA, Simulated Annealing And Hybrid of Both Strategies on a CVRP
  2. Comparative Study of GA, Simulated Annealing And Hybrid of Both Strategies on a CVRP
  3. Comparative Study of GA, Simulated Annealing And Hybrid of Both Strategies on a CVRP
  4. Comparative Study of GA, Simulated Annealing And Hybrid of Both Strategies on a CVRP
  5. Comparative Study of GA, Simulated Annealing And Hybrid of Both Strategies on a CVRP
Click to toggle comment form

From research

Feature Selection ALPS

Feature selection is the process of refining input data by removing irrelevant and/or redundant features. Feature selection deals with selection of a ...

read more »

Genetic Algorithms Problems

In my spare time, i enjoy working on some NP complete problems. The latest ones include(but not limited to) feature selection, computer ...

read more »

Comparing GA & ACO on TSP

Genetic Algorithm and Ant Colony Optimization was tested on a TSP. According to the results, ACO outperformed GA on the TSP problem. ...

read more »

Recent Works

From My Blog

  1. Feature Selection ALPS

    Feature selection is the process of refining input data by removing irrelevant and/or redundant features. Feature selection deals with selection of a ...

    Posted Fri, October 2 2015 at 1:14 pm
  2. Genetic Algorithms Problems

    In my spare time, i enjoy working on some NP complete problems. The latest ones include(but not limited to) feature selection, computer ...

    Posted Mon, October 20 2014 at 7:48 am
  3. Comparing GA & ACO on TSP

    Genetic Algorithm and Ant Colony Optimization was tested on a TSP. According to the results, ACO outperformed GA on the TSP problem. ...

    Posted Mon, October 20 2014 at 6:33 pm
  4. Evolutionary Algorithms

    I am the community owner and administrator of the "Evolutionary Algorithms" group on g+

    Posted Mon, October 20 2014 at 6:33 pm
  5. Genetic Programming

    I am the community owner and administrator of the "Genetic Programming" group on g+

    Posted Mon, October 20 2014 at 6:33 pm
  6. Grey Intel

    see https://www.facebook.com/greyintel/

    Posted Mon, October 20 2014 at 6:33 pm