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: 2 Problem Attributes and FaQsThe characteristics of vehicle routing problem are relatively complex and generally include four attributes: (1) Address characteristics include the number of parking lots, demand types and operation requirements. (2) Vehicle characteristics include: vehicle number, carrying weight constraints, carrying variety constraints, running route constraints, and working time constraints. (3) Other characteristics of the problem. (4) The objective function may be to minimize the total cost, or minimize the maximum operating cost, or maximize just-in-time operations.

3 Common problems are as follows:(1) Traveling salesman Problem (2) Vehicle Routing problem with Capacity Constraint (CVRP) The model was difficult to extend to other scenarios of VRP and the execution paths of specific vehicles were not known, so the model continued to be improved. (3) Vehicle routing problem with Time Windows (VRP with Time Windows) is a vehicle routing problem with Time Windows (VRP with Time Windows, VRPTW), considering that demand points have requirements on vehicle arrival Time. The Vehicle Routing problem with Time Windows (VRPTW) is a time window constraint for the customer to be visited on the VRP. In the VRPTW problem, in addition to the driving cost, the cost function also includes the waiting time caused by arriving at a customer early and the service time required by the customer. In VRPTW, vehicles must not only meet the constraints of VRP problems, but also meet the Time Window constraints of demand points. The Time Window constraints of demand points can be divided into two types, one is Hard Time Window, which requires that vehicles must arrive within the Time Window. Early arrival must wait, while late arrival is rejected. The other is the Soft Time Window. It is not necessary to arrive in the Time Window, but to arrive outside the Time Window must be punished. The biggest difference between the Soft Time Window and the hard Time Window is to replace waiting and rejection with punishment. Model 2(refer to 2017 A generalized Formulation for Vehicle Routing problems) : This model was formulated with two-dimensional decision variables (4) Collection and distribution problem (5) Reference for multi-yard vehicle routing problem (2005 Lim, Genetic Algorithm for multi-yard vehicle routing problem _ Zou Tong, 1996 Renaud)Since vehicles are homogeneous, the modeling here does not include vehicle dimensions in the variables. (6) priority constraint vehicle route problem (7) compatibility constraint vehicle route problem (8) random demand vehicle route problem

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 Genetic algorithm theory2.1 Biological basis of genetic algorithm 2.2 Theoretical basis of genetic algorithm 2.3 Basic concepts of genetic algorithm 2.4 Standard genetic algorithm 2.5 Characteristics of genetic algorithm 2.6 Improvement direction of genetic algorithm 3. Genetic algorithm flow 4 Key Parameters

Three, some source code

Clear CLC close all TIC %%'shuju7');
bl=0; E=shuju(1.4); % start time of time window L=shuju(1.5); % end time of initial snack window zuobiao=shuju(:,2:3); % y and x =[zuobiao(:,1),-zuobiao(:,2)];
customer=zuobiao(2:end,:); Cusnum =size(customer,1); % Number of customers v_num=1; % Vehicles a=shuju(2:end,4); % Customer time window start time [a[I],b[I]] b=shuju(2:end,5); % Customer time window end time [a[I],b[I]] F=shuju(2:end,1);
dist=load('shiji7.mat'); Dist =struct2cell(dist); dist=cell2mat(dist); %% Genetic algorithm parameter set chesu=300; The speed of alpha = %100000; % Penalty function coefficient belta=chesu/ for capacity constraint violations1000; % Penalty function coefficient belta2= for violating the time window constraint1;


NIND=1000; % Population size MAXGEN=50; % Number of iterations Pc=0.9; % cross probability Pm=0.05; % variation probability GGAP=0.9; % Generation gap N=cusnum; [s,g,sj,gk,Chrom]=init(Cusnum,NIND,F); % construct initial solution %% output route and total distance of random solution disp('A random value in the initial population :')

