Many real-world vehicle routing problems are dynamic optimization problems, with customer requests arriving over time, requiring a repeated reoptimization. In this paper, we consider a dynamic vehicle routing problem where one additional customer arrives at a beforehand unknown location when the vehicles are already under way. Our objective is to maximize the probability that the additional customer can be integrated into one of the otherwise fixed tours without violating time constraints. This is achieved by letting the vehicles wait at suitable locations during their tours, thus influencing the position of the vehicles at the time when the new customer arrives. For the cases of one and two vehicles, we derive theoretical results about the best waiting strategies. The general problem is shown to be NP-complete. Several deterministic waiting strategies and an evolutionary algorithm to optimize the waiting strategy are proposed and compared empirically. It is demonstrated that a proper waiting strategy can significantly increase the probability of being able to service the additional customer, at the same time reducing the average detour to serve that customer.

Since Hurricane Katrina, extensive studies have been conducted aiming to optimize the transit vehicle routing in the event of an emergency evacuation. However, the vast majority of the studies focus on solving the deterministic vehicle routing problem that all the evacuation data are known in advance. These studies are generally not practical in dealing with real-world problems which involve considerable uncertainty in the evacuation data set. In this dissertation, a SmartEvac system is developed for dynamic vehicle routing optimization in emergency evacuation. The SmartEvac system is capable of processing dynamic evacuation data in real time, such as random pickup requests, travel time change, network interruptions. The objective is to minimize the total travel time for all transit vehicles. A column generation based online optimization model is integrated into the SmartEvac system. The optimization model is based on the following structure: a master problem model and a sub-problem model. The master problem model is used for routes selection from a restricted routes set while the sub-problem model is developed to progressively add new routes into the restricted routes set. The sub-problem is formulated as a shortest path problem with capacity constraint and is solved using a cycle elimination algorithm. When the evacuation data are updated, the SmartEvac system will reformulate the optimization model and generate a new routes set based on the existing routes set. The computational results on benchmark problems are compared to other studies in the literature. The SmartEvac system outperforms other approaches on most of the benchmark problems in terms of computation time and solution quality. CORSIM simulation is used as a test bed for the SmartEvac system. CORSIM Run-Time-Extension is developed for communications between the simulation and the SmartEvac system. A case study of the Hurricane Gustav emergency evacuation is conducted. Different scenarios corresponding to different situations that presented in the Hurricane Gustav emergency evacuation are proposed to evaluate the performance of the SmartEvac system in response to real-time data. The average processing time is 28.9 seconds and the maximum processing time is 171 seconds, which demonstrate the SmartEvac system’s capability of real-time vehicle routing optimization.

This dissertation introduces and analyzes the Bus Evacuation Problem (BEP), a unique Vehicle Routing Problem motivated both by its humanitarian significance and by the routing and scheduling challenges of planning transit-based, regional evacuations. First, a variant where evacuees arrive at constant, location-specific rates is introduced. In this problem, a fleet of capacitated buses must transport all evacuees to a depot/shelter such that the last scheduled pick-up and the end of the evacuee arrival process occurs at a location-specific time. The problem seeks to minimize their accumulated waiting time, restricts the number of pick-ups on each location, and exploits efficiencies from service choice and from allowing buses to unload evacuees at the depot multiple times. It is shown that, depending on the problem instance, increasing the maximum number of pick-ups allowed may reduce both the fleet size requirement and the evacuee waiting time, and that, past a certain threshold, there exist a range of values that guarantees an efficient usage of the available fleet and equitable reductions in waiting time across pick-up locations. Second, an extension of the Ritter (1967) Relaxation Algorithm, which explores the inherent structure of problems with complicating variables and constraints, such as the aforementioned BEP variant, is presented. The modified algorithm allows problems with linear, integer, or mixed-integer subproblems and with linear or quadratic objective functions to be solved to optimality. Empirical studies demonstrate the algorithm viability to solve large optimization problems. Finally, a two-stage stochastic formulation for the BEP is presented. Such variant assumes that all evacuees are at the pick-up locations at the onset of the evacuation, that the set of possible demands is provided, and, more importantly, that the actual demands become known once buses visit the pick-up locations for the first time. The effect of exploratory visits (sampling) and symmetry is explored, and the resulting insights used to develop an improved formulation for the problem. An iterative (dynamic) solution algorithm is proposed. / Ph. D.

