{'fraction_non_alphanumeric': 0.030057287404210997, 'fraction_numerical': 0.009225504054757831, 'mean_word_length': 4.771575783598111, '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}}
Multi-objective Optimization For The Dynamic Multi-Pickup and Delivery Problem with Time Windows

The PDPTW is an optimization vehicles routing problem which must meet requests for transport between suppliers and customers satisfying precedence, capacity and time constraints. We present, in this paper, a genetic algorithm for multi-objective optimization of a dynamic multi pickup and delivery problem with time windows (Dynamic m-PDPTW). We propose a brief literature review of the PDPTW, present our approach based on Pareto dominance method and lower bounds, to give a satisfying solution to the Dynamic m-PDPTW minimizing the compromise between total travel cost and total tardiness time. Computational results indicate that the proposed algorithm gives good results with a total tardiness equal to zero with a tolerable cost.


INTRODUCTION
The vehicle routing problems are studied because of the growing passenger and freight today. Some studies are primarily oriented towards solving the vehicle routing problem (VRP: Vehicle Routing Problem).
Another major area of research focused on an important variant of VRP is the PDPTW, where in addition to the existence of time constraints and capacity constraints on the vehicle, this problem involves a clients set and a suppliers set geographically located. Each routing will also satisfy precedence constraints to ensure that a customer should not be visited before his supplier. The PDPTW is the Pickup and Delivery Problem with Time Windows, is divided into two categories: 1-PDPTW (a vehicle) and m-PDPTW (multiple vehicles). These can also be treated in two versions: static or dynamic In this paper we present a literature review of the PDPTW followed our multi-objective approach, minimizing the compromise between total travel cost and total tardiness time, based on genetic algorithms and lower bounds, which treats the dynamic m-pdptw by incorporating unexpected while routing have been planned and that their operation has started.

A. Vehicle routing problem
The Vehicle Routing Problem (VRP) represents a multi-goal combinatorial optimization problem which has been the subject of many work and variations in the literature. [1] [2] 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. [3] The Meta heuristics were also applied to solve the vehicle routing problem.
Among these methods, we can include ant colony algorithms and genetic algorithm which were used for the resolution of DVRP. [4] [5] Savelsbergh and al have shown that the VRP is a NP-hard problem [6]. Since the m-PDPTW is a generalization of the VRP it's a NP-hard problem.

B. 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. [7] A dynamic approach for resolving 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. [8] 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. [9] 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). [10] 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. [11] [12] This work has 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. [13] [14] 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. [15] 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. [16] A new metaheuristic based on a tabu algorithm, was developed by Li, H and al to solve the m-PDPTW. [17] Li, H and al have developed a "Squeaky wheel" method to solve the m-PDPTW with a local search. [18] A genetic algorithm was developed by Harbaoui Dridi. I and al treating the m-PDPTW to minimize the total travel distance and the total transport cost [19]. This work has been extended, in proposing a new approach based on the use 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. [20] [21] One more approach based on the genetic algorithm was also developed by [22] to solving the DPDPTW. This approach is evaluated using a large number of problem instances with varying degrees of dynamism.
Mitrovic-Minic S and al describe a doublehorizon based heuristics for the dynamic PDPTW. The Computational results of this work show the advantage of using a double-horizon in conjunction with insertion and improvement heuristics. [23] Rusdiansyah. A and al have developed a model and heuristic algorithm for Dynamic Pick Up and Delivery Problem with Time Windows for City-Courier providers. Considering the number of timeslots and Degree of Dynamism has a direct relationship to the time required computational. [24] III. MATHEMATICAL FORMULATION Our problem is characterized by the following parameters: • N : Set of customers, supplier and depot vertices, There is one depot, • The capacity constraint must be respected,

•
The depot is the start and the finish vertex for the vehicle, • The vehicle stops at every vertex for a period of time to allow the request processing, • If the vehicle arrives at a vertex i before its time windows beginning date ei, it waits.
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)  The principle of different genetic operations such as chromosome coding, the generation of populations as well as procedures for correcting capacity and precedence are detailed in our work [19].
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. The second population noted P vehicle indicates nodes number visited by each vehicle.
Whereas these two populations and correction procedures, we obtain the final population P node / vehicle whose shows an individual example in

