Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-15T11:46:12Z No. of bitstreams: 1 arquivototal.pdf: 884446 bytes, checksum: 92314027dddef8365b4a2e655b65bd78 (MD5) / Made available in DSpace on 2017-08-15T11:46:13Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 884446 bytes, checksum: 92314027dddef8365b4a2e655b65bd78 (MD5) Previous issue date: 2016-05-20 / The Static Bike Rebalancing Problem (SBRP) is a recent problem motivated by the task of repositioning bikes among stations in a self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes (even all of them) from a station, thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This work deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to nd a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station should be appropriately determined in order to respect such constraints. This is a NP-Hard problem since it contains other NP-Hard problems as special cases, hence, using exact methods to solve it is intractable for larger instances. Several methods have been proposed by other authors, providing optimal values for small to medium sized instances, however, no work has consistently solved instances with more than 60 stations. The proposed algorithm to solve the problem is an iterated local search (ILS) based heuristic combined with a randomized variable neighborhood descent (RVND) as local search procedure. The algorithm was tested on 980 benchmark instances from the literature and the results obtained are quite competitive when compared to other existing methods. Moreover, the method was capable of nding most of the known optimal solutions and also of improving the results on a number of open instances. / O Problema do Rebalanceamento Est atico de Bicicletas (Static Bike Rebalancing Problem, SBRP) e um recente problema motivado pela tarefa de reposicionar bicicletas entre esta c~oes em um sistema self-service de compartilhamento de bicicletas. Este problema pode ser visto como uma variante do problema de roteamento de ve culos com coleta e entrega de um unico tipo de produto, onde realizar m ultiplas visitas a cada esta c~ao e permitido, isto e, a demanda da esta c~ao pode ser fracionada. Al em disso, um ve culo pode descarregar sua carga temporariamente em uma esta c~ao, deixando-a em excesso, ou, de maneira an aloga, coletar mais bicicletas (at e mesmo todas elas) de uma esta c~ao, deixando-a em falta. Em ambos os casos s~ao necess arias visitas adicionais para satisfazer as demandas reais de cada esta c~ao. Este trabalho lida com um caso particular do SBRP, em que apenas um ve culo est a dispon vel e o objetivo e encontrar uma rota de custo m nimo que satisfa ca as demandas de todas as esta c~oes e n~ao viole os limites de carga m nimo (zero) e m aximo (capacidade do ve culo) durante a rota. Portanto, o n umero de bicicletas a serem coletadas ou entregues em cada esta c~ao deve ser determinado apropriadamente a respeitar tais restri c~oes. Trata-se de um problema NP-Dif cil uma vez que cont em outros problemas NP-Dif cil como casos particulares, logo, o uso de m etodos exatos para resolv^e-lo e intrat avel para inst^ancias maiores. Diversos m etodos foram propostos por outros autores, fornecendo valores otimos para inst^ancias pequenas e m edias, no entanto, nenhum trabalho resolveu de maneira consistente inst^ancias com mais de 60 esta c~oes. O algoritmo proposto para resolver o problema e baseado na metaheur stica Iterated Local Search (ILS) combinada com o procedimento de busca local variable neighborhood descent com ordena c~ao aleat oria (randomized variable neighborhood descent, RVND). O algoritmo foi testado em 980 inst^ancias de refer^encia na literatura e os resultados obtidos s~ao bastante competitivos quando comparados com outros m etodos existentes. Al em disso, o m etodo foi capaz de encontrar a maioria das solu c~oes otimas conhecidas e tamb em melhorar os resultados de inst^ancias abertas.