Unternehmen der Transportbranche müssen gerade im operativen Tagesgeschäft bei der Tourenplanung und Transportdisposition Planungsprobleme lösen, die ein hohes Maß an Dynamik aufweisen. Speziell die Inputfaktoren der Tourenplanung sind größtenteils dynamisch und stochastisch. Aus Sicht des Autors kann die Qualität von Tourplanungsergebnissen durch die zeitnahe Berücksichtigung unvorhergesehener Ereignisse nachhaltig verbessert werden. Jedoch findet diese zunehmend erfolgskritische Funktionalität in der Literatur bisher nur unzureichend Beachtung, obwohl das Tourenplanungsproblem (Vehicle Routing Problem (VRP)) eines der wichtigsten und am meisten erforschten kombinatorischen Optimierungsprobleme ist. Verfahren für kapazitierte dynamische Tourenplanungsproblemstellungen sind in der Literatur kaum zu finden. Speziell im Bereich der Algorithmen, die eine große Lösungsgeschwindigkeit, eine leichte Verständlichkeit, eine aus praktischer Sicht akzeptable Lösungsgüte aufweisen und die Möglichkeit besitzen, die aktuellen Routenpläne der Fahrzeuge ausgehend von der momentanen geographischen Position real-time zu verändern, besteht Forschungsbedarf. Die Arbeit geht daher der Forschungsfrage nach, wie ein Verfahren für die dynamische Tourenplanung zu konstruieren ist, welches das kapazitierte dynamische Tourenplanungsproblem mit der Möglichkeit der Änderung des aktuellen Fahrzeugzuges unter Einhaltung sehr kurzer Rechenzeiten bei größtmöglicher Verständlichkeit löst. Durch die genannten Kriterien wird im Rahmen der Arbeit der Schwerpunkt auf die Modifikation von klassischen heuristischen Verfahren für die Lösung von dynamischen Tourenplanungsproblemen gelegt. Die Arbeit befasst sich sowohl mit dem Gesamtkonzept zur Disposition dynamischer Kunden als auch mit konkreten Modellen und Verfahren zur Lösung von Subproblemen innerhalb des Gesamtkonzeptes. Ferner erfolgt die Präsentation von umfangreichen Simulationsergebnissen, die auf der durchgeführten softwaretechnischen Implementierung der entwickelten Verfahren basieren. Die gute Anwendbarkeit der neuen Verfahren in der Praxis wird gezeigt. Zwecks der möglichst ganzheitlichen Betrachtung des Themengebietes erfolgt in der Arbeit zum einen sowohl die Erörterung von quantitativen als auch von qualitativen Aspekten der dynamischen Tourenplanung und zum anderen die Analyse von Schnittstellen zwischen der dynamischen Tourenplanung und eng damit verbundenen Bereichen wie Flottenmanagement oder Auftragseingang bzw. -disposition. Hierzu werden die Informationsflüsse zwischen den beteiligten Elementen im Rahmen des dynamischen Dispositionsprozesses aufgezeigt, telematische Komponenten zur Unterstützung des Informationsmanagements und der Informationsübertragung vorgestellt sowie die benötigten Inputdaten erläutert. Den Schwerpunkt der Arbeit stellt jedoch die Entwicklung von neuen quantitativen Methoden zur dynamischen Tourenplanung dar.

