1 Background

Suppose there are 20 small islands in the sea area of an archipelago, and each island produces different kinds of seafood. Now it is necessary to carry out outward transportation of seafood of each island, and select a central island as the central hub (hereinafter referred to as the central island); The cargo of each island is transported to the central hub island, and then transported from the central island to the mainland. The optimal transportation route is determined by referring to various factors. There are two types of ships transported from each island to the central island. And choose the ship. Matlab programming, tabu search method.

Given the geographical characteristics of remote islands, their transport network generally consists of three nodes: the mainland port, the central island and the satellite island. The mainland port is the logistics and transportation channel of the island relying on the mainland. The central island is a hub for collecting supplies from the surrounding islands; Satellite islands are the terminal islands that supply production supplies to the central islands.

First of all, since the sea navigation is greatly affected by typhoon, it is necessary to prevent the interruption of inter-island transportation. The statistical data of typhoon occurrence in this area are analyzed, and the probability distribution curve of typhoon influence time is obtained by data fitting combined with the living data of each island. Under certain guarantee rate, the average daily production capacity of each island is established under the premise of non-spoilage. Then, optimization of the location and traffic of the central island is necessary. The structure of the transport system includes the number of routes, the form of transport organization and arrival order, the ship type and schedule of each route, the scale of each island wharf, etc. Build and optimize the storage system (including storage capacity and periodic supply).

Obviously, transportation system cost and storage system are two contradictory aspects of the unified cost of optimization objectives. That is, if ships on a certain route are as full as possible, the interval of transportation schedule can be extended, thus reducing the transportation cost of transportation plan, but at the same time, it will increase the cost of cargo storage and warehouse construction. If ship type constant, increase the supply of routes on the island, it can reduce the number of routes and ship procurement, goods collection cycle and inventory costs, and inventory of goods storage cost and the cost of the construction of the warehouse, but the increase of transportation distance and the extension of route will lead to increased transport costs, resulting in changes in the total cost of the system. In addition, the location of the central island will directly affect route planning and the choice of transportation organization form, and thus indirectly affect the optimization of the storage system.

In the process of optimizing the ocean shipping system, in addition to the above traditional LIRP problems, we should also consider the decision of site selection, transportation and storage. In addition to the interaction, we also need to consider the characteristics of the shipping system itself: (1) Since the load of ships is generally much larger than the daily production of the island, two-way loading route can prolong the loading cycle and greatly reduce the frequency of transportation compared with one-way transportation. Although the distance is increased, the cost of transportation is likely to be relatively lower. Even if inventory and the resulting cost of goods storage and warehouse construction increases, the overall cost of the system may eventually decrease. The choice of specific transportation organization should be based on the number and distance of the route islands.

(2) compared with the small boat, if you select routes, should be determined according to the number of routes in the islands and distance, large ship type can be multiplied regular loading, extend the delivery period, decrease The Times of transportation and reduce the transportation cost, but always ship procurement costs and the wharf construction costs, inventory, and the resulting goods storage cost and warehouse construction costs will increase, leading to changes in the total cost of the system.

In the transportation system, no matter how many lines, all of the total number of terminal satellite island is fixed, but due to the different routes of ship form is different, so the satellite island wharf of different size and the resulting wharf construction costs are also different, and every kind of form, center island more needs to be equipped with corresponding type wharf. Therefore, it has a great impact on the construction cost of the terminal. To sum up, the optimization of the maritime logistics system of outlying islands should select the central island based on the above characteristics, divide the route group for satellite island transportation, establish the transportation organization form of each route (circular transportation), configure different ship types and formulate voyage times. The storage capacity of each island is set during the shift of the line so as to minimize the total cost of the logistics system of the entire archipelago under the influence of typhoons and other remote islands.

2.1 Overview of Genetic Algorithm Genetic Algorithm (GA), also known as evolutionary Algorithm. Genetic algorithm (GA) is a heuristic search algorithm which is inspired by Darwin’s theory of evolution and referred to the biological evolution process. Its main characteristic is directly on the object structure, so different from other algorithms for solving the optimal solution, the genetic algorithm and continuity of function limit, there is no derivative method of probability optimization method, do not need to make sure the rules can automatically acquire and to guide the optimization of search space, adaptively adjust the search direction.

The above is a relatively abstract summary of genetic algorithm. In order to explain the general principle of genetic algorithm in a more concrete image, we first introduce some biological concepts:

(1) population: groups formed by different biological individuals, biological evolution in the form of groups, such a group is called a population;

2. An individual organism constituting a population;

(3) Genes: DNA fragments with genetic information. Genes can be commonly understood as a piece of information, which determines the traits of individual organisms.

(4) Phenotype: according to the external performance of the individual formed by the gene;

(5) fitness: the degree of adaptation of an individual to the living environment, the more adaptable it is, the greater the probability of survival and reproduction;

⑥ Inheritance: through the process of reproduction, the offspring will get part of the genes from both parents, forming their own genes, in this process, gene replication, crossover, but also with a low probability of gene mutation;

⑦ Natural selection: natural selection, survival of the fittest natural selection mechanism. Specifically, individuals with high adaptability to the environment have more opportunities to participate in reproduction, and there will be more and more offspring. Individuals with low fitness have fewer opportunities to participate in reproduction, resulting in fewer offspring;

(8) Evolution: the process in which populations continuously adapt to the living environment through intergenerational reproduction. In this process, the adaptability to the external environment is the evaluation standard, and the characters of organisms are constantly improved.

