Vehicle route optimization system with stochastic demands including predictive models

Abstract

[ES] Durante los últimos años se ha producido un incremento en el número de ciudades que están incorporando nuevos sistemas basados en el concepto conocido como Internet de las Cosas o Internet of Things (IoT) para, por un lado, obtener nuevos datos acerca de la ciudad y, por otro, a partir de estos, ofrecer nuevos servicios y optimizar el consumo energético. Estas ciudades se mueven hacia un paradigma de ciudad inteligente o Smart City, cuyo principal objetivo es conseguir ciudades más sostenibles y que constituyan un mejor lugar donde vivir. Entre todas las aplicaciones que han surgido para Smart Cities, cabe destacar las destinadas a la logística inteligente, que buscan el ahorro y la eficiencia energética en el transporte realizado por las flotas de vehículos. Unido a esto, nuevos sensores han emergido para llevar a cabo proyectos que incorporen el concepto de IoT y la conexión de cualquier objeto de la vida diaria a Internet. Estos sensores o nodos se agrupan en las conocidas como Wireless Sensor Networks (WSN) o redes inalámbricas de sensores. Dichas redes pueden desplegarse tanto en entornos rurales como en urbanos y suponen la infraestructura básica para la toma de datos en aplicaciones para Smart Cities. En la presente tesis se realiza una investigación sobre el uso indicado de los sensores junto con las WSN para la toma de datos en sistemas de recogida de desechos. Asimismo, el procesamiento de los datos obtenidos por dichas redes y la extracción de patrones que permitan modelar su comportamiento ofrecen una valiosa información que puede emplearse más tarde para mejorar otros sistemas, como, por ejemplo, sistemas de optimización de rutas de vehículos. En este trabajo de tesis se aborda la utilización de modelos de predicción para predecir la demanda y que esta información pueda proporcionarse a otros sistemas para su posterior uso. Por último, los datos obtenidos a través de una red de sensores y la información extraída gracias a los modelos de predicción habilitan la inclusión de nuevos métodos de optimización de rutas de vehículos en un sistema de recogida inteligente de desechos o Smart Waste Collection System en inglés. La optimización de las rutas de vehículos en este tipo de sistemas se formula en la literatura como un problema de rutas de vehículos o Vehicle Routing Problem (VRP), en el que generalmente sus parámetros son de naturaleza estocástica, pero con frecuencia son tratados de forma determinista. En esta tesis se aborda la resolución de problemas VRP que incluyan incertidumbre en la demanda de sus clientes. Para ello, se emplean nuevas metodologías propuestas en la literatura como Simheuristics y se propone incluir modelos de predicción con el fin de obtener mejores resultados.

[EN]In recent years there has been an increase in the number of cities that are incorporating new systems based on the concept known as the Internet of Things (IoT) to, on the one hand, obtain new data about the city and, on the other hand, from these, offer new services and optimize energy consumption. These cities are moving towards an intelligent city paradigm called Smart City, whose main objective is to achieve more intelligent and sustainable cities that constitute a better place to live. Among all the applications that have arisen for Smart Cities, it is worth highlighting those aimed at intelligent logistics, which seek savings and energy efficiency in transport performed by vehicle fleets. Along with this, new sensors have emerged to carry out projects that incorporate the concept of IoT and the connection of an object of daily life to the Internet. These sensors or nodes are grouped into what are known as Wireless Sensor Networks (WSN). These networks can be deployed in both rural and urban environments and provide the essential infrastructure for data collection in applications for Smart Cities. In the present thesis, a research is conducted on the indicated use of the sensors together with the WSN for the data collection in waste collection systems. Likewise, the processing of the data obtained by these networks and the extraction of patterns that allow modelling their behaviour offer valuable information which can be used later to improve other systems such as routing optimization systems. This thesis work deals with the use of prediction models to predict demand and then provide this information to other systems for later use. Finally, the data obtained through a network of sensors and the information extracted through predictive models enable the inclusion of new methods of vehicle routing optimization in an intelligent waste collection system or Smart Waste Collection System. The optimization of vehicle routes in this type of system is formulated in the literature as a Vehicle Routing Problem (VRP), in which its parameters are generally stochastic in nature, but are treated deterministically. This thesis deals with the resolution of VRP problems that include uncertainty in the demand of their customers. To this end, new methodologies in the literature such as Simheuristics are used and, in this work, modifications are proposed including prediction models in their use in order to obtain better results.