A list,

Vehicle routing problem (VRP) was first proposed by Dantzig and Ramser in 1959. It refers to a certain number of customers with different demand for goods. Distribution center provides goods to customers, a fleet is responsible for distributing goods, and appropriate driving routes are organized. And under certain constraints, to achieve such as the shortest distance, the least cost, the least time and so on.



2.1 Vehicle Routing Problem with Capacity Constraints (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.







Problem attributes and faQs

The characteristics of vehicle routing problem are relatively complex and generally include four attributes:

(1) Address characteristics include: number of yards, demand type 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.

Ii. Source code

Tic clear CLC %% tic clear CLC %% tic clear CLC %%'rc208.txt');
cap=1000; Vertexs =data(:,2:3); % customer=vertexs(2:end,:); Cusnum =size(customer,1); % Number of customers v_num=25; % Max =data(2:end,4); % demand h=pdist(vertexs); dist=squareform(h); % Distance matrix %% Genetic algorithm parameter setting alpha=10; % Penalty function coefficient for capacity constraint violation NIND=50; % Population size MAXGEN=200; % Number of iterations Pc=0.9; % cross probability Pm=0.05; % variation probability GGAP=0.9; % Generation gap N= Cusnum +v_num- 1; % chromosome length = number of customers + maximum number of vehicles used- 1%% population initialization Chrom=InitPop(NIND,N); %% Output route and total distance of random solution disp('A random value in the initial population :')
[currVC,NV,TD,violate_num,violate_cus]=decode(Chrom(1,:),cusnum,cap,demands,dist); % of initial solution decoding currCost = costFuction (currVC, dist, demands, cap, alpha); % The cost of the initial distribution scheme = the total cost of the vehicle +alpha* The sum of the capacity constraints violated disp(['Number of Vehicles used:',num2str(NV),', total distance travelled by vehicle:,num2str(TD),', number of paths violating constraints: ',num2str(violate_num),', number of customers violating constraints: ',num2str(violate_cus)]);
disp('~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~'%% BestCost=zeros(MAXGEN,1); % Record the total cost of the global optimal solution for each generation gen=1;
whileGen < = MAXGEN calculation fitness ObjV % % = calObj (Chrom, cusnum, cap, demands, dist, alpha); % Calculate population objective function value FitnV=Fitness(ObjV); % % choose SelCh = Select (Chrom, FitnV, GGAP); SelCh=Recombin(SelCh,Pc); % % variable SelCh = Mutate (SelCh, Pm); % % local search operations SelCh = LocalSearch (SelCh cusnum, cap, demands, dist, alpha); %% Chrom=Reins(Chrom,SelCh,ObjV); %% delete the duplicate individuals in the population, and complement the deleted individuals Chrom=deal_Repeat(Chrom); % % to print the current optimal solution ObjV = calObj (Chrom, cusnum, cap, demands, dist, alpha); % Calculate population objective function value [minObjV,minInd]=min(ObjV); BestCost(gen)=minObjV; disp(['the first',num2str(gen),'Optimal solution of generation :'])
    [bestVC,bestNV,bestTD,best_vionum,best_viocus]=decode(Chrom(minInd(1),:),cusnum,cap,demands,dist);
    disp(['Number of Vehicles used:',num2str(bestNV),', total distance travelled by vehicle:,num2str(bestTD),', number of paths violating constraints: ',num2str(best_vionum),', number of customers violating constraints: ',num2str(best_viocus)]);
    fprintf('\n') %% Number of update iterations gen=gen+1; End %% Print the total cost variation trend figure of the global optimal solution for each iteration of the outer loop; plot(BestCost,'LineWidth'.1);
title('Trend chart of total cost of global Optimal solution')
xlabel('Number of iterations');
ylabel('Total cost'); Draw_Best (bestVC,vertexs); tocCopy the code

3. Operation results



Fourth, note

Version: 2014 a