B. Multi-criteria evaluation
A multi-criteria problem is defined as an optimization vector problem, which seeks to optimize several components of a vector function cost.
However, 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 [25].
V. Pareto formulated the following concept: in a multi-criteria problem, there is a balance so that we cannot improve one criterion without deteriorating at least one other. This balance has been called Pareto optimal A solution is noted Pareto optimal if it is dominated by any other point in solutions space. These points are noted non-dominated solutions.

C. Calculation of lower bounds
Since we have transformed our multi-objective problem (MOP) in a mono-objective problem (PMOλ), as shown in Equation 1, which is to combine the different cost functions f i of the problem into a single objective function F, usually a linear [27].
The problem now, is to determine the various constants c i that are weights and scaling coefficients. The constants c i are usually initialized to 1 is the optimal solution associated to the objective function f i .
Because we haven't information on the optimal solutions associated with different cost functions f i for our problem we are facing the calculation of lower bounds to determine the scaling constants c i .
To do this, we used the relaxation of various constraints.
All computation done, we obtain 1 f b and 2 f b successively representing a lower bound of the total travel cost and a lower bound of the total tardiness time. [26] 1 1

D. Dynamic study
The dynamic m-pdptw is an extension of the mpdptw where besides the temporal, precedence and capacity constraints, which imposes this last one, the dynamic m-pdptw distinguishes itself by the appearance of dynamic and urgent requests having planned the routing associated with each vehicle.
The planner will then have to satisfy the new requests besides the former while optimizing the chosen criteria and by respecting the imposed constraints.
We will present our approach of dynamic adaptation, by using two different methods for the insertion of new requests. The first method (Fig 2) consists in inserting the dynamic nodes from their appearances on the routing vehicle which minimizes the chosen criteria, by satisfying this last one. By keeping the same list of remaining nodes to visit, after insertion of dynamic requests.
The second method (Fig 3) is based on the adaptation of the genetic operators and the correction procedures of precedence and capacity initially conceived for the static case to serve in the dynamic case. While ensuring that vehicles must not, under any circumstances, visit a node already served.

E. Computational results
To test our approach, we use benchmark problem instances generated by Li and Lim [17] from Solomon's ones [28] Corresponding to Solomon's classification of C1, C2, R1, R2, RC1 and RC2, their data sets were also generated in six classes: LC1, LC2, LR1, LR2, LRC1 and LRC2. The LC problems are clustered whereas in the LR problems, providers and customers are randomly generated. Therefore in the LRC problems the providers and the customers are partially clustered and partially randomly distributed. While LC1, LR1 and LRC1 problems have a short scheduling horizon, LC2, LR2 and LRC2 have longer scheduling one. [29] Each problem includes several classes. All these classes have approximately 100 suppliers and customers. They also contain the time windows, capacity, the quantities required for each vertex and the coupling constraints (supplier, customer).
In our work we will study the 8 classes that group the problem LRC1 noted successively LRC101 until LRC108. Table I and II show the results of our simulation, by inserting it every time the couple of the dynamic request. Of course, for every given solution, we note the corresponding routing, crossed by each vehicle.

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 N sol : represents the number of non-dominated solutions.
N k : represents the vehicles number used. Tables 1 and 2 show, for each study case, the solution which minimizes the total travel cost and the one who minimizes the total tardiness time. Noting that these two last ones are sorted among the not-dominated solutions.
Adding as well as for each case, we use two different methods for computation the vehicles number used. We consider a vehicle number k ranging between 1 and 25.
We observe that our approach generates a multiple number of solutions minimizing the compromise between the total travel cost and the total tardiness time, that give flexibility of choice for the decision maker.
We also observe that we obtain a total tardiness equal to zero with a tolerable cost, by using the second method of insertion from dynamic request.
These results justify the genetic algorithms utility.

V. CONCLUSION
In this paper, we have presented our approach to solve the dynamic m-PDPTW, based on Pareto dominance method, with use of genetic algorithm and lower bounds. We proposed a brief literature review on the VRP, 1-PDPTW and m-PDPTW and The mathematical formulation of our problem. Then, we have detailed the use aggregation method and lower bounds to determine a set of solutions, minimizing our objective functions by inserting the couple of the dynamic request. Simulation was presented in a last part by using benchmark's data.