Les entreprises de transport et de distribution sont confrontées à des difficultés d’exploitation liées à la taille et à la complexité de leur processus de livraison. Dans cette problématique, nous proposons une approche globale du Problème Général de Livraison (PGL).Au niveau méthodologique, c’est une approche hiérarchique (stratégique, tactique, opérationnelle) et structurée. Il s’agit de concevoir et d’exploiter un PGL en le décomposant en problèmes de livraisons élémentaires identifiés et le plus possible indépendants les uns des autres (problèmes de transport, de hubs, d’agences, de tournées...).Au niveau algorithmique, des modèles et algorithmes de résolution ont été proposés pour résoudre ces problèmes élémentaires de livraison dans la phase opérationnelle en tenant compte, en particulier, du nombre et de la capacité limités des moyens de transport.Au niveau applicatif, deux exemples réels sont traités : le système de livraison d’une entreprise de Vente à Distance et le système de livraison des casernes de pompiers du Nord de la France à partir de la pharmacie centrale de Lille / Transport and delivery companies are confronted by difficulties in their transportation process due to the scale and the complexity of their distribution process. In this context, we propose a comprehensive approach to General Delivery Problem (GDP). In terms of methodology, it is a hierarchical (strategic, tactical and operational) and structured approach. It consists of designing and decomposing the GDP into well identified basic delivery problems as independent as possible. These basic transport problems involve the problems about transportation, intermediate facility, agencies, routings, etc. At the algorithm level, models and solution algorithms have been proposed to solve these basic delivery problems in the operational phase, taking account in particular transportation restriction about the number and capacity of vehicles.At the application level, two real examples are discussed: one is the delivery system of a delivery company; the other one is the delivery system of the Regional Fire and Emergency Center in the north of France

abstract: Optimization of on-demand transportation systems and ride-sharing services involves solving a class of complex vehicle routing problems with pickup and delivery with time windows (VRPPDTW). Previous research has made a number of important contributions to the challenging pickup and delivery problem along different formulation or solution approaches. However, there are a number of modeling and algorithmic challenges for a large-scale deployment of a vehicle routing and scheduling algorithm, especially for regional networks with various road capacity and traffic delay constraints on freeway bottlenecks and signal timing on urban streets. The main thrust of this research is constructing hyper-networks to implicitly impose complicated constraints of a vehicle routing problem (VRP) into the model within the network construction. This research introduces a new methodology based on hyper-networks to solve the very important vehicle routing problem for the case of generic ride-sharing problem. Then, the idea of hyper-networks is applied for (1) solving the pickup and delivery problem with synchronized transfers, (2) computing resource hyper-prisms for sustainable transportation planning in the field of time-geography, and (3) providing an integrated framework that fully captures the interactions between supply and demand dimensions of travel to model the implications of advanced technologies and mobility services on traveler behavior. / Dissertation/Thesis / Doctoral Dissertation Civil, Environmental and Sustainable Engineering 2018

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-06T17:59:08Z No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:08Z (GMT) No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:14Z (GMT) No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Made available in DSpace on 2016-10-20T13:51:20Z (GMT). No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) Previous issue date: 2016-03-21 / Não recebi financiamento / Vehicle routing problems occur in many practical situations where the pickup and/or delivery of goods is required. In this context, the present research aims to contribute to the study of logistic operations that arise in companies that deliver products on a regular basis to customers in densely populated urban areas. The problem consists in designing minimal cost daily routes serving the maximal number of customers. To this end, the crew of each vehicle comprise multiple deliverymen as means to reduce service times. Based on a case study in a drinks producer and distributor in the state of São Paulo, it is proposed a mixed integer linear programming model that comprise costs with own and chartered vehicles and the number of deliverymen, and various operational constraints such as time windows in customers, multiple daily trips, time limitations for the circulation of some vehicle types in specific areas, compatibility between vehicles and customers, maximum load in each vehicle, maximum route time and minimum load for the realization of a second trip. Results obtained by solving the model with real instances through exact (branch&cut), heuristic (constructive, local search, GRASP and Simulated Annealing) and hybrid (GRASP and branch&cut) approaches demonstrate the good quality of the generated solutions, and indicate the potential of application of some of these methods in practice. / Problemas de roteamento de veículos ocorrem em diversas situações práticas onde se faz necessária a distribuição e/ou coleta de produtos. Nesse contexto, a presente pesquisa visa o estudo das operações logísticas presentes em empresas que entregam produtos em base regular a clientes localizados em áreas urbanas de alta densidade demográfica. O problema consiste na obtenção de rotas de mínimo custo visando o atendimento do maior número de clientes da carteira diária. Para tal, a tripulação de cada veículo pode contemplar múltiplos entregadores para redução dos tempos de serviço. Com base em um estudo de caso em uma distribuidora de bebidas do interior do Estado de São Paulo, é proposto um modelo de programação linear inteira mista que considera custos com frota própria e fretada e com o número de entregadores, e diversas restrições operacionais, tais como janelas de tempo em clientes, múltiplas viagens diárias, limitações de horários de circulação de tipos de veículos, compatibilidade entre veículos e clientes, capacidade máxima de carga a ser transportada em cada veículo, tempo máximo de rota e carga mínima para realização da segunda viagem. Resultados da resolução do modelo para instâncias reais por meio de abordagens exatas (branch&cut), heurísticas (construtiva, busca local, GRASP e Simulated Annealing) e híbrida (GRASP e branch&cut), demonstram a boa qualidade das soluções geradas, e evidenciam o potencial de uso dessas metodologias na prática.

