1 Mathematical Model

(1) Explanations and assumptions about the model

1) Known quantities in the model include: location coordinates of each demand point, quantity of material demand at each demand point, arrival time requirements of materials at each demand point, the shortest driving distance between distribution center and each demand point, and the shortest transportation distance between each demand point.

2) The field investigation found that the materials to be distributed can be mixed on the same material rack, and the quantity of materials required by each demand point is smaller than the stock of the material warehouse.

3) Ignore external factors unfavorable to production, such as crowded queues encountered by vehicles in the distribution process, that is to say, the whole assembly workshop runs normally. At the same time, the type, speed and load capacity of the vehicles used in the distribution process are the same, and the distribution vehicles run at a uniform speed in the workshop.

4) Due to the different consumption rates of materials at each production station, in order to better conduct the research, the consumption rates of materials at each demand point should be consistent with the corresponding planned production beat, and the reproduction status of unqualified products should be ignored.

(2) Several constraints on the model

In the modeling process, the following constraints should be taken into account.

1) On each distribution path, the sum of material demands at all demand points shall not exceed the maximum loading capacity of unit distribution vehicles

2) There is only one vehicle on each distribution path for material delivery, and no other vehicles can be used for delivery. Moreover, delivery vehicles only arrive at each demand point on each path once.

3) All the distribution vehicles go out of afa by the same distribution center for material distribution activities. After the distribution activities, the vehicles must return to the original distribution center, and there is no loading situation during the distribution process.

4) For two adjacent demand points on the same distribution path, the moment when the vehicle arrives at the previous demand point shall not exceed the moment when it arrives at the later demand point.





2 Genetic Algorithm

Step 1: The setting of relevant parameters, generally including coding length L, population size M, iteration times G, crossover rate Pc, mutation rate Pm, etc.

The second step: in the algorithm, the solution in the mathematical model cannot be directly used for operation, and the solution needs to be processed to construct the chromosome of the adaptive function.

Step 3: M individuals are randomly generated to form the initial population Po, and the individuals are distributed in the solution space in order. Each individual is a corresponding solution of the problem.

Step 4: Calculate the fitness of each individual, and conduct selection and other operations in the population according to the fitness.

Step 5: According to the fitness of each individual, select individuals with high fitness for individual selection and other operations, usually using roulette, etc.

Step 6: Set crossover rate Pc to control the crossover operation of the parent chromosome, and the crossed individual will replace the parent to enter the new population.

Step 7: Set mutation rate Pm to control mutation operation of paternal chromosome. Mutations can cause genes not present in the population or eliminated in the selection process to reappear, and mutated individuals to replace their fathers into the new population.

Step 8: Judge whether the updated population meets the termination conditions after the selection, crossover and mutation operations in the next iteration. If not, re-enter the fourth step to carry out the cycle iteration process. If so, the algorithm is stopped, and the maximum number of iterations is usually used as the termination criterion.

Step 9: Decode the chromosomes that meet the termination conditions to obtain the optimal solution of the problem. According to the above steps, the basic process of genetic algorithm can be known

Genetic operations

1) The selection operation adopts roulette to operate the selected individual. 2) The crossover operation exchanges part of the selected two paternal chromosomes to form a new individual. The crossover operation method in this paper is a partial matching crossover method. Firstly, random crossover points were generated for transformation, and then repeated gene fragments were eliminated. The specific operation of crossover was as follows: Parent 1: A E C/H D F G/I B Parent 2: C f a /b g h e/I d The two intersection points randomly generated in parents 1 and 2 were at oblique positions, and then the gene fragments in the middle of oblique positions of parents 1 and 2 were exchanged and placed at the positions of each chromosome head to obtain parent 1 and parent 2, as follows: parent 1*: B g h e /a e c h d f g I b Parent 2*: h d f g g /c f a b g h e I d Progeny 1 and 2: progeny 1: b g h e a c d f I H d f g c a b e I 3) mutation variation is random location in the chromosomes of value transformation, he is a kind of method can produce besides cross to generate new individual, by setting the mutation probability to randomly select a single chromosome to operate, which contains a random mutation way, insert and exchange of three methods of mutation. Taking one chromosome R =(G, A, F, H, C, B, I, D, E) as an example, the flipping operation is to randomly generate two cut points on the chromosome and flip the middle part of the cut points. Assuming that the cut points are between A-F and I-D, the new chromosome is rm=(G, A, I, B, C, H, F, D, E). The insertion operation is to randomly generate a certain number in a-N as the mutation point. Assuming that the selected gene is I and the tangent point is between E-G, the selected gene is placed at the insertion point to obtain the mutation chromosome Rm =(G, A, F, I, H, C, B, D, E). The switching operation is to randomly generate two points as the two selected genes, and then swap the positions of the two selected gene points. The randomly selected genes are H and D, and the mutant chromosome RM = (7, a, F, D, C, B, I, H, E) is obtained. The detailed process is shown as follows. The fitness of the new individuals who have completed the mutation is calculated, and the good results generated by the mutation are retained and the bad ones are eliminated. In this way, the diversity of the population is well preserved and the algorithm develops in a better direction. R: g a f h c b I d e flip: g a f/h c b I/d e g a I b c h f d e insert: g a f/h c b I d e g g a f I h c b d e g a f h c b i d e g a f d c b i h e