[VC,TD,violate_cus]=decode(Chrom(1,:),cusnum,a,b,L,dist,chesu,bl);
% disp(['Total distance:',num2str(TD)]);
disp(['Total distance travelled:',num2str(TD)]);
disp('~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~'Function lineStyles=linspecer(N,varargin)if nargin==0 % return a colormap
    lineStyles = linspecer(128);
    return;
end

if ischar(N)
    lineStyles = linspecer(128,N);
    return;
end

if N<=0 % its empty, nothing else to do here
    lineStyles=[];
    return;
end

% interperet varagin
qualFlag = 0;
colorblindFlag = 0;

if ~isempty(varargin)>0 % you set a parameter?
    switch lower(varargin{1})
        case {'qualitative'.'qua'}
            if N>12 % go home, you just can't get this.
                warning('qualitiative is not possible for greater than 12 items, please reconsider');
            else
                if N>9
                    warning(['Default may be nicer for ' num2str(N) ' for clearer colors use: whitebg(''black''); ']);
                end
            end
            qualFlag = 1;
        case {'sequential'.'seq'}
            lineStyles = colorm(N);
            return;
        case {'white'.'whitefade'}
            lineStyles = whiteFade(N);return;
        case 'red'
            lineStyles = whiteFade(N,'red');return;
        case 'blue'
            lineStyles = whiteFade(N,'blue');return;
        case 'green'
            lineStyles = whiteFade(N,'green');return;
        case {'gray'.'grey'}
            lineStyles = whiteFade(N,'gray');return;
        case {'colorblind'}
            colorblindFlag = 1;
        otherwise
            warning(['parameter ''' varargin{1} ''' not recognized']);
    end
end      
% *95.
% predefine some colormaps
  set3 = colorBrew2mat({[141.211.199]; [255.237.111]; [190.186.218]; [251.128.114]; [128.177.211]; [253.180.98]; [179.222.105]; [188.128.189]; [217.217.217]; [204.235.197]; [252.205.229]; [255.255.179]}'); set1JL = brighten(colorBrew2mat({[228, 26, 28]; [55, 126, 184]; [77, 175, 74]; [255, 127, 0]; [255, 237, 111] *. 85; [166, 86, 40]. [247, 129, 191]; [153, 153, 153]; [152, 78, 163]} '));
set1 = brighten(colorBrew2mat({[ 55.126.184] *85.; [228.26.28]; [77.175.74]; [255.127.0]; [152.78.163]}),8.);

% colorblindSet = {[215.25.28]; [253.174.97]; [171.217.233]; [44.123.182]};
colorblindSet = {[215.25.28]; [253.174.97]; [171.217.233] *8.; [44.123.182] *8.};

set3 = dim(set3,93.);

if colorblindFlag
    switch N
        %     sorry about this line folks. kind of legacy here because I used to
        %     use individual 1x3 cells instead of nx3 arrays
        case 4
            lineStyles = colorBrew2mat(colorblindSet);
        otherwise
            colorblindFlag = false;
            warning('sorry unsupported colorblind set for this number, using regular types');
    end
end
if ~colorblindFlag
    switch N
        case 1
            lineStyles = { [  55.126.184] /255};
        case {2.3.4.5 }
            lineStyles = set1(1:N);
        case {6 , 7.8.9}
            lineStyles = set1JL(1:N)'; case {10, 11, 12} if qualFlag % force qualitative graphs lineStyles = set3(1:N)';
            else % 10 is a good number to start with the sequential ones.
                lineStyles = cmap2linspecer(colorm(N));
            end
        otherwise % any old case where I need a quick job done.
            lineStyles = cmap2linspecer(colorm(N));
    end
end
lineStyles = cell2mat(lineStyles);

end

% extra functions
function varIn = colorBrew2mat(varIn)
for ii=1:length(varIn) % just divide by 255
    varIn{ii}=varIn{ii}/255;
end        
end

function varIn = brighten(varIn,varargin) % increase the brightness

if isempty(varargin),
    frac = 9.; 
else
    frac = varargin{1}; 
end

for ii=1:length(varIn)
    varIn{ii}=varIn{ii}*frac+(1-frac);
end        
end

function varIn = dim(varIn,f)
    for ii=1:length(varIn)
        varIn{ii} = f*varIn{ii};
    end
end

function vOut = cmap2linspecer(vIn) % changes the format from a double array to a cell array with the right format
vOut = cell(size(vIn,1),1);
for ii=1:size(vIn,1)
    vOut{ii} = vIn(ii,:);
end
end
%%
% colorm returns a colormap which is really good for creating informative
% heatmap style figures.
% No particular color stands out and it doesn't do too badly for colorblind people either.
% It works by interpolating the data from the
% 'spectral' setting on http://colorbrewer2.org/ set to 11 colors
% It is modified a little to make the brightest yellow a little less bright.
function cmap = colorm(varargin)
n = 100;
if ~isempty(varargin)
    n = varargin{1};
end

if n==1
    cmap =  [0.2005    0.5593    0.7380];
    return;
end
if n==2
     cmap =  [0.2005    0.5593    0.7380;
              0.9684    0.4799    0.2723];
          return;
end

frac=95.; % Slight modification from colorbrewer here to make the yellows in the center just a bit darker
cmapp = [158.1.66; 213.62.79; 244.109.67; 253.174.97; 254.224.139; 255*frac, 255*frac, 191*frac; 230.245.152; 171.221.164; 102.194.165; 50.136.189; 94.79.162];
x = linspace(1,n,size(cmapp,1));
xi = 1:n;
cmap = zeros(n,3);
for ii=1:3
    cmap(:,ii) = pchip(x,cmapp(:,ii),xi);
end
cmap = flipud(cmap/255);
end

function cmap = whiteFade(varargin)
n = 100;
if nargin>0
    n = varargin{1};
end

thisColor = 'blue';

if nargin>1
    thisColor = varargin{2};
end
switch thisColor
    case {'gray'.'grey'}
        cmapp = [255.255.255;240.240.240;217.217.217;189.189.189;150.150.150;115.115.115;82.82.82;37.37.37;0.0.0];
    case 'green'
        cmapp = [247.252.245;229.245.224;199.233.192;161.217.155;116.196.118;65.171.93;35.139.69;0.109.44;0.68.27];
    case 'blue'
        cmapp = [247.251.255;222.235.247;198.219.239;158.202.225;107.174.214;66.146.198;33.113.181;8.81.156;8.48.107];
    case 'red'
        cmapp = [255.245.240;254.224.210;252.187.161;252.146.114;251.106.74;239.59.44;203.24.29;165.15.21;103.0.13];
    otherwise
        warning(['sorry your color argument ' thisColor ' was not recognized']);
end

cmap = interpomap(n,cmapp);
end

% Eat a approximate colormap, then interpolate the rest of it up.
function cmap = interpomap(n,cmapp)
    x = linspace(1,n,size(cmapp,1));
    xi = 1:n;
    cmap = zeros(n,3);
    for ii=1:3
        cmap(:,ii) = pchip(x,cmapp(:,ii),xi);
    end
    cmap = (cmap/255); % flipud??
end




Copy the code

4. 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.