Made available in DSpace on 2016-06-02T19:50:25Z (GMT). No. of bitstreams: 1 6346.pdf: 5901404 bytes, checksum: 2d78b0f5f68ac25a089acd315f55b157 (MD5) Previous issue date: 2014-06-09 / The production of sugar, ethanol and electricity from sugar cane necessarily involves harvesting and transportation of raw materials, which are expensive and complex operations and have significant influence on the quality of the industrial raw material. The literature reports several optimization approaches related to the planning of planting, harvesting and transporting of sugarcane, however the scheduling of harvesting fronts is underexplored. This thesis intends to contribute to the state-of-art of this important issue in the context of the Brazilian agribusiness. Optimization approaches to support scheduling decisions of harvesting fronts considering the balance of harvesting and transportation capacities, as well as good agronomic management are proposed. The approaches are inspired by the representation of the problem as a lot sizing and scheduling model with parallel machines and sequence-dependent setup costs and times, a modelling technique well studied in the production planning and control literature. Three variants of this formulation, based on mathematical programming models, were developed and tested in two real case studies of medium size sugar mills. Heuristic methods based on aggregation procedures and mathematical programming have also been studied and developed to solve large scaled problems found in practice. Among the three variants studied, one presented the best solution quality within the expected execution time. Important scenario analysis were done indicating that the schedule s fulfilment provides reduction of harvesting and transporting complexity to the following season, which can generate significant saves in the cases studied. Besides that, comparing the proposed scheduling method with one of the sector s practice, it can be generated also significant cost reduction in the cases studied. The results were analyzed according to a validation methodology (descriptive facet of tetraedrum) well known in the literature. / A produção de açúcar, álcool e energia elétrica a partir de cana-de-açúcar passa necessariamente pela colheita e transporte da matéria-prima, que são operações custosas, complexas e que interferem significativamente na qualidade da matéria-prima industrial. A literatura reporta várias abordagens de otimização relacionadas ao planejamento do plantio, da colheita e do transporte de cana-de-açúcar, todavia a programação das frentes de colheita é pouco explorada. Nesta tese pretende-se contribuir para o estado da arte deste importante tema no contexto do agronegócio brasileiro. Propõe-se abordagens de otimização para apoiar decisões de programação das frentes de colheita, considerando-se o equilíbrio das capacidades de colheita e transporte, bem como um bom manejo agronômico. As abordagens são inspiradas na representação do problema por meio de um modelo de dimensionamento de lotes e sequenciamento da produção em máquinas paralelas com custos e tempos de setup dependentes da sequência, bem estudado na literatura em contextos de planejamento e controle da produção. Para isso foram desenvolvidas três variantes desta formulação baseadas em programação matemática, voltadas para a programação das frentes de colheita, que foram testadas em dois estudos de caso reais de usinas de cana-de-açúcar de médio porte do setor. Métodos heurísticos baseados em procedimentos de agregação e programação matemática também foram estudados e desenvolvidos para a resolução dos problemas de grande porte encontrados na prática. Das três variantes estudadas, uma delas apresentou melhor qualidade da solução dentro de tempos computacionais aceitáveis para o problema. Análises de cenário importantes foram feitas indicando que o cumprimento da programação proporciona redução de complexidade da colheita e transporte na safra seguinte, podendo gerar economias significativas nos casos estudados. Além disso, a comparação dos resultados das abordagens aqui exploradas com o que é praticado no setor indica um potencial de redução de custos também significativo para os casos estudados. Os resultados foram analisados de acordo com uma metodologia de validação (faceta descritiva do tetraedro) conhecida na literatura.

