{'fraction_non_alphanumeric': 0.03698394495412844, 'fraction_numerical': 0.014143730886850153, 'mean_word_length': 4.632400430570506, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Genetic Algorithm for Mulicriteria Optimization of a Multi-Pickup and Delivery Problem with Time Windows

In This paper we present a genetic algorithm for mulicriteria optimization of a multipickup and delivery problem with time windows (m-PDPTW). The m-PDPTW is an optimization vehicles routing problem which must meet requests for transport between suppliers and customers satisfying precedence, capacity and time constraints. This paper purposes a brief literature review of the PDPTW, present an approach based on genetic algorithms and Pareto dominance method to give a set of satisfying solutions to the m-PDPTW minimizing total travel cost, total tardiness time and the vehicles number.


INTRODUCTION
Nowadays, the transport goods problem occupies an important place in the economic life of modern societies.
With the time and economic constraints implications of this problem, its resolution becomes very difficult, requiring the use of tools from different disciplines (manufacturing, information technology, combinatorial optimization, etc.)... Indeed, the process from transport systems and scheduling are becoming more complex by their large size, by the nature of their relationship dynamics, and by the multiplicity of which they are subjected.
Many studies have been directed mainly towards solving the vehicle routing problem (VRP). It's an optimization vehicle routing problem to meet travel demands. Other researchers became interested on an important variant of VRP which is the PDPTW (Pickup and Delivery Problem with Time Windows) with capacity constraints on vehicle.
Our object is to design a tool for m-PDPTW resolution based on genetic algorithms and Pareto dominance method to give a set of satisfying solutions to this problem minimizing total cost travelled, total tardiness time and the vehicles number.

VEHICLE ROUTING PROBLEM
The Vehicle Routing Problem (VRP) represents a multigoal combinatorial optimization problem which has been the subject of much work and many variations in the literature. It belongs to the NP-hard class. . [Christofides. N and al., 1979] [Lenstra. J and al., 1981] The Meta heuristics were also applied to solving the vehicle routing problem. Among these methods, we can include ant colony algorithms, which were used by Montamenni, R and al for the resolution of DVRP. [Montamenni. R and al., 2002] The VRP principle is: given a depot D and a set of customers orders C = (c1, ... , Cn), to build a package routing, for a finite number of vehicles, beginning and ending at a depot. In these routing, a customer must be served only once by a single vehicle and vehicle capacity transport for a routing should not be exceeded. [Nabaa. M and al., 2007] Savelsbergh and al have shown that the VRP is a NP-hard problem [Savelsbergh. M.P.W and al., 1995]. Since the m-PDPTW is a generalization of the VRP it's a NP-hard problem.

THE PDPTW: PICKUP AND DELIVERY PROBLEM WITH TIME WINDOWS
The PDPTW is a variant of VRPTW where in addition to the existence of time constraints, this problem implies a set of customers and a set of suppliers geographically located. Every routing must also satisfy the precedence constraints to ensure that a customer should not be visited before his supplier. [Psaraftis. H.N., 1983] A dynamic approach for resolve the 1-PDP without and with time windows was developed by Psaraftis, H.N considering objective function as a minimization weighting of the total travel time and the non-customer satisfaction. [Psaraftis. H.N., 1980] Jih, W and al have developed an approach based on the hybrid genetic algorithms to solve the 1-PDPTW, aiming to minimize combination of the total cost and total waiting time. [Jih. W and al., 1999] Another genetic algorithm was developed by Velasco, N and al to solve the 1-PDP bi-objective in which the total travel time must be minimized while satisfy in prioritise the most urgent requests. In this literature, the method proposed to resolve this problem is based on a No dominated Sorting Algorithm (NSGA-II). [Velasco. N and al., 2006] Kammarti, R and al deal the 1-PDPTW, minimizing the compromise between the total travel distance, total waiting time and total tardiness time, using an evolutionary algorithm with Special genetic operators, tabu search to provide a set of viable solutions. [Kammarti. R and al., 2004] [Kammarti. R and al 2005a] This work have been extended, in proposing a new approach based on the use of lower bounds and Pareto dominance method, to minimize the compromise between the total travel distance and total tardiness time. [Kammarti. R and al 2006] [Kammarti. R and al 2007] About the m-PDPTW, Sol, M and al have proposed a branch and price algorithm to solve the m-PDPTW, minimizing the vehicles number required to satisfy all travel demands and the total travel distance. [Sol. M and al., 1994] Quan, L and al have presented a construction heuristic based on the integration principle with the objective function, minimizing the total cost, including the vehicles fixed costs and travel expenses that are proportional to the travel distance. [Quan. L and al., 2003] A new metaheuristic based on a tabu algorithm, was developed by Li, H and al to solve the m-PDPTW. [Li. H and al., 2001] Li, H and al have developed a "Squeaky wheel" method to solve the m-PDPTW with a local search. [Li. H and al., 2002] A genetic algorithm was developed by Harbaoui Dridi, I and al dealing the m-PDPTW to minimize the total travel distance and the total transport cost. [Harbaoui Dridi. I and al., 2008] 3. MATHEMATICAL FORMULATION Our problem is characterized by the following parameters: The function to minimize is given as follows: Subject to: The constraint (2) and (3) ensure that each vertex is visited only once by a single vehicle. The constraint (4) and (5) ensure that the vehicle route beginning and finishing is the depot. The constraint (6) ensures the routing continuity by a vehicle. (7), (8) and (9) are the capacity constraints. The precedence constraints are guaranteed by (10) and (11). The constraints (12), (13) and (14) ensure compliance time windows.

MULTI-CRITERIA EVALUATIOIN
A multi-objective problem is defined as an optimization vector problem, which seeks to optimize several components of a vector function cost.

PARETO DOMINANCE METHOD
A multi-criteria problem P consists of n variables, m inequality constraints, p equality constraints and k criteria whose can be formulated as follows: Therefore, it is necessary to find solutions representing a possible compromise between the criteria. The Pareto optimality concept introduced by the economist V. Pareto in the nineteenth century is frequently used [Pareto. V., 1897].
A solution is noted Pareto optimal if it is dominated by any other point in solutions space. These points are noted nondominated solutions. Fig.1 shows an example where we seek to minimize 1 f and 2 f . The points 1, 3 and 5 are not dominated. By against Point 2 is dominated by point 3, and point 4 is dominated by point 5.

SOLUTIONS CODING
A chromosome is a succession (permutation) vertex, which indicates the order in which a vehicle is to visit all the vertices. Fig. 2 represents the solutions under form of chromosomes.

GENERATION OF INITIAL POPULATION
The choice of the initial population is important because it can make a genetic algorithm more or less fast to converge towards the global optimum.
In our case, we will generate two types of populations. A first population noted P node , which represents all nodes to visit with all vehicles, according to the permutation list coding (Fig.2). The second population noted P vehicle indicates nodes number visited by each vehicle. Knowing that k varies between 1 and N' 2 vehicles. Fig.3 shows an individual example of P vehicle with N' =10.

Fig.3: Individual example of P vehicle
Considering the population P node given by Fig.2, correction procedures and P vehicle population, given by Following the generation of the initial population, we proceed to crossover phase which ensures the recombination of parental genes for train new descendants.
To do this, we choose the one point crossover.

MUTATION OPERATOR
Mutation operator aims to choose two positions at random, within a chromosome and exchange their respective values.

CORRECTION PROCEDURE
The principle of correction precedence and capacity [Harbaoui Dridi, I and al., 2008] is to ensure that a customer is not visited before his supplier while respecting the vehicles capacity.
6. APPROACH PROPOSED TO MINIMIZE TOTA TRAVEL COST, TOTAL TARDINESS TIME AND THE VEHICLES NUMBER After the generation of the population P node/vehicle , which an example is shown in Fig.3, we determine for each individual, the 1 f , 2 f and 3 f values, which correspond to the vehicles number, the total tardiness time and the total travel cost. We obtain the subsequent population noted P pareto-dominance . Fig.5 shows an individual example of this population. The procedure for determining different population is given in our work [Harbaoui Dridi, I and al., 2008].

COMPUTATIONAL RESULTS
The following table (Table.1) represents the parameters characterizing our problem. Experimental results are given in Table.2: 1  The total tardiness time is expressed in time units.
Our approach provides a set of non-dominated solutions to ensure choice flexibility. This set of solutions is Pareto space from which the maker will take its decision.

CONCLUSION
In this paper, we have presented our genetic approach to solve the m-PDPTW, based on Pareto dominance method. We proposed in the first part a brief literature review on the VRP, 1-PDPTW and m-PDPTW. The mathematical formulation of our problem is detailed in second part.

Begin
Step 1: Create the initial population, (size n).
Step 2: Fill the intermediate population P node (size 2n) with individuals' crossover, mutation or copy.
Step 3: Correction procedure of Precedence and capacity.
Step 4: Create the 2 nd intermediate population P node/vehicle (size 2n * 2n) representing the routing of each vehicle.
While the generation number is not reached do Step 5: Determine fitness values for each individual of the population P node/vehicle , in order to obtain thereafter the population P pareto-dominance Step 6: Sort of population P pareto-dominance by the minimum value of fitness (Vehicles number / Total tardiness time / Total travel cost) Step 7: Copy non-dominated solutions Increment the generation number