No description available.

Cette thèse porte sur la modélisation et la résolution de différents problèmes de tournées de véhicules et plus particulièrement sur des problèmes de transport de personnes. Ces problèmes, demandent, entre autre, de respecter une qualité de service minimale pour les solutions proposées. Pour résoudre ces problèmes, plusieurs méthodes d'optimisation de type métaheuristique sont proposées pour obtenir des solutions de bonne qualité dans des temps raisonnables. Trois problèmes sont traités successivement : le DARP, le TDVRP, le SDARP. Le premier est un problème de transport à la demande (DARP - Dial-A-Ride Problem) qui est le problème de transport de personnes le plus connu de la littérature. Il est proposé dans ce chapitre une méthode de type ELS qui a été comparée aux meilleures méthodes publiées. Les tests montrent que la méthode ELS est compétitive en termes de temps de calcul et de qualité des résultats. Le deuxième problème est une extension du problème de tournées de véhicules (VRP - Vehicle Routing Problem) dans lequel les temps de trajet entre les sommets varient au cours de la journée (TDVRP - Time Dependent Vehicle Routing Problem). Dans ce problème, une distinction existe entre les temps de conduite et les temps de travail des chauffeurs. La différence entre les deux correspond aux temps de pause. Ils sont utilisés ici durant les tournées pour éviter aux chauffeurs de conduire durant les périodes à fort ralentissement du trafic. La méthode proposée permet entre autre de positionner stratégiquement ces pauses afin de réduire le temps de conduite et de proposer de nouvelles solutions. Le dernier problème traité concerne la résolution d'un DARP stochastique. Dans ce problème, les temps de trajet entre les clients ne sont plus déterministes, et ils sont modélisés par une loi de probabilité. L'objectif est de déterminer des solutions robustes aux fluctuations des temps de trajets sur les arcs. Une première approche a permis de calculer des solutions robustes qui ont une probabilité importante d'être réalisables, une seconde approche a permis de générer un ensemble de solutions offrant un équilibre entre la robustesse et le coût. / In this thesis, we are interested in modeling and solving various vehicle routing problems (VRP), especially passenger transportation problems. These problems aim at finding solutions which guarantee a required quality of service. Several metaheuristics are proposed to obtain high quality solutions within reasonable time. Three problems are addressed: the Dial-A-Ride Problem (DARP), the Time-Dependent Vehicle Routing Problem (TDVRP) and the Stochastic DARP (SDARP). The DARP is a well-known on-demand transportation problem. We propose an Evolutionary Local Search (ELS) method. It relies on a new randomized constructive heuristic and on adaptive probabilities for selecting neighborhood structures. This approach is compared with existing methods on classical instances. Results show the interest of the proposed method. The TDVRP is an extension of VRP in which the transportation time varies throughout the day. The driving time is separated from the drivers working time and the difference corresponds to the resting time. The resting time is used to avoid driving during highly congested periods. The proposed method set these resting times in order to reduce the driving time. Hence new solutions avoiding congestion as much as possible are proposed. In the SDARP, the travel time between clients is stochastic and thus follows a probability distribution. The objective is to compute robust solutions, i.e. solutions which handle variations of the transportation time. Two approaches are proposed for this problem. The first one produces robust solutions that have a significant probability of staying feasible. The second one generates a set of compromise solutions, balancing the robustness and the cost.

Made available in DSpace on 2016-12-23T14:05:56Z (GMT). No. of bitstreams: 1 patricia rodrigues parte 1 p 1-46.pdf: 620096 bytes, checksum: 2df2214171a193891fb63f38e815ac0e (MD5) Previous issue date: 2011-09-16 / Problems that deal with wheelchair users public transportation are often solved by Dial a Ride Problem (DARP) with time window (Time Window TW). The goal of this type of problem is the minimization of the operation cost, in other words, the ride time respecting constraints like time windows for pickup and delivery of each user, the number of vehicles available and each vehicle capacity. This thesis proposes an exact Mixed Integer Linear Program model to solve the DARPTW. In order to apply the model in a real application, the model was tested with data provided by the Vitória City Hall Infrastructure and Transportation Secretary. The model was implemented using CPLEX software and the results showed that instances up to 20 wheelchair users can be solved optimally. Moreover, it was done an analysis for fleet used / Os problemas de transporte público de cadeirantes são comumente resolvidos pelo modelo Dial-a-Ride Problem (DARP) com janelas de tempo (Time Window - TW). Com base nas restrições de janela de tempo na origem e no destino de cada cliente, no número de veículos e na capacidade de cada um deles, deseja-se minimizar os custos de atendimento dessas demandas, ou seja, o tempo de viagem. A presente dissertação propõe um modelo de Programação Linear Inteira Mista para resolver o problema do DARP-TW. Visando uma aplicação do modelo no transporte público de cadeirantes foram utilizados dados reais fornecidos pela Secretaria de Transportes, Trânsito e Infraestrutura da Prefeitura de Vitória. O modelo foi executado no software CPLEX e os resultados mostraram que cenários com até 20 clientes podem ser resolvidos otimamente. Além disso, foi possível uma análise em relação à frota utilizada

