A Genetic Algorithm for the Multi-Pickup and Delivery Problem with time windows

In This paper we present a genetic algorithm for the multi-pickup 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 our approach based on genetic algorithms to minimizing the total travel distance and thereafter the total travel cost, by showing that an encoding represents the parameters of each individual.


Introduction
With the time and economic constraints implications of the transport goods 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 the total travel distance and thereafter the total travel cost, by showing that an encoding represents the parameters of each individual.

Vehicle routing problem
The Vehicle Routing Problem (VRP) represents a multi-goal 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] Heuristic methods have been used by Matsinen, T and al to solve the general problem in this area as the Travelling Salesman Problems [Matsinen, T and al., 1992]. The Meta heuristics were as well 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 and used also by Sorin C, N and al to solving the multiple constraints problem: vehicle route allocation. [Montamenni, R and al., 2002] [Sorin C, N and al., 2008] 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 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. 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]

Mathematical formulation
Our problem is characterized by the following parameters: • N : Set of customers, supplier and depot vertices, 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.

Genetic algorithm for minimizing the total travel cost
In this part, we present our approach based on genetic algorithms to minimize the total travel cost.

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

Decoding the vehicles passage
The decoding allows, from every chromosome of the population to obtain an initial solution sign the passage of each vehicle on the corresponding vertex. (Fig.2) 1

Crossover operator
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. (Fig.3) 1 2 3 4 5 6 7 8 9 10

Mutation operator
Mutation operator (Fig.4) is to choose two positions at random, within a chromosome and exchange their respective values.

Fig.4 : Mutation operator
Note here that we must respect the constraint precedence, to ensure that a customer is not visited before his supplier, and capacity to ensure the non-overload of each vehicle.

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.1). The second population noted P vehicle indicates nodes number visited by each vehicle. Knowing that k varies between 1 and

N' 2
vehicles. Fig.5 shows an individual example of P vehicle with

Correction procedure
The principle of correction precedence and capacity is to ensure that a customer is not visited before his supplier while respecting the vehicles capacity.

Generation of population P node/vehicle
Considering the population P node given by Fig.1, correction procedures and P vehicle population, given by Fig.5, we illustrated in Fig.8 an individual of the population P node/vehicle .

Calculation procedure
Each vehicle will serve vertices in the assignment order. Once returned to the depot, we calculate the transport cost corresponding to the travel distance, and we repeat this until all the vertices are served. We reproduce this work for each individual to the population P vehicle , taking into account the different possible combinations between P vehicle and P node , to obtain thereafter the correspondent individual of the population P node/vehicle that minimizes our objective function. The algorithm of this procedure is shown by the Fig.9. Fig.10 indicates how to minimizing the total cost of transport.

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

Simulation
We present in Table 1, the simulation results given by our approach. We observe that our approach reduces the vehicles number (2 vehicles to serve up to 50 vertices and 4 vehicles to serve 100 vertices). Knowing that a vehicle will cause an augmentation travel cost on the addition of a driver, the travel fixed costs, to depreciation of the vehicle used. Hence the interest of our approach that aims to minimize the total travel cost.

Conclusion
In this paper we have proposed, following a study of the different approaches proposed for the resolution of 1-PDPTW and m-PDPTW, a genetic algorithm for minimizing the total travel cost. To do this, we presented the mathematical formulation of our problem, and we have detailed the calculation procedure for determine the optimal solution, that minimizes our objective function