Optimización de rutas para ride-pooling

Abstract

Podemos definir ride-pooling como el servicio de movilidad en el cual varios pasajeros comparten un conductor profesional. El objetivo de ride-pooling es proporcionar una solución que permita reducir el coste económico de los viajes (menos viajes con más pasajeros), tratar de minimizar los viajes en vacío (trayectos sin pasajero) y de ese modo ayudar a lograr ciudades más sostenibles medioambientalmente y con menos coches. El trabajo se centra el desarrollo de una solución tecnológica que permita obtener rutas de transporte óptimas mediante la agrupación de usuarios. El problema que se trata de abordar es una especialización de VPR o problema de enrutamiento de vehículos. Para lograr el objetivo el trabajo contextualiza e investiga el problema para abordar finalmente de forma iterativa e incremental la construcción en lenguaje Go de un servicio de optimización de rutas para ride-pooling. Para ello, se apoya en la implementación de un algoritmo heurístico que soluciona nuestro problema. El resultado del trabajo incluye como entregables un servicio funcional en forma de API HTTP que permite enviar problemas de VRP y obtener su solución de forma escalable y eficiente. Este solver permite agrupar usuarios en vehículos proporcionando como resultado rutas óptimas, tanto de forma síncrona como asíncrona, atendiendo a las restricciones del problema.

We can define ride-pooling as the mobility service in which several passengers share a professional driver. The objective of ride-pooling is to provide a solution that allows to reduce the economic cost of journeys (fewer journeys with more passengers), try to minimize empty journeys (journeys without a passenger) and thus help to achieve more environmentally sustainable cities and with fewer cars. The work focuses on the development of a technological solution that allows obtaining optimal transport routes by grouping users. The problem they are trying to address is a VPR (vehicle routing problem) specialization. To achieve the objective, the work contextualizes and investigates the problem to finally approach in an iterative and incremental way the construction in Go language of a route optimization service for ride-pooling. For this, it relies on the implementation of a heuristic algorithm that solves our problem. The result of the work includes as deliverables a functional service in the form of an HTTP API that allows to send VRP problems and obtain their solution in a scalable and efficient way. This solver allows users to be grouped into vehicles, resulting in optimal routes, both synchronously and asynchronously, taking into account the constraints of the problem.

Podem definir ride-pooling com el servei de mobilitat en el qual diversos passatgers comparteixen un conductor professional. L'objectiu de ride-pooling és proporcionar una solució que permeti reduir el cost econòmic dels viatges (menys viatges amb més passatgers), tractar de minimitzar els viatges en buit (trajectes sense passatger) i d'aquesta manera ajudar a aconseguir ciutats més sostenibles mediambientalment i amb menys cotxes. El treball se centra el desenvolupament d'una solució tecnològica que permeti obtenir rutes de transport òptimes mitjançant l'agrupació d'usuaris. El problema que es tracta d'abordar és una especialització de VPR o problema d'encaminament de vehicles. Per a aconseguir l'objectiu el treball contextualitza i investiga el problema per a abordar finalment de manera iterativa i incremental la construcció en llenguatge Go d'un servei d'optimització de rutes per a ride-pooling. Per a això, es recolza en la implementació d'un algorisme heurístic que soluciona el nostre problema. El resultat del treball inclou com a lliurables un servei funcional en forma de API HTTP que permet enviar problemes de VRP i obtenir la seva solució de manera escalable i eficient. Aquest solver permet agrupar usuaris en vehicles proporcionant com a resultat rutes òptimes, tant de manera síncrona com asíncrona, ateses les restriccions del problema.