A concern of logistics management is the correct and efficient use of the available fleet. The central focus of fleet management is determining the routes that will be used in customer service and the efficient allocation of available resources (vehicles). The correct fleet management can generate a competitive advantage. There is a problem in the Operations Research dedicated to working this type of situation, the Vehicle Routing Problem (VRP). The VRP tries to generate the most economical route to efficient use of the available fleet. The case study discussed in this work was a particular situation VRP where there is a heterogeneous fleet and where the collections and deliveries of passengers are carried at separate times. To solve this problem we designed a Genetic Algorithm. Additionally, three different crossover operators were tested in the search for better results. At the end of the study, the Genetic Algorithm was capable of solving the problem in a short time and finding the most economical way to generate routes, using efficiently the fleet and fulfilling all requests. / Uma das preocupaÃÃes da gestÃo logÃstica à a correta e eficiente utilizaÃÃo da frota disponÃvel. O foco central da gestÃo da frota està em determinar as rotas que serÃo utilizadas no atendimento aos clientes e a alocaÃÃo eficiente dos recursos (veÃculos) disponÃveis. A gestÃo correta da frota pode gerar um diferencial competitivo. Existe na Pesquisa Operacional um problema dedicado a trabalhar este tipo de situaÃÃo, denominado Problema de Roteamento de VeÃculos (PRV). O PRV procura gerar a rota mais econÃmica com utilizaÃÃo eficiente da frota disponÃvel. No estudo de caso, realizado neste trabalho, foi abordada uma situaÃÃo particular do PRV onde hà uma frota heterogÃnea e as coletas e entregas de passageiros sÃo realizadas em momentos separados. Para a resoluÃÃo deste problema foi desenvolvido e implementado um Algoritmo GenÃtico (AG). Adicionalmente, trÃs operadores de cruzamento diferentes foram testados na busca dos melhores resultados encontrados pelo AG. Ao final, o Algoritmo GenÃtico conseguiu se mostrar capaz de resolver o problema em tempo hÃbil e de maneira a gerar rotas mais econÃmicas, utilizando eficientemente a frota e atendendo todas as solicitaÃÃes.

Diplomová práce se zabývá analýzou a výpočtem optimalizační úlohy z praxe. Jedná se o optimalizaci nočních linek vnitrostátní přepravy na území ČR. Cílem je nalezení řešení, které zefektivní organizaci těchto linek a usnadní práci lidí s nimi spojenou. Celý výpočet úlohy je inspirován okružním problémem s doručením a vyzvednutím (?Pickup and Delivery Problem?). Na výpočet problému jsou použity dva modely: model založený na hledání optimálního více produktového toku a model spočívající na výběru tras. Modely jsou založeny na rozdílných přístupech. Díky oběma modelům je možné si uvědomit, že na jednu optimalizační úlohu lze pohlížet z více stran a z obdržených výsledků si pak vytvořit ucelenější pohled na problém.

<p>Online retail sales and grocery/food orders have been breaking records every year. As a result, third-party delivery companies have found an opportunity to get their share from the growing transportation network. Electric vehicles (EVs) are becoming a preferable choice for such large delivery systems due to their environmental benefits. However, EVs have limited-service ranges; therefore, intra-route facilities are needed for EVs to stay operational. These facilities offer charging stations for EVs and storage areas for requests, e.g., food and packages. In this dissertation, we propose a novel <em>Pickup and Delivery Problem</em> (PDP) with EVs and transfers. There are requests to be picked up and delivered. EVs leave their origin depot, serve requests, and return to their destination depot. Unlike the generic PDP, intra-route facilities allow EVs to exchange requests. Thus, a request can be transported by more than one vehicle. In this dissertation, three new problems are introduced, and the following research questions are investigated: 1) "How valuable is to include intra-route facilities and allow transfers in a pickup and delivery network with EVs?", 2) "What is the cost of locating intra-route facilities randomly rather than finding the best locations while creating the routes for EVs?", and 3) "How much can drones improve the delivery speed in a pickup and delivery network with EVs and transfers?". A <em>Mixed-integer Linear Programming</em> (MILP) model and a <em>Simulated Annealing</em> (SA) algorithm are developed and compared with each other to answer the first question. For the second question, a MILP model is formulated; however, due to unreasonable computational runtimes, a SA algorithm and an <em>Adaptive Large Neighborhood Search</em> (ALNS) algorithm are proposed. Finally, a MILP model is developed for the hybrid-fleet problem. The overall results highlight that intra-route facilities shorten the total traveled distance in the PDP network by allowing exchanges and recharging.</p>

