I. Introduction to VRP
1 Basic principles of VRPVehicle Routing Problem (VRP) is one of the most important research problems in operations research. VRP is concerned with the path planning of a supplier and K points of sale, which can be summarized as: for a series of delivery points and receiving points, the organization calls certain vehicles, arranges appropriate driving routes, and makes the vehicles pass through them in an orderly manner, under specified constraints (e.g. The demand and quantity of goods, delivery and delivery time, vehicle capacity limit, mileage limit, driving time limit, etc.), and strive to achieve certain goals (such as the shortest total mileage of empty vehicles, the lowest total transportation cost, vehicles arrive at a certain time, the use of the smallest number of vehicles, etc.). The legend of VRP is as follows:
3 Common problems are as follows:(1) Traveling salesman Problem (2) Vehicle Routing problem with Capacity Constraint (CVRP)
4 solutions (1) mathematical analysis method (2) human-computer interaction method (3) group and then arrange route method (4) group and then arrange route method (5) save or insert method (6) improve or exchange method (7) mathematical programming approximation method (8) heuristic algorithm
5 Comparison between VRP and VRPTW
Introduction to genetic algorithm
1 the introduction 
Three, some source code
%% includes charging stations1
clc;
clear all
close all
filename='.\evrptw_instances\c101_21.txt';
[NO,type,XCOORD, YCOORD,DEMAND,READY_TIME,DUE_DATE,SERVICE_TIME]=textread(filename,'%s%s%s%s%s%s%s%s'.'headerlines'.1); Empirical solution path K= Randperm (100); % Randomly sort customer points M=30; % Task capacity =200; % timewindows_yuanshi=[str2num(char(READY_TIME))'; str2num(char(DUE_DATE))']; % time window coordinate_yuanshi=[str2num(char(XCOORD)),str2num(char(YCOORD))]; % Coordinate information Coordinate_chongdianzhan =[coordinate_yuanshi(2:22.1)'; Coordinate_yuanshi (2:22, 2) '; ]'; Demand_yuanshi =str2num(char(DEMAND))'; Service_yuanshi =str2num(char(SERVICE_TIME))'; % All service time D=distanse(coordinate_yuanshi); % distance 1 coordinate=[coordinate_yuanshi(1,1),coordinate_yuanshi(K(1:M)+22,1)'; coordinate_yuanshi(1.2),coordinate_yuanshi(K(1:M)+22.2)'; ] '; % Center and customer location timeWindows =[timewindows_yuanshi(1.1),timewindows_yuanshi(1,K(1:M)+22) ;timewindows_yuanshi(1.2),timewindows_yuanshi(2,K(1:M)+22)]; % demand=[demand_yuanshi(1),demand_yuanshi(K(1:M)+22)]; % service=[service_yuanshi(1),service_yuanshi(K(1:M))+22]; % Coordinate_yuanshi1 =[Coordinate_yuanshi (1.1),coordinate_yuanshi(23:end,1)'; Coordinate_yuanshi coordinate_yuanshi (1, 2), (23: end, 2) '; ]';%中心和客户坐标位置
% D1=distanse(coordinate_yuanshi1);%距离
D2=distanse(coordinate);%距离
renwudian1=[1,K(1:M)+1];%包括起点的任务点
Q=77.751111;%电量
r=1;%消耗率
g=0.39;%充电
v=1;%速度
% %% 遗传参数初始化
C=500;%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定
Pc=0.9;%交叉概率
Pm=0.4;%变异概率
popsize=80;%种群数量
%经验公式m=[Σgi /aq]＋1,粗求车辆数
function [ farm ] = crossover( farm,n,k,popsize,Pc )
%CROSSOVER Summary of this function goes here
% Detailed explanation goes here
% ⑴随机产生交叉位，如果在交叉位的外侧两端的父代基因都是0的话，则对父代1
% 进行简单交叉；如果交叉位的外侧两端的父代基因不为0的话，则将左交叉位向左
% 移，直至移动到左交叉位的左端基因为0时停止。以左交叉位为起点，继续向右移
% 动右交叉位，直至右交叉位的右端基因为0为止。这样就保证了父代染色体都用1条
% 子路径来进行交叉。
% ⑵经过第1步操作，子代中仍会产生访问同一客户2次的情况，需要对
% 子代进行整理。在子代中选择那些具有重复情况的自然数，如果该自然数并非
% 在交叉位内的话，则删除之。子代如存在未访问到某一客户的情况，则在染色
% 体的交叉位外补上该客户对应的自然数。
% ⑶经过第2步的操作，如果产生了某一子路径为空的情况，即染色体中含
% 有2个连续的0，须继续进行第3步操作。将其中的1个0与染色体其它位上
% 的客户自然码进行交换。对该客户自然码的要求是该码的前一位与后一位均不
% 为0。本步操作可放在对子代的变异后进行。
function temp = minsert(chrom,num,n)%insert函数，向量中指定位置插入数
%n是要插入的位置（之后）
[x,xx] = size(chrom);
temp = zeros(1,xx+1); %初始化
temp(1,1:n) = chrom(1,1:n);
temp(1,n+1) = num;
temp(1,(n+2):(xx+1)) = chrom(1,(n+1):xx);
end
function temp = mdelete(chrom,n)%delete函数，向量中指定位置删除数
%n是要删除数的坐标
[x,xx] = size(chrom);
temp = zeros(1,xx-1); %初始化
temp(1,1:n-1) = chrom(1,1:n-1);
temp(1,n:xx-1) = chrom(1,(n+1):xx);
end
total = n+k+1;
for i = 1:(popsize/2) %按对进行交叉
if Pc > rand
chromosome1 = zeros(1,total);
chromosome2 = zeros(1,total);
chromosome1 = farm(i,:); %染色体1
chromosome2 = farm(popsize - i + 1,:); %染色体2
%第一步*************************************************************
ran1L = round(rand*(total-3)+2); %随机数1 注意1和最后不要随机到
while chromosome1(1,ran1L) == 0 %不能随机到0
ran1L = round(rand*(total-3)+2);
end
ran1R = ran1L;
ran2L = round(rand*(total-3)+2); %随机数2
while chromosome2(1,ran2L) == 0 %不能随机到0
ran2L = round(rand*(total-3)+2);
end
ran2R = ran2L;
while chromosome1(1,ran1L-1) ~= 0 %左移直至第一个0出现
ran1L = ran1L - 1;
end
while chromosome1(1,ran1R+1) ~= 0 %右移直至第一个0出现
ran1R = ran1R + 1;
end
while chromosome2(1,ran2L-1) ~= 0 %左移直至第一个0出现
ran2L = ran2L - 1;
end
while chromosome2(1,ran2R+1) ~= 0 %右移直至第一个0出现
ran2R = ran2R + 1;
end
%交换片段**********************************************************
temp1 = zeros(1,total); %临时储存
temp2 = zeros(1,total); %临时储存
length1 = ran1R-ran1L+1; %片段长
length2 = ran2R-ran2L+1; %片段长
for ii = 1:length1 %转移到临时储存
temp1(1,ii) = chromosome1(1,ran1L+ii-1);
end
for ii = 1:length2 %转移到临时储存
temp2(1,ii) = chromosome2(1,ran2L+ii-1);
end
chrom1 = zeros(1,total+length2-length1); %中间染色体1
chrom2 = zeros(1,total+length1-length2); %中间染色体2
%重新拼接染色体***************************************************
chrom1(1,1:ran1L-1) = chromosome1(1,1:ran1L-1);
chrom1(1,ran1L:ran1L+length2-1) = temp2(1,1:length2);
chrom1(1,ran1L+length2:total+length2-length1) = chromosome1(1,ran1R+1:total);
chrom2(1,1:ran2L-1) = chromosome2(1,1:ran2L-1);
chrom2(1,ran2L:ran2L+length1-1) = temp1(1,1:length1);
chrom2(1,ran2L+length1:total+length1-length2) = chromosome2(1,ran2R+1:total);
%第二步*************************************************************
nala1 = zeros(1,total);%搜索temp2中有而temp1中没有的数,那个数1中必定重复
nala11 = zeros(1,total);%存放nala中数的位置
nala2 = zeros(1,total);%搜索temp1中有而temp2中没有的数,那个数2中必定重复
nala22 = zeros(1,total);%存放nala中数的位置
%搜索相互没有的数
kk = 1; %nala的下标 好累啊，wwwww......
for ii = 1:length2
flag = 0;
for j = 1:length1
if temp2(1,ii) == temp1(1,j);
flag = 1;
end
end
if flag == 0
nala1(1,kk) = temp2(1,ii);
kk = kk + 1;
end
end
kk = 1; %nala的下标
for ii = 1:length1
flag = 0;
for j = 1:length2
if temp1(1,ii) == temp2(1,j);
flag = 1;
end
end
if flag == 0
nala2(1,kk) = temp1(1,ii);
kk = kk + 1;
end
end
%将多余的数设为0***************************************************
ii = 1;
while nala1(1,ii) ~= 0
[x,xx] = find(chrom1==nala1(1,ii)); %找出重复的位置
j = 1;
while xx(1,j) >= ran1L && xx(1,j) <= ran1L+length2-1
j = j + 1;
end
nala11(1,ii) = xx(1,j); %将重复数的位置保存下来
chrom1(1,xx(1,j)) = 0; %%重复的数变为零
ii = ii + 1;
end
ii = 1;
while nala2(1,ii) ~= 0
[x,xx] = find(chrom2==nala2(1,ii)); %找出重复的位置
j = 1;
while xx(1,j) >= ran2L && xx(1,j) <= ran2L+length1-1
j = j + 1;
end
nala22(1,ii) = xx(1,j); %将重复数的位置保存下来
chrom2(1,xx(1,j)) = 0; %%重复的数变为零
ii = ii + 1;
end
%补上没有的数******************************************************
[xx,x] = size(nonzeros(nala1));%得到nala的大小
[yy,y] = size(nonzeros(nala2));%得到nala的大小
if yy-xx < 0 %交换后变成yy>xx的情况
%交换
[chrom1,chrom2] = exchange(chrom1,chrom2);
[nala1,nala2] = exchange(nala1,nala2);
[nala11,nala22] = exchange(nala11,nala22);
end
% yy-xx > 0 --> 说明变化后1比2短-->1需要补0并且插入,2需要补0并且删0
% yy-xx < 0 --> 说明变化后2比1短-->2需要补0并且插入,1需要补0并且删0
%补0
ii = 1;
while nala11(1,ii) ~= 0
chrom1(1,nala11(1,ii)) = nala2(1,ii);%1中补0
chrom2(1,nala22(1,ii)) = nala1(1,ii);%2中补0
ii = ii + 1;
end
%||||||||stage3|||||||||
%当前ii在下一位的位置
%1插入&2删除*****************************************************
model1 = chrom1; %用来适应变量维度
model2 = chrom2;
j = 1; %!!!!!!!j初始化应该放在while循环外面，小错误不断啊
flag_nala22 = 1;
% %两个chrom的维度是一个问题
% chrom11 = zeros(1,total);
% chrom22 = zeros(1,total);
while nala2(1,ii) ~= 0
%插入，先扩充model->存储变维后的数据；然后chrom扩充，得到model保存的数据
model1 = [model1,0]; %注意顺序
model1 = minsert(chrom1,nala2(1,ii),1);
chrom1 = [chrom1,0];
chrom1 = model1;
%删除0，首先降序排列,用来从后向前删除；之后model变维
while flag_nala22 %又是一个错误，靠，nala22temp每次循环都会被初始化，1次就够了，细心细心，淡定淡定......
nala22temp = zeros(1,total-ii+1);
nala22temp = nala22(1,ii:total);
flag_nala22 = 0;
end
nala22temp = sort(nala22temp);
nala22temp = fliplr(nala22temp);
[q,qq] = size(chrom2);
model2 = zeros(1,qq-1); %注意顺序
model2 = mdelete(chrom2,nala22temp(1,j));
j = j + 1;
chrom2 = zeros(1,qq-1);
chrom2 = model2;
%千万不要忘记迭代+1
ii = ii + 1;
end
farm(i,:) = chrom1;
farm(popsize - i + 1,:) = chrom2;
%在整个算法中，我通过重复的数设0避免了0接着0的情况，很有成就感。
end %交叉概率检测
end %main loop
end %function
Copy the code4. Operation results
Matlab version and references
1 matlab version 2014A
[1] Yang Baoyang, YU Jizhou, Yang Shan. Intelligent Optimization Algorithm and Its MATLAB Example (2nd Edition) [M]. Publishing House of Electronics Industry, 2016. [2] ZHANG Yan, WU Shuigen. MATLAB Optimization Algorithm source code [M]. Tsinghua University Press, 2017.