Investigação de metaheurísticas aplicadas ao problema de roteamento de veículos multiobjetivo com coleta opcional

Abstract

The vehicle routing problem with pickup and delivery services is a basic problem of reverse logistics. In general, this problem consists in defining lowest-cost routes that satisfy all consumer demands of collection and delivery, and meet the limited capacity of the vehicles. However, in many real situations, this problem is not limited to just a single goal, but there are others performance criteria that need to be evaluated, such as customer satisfaction, employee satisfaction or compliance with current legislation. In this context, the main contributions of this thesis is an approach for multiobjective vehicle routing problem with pickup and delivery services. In the mathematical model, the fulfillment of pickup demands are not mandatory, but highly desirable. Therefore, the objectives are the minimization of transportation costs and the maximization of pickup demands satisfied. Due to the computational complexity of the problem, four heuristic algorithms are implemented: MOGVNS, NSGA-II, P and IBMOLS. These algorithms exploit the particularities of the metaheuristics based on local search and population, and the traditional techniques for solving multiobjective problems such as -Restricted method. The algorithms quality is assessed in 2 sets of known instances. The first one is composed by 40 test problems with 50 customers. The other one is composed by 14 test problems with 50 to 200 customers. The analysis in different groups of instances allow to qualified the algorithms for instances of different sizes. The solutions obtained is evaluate in terms of hypervolume, cardinality, execution time and coverage metrics. After statistical analysis, the hypothesis tests demonstrated significant differences between the algorithms, indicating that the MOGVNS outperformed the NSGA-II and IBMOLS algorithms. Analysing the hypervolume and coverage metrics, the solutions found by MOGVNS are closer to the Pareto-optimal frontier and/or better distributed, for both sets of instances. Thus, further analysis were performed with the MOGVNS to verify the solution quaviii lityin one end point, which can be compared with literature results. The MOGVNS algorithm achieved good results compared to the Vehicle Routing Problem with Simultaneous Pickup and Delivery solution, which is an approximation of the frontier extreme point where all pickup demands are fulfilled. Furthermore, we have found the Pareto optimal frontier for the two instances with the smaller number of consumers while for the other instances a lower bound was defined. The results showed that MOGVNS returned the optimal solution in the most frontier points and points closer to the lower bound. During the lower bound generation, it was observed that the difference between the lower and upper bounds presented by the solver was very high even limiting the computational time to 5 days. These data emphasize the need to use efficient heuristics to find a solution to the problem in a feasible time. Finally, the results also confirm the importance of a multiobjective approach to the reported problem. In general, problems in which the sum of the demands collection is less than the sum of demands delivery, the difference in transport cost between the ends of the frontier is very small, i.e., the difference in transport cost to perform all pickup and not perform them is almost negligible. This information combined with the representation of the Pareto optimal frontier, that allows the visualization of all solutions that would be applied, the decision maker can adopt more efficient solutions and better suited to reality.