O tema de roteamento de veículos é de grande importância na literatura e tem sido amplamente estudada pela sua importância para muitas indústrias. Com a evolução na literatura, mais características foram adicionadas para torná-lo mais próximo de situações reais. Alinhado com esta tendência, este trabalho aborda o problema de roteamento de veículos quando há a terceirização da frota que realiza as entregas. Uma forma de cobrança do frete é por meio de custos escalonados, que são calculados de acordo com o tipo de veículo e a distância percorrida, com valores fixos para cada faixa de distância. Embora seja uma forma comum de trabalho na indústria, nenhum trabalho focado nesta característica foi encontrado na literatura. Este problema é o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados (FSMVRPTWSC). Ao abordar este problema, este trabalho apresenta um modelo de programação linear inteira mista que é avaliado em um cenário real da indústria. Além disso, três heurísticas de inserção sequencial são propostas para lidar com problemas maiores. Estes métodos são examinados por meio de testes computacionais em 168 problemas de referência gerados para este problema. Os experimentos numéricos mostram que os métodos são robustos e eficientes, apresentando um bom desempenho em conjuntos de problemas com diversas características. / The theme of vehicle routing is of great importance in the literature and has been widely studied for its relevance to many industries and, throughout the literature, more characteristics have been added to make it closer to real situations. Aligned with this trend, this paper addresses the vehicle routing problem when there is outsourcing of the fleet that delivers goods. One form of freight charging is by scaled costs, which are calculated according to the type of vehicle and the distance traveled, with fixed values for each distance range. Though it is a common form of work in the industry, no work focused on this characteristic was found in the literature. This problem is the fleet size and mix vehicle routing problem with time windows and scaled costs (FSMVRPTWSC). In approaching this problem, this paper presents a mixed integer linear programming model that is evaluated under a real situation scenario. Furthermore, three sequential insertion heuristics are proposed in order to deal with larger problems. These methods are examined through a computational comparative study in 168 benchmark problems generated for this problem. The numerical experiments show that the methods are robust and efficient, performing well in different problem sets.

Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2017-10-20T16:09:47Z No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-10-23T10:05:52Z (GMT) No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-10-23T10:05:52Z (GMT). No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-06-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Three different integer linear programming models for the Vehicle Routing Problem with Two-dimensional Loading Constraints are developed in this work. The version of the problem studied considers that the unloading of the rectangular items can respect or not the sequence of the clients visited on the route, that is, we solve the sequential and unrestricted versions of the problem. The first model deals with the problem completely, that is, with all constraints inserted at once. The second and third models are based, respectively, on a three- and two-index formulation. Separation routines are considered to detect violated inequalities related with packing on the second and third models, while the third model also considers cuts on connectivity and capacity. Computational experiments were carried out over instances of the literature with the quantity of customers ranging from 15 to 36 and items from 15 to 114, besides to consider the cases in which the cost of traversing an edge is integer and real. The models with cuts on demand were better in relation to the first model, besides being competitive when comparing with the results fromthe literature. The first model solved 4 of the 80 instances, the three-index model solved 7 and, the two-index model solved 53. On the sequential version, the adopted model solved 33 instances for the case with integer costs (and 37 for the case with real costs). In comparing with a recent heuristic from the literature, the best model was capable of tying in 48 instances in the unrestricted version and 24 in the sequential version. / Neste trabalho desenvolvem-se três modelos de programação linear inteira para o Problema de Roteamento de Veículos com Restrições de Empacotamento Bidimensional. A versão do problema estudado considera que o descarregamento dos itens retangulares pode respeitar (ou não) a sequência de clientes visitados na rota, ou seja, resolve-se as versões sequencial e irrestrita do problema. O primeiro modelo trata do problema de forma completa, isto é, com todas as restrições inseridas de uma só vez. O segundo e o terceiro modelo são baseados, respectivamente, em uma formulação de três e dois índices. Rotinas de separação são consideradas para detectar desigualdades violadas de empacotamento no segundo e no terceiro modelo, enquanto o último modelo considera também cortes de conectividade e capacidade. Experimentos computacionais foram realizados em instâncias da literatura com número de clientes variando de 15 a 36 e itens de 15 até 114, além de considerar os casos em que o custo da aresta é inteiro ou real. Os modelos com cortes sob demanda foram melhores em relação ao primeiro modelo, além de serem competitivos quando comparado com a literatura. O modelo completo encontrou a solução ótima em 4 das 80 instâncias, o modelo de três índices 7 e o modelo de dois índices 53. Na versão sequencial, o modelo adotado resolveu 33 instâncias para o custo inteiro (e 37 para o custo real). Na comparação com uma heurística recente da literatura, o melhor modelo conseguiu empatar em 48 instâncias na versão irrestrita e em 24 na versão sequencial.