Made available in DSpace on 2016-06-02T19:51:37Z (GMT). No. of bitstreams: 1 2212.pdf: 1886443 bytes, checksum: bddd5428751623f23f36b7a2f2f3442c (MD5) Previous issue date: 2008-12-15 / Universidade Federal de Minas Gerais / In recent years, several studies have been revising static distribution models used by companies in order to incorporate intrinsic dynamic features of transport operations. Thanks to new technologies such as global positioning systems and wireless communications, vehicle routes elaborated in the beginning of the planning horizon can be altered in real time in order to serve new requests, avoid traffic jams, or find alternatives when some of the fleet vehicles are late or broke. In this way, realistic solutions of better quality are expected to be obtained from the company´s point of view (smaller costs) as well as from the customers´ (better service level). The main objective of this work is to analyze the impacts resulting from the incorporation of dynamic vehicle routing and scheduling in service production systems where the due dates for service is a prioritary issue. Specifically, we tackled the Dynamic Vehicle Routing Problem, where route plans are elaborated in a planning horizon. Initially, the definition and characteristics of dynamic problems are presented along with a review of some of the main contributions in the literature. We propose a heuristic based on Pureza and Laporte´s algorithm (2008) in order to obtain routes in real time. The relative impact of the heuristic application to other methods is analyzed by means of a set of generated instances from the data supplied by a drink company in São Paulo State. / Nos últimos anos, um crescente número de estudos científicos vem revisando modelos estáticos de distribuição adotados por empresas a fim de incorporar o dinamismo intrínseco às operações envolvidas. Esta tendência se deve principalmente aos avanços tecnológicos na área de geo-referenciamento, os quais permitem que rotas elaboradas no início do horizonte de planejamento sejam alteradas em tempo real a fim de atender novas requisições de clientes, evitar congestionamentos de tráfego, ou ainda, encontrar alternativas na ocorrência de veículos atrasados ou quebrados. Desta forma, espera-se obter soluções realistas de maior qualidade tanto do ponto de vista da empresa (menores custos) como dos clientes (melhor nível de serviço). Este trabalho tem como objetivo principal analisar o impacto decorrente da incorporação de métodos de roteamento dinâmico de veículos em ambientes de prestação de serviço onde o prazo de atendimento é o objetivo prioritário. Especificamente, é tratado o Problema de Roteamento de Veículos Dinâmico, onde planos de rotas são elaborados ao longo de um horizonte de planejamento. Inicialmente, a definição e características de problemas dinâmicos são apresentadas, juntamente com uma revisão de algumas das principais contribuições da literatura. É proposta, então, uma heurística baseada no algoritmo de Pureza e Laporte (2008) para elaboração de rotas em tempo real. O impacto da aplicação da heurística é analisado frente a outros métodos, utilizando-se um conjunto de instâncias geradas a partir de dados fornecidos por uma empresa do setor de bebidas do interior do estado de São Paulo.

Les activités de transport jouent un rôle crucial autant dans le domaine de la production que dans celui des services. En particulier, elles permettent d’assurer la distribution de biens et de services entre fournisseurs, unités de production, entrepôts, distributeurs, et clients finaux. Plus spécifiquement, les problèmes de tournées de véhicules (VRP) considèrent la mise au point d’un ensemble de tournées de coût minimal servant la demande en biens ou en services d’un ensemble de clients distribués géographiquement, tout en vérifiant un ensemble de contraintes opérationnelles. Alors qu’il s’agissait d’un problème statique, des avancées technologiques récentes permettent aux organisations de gérer leur flotte de véhicules en temps réel. Cependant, ces nouvelles technologies introduisent également une plus grande complexité dans les tâches de gestion de flotte, révélant une demande pour des outils d’aide à la décision dédiés aux problèmes de tournées de véhicules dynamiques. Dans ce contexte, les contributions de la présente thèse de doctorat s’organisent autour de trois axes : (i) elle présente un état de l’art détaillé des problèmes de tournées dynamiques; (ii) elle introduit des frameworks d’optimisation génériques adaptés à une grande variété de problèmes ; (iii) elle définit un problème de tournées novateur et aux nombreuses applications. / Within the wide scope of logistics management,transportation plays a central role and is a crucialactivity in both production and service industry.Among others, it allows for the timely distributionof goods and services between suppliers, productionunits, warehouses, retailers, and final customers.More specifically, Vehicle Routing Problems(VRPs) deal with the design of a set of minimal costroutes that serve the demand for goods orservices of a set of geographically spread customers,satisfying a group of operational constraints.While it was traditionally a static problem, recenttechnological advances provide organizations withthe right tools to manage their vehicle fleet in realtime. Nonetheless, these new technologies alsointroduce more complexity in fleet managementtasks, unveiling the need for decision support systemsdedicated to dynamic vehicle routing. In thiscontext, the contributions of this Ph.D. thesis arethreefold : (i) it presents a comprehensive reviewof the literature on dynamic vehicle routing ; (ii)it introduces flexible optimization frameworks thatcan cope with a wide variety of dynamic vehiclerouting problems ; (iii) it defines a new vehicle routingproblem with numerous applications.

