Combination of vehicle routing models and dynamic traffic simulation for city logistics applications

Abstract

The urban network is a highly dynamic system. Thus, a modern and efficient fleet management in urban areas should account for dynamics of traffic conditions, variability in travel times, changes in demand and fleet availability. All these factors significantly affect the distribution of goods and the provision of services. As a consequence, the freight operations optimizing approaches should be based on the time-dependent travel time estimates rather than on the average static values commonly employed as input data. Proficient dynamic fleet management decisions need to take into consideration all the factors conditioning the addressed problem. Hence, the customers’ requests and service conditions (demands, time windows, etc.), operational conditions of the employed fleet (vehicles’ availability, status, positions, current occupancy of the carriage space, etc.) and traffic conditions need to be reckoned with. This information can be provided in the real-time fashion and at an affordable price by the ICT applications and tools such as: ATIS, GPS, GPRS or other. Instead of relying exclusively on the experience of a dispatcher, it is effective to base the freight management decisions on information provided by a professional Decision Support System facilitating the consideration of all the factors conditioning the addressed issue. The objective of the present thesis is to propose, implement and computationally test, on the basis of a simulation, the architecture of a Decision Support System for real-time freight management able of accounting for all the dynamic factors mentioned above. Its design is based on integration of a selected pickup and delivery vehicle routing model and dynamic traffic simulation models, whose purpose is to carefully emulate the evolving traffic conditions. The optimal dynamic routing and scheduling of a vehicle fleet is obtained due to dynamic modifications of the current routing and scheduling plan on the basis of the recently revealed information conditioning the addressed problem. The obtained results of computational experiments show that the performance of freight fleet strongly depends on the traffic information used to create the routing and scheduling plan. Due to the special character of transport operations performed in metropolitan areas it is possible that not all the scheduled customers would be served, although a feasible initial solution is created on the basis of the historical travel times’ data. Hence, there is a need to implement real-time rerouting strategies allowing modifications of the original routes in order to feasibly fulfil the routing tasks. In addition, the tighter the constraints specifying the customers’ time windows and the higher the number of dynamically appearing requests, the higher the cost of the performance and the level of utilization of the freight fleet.

La red urbana es un sistema altamente dinámico. Por lo tanto, la gestión moderna y eficiente de la flota en las zonas urbanas debe tener en cuenta la dinámica de las condiciones del tráfico, la variabilidad en los tiempos de viaje y los cambios en la disponibilidad de la demanda y de la flota, ya que afectan de manera significativa en la distribución de bienes y la prestación de servicios. Como consecuencia, los enfoques para optimizar las operaciones de carga deben basarse en las estimaciones de los tiempos de viaje dependientes del tiempo y no en los valores medios estáticos comúnmente empleados como datos de entrada. Las decisiones competentes de gestión dinámica de las flotas necesitan tener en cuenta todos los factores que condicionan el problema abordado. Por lo tanto, hay que considerar las características de las peticiones y las condiciones de servicio de los clientes (demanda, ventanas de tiempo, etc.), las condiciones operacionales de la flota empleada (disponibilidad de los vehículos, estatus, ubicación, ocupación actual del espacio de transporte, etc.) y las condiciones de tráfico. Esta información puede ser proporcionada en tiempo real a un precio asequible por las aplicaciones de las TIC y herramientas tales como: ATIS, GPS, GPRS u otros. En lugar de confiar exclusivamente en la experiencia de un distribuidor, también sería correcto basar las decisiones de gestión de transporte de mercancías en la información proporcionada por un sistema profesional de apoyo a la toma de decisiones que facilita la consideración de todos los factores que condicionan el problema abordado. El objetivo de esta tesis es proponer, implementar y validar computacionalmente en base a la simulación, la arquitectura de un Sistema de Apoyo a la Toma de Decisiones para la gestión de transporte de mercancías en tiempo real capaz de considerar todos los factores dinámicos previamente mencionados. Su diseño se basa en la integración de un modelo seleccionado de rutas de vehículos con recogida y entrega y modelos de simulación de tráfico dinámicos cuyo propósito es emular detalladamente las condiciones de tráfico que cambian con el paso del tiempo. Las rutas y los horarios dinámicos óptimos para una flota de vehículos que transporta mercancías se obtienen de las modificaciones dinámicas de un plan actual de rutas y horarios en base a la nueva información recibida que condiciona el problema abordado. Los resultados obtenidos de los experimentos computacionales demuestran que el rendimiento de la flota de transporte de mercancías depende en gran medida de la información de tráfico utilizada para crear el plan de rutas y los horarios. Debido al carácter especial de las operaciones de transporte realizadas en las áreas metropolitanas, a pesar de una solución inicial factible que se crea sobre la base de los datos históricos de los tiempos de viaje, es posible que no todos los clientes sean servidos. Por lo tanto, hay una necesidad de implementar estrategias de cambios de rutas en tiempo real, que permiten modificar las rutas originales con el fin de cumplir las tareas de enrutamiento viables. Además, más estrictas son las limitaciones que especifican las ventanas del tiempo de los clientes y más alto es el número de solicitudes de servicio que aparecen de forma dinámica, mayor será el coste final de las prestaciones del servicio y el nivel de utilización de la flota de transporte de mercancías.