Descrição:

The Vehicle Routing Problem (VRP) is one of the most important, and studied, combinatorial optimization problem. It can be described as the computation of the optimal set of routes to be performed by a fleet of vehicles to serve a give set of customers, distributed in a certain area.

The Vehicle Routing Problem with Time Windows (VRPTW) is an extension of the basic model, where time constraints are introduced to define a limited time range within the service should start.

The present work aims to introduce a new VRPTW constructive heuristic for the population initialization in a genetic algorithm (GA), an evolutionary strategy that currently provides the best results. Our intent is designing a time constraints-driven methodology exploiting the randomized approach.

The Time Agitation Heuristic (TAH) starts generating a stochastic forecasted scenario based on the time windows constraints. In this phase the customers are ordered according to a value randomly chosen within the ready and the due times. Proceeding with this order, the algorithm applies a greedy strategy to define the tours. For each customer are evaluated all the current partial routes, if it doesn’t violate the capacity and time constraints, and a possible new tour starting from the depot, serving it with the vehicle that minimize a cost function.

To analyze the performance obtained by our algorithm generating the population for a genetic algorithm, we have to evaluate the quality reached, the time complexity and the individual diversity, a fundamental property to prevent premature convergence.

In terms of quality, comparing TAH with the PFIH stochastic version, a constructive heuristic widely used to initialize a GA, and a completely randomized generator, the obtained distribution is significantly better than the randomized one and mostly overlapped with the one derived from PFIH.

Looking at the time complexity, we obtain that, running 300 benchmark problems from 200 to 1000 customers, TAH is one thousand times faster than the PFIH.

Moreover, we have designed an experiment to quantify the “diversity” property for a genetic population. Considering the randomized generation as the most diversified, we obtained, using two different estimators, that TAH constantly produces better results than PFIH.

In conclusion, TAH represents a good compromise for genetic algorithms initialization, providing acceptable results within a really short time and without affecting the required individuals diversity

Participantes:

Simone Catana

Orientador:

Reginaldo Arakaki