A Roteirização de Veículos desempenha papel fundamental nos processos modernos de distribuição de produtos e realização de serviços. A atual disseminação de recursos de tecnologia de informação e comunicação, de forma confiável e economicamente acessível, permite trabalhar com informações em tempo real e melhoram os padrões de nível de serviço associados. O presente trabalho apresenta uma solução para roteirização de veículos cujas equipes de bordo realizam serviços que justificam seu deslocamento, uma vez que as demandas estão geograficamente dispersas. Tais demandas são, em parte, conhecidas antes do despacho (permitem programação antecipada) dos veículos e suas equipes; outra parte surge durante a jornada de trabalho. Como exemplos podem-se citar os casos de serviços de montagem e manutenção de instalações, equipamentos, engenharia e inspeção de tráfego, policiamento etc. Trata-se da aplicação da roteirização parcialmente dinâmica, conforme Larsen (2000), cujas bases foram definidas por Psaraftis (1988,1995), Bertsimas et al (1993) no problema DTRP (Dynamic Travelling Repairman Problem). A função objetivo apresenta uma combinação de minimização dos custos de deslocamento, para os pedidos de serviços conhecidos antes da saída dos veículos e de minimização do tempo de resposta (chegada no local do cliente ou da ocorrência) para os casos de pedidos imediatos ou emergenciais. A solução do problema envolve um modelo computacional de testes e avaliação, heurística de Clarke e Wright (1964) para formação das rotas estáticas, no Método Húngaro (Kuhn, 1955) para designar o veículo que resulta no menor tempo de resposta no atendimento a um pedido emergencial e a heurística de Clarke e Wright modificada na otimização do restante dos pedidos quando o veículo voltar a sua rota original. O modelo computacional foi testado em uma empresa de manutenção de elevadores na cidade de São Paulo, Brasil, onde demonstrou resultados comparativamente melhores em relação ao sistema de roteirização utilizado atualmente pela empresa. / The Vehicle Routing Problem plays a critical role on modern processes related to physical distribution of goods and services. The present expansion of information and communication technology in a reliable, economic and accessible way allows real time information and requires the utilization of appropriate tools for real time decisions resulting in significant improvements in quality and service level related to dynamic vehicle routing. A dynamic routing problem is presented, in which vehicles serve geographic dispersed service demands that justify their movement in a fixed area. Such service demands are partially known before vehicles dispatching (allowing prior programming) whilst others are known during the work journey. As examples, one can mention cases concerning installation and maintenance of utilities, equipment, engineering and surveillance services that refer to applications of Partially Dynamic Routing according to Larsen (2000), the groundings of which were defined by Psaraftis (1988,1995), Bertsimas et al (1993) in the Dynamic Travelling Repairman Problem (DTRP). The objective function is a combination of the minimization of movement costs to serve the prior demands and the minimization of time to reach (time to response) Dynamic-or-emergency-demand sites. The proposed solution involves a computational model for testing and evaluating a set of heuristics and methods comprising the Clarke and Wright (1964) Heuristic to compose the static routes, the Hungarian Method (Kuhn, 1955) to assign vehicles to the dynamic demands that produces the lowest response time and, finally, a Clarke and Wright Modified Heuristic used to optimize the remainder of the route when each diverted vehicle returns to its static route. The Computational Model was applied to a lift maintenance company located in the city of São Paulo (Brazil) demonstrating better results as compared to the present routing system.

