Genetic Algorithm for Open Vehicle Routing Problem

In this post, I’m going to show you my Matlab code of Genetic Algorithm for solving open vehicle routing problem. It is possible to download and customize this Matlab code to solve new vehicle routing problems.

Vehicle routing problem (VRP) has many useful applications in industry such as transportation and logistics. Vehicle routing problem is a combinatorial optimization problem, in which we are required to find the optimal set of routes for vehicles to visit in order to deliver to a given set of customers. The vehicle routing problem is a generalization of the well-known travelling salesman problem (TSP). Open vehicle routing problem (OVRP) is a vehicle routing problem in which vehicles are not required to return to the depot.

Finding the optimal solution to open vehicle routing problem is NP-hard (Non-deterministic Polynomial), which means that the run-time will not be polynomial. So, deterministic methods can’t solve large-size problems because massive computing time will be required. Instead, we often use stochastic methods. In this post, we’re going to use genetic algorithm to solve open vehicle routing problems.

Let’s see how my Genetic Algorithm works:

For more videos like this, check my YouTube channel here.

Matlab Code

population.m

function Y=population(n,nc)
% nc = number of cities
% n = pop size
B=zeros(n,nc);
for j=1:n
    A=1:1:nc;   
    [x y]=size(A);
    for i = 1:nc
        r = randi(y);
        B(j,i)=A(r);
        A(:,r) = [];
        [x y]=size(A);
    end
end
Y=B;

crossover.m

function YY = crossover(X,n)
% X = population
% n = Number of chromosomes to be crossed
[x1 y1] = size(X);
Y = zeros(n,y1);

for z = 1:n
    B = X(randi(x1),:); % select parent chromosome
    r1 = 1 + randi(y1-1);
    C = B(1,1:r1);
    B(:,1:r1) = [];  % cut
    [x3 y3] = size(B);
    B(1,y3+1:y1) = C;
    Y(z,:) = B;
end
YY = Y;

mutation.m

function Y = mutation(X,n)
% X = population
% n = number of chromosomes to be mutated
[x1 y1]=size(X);
Y=zeros(n,y1);

for z=1:n
    A=X(randi(x1),:); % select parent chromosome
    r1=1+randi(y1-1,1,2);
    while r1(1)==r1(2)
            r1=1+randi(y1-1,1,2);
    end
    B=A(1,r1(1));
    A(1,r1(1))=A(1,r1(2));
    A(1,r1(2))=B;
    Y(z,:)=A;
end
YY = Y;
.
.
.
Sorry! This is only a part of the Matlab code.

Notice: It would take you from 1 to 3 hours to re-type the Matlab code yourself; or with just €2.99 (the cost of a cup of coffee), you can download/copy the whole Matlab code within 2 minutes. It’s your choice to make.

Original price is €4.99 but today it’s only €2.99 (save €2 today – available for a limited time only)

Download the whole Matlab code here (Membership Code ID: 024)

No need to build the Matlab code from scratch because it’s very time-consuming. My idol, Jim Rohn, once said: “Time is more value than money. You can get more money, but you cannot get more time”. If you think this code can be used in your research/teaching work, you should download it and then customize/modify/apply it to your work, without any obligation of citing the original source if you don’t want. However, redistribution (i.e., downloading the code/script here and then making it available on another site on the Internet) is strictly prohibited.

If you have any question or problem, please contact Dr. Panda by email: learnwithpanda2018@gmail.com

Thank you very much and good luck with your research!