The aim of this work is to show the application of operational research on an example that is put into practise and to show the usabillity of this science field. The problem solved will be the Vehicle routing problem with split delivery. The whole process of solving this issue is described in the text. From the income data and automatised data aquisition from publicly acessible resources for the distance matrix to the created mathemathical model for this issue together with the implementation in SW Lingo. Furthermore, in my work classic distribution problem of linear programming in connection to the solved issue are described. Beside that three mathematical models are shown that are occyupying with this type of delivery. They can not be used for fading the solution to this issue as they include certain requirements or conditions which are not taken into account by the given models.

This diploma thesis focuses on meta-heuristic algorithms and their ability to solve difficult optimization problems in polynomial time. The thesis describes different kinds of meta-heuristic algorithms such as genetic algorithm, particle swarm optimization or ant colony optimization. The implemented application was written in Java and contains ant colony optimization for capacitated vehicle routing problem and particle swarm optimization which finds the best possible parameters for ant colonies.

The following thesis deals with optimization of freight transport planning. The goal is to minimize expenses connected to transportation, which emerge from travelled distance. The expenses can be heavily reduced, if the routes are correctly planned, especially when there is a large number of customers to be served. This thesis focuses on solving the problem by using the evolutional algorithms, that are optimization methods based on principles of evolution. Thesis concentrates on Heterogeneous Fixed Fleet Vehicle Routing Problem. Thesis introduces multiple evolutional algorithms and their results are compared. The best algorithm, evolutional strategy with local neighbourhood search, achieves similar, for certain tasks even better results, than other existing evolutional algorithms, created to solve given problem.

Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten Erfolgsgeschichten des Operations Research. Das starke Interesse an diesen Problemen durch Industrie und Forschung liegt zum einen am wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet. In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur verwiesen.