Within the wide scope of logistics management,transportation plays a central role and is a crucialactivity in both production and service industry.Among others, it allows for the timely distributionof goods and services between suppliers, productionunits, warehouses, retailers, and final customers.More specifically, Vehicle Routing Problems(VRPs) deal with the design of a set of minimal costroutes that serve the demand for goods orservices of a set of geographically spread customers,satisfying a group of operational constraints.While it was traditionally a static problem, recenttechnological advances provide organizations withthe right tools to manage their vehicle fleet in realtime. Nonetheless, these new technologies alsointroduce more complexity in fleet managementtasks, unveiling the need for decision support systemsdedicated to dynamic vehicle routing. In thiscontext, the contributions of this Ph.D. thesis arethreefold : (i) it presents a comprehensive reviewof the literature on dynamic vehicle routing ; (ii)it introduces flexible optimization frameworks thatcan cope with a wide variety of dynamic vehiclerouting problems ; (iii) it defines a new vehicle routingproblem with numerous applications.

A Roteirização de Veículos desempenha papel fundamental nos processos modernos de distribuição de produtos e realização de serviços. A atual disseminação de recursos de tecnologia de informação e comunicação, de forma confiável e economicamente acessível, permite trabalhar com informações em tempo real e melhoram os padrões de nível de serviço associados. O presente trabalho apresenta uma solução para roteirização de veículos cujas equipes de bordo realizam serviços que justificam seu deslocamento, uma vez que as demandas estão geograficamente dispersas. Tais demandas são, em parte, conhecidas antes do despacho (permitem programação antecipada) dos veículos e suas equipes; outra parte surge durante a jornada de trabalho. Como exemplos podem-se citar os casos de serviços de montagem e manutenção de instalações, equipamentos, engenharia e inspeção de tráfego, policiamento etc. Trata-se da aplicação da roteirização parcialmente dinâmica, conforme Larsen (2000), cujas bases foram definidas por Psaraftis (1988,1995), Bertsimas et al (1993) no problema DTRP (Dynamic Travelling Repairman Problem). A função objetivo apresenta uma combinação de minimização dos custos de deslocamento, para os pedidos de serviços conhecidos antes da saída dos veículos e de minimização do tempo de resposta (chegada no local do cliente ou da ocorrência) para os casos de pedidos imediatos ou emergenciais. A solução do problema envolve um modelo computacional de testes e avaliação, heurística de Clarke e Wright (1964) para formação das rotas estáticas, no Método Húngaro (Kuhn, 1955) para designar o veículo que resulta no menor tempo de resposta no atendimento a um pedido emergencial e a heurística de Clarke e Wright modificada na otimização do restante dos pedidos quando o veículo voltar a sua rota original. O modelo computacional foi testado em uma empresa de manutenção de elevadores na cidade de São Paulo, Brasil, onde demonstrou resultados comparativamente melhores em relação ao sistema de roteirização utilizado atualmente pela empresa. / The Vehicle Routing Problem plays a critical role on modern processes related to physical distribution of goods and services. The present expansion of information and communication technology in a reliable, economic and accessible way allows real time information and requires the utilization of appropriate tools for real time decisions resulting in significant improvements in quality and service level related to dynamic vehicle routing. A dynamic routing problem is presented, in which vehicles serve geographic dispersed service demands that justify their movement in a fixed area. Such service demands are partially known before vehicles dispatching (allowing prior programming) whilst others are known during the work journey. As examples, one can mention cases concerning installation and maintenance of utilities, equipment, engineering and surveillance services that refer to applications of Partially Dynamic Routing according to Larsen (2000), the groundings of which were defined by Psaraftis (1988,1995), Bertsimas et al (1993) in the Dynamic Travelling Repairman Problem (DTRP). The objective function is a combination of the minimization of movement costs to serve the prior demands and the minimization of time to reach (time to response) Dynamic-or-emergency-demand sites. The proposed solution involves a computational model for testing and evaluating a set of heuristics and methods comprising the Clarke and Wright (1964) Heuristic to compose the static routes, the Hungarian Method (Kuhn, 1955) to assign vehicles to the dynamic demands that produces the lowest response time and, finally, a Clarke and Wright Modified Heuristic used to optimize the remainder of the route when each diverted vehicle returns to its static route. The Computational Model was applied to a lift maintenance company located in the city of São Paulo (Brazil) demonstrating better results as compared to the present routing system.