Made available in DSpace on 2016-12-23T14:21:18Z (GMT). No. of bitstreams: 1 Andre Manhaes Machado.pdf: 1039285 bytes, checksum: 2b356c4d0279c975232bd92c5e2ab326 (MD5) Previous issue date: 2013-11-16 / O petróleo é a principal fonte energética do mundo contemporâneo, insumo básico de diversos setores econômicos. Com a descoberta do Pré-sal, o Brasil tem a oportunidade de tornar-se um dos maiores produtores de petróleo. Entretanto, para que isso seja alcançado, vários desafios deverão ser superados e, dentre eles, encontra-se o problema de transporte de empregados para operarem as plataformas offshore, distantes até 300km de distância da costa brasileira. Os problemas referentes ao deslocamento de empregados por meio de helicópteros são usualmente tratados como o Capacitated Helicopter Routing Problem (CHRP). Com base nas restrições de origem e de destino de cada cliente, no número de veículos e na capacidade e restrições de voo dos helicópteros, neste tipo de problema deseja-se minimizar os custos de aluguel de helicópteros mais o custo total de quilômetros voados. A presente dissertação propõe um modelo de Programação Linear Inteira Mista (PLIM) para o problema de roteirização de helicópteros com base no Dial-a-Ride Problem (DARP). Além do modelo apresentado, foram apresentados duas abordagens para a execução do modelo de forma exata: i) abordagem sem agrupamento, na qual as requisições que possuem origens iguais e destinos iguais são modeladas como requisições distintas e ii) abordagem com agrupamento, na qual requisições que possuem origens iguais e destinos iguais são aglutinados numa nova e única requisição. O modelo matemático foi executado no software CPLEX e os resultados mostraram que instâncias com até 25 requisições podem ser resolvidas pela abordagem com agrupamento / Oil is the main energy source of contemporary world; it is basic inputs of various economic sectors. With the discovery of Brazil pre-salt, there is an opportunity to become one of the largest oil producers. However, to achieve her own goals, Brazil must overcome several challenges, including the problem of transporting employees to operate offshore platforms 300km distant away from the Brazilian coast. Problems related to displacement of employees by helicopters are usually treated as Capacitated Helicopter Routing Problem (CHRP). Based on source and destination restrictions of each client, the number of vehicles, capacity and helicopter flight constraints, this type of problem proposes to minimize the cost of renting helicopters and the total cost of flown kilometers. This dissertation proposes a model of Mixed Integer Linear Programming (MILP) for the helicopters routing problem based on a Dial-a-Ride Problem (DARP). Besides the presented model, we presented two approaches to implementing the model in an exact way: i) non-clustered approach, in which requests that have the same origin and destination are equal modeled as separate requests; and ii) clustered approach, in which requests that have the same origins and destinations are clumped together in a new single request. The mathematical model was implemented in software CPLEX and results showed that instances with up to 25 requests can be resolved in the clustered approach

Problèmes de tournées de véhicules statiques et déterministes ne peuvent pas être utilisés dans de nombreux systémes de la vieréelle, du fait que les données d’entrée ne sont pas fiables et sont révélées au fil du temps. Dans cette thèse, nous étudions un problème de ramassage et de livraison avec fenêtres de temps et un maximum de temps de trajet - le problème dial-a-ride - dans sa variante statique et dynamique, et nous faisons des propositions spécifiques sur les modèles d’optimisation robustes pour résoudre ce problème. Pour résoudre le modèle statique, nous développons une approche branch-and-price qui gère toutes les contraintes detemps dans le processus de création d’itinéraires de véhicules. Notre travail est axé sur les techniques de résolution du sous-problème et d’accélération pour l’approche branch-and-price. Nos résultats numériques montrent que la méthode est compétitive par rapport aux approches existantes qui sont basées sur le branch-and-cut. Dans le contexte dynamique, où certaines données d’entrée sont révélées dynamiquement ou modifiées au fil du temps, nous appliquons notre algorithme branch-and-price pour la ré-optimisation dans une approche sur horizon glissant. / Static and deterministic vehicle routing problems cannot be used in many real-life systems, as input data are not reliable and revealedover time. In this thesis, we study a pickup and delivery problem with time windows accounting for maximum ride time constraints – the so-called diala- ride problem – in its static and dynamic variant, and we make specific proposal on robust optimization models for this problem. To solve the static model, we develop a branch-and-price approach that handles ride time constraints in the process of generating feasible vehicle routes in the course of the optimization procedure. Our work is focussed on the pricing problem solver and acceleration techniques for the branch-and-price approach. Our numerical results show that the method is competitive compared to existing approaches that are based on branch-and-cut. In the dynamic context, where some input data are revealed or modified over time, we apply our branchand- price algorithm for re-optimization in a rolling horizon approach.