The simulation results







Optimized data









Matlab code display

Clear CLC close all tic %% % shuju= importData ('cc101.txt'); load('cc101'); shuju=c101; % bl=importdata('103.txt'); bl=0; cap=800; % maximum vehicle loading %% extracted data information E=shuju(1,5); % start time of distribution center time window L=shuju(1,6); % End time of distribution center time window zuobiao=shuju(:,2:3); % vertexs= vertexs./1000; customer=zuobiao(2:end,:); Cusnum =size(customer,1); % number of customers v_num=6; % Max value =shuju(2:end,4); A =shuju(2:end,5); % customer time window start time [a[I],b[I]] b=shuju(2:end,6); % customer time window end time [a[I],b[I]] s=shuju(2:end,7); % Customer point service time h=pdist(zuobiao); % dist=load('dist1.mat'); % dist=struct2cell(dist); % dist=cell2mat(dist); % dist=dist./1000; Dist =squareform(h); C [I][j]=dist[I][j] %% genetic algorithm parameter setting alpha=100000; % penalty function coefficient belta=900 for capacity constraint violation; % Penalty function coefficient belta2=60 for violating the time window constraint; Chesu = 0.667; NIND=100; % population size MAXGEN=50; % iteration times 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 -1 % N= Cusnum; Init (Cusnum, A,demands,cap); Chrom=InitPopCW(NIND,N,cusnum,init_vc); %% Output route and total distance of random solution disp(' a random value in the initial population :') [VC,NV,TD,violate_num,violate_cus]=decode(Chrom(1,:),cusnum,cap,demands,a,b,L,s,dist,chesu,bl); % disp(' disp: ',num2str(TD)]); Disp (' number of vehicles used: ',num2str(TD),',num2str(TD),', violate_num (violate_num),', number of customers violated: ',num2str(violate_cus)]); Disp (' ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ') % % optimization gen = 1; figure; hold on; Box on xlim([0,MAXGEN]) title(' optimized process ') xlabel(' algebra ') ylabel(' optimal value ') ObjV=calObj(Chrom,cusnum,cap,demands,a,b,L,s,dist,alpha,belta,belta2,chesu,bl); % preObjV=min(ObjV); While gen < = MAXGEN calculation fitness ObjV % % = calObj (Chrom, cusnum, cap, demands, a, b, m, s, dist, alpha, belta, belta2, chesu, bl); % Calculate population objective function value line([gen-1,gen],[preObjV,min(ObjV)]); Pause (0.0001)% preObjV=min(ObjV); 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, a, b, L, s, dist, alpha, belta, belta2, chesu, bl); %% 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, a, b, L, s, dist, alpha, belta, belta2, chesu, bl); % Calculate population objective function value [minObjV,minInd]=min(ObjV); Disp ([' ',num2str(gen),' ']) [bestVC,bestNV,bestTD,best_vionum,best_viocus]=decode(Chrom(minInd(1),:),cusnum,cap,demands,a,b,L,s,dist,chesu,bl); Disp ([' number of vehicles used: ',num2str(bestNV),',num2str(bestNV),',num2str(best_vionum),', number of customers violated the constraint: ',num2str(best_vionum),', ',num2str(best_viocus)]); Fprintf ('\n') %% Number of iterations gen=gen+1; End % % of the optimal solution roadmap ObjV = calObj (Chrom, cusnum, cap, demands, a, b, m, s, dist, alpha, belta, belta2, chesu, bl); % Calculate population objective function value [minObjV,minInd]=min(ObjV); Disp (' best solution :') bestChrom=Chrom(minInd(1),:); [bestVC,bestNV,bestTD,best_vionum,best_viocus]=decode(bestChrom,cusnum,cap,demands,a,b,L,s,dist,chesu,bl); Disp ([' number of vehicles used: ',num2str(bestNV),',num2str(bestNV),',num2str(best_vionum),', number of customers violated the constraint: ',num2str(best_vionum),', ',num2str(best_viocus)]); Disp (' -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - ') % % determine the optimal solution meets the time window constraints and capacity constraints, 0 means in violation of the constraints, 1 to satisfy all constraints flag = Judge (bestVC, cap, demands, a, b, L, s, dist, chesu, bl); DEL=Judge_Del(bestVC, Cusnum); init_v=vehicle_load(bestVC,demands); Draw_Best (bestVC,zuobiao);Copy the code
  • The code download www.cnblogs.com/matlabxiao/…