Dans ce mémoire, nous présentons un nouveau type de problème de confection de tour- née pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement. Cette variante est motivée par des problèmes similaires rapportés dans la littérature. Le véhi- cule en question contient plusieurs piles où des colis de hauteurs différentes sont empilés durant leur transport. La hauteur totale des items contenus dans chacune des piles ne peut dépasser une certaine hauteur maximale. Aucun déplacement n’est permis lors de la li- vraison d’un colis, ce qui signifie que le colis doit être sur le dessus d’une pile au moment d’être livré. De plus, tout colis i ramassé avant un colis j et contenu dans la même pile doit être livré après j. Une heuristique à grand voisinage, basé sur des travaux récents dans le domaine, est proposée comme méthode de résolution. Des résultats numériques sont rapportés pour plusieurs instances classiques ainsi que pour de nouvelles instances. / In this work, we consider a new type of pickup and delivery routing problem with last- in-first-out loading constraints for a single vehicle with multiple stacks. This problem is motivated by similar problems reported in the literature. In the problem considered, items are collected and put on top of one of multiple stacks inside the vehicle, such that the total height of the items on each stack does not exceed a given threshold. The loading constraints state that if items i and j are in the same stack and item i is collected before item j, then i must be delivered after j. Furthermore, an item can be delivered only if it is on the top of a stack. An adaptive large neighborhood heuristic, based on recent studies in this field, is proposed to solve the problem. Numerical results are reported on many classical instances reported in the literature and also on some new ones.

Dans cette thèse, nous nous intéressons à la gestion des flux de marchandises en zone urbaine aussi appelée logistique du dernier kilomètre, et associée à divers enjeux d’actualité : économique, environnemental, et sociétal. Quatre principaux acteurs sont concernés par ces enjeux : chargeurs, clients, transporteurs et collectivités, ayant chacun des priorités différentes (amélioration de la qualité de service, minimisation de la distance parcourue, réduction des émissions de gaz à effet de serre, …). Face à ces défis dans la ville, un levier d’action possible consiste à optimiser les tournées effectuées pour la livraison et/ou la collecte des marchandises. Trois types de flux urbains sont considérés : en provenance ou à destination de la ville, et intra-urbains. Pour les flux sortants et entrants dans la ville, les marchandises sont d’abord regroupées dans un entrepôt situé en périphérie urbaine. S’il existe plusieurs entrepôts, le problème de planification associé est de type Location Routing Problem (LRP). Nous en étudions une de ses variantes appelée Capacitated Location Routing Problem (CLRP). Dans cette dernière, en respectant la contrainte de capacité imposée sur les véhicules et les dépôts, la localisation des dépôts et la planification des tournées sont considérées en même temps. L’objectif est de minimiser le coût total qui est constitué du coût d’ouverture des dépôts, du coût d’utilisation des véhicules, et du coût de la distance parcourue. Pour tous les flux, nous cherchons également à résoudre un problème de tournées de type Pickup and Delivery Problem (PDP), dans lequel une flotte de véhicules effectue simultanément des opérations de collecte et de livraison. Nous nous sommes focalisés sur deux de ses variantes : la variante sélective où toutes les demandes ne sont pas toujours satisfaites, dans un contexte de demandes appairées et de sites contraints par des horaires d’ouverture et fermeture (Selective Pickup and Delivery Problem with Time Windows and Paired Demands, ou SPDPTWPD). La seconde variante étudiée est l’extension de la première en ajoutant la possibilité d’effectuer les transports en plusieurs étapes par l’introduction d’opérations d’échanges des marchandises entre véhicules en des sites de transfert (Selective Pickup and Delivery with Transfers ou SPDPT). Les objectifs considérés pour ces deux variantes de PDP sont de maximiser le profit et de minimiser la distance. Chaque problème étudié fait l’objet d’une description formelle, d’une modélisation mathématique sous forme de programme linéaire, puis d’une résolution par des méthodes exactes, heuristiques et/ou métaheuristiques. En particulier nous avons développé des algorithmes basés sur une métaheuristique appelée Particle Swarm Optimization, que nous avons hybridée avec de la recherche locale. Les approches sont validées sur des instances de différentes tailles issues de la littérature et/ou que nous avons générées. Les résultats sont analysés de façon critique pour mettre en évidence les avantages et inconvénients de chaque méthode. / In this thesis, we are interested in the management of goods flows in urban areas, also called last mile logistics, and associated with various current issues: economic, environmental, and societal. Four main stakeholders are involved by these challenges: shippers, customers, carriers and local authorities, each with different priorities (improving service quality, minimizing the travelling distance, reducing greenhouse gas emissions, etc.). Faced with these challenges in the city, one possible action lever is to optimize the routes for the pickup and/or delivery of goods. Three types of urban flows are considered: from or to the city, and intra-urban. For outgoing and incoming flows into the city, the goods are first grouped in a warehouse located on the suburban area of the city. If there are several warehouses, the associated planning problem is the Location Routing Problem (LRP). We are studying one of its variants called the Capacitated Location Routing Problem (CLRP). In this problem, by respecting the capacity constraint on vehicles and depots, the location of depots and route planning are considered at the same time. The objective is to minimize the total cost, which consists of the cost of opening depots, the cost of using vehicles, and the cost of the travelling distance. For all flows, we are also looking to solve a Pickup and Delivery Problem (PDP), in which a fleet of vehicles simultaneously carries out pickup and delivery operations. We focus on two of its variants: the selective variant where not all requests are satisfied, in a context of paired demands and time windows on sites (Selective Pickup and Delivery Problem with Time Windows and Paired Demands, or SPDPTWPD). The second studied variant is the extension of the first one by adding the possibility of carrying out transport in several stages by introducing operations for the exchange of goods between vehicles at transfer sites (Selective Pickup and Delivery with Transfers or SPDPT). The considered objectives for these two variants of PDP are to maximize profit and to minimize distance. Each studied problem is formally described, mathematically modelled as a linear program and then solved by exact, heuristic and/or metaheuristic methods. In particular, we have developed algorithms based on a metaheuristic called Particle Swarm Optimization, which we have hybridized with local search operators. The approaches are validated on instances of different sizes from the literature and/or on instances that we have generated. The results are critically analyzed to highlight the advantages and drawbacks of each method.

