Model algorithm and solution

48

that are generated during the r-refresh) are completed at the r-refresh time.

In the constraints, equation (3-17) represents the distribution process of newly generated take out orders when R refreshes, indicating that each newly generated order is served only once by a crowdsourced take out distributor;

Formula (3-18) and formula (3-19) mean that each crowdsourcing delivery clerk has a temporary delivery starting point and a virtual destination in his delivery route, that is, each crowdsourcing delivery clerk starts from his temporary delivery starting point and finishes the delivery from the completion of the delivery to the virtual destination;

Equation (3-20) indicates that each crowdsourcing delivery person will leave from an order node (all unfinished order task points after r refresh) after arriving at it;

Equation (3-21) indicates that the starting point of an order (the old order without taking meal or delivering meal before r refresh and the new order generated during R refresh) must be served by the same crowdsourcing delivery clerk;

Equation (3-22) refers to the quantity of unfinished orders of K distributor in R refresh, excluding the newly generated orders in R refresh;

Equation (3-23) means the limit of the maximum number of orders received at one time by each crowdsourcing delivery clerk during the R refresh, which is used to determine the maximum number of new orders generated by the platform for the crowdsourcing delivery clerk during the R refresh.

Equation (3-24) indicates the time when the crowdsourcing take away delivery delivery clerk K arrives at point v;

Equation (3-25) indicates that for an order (the old order without meal and delivery before r refresh and the new order generated during R refresh), the distributor must visit the starting point of the order first, and then the end point of the order;

Equation (3-26) indicates r refreshes, and the crowd delivery delivery staff starts from their own temporary delivery starting point, which is RT;

Equation (3-27) represents the decision variable.

49

algorithm is as follows: first, we generate a certain scale of initial population, one chromosome represents a complete distribution scheme, then we select the optimal chromosome in the initial population to enter the next population and select the remaining chromosomes to perform cross variation, so as to generate multiple generations, then we select the excellent individuals to enter the next population to perform cross variation repeatedly Operate differently until the termination conditions are met.

1.Generate initial population

Genetic algorithm is based on the initial population, so the setting of the initial population has a significant impact on the quality of the final solution. The initial population is usually generated randomly, but the delivery problem needs to meet the pairwise and priority constraints of the order when arranging the delivery path, that is, the start and end point of an order must be arranged to the same crowdsourced delivery staff for distribution, and the crowdsourced delivery staff must first complete the catering task at the beginning of the order and then complete the catering task at the end of the order. A large number of invalid solutions may be generated by the random generation method. Therefore, this paper uses the order pair point insertion method to generate the initial solution. The specific steps are as follows:

Step 1: A certain size of order scheduling is generated taking no account of the location of crowdsourced takeaway distributors. This paper uses 1,2,...,n to represent orders, assuming that there are currently 6 orders to be distributed, with a population size of 20, i.e. 20 order arrangements are generated, one of which can be represented as (1 2 3 4 5 6).

Step 2: Insert the location point of the crowdsourcing takeaway distributor in the order scheduling generated in Step 1 and consider the allocation of the orders for the crowdsourced takeaway distributor under the condition that the maximum one-time pick-up quantity of the crowdsourcing takeaway distributor is not exceeded. For example, there are 2 crowdsourcing takeaway distributions of A and B, the starting position of the crowdsourcing takeaway distributor A is inserted into the first place on the chromosome, the crowdsourcing takeaway delivery staff B is inserted behind the belt 4, that is (A 1 2 3 4 B 5 6), which represents assigning orders 1, 2, 3 and 4 to crowdsourcing takeaway deliveryman A, and assigning Orders 5 and 6 to crowdsourcing takeaway deliveryman B.

Step 3: To Arrange the delivery order at the start and end points of the order. The

50