Made available in DSpace on 2014-12-17T14:53:10Z (GMT). No. of bitstreams: 1 SauloTAD_DISSERT.pdf: 1587906 bytes, checksum: 2d163959ab0b72bafed179c3efb3b6c8 (MD5) Previous issue date: 2012-07-04 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Worldwide, the demand for transportation services for persons with disabilities, the elderly, and persons with reduced mobility have increased in recent years. The population is aging, governments need to adapt to this reality, and this fact could mean business opportunities for companies. Within this context is inserted the Programa de Acessibilidade Especial porta a porta PRAE, a door to door public transportation service from the city of Natal-RN in Brazil. The research presented in this dissertation seeks to develop a programming model which can assist the process of decision making of managers of the shuttle. To that end, it was created an algorithm based on methods of generating approximate solutions known as heuristics. The purpose of the model is to increase the number of people served by the PRAE, given the available fleet, generating optimized schedules routes. The PRAE is a problem of vehicle routing and scheduling of dial-a-ride - DARP, the most complex type among the routing problems. The validation of the method of resolution was made by comparing the results derived by the model and the currently programming method. It is expected that the model is able to increase the current capacity of the service requests of transport / Em todo o mundo, a demanda por servi?os de transporte para pessoas portadoras de necessidades especiais, idosos, e pessoas com mobilidade reduzida v?m crescendo nos ?ltimos anos. A popula??o est? envelhecendo, os governos precisam se adaptar a esta realidade, e este fato pode significar oportunidade de neg?cios para as companhias. Dentro deste contexto est? inserido o Programa de Acessibilidade Especial porta a porta PRAE do munic?pio de Natal-RN. A pesquisa presente neste trabalho procura desenvolver um modelo de programa??o capaz de auxiliar o processo de tomada de decis?o dos gestores deste servi?o de transporte. Para tanto, foi criado um algoritmo baseado em m?todos de gera??o de solu??es aproximativas conhecidas como heur?sticas. O objetivo do modelo ? incrementar o n?mero de pessoas atendidas pelo PRAE, dada a frota dispon?vel, gerando programa??es de roteiros otimizadas. O PRAE consiste em um problema de roteiriza??o e programa??o de ve?culos do tipo dial-a-ride DARP, o tipo mais complexo dentre os problemas de roteiriza??o. A valida??o do m?todo de resolu??o ser? feita mediante compara??o entre os resultados auferidos pelo modelo e a programa??o real. Espera-se que o modelo seja capaz de elevar a capacidade de solicita??es atual deste servi?o de transporte