La présente thèse se déroule dans le cadre du projet ANR PRODIGE et est axée sur la recherche de stratégies permettant l’optimisation du transport en général et du transport routier de marchandises en particulier. Le problème de transport support de cette étude est le problème de collecte et livraison avec transbordement. Ce problème généralise plusieurs problèmes de transports classiques. Le transbordement y est utilisé comme levier de flexibilité et d’optimisation. Pour analyser et résoudre ce problème, les analyses sont effectuées suivant trois axes : le premier axe concerne l’élaboration d’un modèle analytique plus précisément d’un modèle mathématique en variables mixtes. Ce modèle permet de fournir dessolutions optimales au décisionnaire du transport mais présente l’inconvénient de nécessiter un temps de résolution qui croit exponentiellement avec la taille du problème. Cette limitation est levée par le deuxième axe d’étude qui permet de résoudre le problème de transport étudié par une méthode d’optimisation approchée tout en garantissant des solutions satisfaisantes.La méthode utilisée est une métaheuristique inspirée de la recherche à voisinages variables (VNS). Dans le troisième axe, l’ensemble des résultats obtenus dans la thèse sont testés en situation de transports réels via le projet PRODIGE. / The thesis is conducted under the ANR project PRODIGE and it is focused on seeking strategies allowing the optimization of transport in general and road freight transport in particular. The transportation problem support for this study is the pickup and delivery problem with transshipment.This problem generalizes several classical transportation problems.Transshipment is used as optimization and flexibility leverage. To study and solve this problem, analyzes are performed along three axes :the first objective concerns the development of an analytical model, more accurately a mathematical model with mixed variables. This model allows providing optimal solution to the decision maker, but has the disadvantage of requiring a time resolution that grows exponentially with the size of the problem. This limitation is overcome by the second line of the study that solves the transportation problem studied by an approximate optimization method while ensuring satisfactory solutions. The method used is a mataheuristic broadly followed the variables neighborhoods research principles. In the third objective, the overall results obtained in the thesis are tested in real transport situation via the PRODIGE project.

