Métodos escalables de resolución para el Dial-a-Ride Problem (DARP)

Abstract

En este documento se lleva a cabo un estudio acerca del problema Dial-a-Ride, sobre el cual es analizado en detalle desde una perspectiva formal,utilizando como herramienta de apoyo su formulación mediante el paradigma de Programación Lineal Mixta y Entera (MILP), a través de la cual se discutesu relación con otros Problemas de Rutas de Vehículos (VRP). Además, se lleva a cabo una descripción sobre los métodos de resolución mas popularespara resolver el problema Dial-a-Ride, partiendo por los Métodos Exactos para posteriormente enfocarse en aquellos basados en (Meta-)Heurísticas.Finalmente, se presenta la versión inicial de la biblioteca jinete como suite de métodos de resolución del problema, cuya implementación se ha llevado acabo como tarea adicional de este trabajo.

In this document, a study about the Dial-a-Ride problem is carried out, on which it is analyzed in detail from a formal perspective, using its formulation using the Mixed Integer Linear Programming (MILP) paradigm, through which its relationship with other Vehicle Route Problems (VRP) is discussed. In addition, a description on the most popular resolution methods to solve the Diala- Ride problem is carried out, starting with the Exact Methods to later focus on those based on (Meta-)Heuristics. Finally, an initial version of the jinete library is presented as a suite of methods for solving the problem, the implementation of which has been carried out as an additional task of this work.