Adaptive metaheuristics for the pickup and delivery problem with time windows

Abstract

Efficiency in vehicle routing has become crucial for the success of logistical operations, especially with the significant increase in demand for product transportation observed recently due to the COVID-19 pandemic, which should remain elevated even after the pandemic's end. In this context emerges the pickup and delivery problem with time windows (PDPTW), which involves determining least-cost routes to collect goods or people at some points and deliver them to their destinations, respecting time intervals defined in advance. This problem has wide applicability and can be used to represent different real situations in the urban context, for example, in the transportation of passengers and in the meal and grocery deliveries. The PDPTW is a complex problem and exact solution methods can hardly obtain optimal solutions in a reasonable time for real-sized instances, compromising the use of such methods to support decision making. Thus, it is important to resort to heuristic approaches, as they are capable of obtaining good solutions in practicable computational times. This project aims to study and implement mathematical models and heuristic methods for the PDPTW, focusing on adaptive metaheuristics, as they have shown superior performance in recent works. The performance of these approaches will be verified through computational experiments using instances from the literature and real-world data provided by a company that manages the pickup and delivery of meals involving different restaurants in urban centers. (AU)