«A Parallel Hybrid Evolutionary Metaheuristic for the Period Vehicle Routing Problem Dalessandro Soares Vianna, Luiz S. Ochi and L cia M. A. Drummond ...»
A Parallel Hybrid Evolutionary Metaheuristic
for the Period Vehicle Routing Problem
Dalessandro Soares Vianna, Luiz S. Ochi
cia M. A. Drummond
Universidade Federal Fluminense - Departamento de Ci^ncia da Computa~o
Travessa Capit~o Zeferino 56 808
i - Rio de Janeiro - Brazil - 24220-230
e-mail: firstname.lastname@example.org, fsatoru,email@example.com
Abstract. This paper presents a Parallel Hybrid Evolutionary Meta-
heuristic for the Period Vehicle Routing Problem PVRP. The PRVP generalizes the classical Vehicle Routing Problem by extending the plan- ning period from a single day to M days. The algorithm proposed is based on concepts used in Parallel Genetic Algorithms and Local Search Heuristics. The algorithm employs the island model in which the mi- gration frequency must not be very high. The results of computational experiments carried out on problems taken from the literature indicate that the proposed approach outperforms existing heuristics in most cases.
1 Introduction The classical Vehicle Routing Problem VRP is de ned as follows: vehicles with a xed capacity Q must deliver order quantities qi i = 1; : : : ; n of goods to n customers from a single depot i = 0. Knowing the distance dij between customers i and j i; j = 0; : : : ; n, the objective of the problem is to minimize the total distance travelled by the vehicles in such a way that only one vehicle handles the deliveries for a given customer and the total quantity of goods that a single vehicle delivers do not be larger than Q.
In classical VRPs, typically the planning period is a single day. The period Vehicle Routing Problem PVRP generalizes the classical VRP by extending the planning period to M days. Over the M-day period, each customer must be visited at least once during the considered period. The classical PVRP consists of a homogeneous vehicle eet vehicles with same capacities which must visit a group of customers from a depot where the vehicles must start and return to at the end of their journeys. Each vehicle has a xed capacity that cannot be exceeded and each customer has a known daily demand that must be completely satis ed in only one visit by exactly one vehicle. The planning period is M days.
If M = 1, then PVRP becomes an instance of the classical VRP. Each customer in PVRP must be visited k times, where 1 k M. In the classical model of PVRP, the daily demand of a customer is always xed. The PVRP can be seen as a problem of generating a group of routes for each day so that the constraints involved are satis ed and the global costs are minimized.
PVRP can also be seen as a multi-level combinatorial optimization problem.
In the rst level, the objective is to generate a group of feasible alternatives combinations for each customer. For example, if the planning period has t = 3 days fd1 ; d2 ; d3 g then the possible combinations are: 0 ! 000; 1 ! 001; 2 !
010; 3 ! 011; 4 ! 100; 5 ! 101; 6 ! 110 and 7 ! 111. If a customer requests two visits, then this customer has the following visiting alternatives: fd1 ; d2 g, fd1 ; d3 g, and fd2 ; d3 g or the options: 3, 5 and 6 of Table 1. In the second level, we must select one of the alternatives for each customer, so that the daily constraints are satis ed. Thus we must select the customers to be visited in each day. In the third level, we solve the vehicle routing problem for each day.
In this paper, our algorithm is applied to the basic model of PVRP with an additional constraint: the number of vehicles is limited, although this limit is not necessarily the same every day. The technique proposed here can be applied to various models of PVRP.
In the last years, Evolutionary Metaheuristics and in particular Genetic Algorithms GA have been used successfully in solution of NP-Complete and NPHARD problems of high dimensions. Hard problems require large search spaces resulting in high computational costs. In this context, Evolutionary Metaheuristics including GA may require a large amount of time to nd good feasible solutions, encouranging the use of parallel techniques 10. Although the main goal of a Parallel Evolutionary Metaheuristic is the reduction of the execution time necessary to nd an acceptable solution, sometimes it can also be used to improve the results obtained by sequential versions.
Most of Evolutionary Metaheuristics, such as GA, Scatter Search, Ant Systems and Neural Nets, are easy to parallelize because of their intrinsic parallelism. There are di erents ways to parallelize GA. The generally used classi cation divides parallel GAs in three categories: Island or stepping stone, Fine Grain and Panmitic Models 10.
In this paper, we propose a parallel hybrid evolutionary metaheuristic based on parallel GA, scatter search and local search methods. The algorithm is based on the Island Model and it was implemented on a cluster of workstations with 4 RISC 6000 processors.
The remainder of this paper is organized as follows. Section 2 presents the related literature about PVRP. Section 3 presents the algorithm proposed. Experimental results are shown in Section 4. Finally, Section 5 concludes the paper.
2 Related Literature Although the PVRP has been used in many applications, it has not been extensively studied in related literature. Golden, Chao and Wasil 7 developed a heuristic based on the concept of record-to-record" proposed by Dueck 5. To the best of our knowledge, there are not many papers using Metaheuristics to solve PVRP. Cordeau, Gendreau and Laporte 4 presented a Tabu Search Metaheuristic to solve this problem. Computational results taken from the literature indicate that their algorithm outperforms all previous conventional heuristics.
GA have been used with great success to solve several problems with high degrees of complexity in Combinatorial Optimization, including models of daily VRP 1, 8, 9, 10 . More recently, Rocha, Ochi and Glover 11 proposed a Hybrid Genetic Algorithm HGA for the PVRP. Their algorithm is based on concepts of GA and Local Search heuristics. Computational experiments using tests available in literature showed the superiority of this method when it is compared with other existing metaheuristics.
3 A Parallel Hybrid Evolutionary Metaheuristic This paper presents a Parallel Hybrid Evolutionary Metaheuristic PAR-HEM for the PVRP. The parallel algorithm is based on the Island Model and it was implemented on a cluster of workstations with 4 RISC 6000 processors. In order to reduce communication overhead, which is usual in this kind of model 9 and ensure the occupation of all processors during the execution of the algorithm, a new criteria of migration and termination were employed. In Island Model, the population of chromosomes of Genetic Algorithms is partitioned into several subpopulations, which evolve in parallel and periodically migrate their individualschromosomes among themselves. Because of the high cost of communication in this model, migration frequency must not be very high. Thus migration is only executed when subpopulation renewal is necessary. The criterion of termination of processes is based on a global condition, which involves every process that composes the PAR-HEM, in order to prevent a process from being idle while the others are still executing.
In our algorithm, each processor executes a pair of tasks mi and qi. Each task mi executes the following steps, based on the sequential algorithm proposed by Rocha, Ochi and Glover 11, described in next subsections: generation of a feasible alternative for each customer; selection of an alternative for each customer;
representation of solutions through chromosomes; generation of an initial population of chromosomes; evaluation and reproduction; and diversi cation.
In order to execute the diversi cation step, mi sends a migration request to qi if population renewal is required. The task qi is responsible for migration and termination of the algorithm above. See 9 for more details.
3.1 Representation of Chromosomes The representation of a feasible solution in a chromosome structure may be much more complex for the PVRP than it is for the VRP. In addition to the problem of nding an optimal assignment of customers to vehicles and de ning the best route for each vehicle, there is also the problem of distributing the number of visits required by each customer in the planning horizon, satisfying the daily constraints. Each chromosome in our GA, is represented by two vectors. The rst vector is associated with the n customers of PVRP, as shown in Table 2.
The ith position ith gene of this vector is a non-negative integer k, such that 0 k 2t, 1, where t is the number of days in the current planning horizon.
The number k represents a feasible alternative combination of visits to the associated customer. The binary representation of k represents the days when the associated customer receives a visit. The second vector associated to the rst corresponds to the accumulated demand of each day in the planning horizon. For example, considering 3 days, we could have the following served daily demand f60, 30, 50g, which means that in the rst day 60 goods were delivered, in the second day 30 goods and nally in the last day 50 goods were delivered.
3.2 Initial Population The initial population of our GA is generated as follows. Initially, a set of feasible alternative visits for each customer is generated. The customers are ordered according to their number of alternatives. For example, in a period of three days t = 3, a customer which requires three visits has only one feasible alternative, while another which requires only one visit has three feasible alternatives. In order to generate an initial chromosome, we randomly select a customer from the set of customers which present the smallest number of feasible alternatives. Then one of the alternatives of this customer is chosen. The integer number associated to this alternative is placed in the corresponding gene. Then successively, an alternative is selected from each of the remaining customers with the smallest number of alternatives. For each alternative selected, we update the data in the second vector vector of served daily demand. If the introduction of an alternative of a new customer violates the global capacity of the eet in any day, this alternative is discarded and another alternative for this customer is sought. When the customer does not have other alternatives, the chromosome is abandoned. The chromosome is complete when every gene has been lled.
In the rst allocation, the customers selected hardly violate the maximum capacity constraint of the daily eet, because few customers have been allocated.
On the other hand, according to the addition of each new customer, the accumulated demand for each day increases and so does the risk of exceeding the maximum capacity allowed for any particular day. Therefore, starting the selection of customers with the one with greatest number of alternatives, may reduce the risk of discarding this chromosome.
3.3 Evaluation and Reproduction The tness level of a chromosome in our GA corresponds to the objective function value for the PVRP. The cost of the objective function is obtained by solving a set of VRPs, one for each day. Although this technique is expensive, it is the simplest form of evaluating a chromosome in most optimization problems. In order to minimize this e ort, we implemented a fast and e cient heuristic, based on saving concepts 3 to solve a VRP for each day.
The reproduction mechanism in our GA uses classical crossover and mutation operators.
In the crossover operator, given two parents from the population, we choose randomly a position gene associated with a customer. Initially, we subtract from the second vector the accumulated demand vector associated with this chromosome the respective demand values corresponding to the selected alternatives. Next, it is tried to change the alternatives of this customer selected in each parent if these alternatives are distinct. If this change does not produce a new feasible solution, considering the maximum daily capacity constraints of the eet, another attempt with a new gene is made. This procedure is applied p times, where p is an input parameter of the problem.
The second operator used, is a Mutation operator, which executes feasible changes in p points selected randomly in the chromosome.
3.4 Diversi cation and Termination In order to diversify a population with a small tax of renewal, our algorithm uses the migration operator.
The strategy adopted in this algorithm, consists of associating to each task mi, which executes the PAR-HEM, a task qi. A task qi, for 1 i w, where w is the number of processors, communicate only by message-passing.
A task qi is activated by the associated task mi in the following cases:
When the renewal tax is less than 5 per cent tax of replacement of parents by o spring's, triggering the migration of individuals.
When the task mi is capable of nishing, initiating the termination of the algorithm.
In the rst case, qi executes a broadcast of requests so that all tasks qj 8j :
j 6= i send their local best solutions LBS generated so far. When this occurs, a new population is generated based on the k-LBS. If a chromosome received is better than one of the k-LBS, then the chromosome received replaces the worst of the k-LBS. Usually the number k is less than the size of a population. Thus, in order to mantain the same number of chromosomes in the new population, the following procedure is executed. Copies of the k-best solutions are generated using the roulette criterion, where the most suitable individuals give a bigger number of copies. For each copy, a window" is opened in a random position and new feasible alternatives for each customer are selected swapping genes in these windows. Built a new population with characteristics from the LBS, the genetic operator is restarted.