Knowing what these terms mean, we can move on to the process of biological evolution. As a result of natural selection is objective existence, which life can only change yourself to adapt to the environment, so in the process of natural selection, the fitness of the individuals low to be eliminated, and high fitness individuals are retained, high degree of paternal and maternal and breed high fitness has a higher probability of their offspring, so after generations of breeding, The population evolves as individuals with high fitness become an increasing proportion of the population.

Now we are going to refer to the process of biological evolution to design an algorithm to solve the problem of finding the optimal solution. The idea of genetic algorithms is that the problem to be solved is simulated as an evolutionary process to find the optimal solution. Take the problem of finding the maximum value of a multimodal function as an example:

Take the possible solution (x, y) as an individual; The function value f(x, y) of multi-peak function is taken as individual fitness; Encode (x, y) as individual genes; Constantly screen biological individuals based on fitness; Through genetic operators (such as replication, crossover, mutation, etc.) continuously produce the next generation. So the cycle of iteration, the completion of evolution. Available in the end, according to a set number of iterations, the last generation of population, the population of individual fitness is higher, and the maximum of multi-peak function has larger probability exists in a group of solutions, with the individual populations with the highest fitness as a problem of the solution, can say the solution is to have a higher probability is what we would like to get the optimal solution.

After all, words are not as easy to understand as charts, so let’s look at the picture (which links this question to natural genetics) :



From the above description, it is not difficult to see that genetic algorithm can not guarantee the optimal solution, but can only obtain the optimal solution with a certain probability. But when we use genetic algorithms, we don’t have to worry about finding the optimal solution, we just have to deny some bad individuals. This advantage is also one of the reasons why genetic algorithm can be widely used.

2.2 Algorithm Flow Through the above description, it has been relatively clear how to simulate natural evolution to find the optimal solution of multi-peak function in the problem. Here I will list the main steps of genetic algorithm and analyze them one by one:

Step 1: Randomly generate a population as the initial solution of the problem (usually, the initial solution may differ greatly from the optimal solution, which is tolerable, as long as the initial solution is guaranteed to be randomly generated to ensure the diversity of individual genes);

Step 2: Find an appropriate coding scheme to encode individuals in the population. Common coding schemes such as floating point coding or binary coding can be selected (it should be pointed out that different coding schemes directly affect the implementation details of subsequent genetic operators).

Step 3: Take the function value of multi-peak function as the individual fitness, calculate the fitness of each individual in the population (the fitness calculated will provide a basis for subsequent individual selection);

Step 4: Parents and mothers are selected to participate in reproduction according to the level of fitness. The principle of selection is that individuals with higher fitness are more likely to be selected (so as to constantly eliminate individuals with lower fitness).

Step 5: Perform genetic operation on the selected parent and mother, that is, copy the genes of the parent and mother, and use crossover, mutation and other operators to generate offspring (on the basis of retaining excellent genes to a large extent, mutation increases the diversity of genes, so as to improve the probability of finding the optimal solution);

The sixth step: according to certain criteria to judge whether to continue to execute the algorithm, or to find out the individual with the highest fitness among all the children to return as the solution and end the program (the criteria can be the threshold of the set solution, the specified number of iterations, etc.).

Ii. Source code

CLC Close All Clear all %% model parameter n=20;
Axes=[35.44;13.36;22.59;30.79
    39.60;31.26;25.21;40.16;52.38
    63.17;66.71;62.50;41.29;71.35
    91.37;25.33;82.74;52.80;49.11
    22.11];
Land=[- 8 -.65];
Dom=((Axes(1.1)-Land(1)) ^2+(Axes(1.2)-Land(2)) ^2) ^0.5;
Dist=getdist(Axes);
Output=[122.77.75.68.87.96.90.110.127.155.141.135.103.163.170.81.147.145.129.95];
Ship.Cp=[1300000.2100000.1e15];
Ship.Ctr=[65.90.1e15];
Ship.V=[18.14.1e15];
T.all=15*365- 1;
T.main=7; %% Ga parameter GenMax=200;
Pc=0.5;
Pv=0.5;
Gen=0;
Popnum=100; Chrom=struct; NewChrom=struct; %% generates initial populationfor i =1:Popnum
    Chrom(i).Index=randperm(n- 1) +1;
    Chrom(i).RouteNum=randi(n- 1.1);
    Chrom(i).Routes=getdivide(Chrom(i).RouteNum,Chrom(i).Index,n);
end
while Gen < GenMax
Gen=Gen+1;
 
for i=1:size(Chrom_all,2)
    ship=[];
    RouteL=[];
    ShipNum=Chrom_all(i).RouteNum;
    for j=1:ShipNum
        EachL=0;
        Route=Chrom_all(i).Routes{j};
        EachOutput(j)=sum(Output(Route(2:end- 1)));
        if EachOutput(j)<=300
            ship(j)=1;
        elseif EachOutput(j)<=500
            ship(j)=2;
        else
            ship(j)=3;
        end
        for k=1:length(Route)- 1
            EachL=EachL+Dist(Route(k),Route(k+1));
        end
        RouteL(j)=EachL;
    end
    Chrom_all(i).Ship=ship;
    Chrom_all(i).Length=RouteL;
end  
[bestC,ind]=getbest(Chrom_all,Ship,Dom,T);
Chrom=Chrom_all(ind(1:Popnum));
Best(Gen).Gen=Chrom_all(ind(1));
Best(Gen).C=bestC(1); End %% % plot([best.c]) title('Total cost evolution curve');
xlabel('Number of iterations')
ylabel('Total cost')
 
 
 
 
%
% end
 
 
Copy the code

3. Operation results

Fourth, note

Version: 2014 a