Pickup and Delivery Problems (PDPs) constitute a class of Vehicle Routing Problems (VRPs) consisting of finding the optimal routes for a fleet of vehicles to deliver requests from a set of origin locations to a corresponding set of destinations. PDPs are NP-hard and have a wide variety of variants and potential constraints. This thesis evaluates methods for solving a dynamic single- vehicle PDP restricted by multiple time-related constraints. The problem is dynamic in the sense that new requests arrive as time is simulated and inserted into the vehicle’s pickup and delivery plan as it is being executed. The time- related constraints include limited time windows during which the requests may be picked up or delivered, as well as maximum ride times that items may spend in the vehicle before being delivered. To solve the problem, we adapt insertion heuristics based on Large Neighborhood Search (LNS) and Heuristic Destroy and Repair (HDR) to the problem and evaluate them in a comparative study. Solution methods for the PDP are also applied on the problem of dynamically assigning incoming orders to vehicles in a delivery service with a short planning horizon. A PDP-based order assignment strategy is compared with assignment strategies based on proximity and workload. Due to the short planning horizon of the target application, the study is focused on finding well-performing methods for quickly solving small PDPs containing 10-15 requests. Our results indicate that LNS outperforms HDR for small problem instances. However, the quick convergence of HDR allows it to outperform LNS for larger problem instances. We also show that applying a PDP- based assignment strategy in the order assignment problem allows the service to accommodate more requests than the alternative assignment strategies while simultaneously providing a significant reduction in operational costs. Future work may improve the order assignment strategy by incorporating more anticipatory functionality and streamlining the PDP methods with more efficient tests for the feasibility of solutions. / Pickup and Delivery Problems (PDP:er) utgör en grupp av Vehicle Routing Problems (VRP:er) som består av att hitta de optimala rutterna för en fordonsflotta för att leverera beställningar från en uppsättning av upplockningsplatser till motsvarande uppsättning av avlämningsplatser. PDP:er är NP-svåra och har en stor mängd olika varianter och potentiella begränsningar. Denna avhandling utvärderar metoder för att lösa ett dynamiskt enkel-fordon PDP med flera tidsrelaterade begränsningar. Problemet är dynamiskt i den mening att nya beställnigar anländer i samband med att tiden simuleras och sätts in i fordonets leveransplan samtidigt som den utförs. De tidsrelaterade begränsningarna innefattar begränsade tidsfönstren under vilka beställningar kan plockas upp eller lämnas av, samt maximala tider som hämtade föremål får tillbringa i fordonet innan de lämnas av. För att lösa problemet anpassar vi insättningsheuristiker baserade på Large Neighborhood Search (LNS) och Heuristic Destroy and Repair (HDR) till problemet och utvärderar dem i en jämförande studie. Lösningsmetoder för PDP tillämpas också på problemet att dynamiskt tilldela inkommande beställningar till fordon i en leveransservice med en kort planeringshorisont. En PDP-baserad tilldelningsstrategi jämförs med strategier baserade på närhet och arbetsbelastning. På grund av målapplikationens korta planeringshorisont så fokuserar studien på att hitta väl presterande metoder för att snabbt lösa små PDP:er som innehåller 10-15 förfrågningar. Våra resultat indikerar att LNS överträffar HDR för små probleminstanser. Däremot leder den snabba konvergensen av HDR till att den överträffar LNS för större probleminstanser. Vi visar också att tillämpningen av en PDP-baserad tilldelningsstrategi i tilldelningsproblemet gör att tjänsten kan tillgodose fler beställningar än de alternativa tilldelningsstrategierna, samtidigt som det ger en betydlig minskning av driftskostnaderna. Framtida arbete kan förbättra tilldelningsstrategin genom att integrera mer förutseende funktionalitet och effektivisera PDP-metoderna med ett mer effektivt test av genomförbarhet för lösningar.

Traditional public transport systems are most often insufficient to provide a good transport service to everyone. Especially, it is not always possible for elderly and disabled persons to use the regular system consisting of timetabled services operating along fixed routes. Normally there is some specific service, often called paratransit, offered to these groups of customers. Such transport services provide better service to these customers, but to a higher cost. This thesis considers planning and evaluation of public transport services that are based on the concept of a dial-a-ride service. This kind of service is suitable for elderly and disabled and often operated as a door-to-door service, where customers are served on demand and rides are coordinated via a call-center. The thesis is divided into two parts. In the first part, a modeling system for simulation of dial-a-ride services is presented. It can be used as a tool to study how different ways of operating a dial-a-ride service, affect the performance and efficiency of the service. This system is used to evaluate how algorithmic changes, based on ruin-and-recreate methods, can improve the replanning of already inserted requests, and thereby improve the scheduling. The modeling system is also used to examine the effects of using zone-based distance estimates instead of true, address-based, distances when computing the schedules. The results show that only small differences are found.The second part of the thesis concerns an extension to dial-a-ride services. By combining a dial-a-ride service with a fixed route service, an integrated dial-a-ride service is created, where some part of each journey may be carried out by the fixed route service. An exact mathematical formulation of this problem is presented and it is shown that the formulation is strengthened by valid inequalities, variable substitution and subtour elimination constraints. Simulations of an integrated service are also performed to analyze and evaluate how the attractiveness and operating costs of the service depend on how the demand responsive service is operated.

