Route planning for e-scooters

According to Wikipedia; The vehicle routing problem (VRP) is a combinatorial integer programming and optimisation problem that asks ¿What is the optimal set of routes that a fleet of vehicles should travel to deliver to a given set of customers?. Many years have passed since Dantzig and Ramser introduced this problem in 1959. They described a real-world application concerning the delivery of gasoline to service stations and proposed the first mathematical programming formulation and algorithmic approach. But even so, route optimisation is now more important than ever. Large delivery companies invest a lot of their capital in VRP consultancy, knowing the most optimal route to deliver saves you a lot of time and money. This project attempts to solve a route planning problem. This problem is based on the primary notions of a TSP (Travel Salesman Problem). Tries to solve a problem where we are in a city on an e-scooter and we want to visit a number of places in that city in the shortest possible time. To reach all the places that are a goal for you, the battery of the e-scooter has to be considered, as it is decreasing through the distance travelled. So you have to consider if it is worth to deviate from the fastest route to take another e-scooter that has enough battery to reach the next destination, changing e-scooter adds extra time (time in which you change from one e-scooter to another). The goal of the thesis is to design and implement an algorithm solving the problem, i.e. that shows you the fastest route and the time it takes to visit all destinations in the shortest possible time.Según la Wikipedia; El problema de enrutamiento de vehículos (VRP) es un problema combinatorio de programación entera y optimización que se pregunta ¿Cuál es el conjunto óptimo de rutas que debe recorrer una flota de vehículos para entregar a un conjunto dado de clientes?. Han pasado muchos años desde que Dantzig y Ramser introdujeron este problema en 1959. Describieron una aplicación del mundo real relativa a la entrega de gasolina en estaciones de servicio y propusieron la primera formulación de programación matemática y un enfoque algorítmico. Pero aún así, la optimización de rutas es ahora más importante que nunca. Las grandes empresas de reparto invierten gran parte de su capital en la consultoría de VRP, ya que conocer la ruta más óptima para el reparto les ahorra mucho tiempo y dinero. Este proyecto trata de resolver un problema de planificación de rutas. Este problema se basa en las nociones primarias de un TSP (Problema del viajante). Trata de resolver un problema en el que nos encontramos en una ciudad en un e-scooter y queremos visitar una serie de lugares de esa ciudad en el menor tiempo posible. Para llegar a todos los lugares que son un objetivo para ti, hay que tener en cuenta la batería del e-scooter, ya que va disminuyendo con la distancia recorrida. Así que hay que considerar si merece la pena desviarse de la ruta más rápida para coger otro e-scooter que tenga suficiente batería para llegar al siguiente destino, el cambio de e-scooter añade tiempo extra (tiempo en el que se cambia de un e-scooter a otro). El objetivo de la tesis es diseñar e implementar un algoritmo que resuelva el problema, es decir, que le muestre la ruta más rápida y el tiempo que tarda en visitar todos los destinos en el menor tiempo posible.Segons la Viquipèdia; El problema d'enrutament de vehicles (VRP) és un problema combinatori de programació sencera i optimització que es pregunta ¿Quin és el conjunt òptim de rutes que ha de recórrer una flota de vehicles per lliurar a un conjunt donat de clients?. Han passat molts anys des que Dantzig i Ramser van introduir aquest problema en 1959. Van descriure una aplicació del món real relativa al lliurament de gasolina en estacions de servei i van proposar la primera formulació de programació matemàtica i un enfocament algorítmic. Però tot i això, l'optimització de rutes és ara més important que mai. Les grans empreses de repartiment inverteixen gran part del seu capital en consultories de VRP, ja que conèixer la ruta òptima per al repartiment els hi estalvia molt de temps i diners. Aquest projecte tracta de resoldre un problema de planificació de rutes. Aquest problema es basa en les nocions primàries d'un TSP (Problema del viatger). Tracta de resoldre un problema en el qual ens trobem en una ciutat en un e-scooter i volem visitar una sèrie de llocs d'aquesta ciutat en el menor temps possible. Per arribar a tots els llocs que s´on un objectiu per a tu, cal tenir en compte la bateria de l'e-scooter, ja que va disminuint amb la distància recorreguda. Així que cal considerar si val la pena desviar-se de la ruta més ràpida per agafar un altre e-scooter que tingui prou bateria per arribar a la següent destinació, el canvi d' e-scooter afegeix temps extra (temps en el qual es canvia d'un e -scooter a un altre). L'objectiu de la tesi és dissenyar i implementar un algoritme que resolgui el problema, és a dir, que li mostri la ruta mès ràpida i el temps que triga a visitar totes les destinacions en el menor temps possible