start and end points of order i are expressed in i⁺and i^- respectively, inserting the start and end points of the order i into the distribution path of the corresponding crowdsourced takeaway distributor in pairs and ensuring that the delivery order of i+ is prior to that of i-. The initial solution is generated until all the start and end points of the orders are inserted into the initial path, e.g. （A 1⁺ 2⁺2^-3⁺ 4⁺1^- 4^- 3^-B 5⁺ 6⁺ 6^- 5^-）. The distribution path for other chromosomes is also inserted in this way, and if all chromosome orders are slotted in the population are inserted, the initial population is generated.

Step 4: To calculate the target function value for each chromosome. Each chromosome represents a distribution solution that calculates the sum of the distribution and time costs of each distribution solution, i.e. the target function value z. Using 1/z to represent the adaptability of chromosomes, the higher the adaptability represents, the better the individual is, and the smaller the target function value is.

2. Genetic operation

Genetic algorithms generate new populations based on initial populations through three steps: selection, crossover and variation, and in the course of evolution, the relatively good individuals are chosen to be left, passing on the good genes of the previous generation to the next generation. This process enables the children to have a higher degree of adaptation than the parent generation, thus generating better solutions.

After several iterations, the most adaptable individual in the last generation of populations can be considered as an approximate optimal solution to the problem.

(1) Selection

In the process of generating the initial population, the adaptive values of each chromosome in the population have been calculated. The most adaptable chromosomes are selected directly into the next generation of populations, and the least adaptable chromosomes are removed from the initial population, and then the chromosomes are selected from the population by roulette for cross-variation. The specific steps for roulette are as follows:

Step1: Calculate the sum of all chromosome adaptations in the initial population;

Step2: Calculate the probability that each chromosome is selected;

f i

å

i i

/

p = f å f

51

Step3: Calculate the probability of each chromosome being selected cumulatively;

Step4: Randomly generate a number within the section of [0, 1], to which it falls the corresponding chromosome should be chosen.

(2) Cross

Cross operation is conducted aiming to the marshalling sequence of the orders during the generation process of initial population. In the cross process, the children are likely to inherit the good genes of the parent generation to become more adaptable individuals, which is conducive to the evolution of the population in a good direction.

Step1: Randomly match chromosomes selected in the previous initial population in pairs;

Step2: Randomly generate the random number within the section of [0, 1], so that each pair of chromosome corresponds to a random number;

Step3: If the random number generated in step 2 is less than or equal to the cross probability, then the corresponding two chromosomes should perform cross-operation;

Step4: Randomly generate an intersection point, the genes after the intersection of two chromosomes should be exchanged, while paying attention to removing the repeat point of the non-interchange gene, the missing point should be supplemented at the end of the chromosome. The specific cross over process is shown in Figure 3.12 below, and the intersection is 3:

parent1:（1 2 3 |4 5 6）parent 2:（2 5 3 |4 6 1）

child（1 2 3 4 6 1）（2 5 3 4 5 6）

（234615）（234561）

Fig.3.12 The Process of Chromosome Crossover

(3) Variations

The main purpose of the variation operation is to strengthen the local search ability of the algorithm, enhance the diversity of the population and prevent the result of premature convergence. The variation operation is performed on the generation distribution path in the initial population. The steps are as follows:

Step1: Generate random numbers corresponding to each chromosome in the initial

i

i j

j

q p

=

=

å

1

52

population;

Step2: Determine whether it meets the condition of variation, if the random number generated is less than or equal to the probability of variation, then the corresponding chromosome performs the mutation operation;

Step3: Randomly select a mutated order and reinsert the start and end of the order into the delivery path of the original distributor, as follows:

Parent（A 1⁺2⁺ 2^- 3⁺4⁺ 1^- 4^- 3^- B 5⁺ 6⁺ 6^- 5^-）

Select Order 2 and Order 6 to reinsert, the mutated chromosome sits as follows:

Children（A 1⁺ 2⁺3⁺ 4⁺ 2^- 1^- 4^- 3^-B 5⁺ 6⁺ 5^- 6^-）