Made available in DSpace on 2016-08-29T11:12:16Z (GMT). No. of bitstreams: 1 tese_6649_Dissertação - André Manhães.pdf: 1047859 bytes, checksum: 5602733dce0d5f103f7c07c76367c8c4 (MD5) Previous issue date: 2013-09-16 / O petróleo é a principal fonte energética do mundo contemporâneo, insumo básico de diversos setores econômicos. Com a descoberta do Pré-sal, o Brasil tem a oportunidade de tornar-se um dos maiores produtores de petróleo. Entretanto, para que isso seja alcançado, vários desafios deverão ser superados e, dentre eles, encontra-se o problema de transporte de empregados para operarem as plataformas offshore, distantes até 300km de distância da costa brasileira. Os problemas referentes ao deslocamento de empregados por meio de helicópteros são usualmente tratados como o Capacitated Helicopter Routing Problem (CHRP). Com base nas restrições de origem e de destino de cada cliente, no número de veículos e na capacidade e restrições de voo dos helicópteros, neste tipo de problema deseja-se minimizar os custos de aluguel de helicópteros mais o custo total de quilômetros voados. A presente dissertação propõe um modelo de Programação Linear Inteira Mista (PLIM) para o problema de roteirização de helicópteros com base no Dial-a-Ride Problem (DARP). Além do modelo apresentado, foram apresentados duas abordagens para a execução do modelo de forma exata: i) abordagem sem agrupamento, na qual as requisições que possuem origens iguais e destinos iguais são modeladas como requisições distintas e ii) abordagem com agrupamento, na qual requisições que possuem origens iguais e destinos iguais são aglutinados numa nova e única requisição. O modelo matemático foi executado no software CPLEX e os resultados mostraram que instâncias com até 25 requisições podem ser resolvidas pela abordagem com agrupamento / Oil is the main energy source of contemporary world; it is basic inputs of various economic sectors. With the discovery of Brazil pre-salt, there is an opportunity to become one of the largest oil producers. However, to achieve her own goals, Brazil must overcome several challenges, including the problem of transporting employees to operate offshore platforms 300km distant away from the Brazilian coast. Problems related to displacement of employees by helicopters are usually treated as Capacitated Helicopter Routing Problem (CHRP). Based on source and destination restrictions of each client, the number of vehicles, capacity and helicopter flight constraints, this type of problem proposes to minimize the cost of renting helicopters and the total cost of flown kilometers. This dissertation proposes a model of Mixed Integer Linear Programming (MILP) for the helicopters routing problem based on a Dial-a-Ride Problem (DARP). Besides the presented model, we presented two approaches to implementing the model in an exact way: i) non-clustered approach, in which requests that have the same origin and destination are equal modeled as separate requests; and ii) clustered approach, in which requests that have the same origins and destinations are clumped together in a new single request. The mathematical model was implemented in software CPLEX and results showed that instances with up to 25 requests can be resolved in the clustered approach

Cette thèse s’intéresse à trouver des solutions informatiques à certains problèmes de l’optimisation combinatoire, à savoir les problèmes de tournées de véhicules. Elle aborde les problèmes de Transport A la Demande (TAD). L’objectif principal visé dans cette thèse fait appel à certaines approches exactes et certaines approches méta-heuristiques pour résoudre des problèmes d’optimisation multi-objective de Transport A la Demande avec plusieurs véhicules. En effet, nos principaux objectifs de recherche consistent à : -I) Résoudre un problème multi-objectif de Transport A La Demande multi-véhicules basé sur la qualité de service ; - II) Résoudre un autre problème de Transport A la Demande multi-objectifs multi-véhicules. Ce problème traite un cas spécifique et qui consiste à l’application de ce problème aux domaines de l’Hospitalisation A Domicile (HAD). Nous avons appliqué des algorithmes exacts de "Branch and Bound" et des méthodes méta-heuristiques telles que l’algorithme évolutionnaire "Algorithme Génétique" et l’algorithme de "Colonie de Fourmis" pour apporter des solutions efficaces à ces différents problèmes. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes pour montrer leurs capacités de produire des solutions de haute qualité en temps de calcul raisonnables. / This thesis focuses on finding computer science solutions for some combinatorial optimization problems, namely Vehicle Routing Problems (VRP). The thesis addresses the Dial A Ride Problems (DARP). Its main objective is to use some exact and meta-heuristics approaches to solve multi-objective optimization of Dial A Ride Problem with multi-vehicles. Hence, our main research aims are : - I)Solve a multi-objective Dial A Ride Problem with multi-vehicles based on quality of service, this problem treats a general case ; - II) Solve another multi-objective Dial A Ride Problem with multi-vehicles, this problem deals with a specific case which is an application of the Dial A Ride Problem in Home Health Care (HHC). We have also applied exact algorithms "Branch and Bound" and meta-heuristic algorithms such as evolutionary algorithms "Genetic Algorithm" and "Ant Colony" algorithm to provide effective solutions to these different problems. A set of numerical results are presented for each of these methods. Our results show that they produce high quality solutions in a reasonable execution time for all the treated problems.