Dans ce mémoire, nous présentons un nouveau type de problème de confection de tour- née pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement. Cette variante est motivée par des problèmes similaires rapportés dans la littérature. Le véhi- cule en question contient plusieurs piles où des colis de hauteurs différentes sont empilés durant leur transport. La hauteur totale des items contenus dans chacune des piles ne peut dépasser une certaine hauteur maximale. Aucun déplacement n’est permis lors de la li- vraison d’un colis, ce qui signifie que le colis doit être sur le dessus d’une pile au moment d’être livré. De plus, tout colis i ramassé avant un colis j et contenu dans la même pile doit être livré après j. Une heuristique à grand voisinage, basé sur des travaux récents dans le domaine, est proposée comme méthode de résolution. Des résultats numériques sont rapportés pour plusieurs instances classiques ainsi que pour de nouvelles instances. / In this work, we consider a new type of pickup and delivery routing problem with last- in-first-out loading constraints for a single vehicle with multiple stacks. This problem is motivated by similar problems reported in the literature. In the problem considered, items are collected and put on top of one of multiple stacks inside the vehicle, such that the total height of the items on each stack does not exceed a given threshold. The loading constraints state that if items i and j are in the same stack and item i is collected before item j, then i must be delivered after j. Furthermore, an item can be delivered only if it is on the top of a stack. An adaptive large neighborhood heuristic, based on recent studies in this field, is proposed to solve the problem. Numerical results are reported on many classical instances reported in the literature and also on some new ones.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-01-24T10:38:55Z No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:50:29Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:51:23Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Made available in DSpace on 2017-02-08T10:51:33Z (GMT). No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) Previous issue date: 2016-04-01 / Outra / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / The object of this study is the routing and scheduling problem of vessels with pickup and delivery and time windows in the oil industry. A case study was performed in a Brazilian oil industry that produces crude oil in o shore platforms, that is, located in the ocean, and transports to the terminals located in the Brazilian coast. Then, it was proposed a mixed integer model to represent the problem adequately and for this, a detailed analysis of the real problem in order to know all its characteristics and consider some simplifying assumptions. Therefore, to the pickup and delivery problem with time windows present in the literature were aggregated other speci c restrictions of the case study, for example, multiple depots, ship mooring restrictions, exible draft and dynamic positioning. Besides that, the eet is heterogeneous related to capacity, LOA (length overall), dynamic positioning and velocity. In practice, in general there are no identical vessels. This problem can be represented as a combinatorial optimization model, which belongs to the NP-hard class and its solution is a challenging in practice depending on the size of the real problems. Then, were proposed several exact branch-and-cut methods based on models with 2 and 3-index variables for routing problems with pickup and delivery and time windows to solve speci cally the Brazilian oil industry problem. Finally, we proposed a branch-and-price method, which includes all characteristics of the problem in oil industry. In summary, the main contributions of this thesis are related to the study and modeling of this problem in practice, and the proposal and development of exact solution methods to solve it, based on branch-and-cut and branch-and-price. The performance of the mathematical model in optimization software and the exact methods were veri ed using a real data set provided by the company. Results show that these approaches may be e ective to solve problems of moderate size in real situations. / O objeto de estudo deste trabalho é o problema de roteamento e programação de navios com coleta e entrega e janelas de tempo na indústria petrolífera. Foi realizado um estudo de caso com uma empresa petrolífera brasileira que produz óleo cru em plataformas o shore, isto é, localizadas no oceano e os transporta até os terminais localizados na costa brasileira. Então, foi proposto um modelo de programação inteira mista para representar o problema adequadamente e para isso, foi necessária uma análise detalhada do problema real, com o intuito de conhecer todas as suas características e considerar hipóteses simpli cadoras. Desta maneira, ao problema de coleta e entrega e janelas de tempo da literatura foram agregadas outras restrições especí cas do problema do estudo de caso como, por exemplo, múltiplos depósitos, restrições de atracação dos navios, calado exível e posicionamento dinâmico. Além disso, a frota de navios é heterogênea em relação à capacidade, LOA (length overall ), posicionamento dinâmico e velocidade. Na prática, em geral não existem navios iguais. Este problema pode ser representado como um modelo de otimização combinatória que pertence à classe NP-difícil e sua solução é bastante desa adora na prática em função do tamanho dos problemas reais. Depois, foram propostos vários métodos do tipo branch-and-cut baseados em modelos com variáveis de 2 e 3-índices para problemas de roteamento com coleta e entrega e janelas de tempo para resolver especi camente o problema da empresa brasileira. E por m, foi proposto um método do tipo branch-and-price, o qual abrange todas as características do problema da indústria petrolífera. Em síntese, as principais contribuições desta tese referem-se ao estudo e modelagem deste problema na prática, e a proposta e desenvolvimento de métodos de solução exatos para resolvê-lo, baseados em branch-and-cut e branch-and-price. O desempenho do modelo matemático em softwares de otimização e também dos métodos exatos propostos foi veri cado usando-se exemplares reais fornecidos pela empresa. Os resultados mostram que essas abordagens podem ser efetivas para resolver problemas de tamanho moderado em situações reais.

No description available.