Unternehmen der Transportbranche müssen gerade im operativen Tagesgeschäft bei der Tourenplanung und Transportdisposition Planungsprobleme lösen, die ein hohes Maß an Dynamik aufweisen. Speziell die Inputfaktoren der Tourenplanung sind größtenteils dynamisch und stochastisch. Aus Sicht des Autors kann die Qualität von Tourplanungsergebnissen durch die zeitnahe Berücksichtigung unvorhergesehener Ereignisse nachhaltig verbessert werden. Jedoch findet diese zunehmend erfolgskritische Funktionalität in der Literatur bisher nur unzureichend Beachtung, obwohl das Tourenplanungsproblem (Vehicle Routing Problem (VRP)) eines der wichtigsten und am meisten erforschten kombinatorischen Optimierungsprobleme ist. Verfahren für kapazitierte dynamische Tourenplanungsproblemstellungen sind in der Literatur kaum zu finden. Speziell im Bereich der Algorithmen, die eine große Lösungsgeschwindigkeit, eine leichte Verständlichkeit, eine aus praktischer Sicht akzeptable Lösungsgüte aufweisen und die Möglichkeit besitzen, die aktuellen Routenpläne der Fahrzeuge ausgehend von der momentanen geographischen Position real-time zu verändern, besteht Forschungsbedarf. Die Arbeit geht daher der Forschungsfrage nach, wie ein Verfahren für die dynamische Tourenplanung zu konstruieren ist, welches das kapazitierte dynamische Tourenplanungsproblem mit der Möglichkeit der Änderung des aktuellen Fahrzeugzuges unter Einhaltung sehr kurzer Rechenzeiten bei größtmöglicher Verständlichkeit löst. Durch die genannten Kriterien wird im Rahmen der Arbeit der Schwerpunkt auf die Modifikation von klassischen heuristischen Verfahren für die Lösung von dynamischen Tourenplanungsproblemen gelegt. Die Arbeit befasst sich sowohl mit dem Gesamtkonzept zur Disposition dynamischer Kunden als auch mit konkreten Modellen und Verfahren zur Lösung von Subproblemen innerhalb des Gesamtkonzeptes. Ferner erfolgt die Präsentation von umfangreichen Simulationsergebnissen, die auf der durchgeführten softwaretechnischen Implementierung der entwickelten Verfahren basieren. Die gute Anwendbarkeit der neuen Verfahren in der Praxis wird gezeigt. Zwecks der möglichst ganzheitlichen Betrachtung des Themengebietes erfolgt in der Arbeit zum einen sowohl die Erörterung von quantitativen als auch von qualitativen Aspekten der dynamischen Tourenplanung und zum anderen die Analyse von Schnittstellen zwischen der dynamischen Tourenplanung und eng damit verbundenen Bereichen wie Flottenmanagement oder Auftragseingang bzw. -disposition. Hierzu werden die Informationsflüsse zwischen den beteiligten Elementen im Rahmen des dynamischen Dispositionsprozesses aufgezeigt, telematische Komponenten zur Unterstützung des Informationsmanagements und der Informationsübertragung vorgestellt sowie die benötigten Inputdaten erläutert. Den Schwerpunkt der Arbeit stellt jedoch die Entwicklung von neuen quantitativen Methoden zur dynamischen Tourenplanung dar.