[pt] Este trabalho apresenta uma aplicação prática do roteamento de navios com coleta-e-entrega e janelas de tempo para o alívio de plataformas de petróleos para exportação. Especificamente para este caso, os navios aliviadores fazem o transporte do petróleo de plataformas offshore diretamente para um terminal de transbordo, onde a carga será transferida para outro navio para ser exportado. Foram propostas adaptações a um modelo de programação linear inteira mista já existente, buscando descrever as peculiaridades deste processo e facilitar a sua resolução pelo método exato. O modelo foi testado com dados realísticos de uma empresa petrolífera e pode fornecer soluções de alta qualidade para testes com períodos de até 30 dias em um tempo de processamento computacional inferior a 10 minutos, estando assim adequado ao uso na rotina do programador de navios desta empresa. / [en] This study presents a practical application of ship routing with pickup-anddelivery and time windows for offloading operations in offshore oil platforms. Specifically in this case, the shuttle tankers transport crude oil from the offshore platforms directly to an onshore terminal, where the cargo will be transferred to another vessel to be exported. Adaptations to an existing mixed-integer linear programming model are proposed to better represent this process and facilitate its resolution by the exact method. The model was tested with realistic data from an oil and gas company and it can provide high-quality solutions for tests with periods up to 30 days, in a processing time of less than 10 minutes, thus being suitable for use in the routine of the company s ship programmer.

Throughout today’s society, increasingly more areas are being automated. Grocery stores however have been the same for years. Only recently, self-checkout counters and online shopping have been utilised in this business area. This thesis aims to take it to the next step by introducing automated grocery stores using a multi-agent system. Orders will be given to the system, and on a small area, multiple agents will pick the products in a time-efficient way and deliver them to the customer. This can both increase the throughput but also decrease the food waste and energy consumption of grocery stores. This thesis investigates already existing solutions for the multi-agent pickup and delivery problem. It extends these to the important case of batched tasks in order to improve the customer experience. Batches of tasks represent shopping carts, where fast completion of whole batches gives greater customer satisfaction. This notion is not mentioned in related work, where completion of single tasks is the main goal. Because of this, the existing solution does not accommodate the need of batches or the importance of completing whole batches fast and in somewhat linear order. For this purpose, a new metric called batch ordering weighted error (BOWE) was created that takes these factors into consideration. Using BOWE, one existing algorithm has been extended into prioritizing completing whole batches and is now called B-PIBT. This new algorithm has significantly improved BOWE and even batch service time for the algorithm in key cases and is now superior in comparison to the other state-of-the-art algorithms.

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

Le transport de matériaux pour la réalisation d’infrastructures routières et le terrassement représente, en 2013, plus de la moitié de l’activité du secteur des travaux publics. Les méthodes d’optimisation de tournées de véhicules permettent aujourd’hui de résoudre des problèmes de grandes tailles en intégrant les contraintes liées au métier. Dans cette thèse, nous nous intéressons à la résolution du problème riche de collectes et livraisons en camions complets avec des contraintes de synchronisation sur les ressources. Dans un premier temps, nous résolvons le problème de tournées de véhicules avec une méthode heuristique en deux phases. Dans un second temps, nous étudions l’intégration des contraintes liées aux temps de conduite des chauffeurs ainsi que l’ajout des pauses déjeuners aux tournées. Nous testons les algorithmes proposés sur des instances de la littérature et des instances réelles issues d’une application industrielle d’une entreprise de Travaux Publics. / In 2013, the transportation of materials for roads construction and earthwork represents more than half of the whole activity of in the public works sector. Optimization methods for vehicle routing problems allow to solve big-size problems with industrial sector constraints. In this thesis, we focus on solving the rich full truckload pickup and delivery problem with resource synchronization. First, we solve this vehicle routing problem with a two phase heuristic method. Then, we study the integration of regulation of drivers’ working hours and the addition of lunch breaks in routes of vehicles. These methods are tested on instances from the literature and real life instances from a public works company.

This dissertation considers daily operations management for a fleet of trucks providing container pickup and delivery service to a port. Truck congestion at access points for ports may lead to serious inefficiencies in drayage operations, and the resultant cost impact to the intermodal supply chain can be significant. Recognizing that port congestion is likely to continue to be a major problem for drayage operations given the growing volume of international containerized trade, this research seeks to develop optimization approaches for maximizing the productivity of drayage firms operating at congested seaports. Specifically, this dissertation addresses two daily drayage routing and scheduling problems. In the first half of this dissertation, we study the problem of managing a fleet of trucks providing container pickup and delivery service to a port facility that experiences different access wait times depending on the time of day. For this research, we assume that the wait time can be estimated by a deterministic function. We develop a time-constrained routing and scheduling model for the problem that incorporates the time-dependent congestion delay function. The model objective is to find routes and schedules for drayage vehicles with minimum total travel time, including the waiting time at the entry to the port due to congestion. We consider both exact and heuristic solution approaches for this difficult optimization problem. Finally, we use the framework to develop an understanding of the potential impact of congestion delays on drayage operations, and the value of planning with accurate delay information. In the second half of this dissertation, we study methods for managing a drayage fleet serving a port with an appointment-based access control system. Responding to growing access congestion and its resultant impacts, many U.S. port terminals have implemented appointment systems, but little is known about the impact of such systems on drayage productivity. To address this knowledge gap, we develop a drayage operations optimization approach based on a column generation integer programming heuristic that explicitly models a time-slot port access control system. The approach determines pickup and delivery sequences with minimum transportation cost. We use the framework to develop an understanding of the potential efficiency impacts of access appointment systems on drayage operations. Findings indicate that the set of feasible drayage tasks and the fleet size required to complete them can be quite sensitive to small changes in time-slot access capacities at the port.

This study focuses on two types of routing problems based on standard Traveling Salesman Problem, which are TSP with pickup and delivery (TSPPD) and TSP with backhauls (TSPB). In both of these problems, there are two types of customers, i.e. &ldquo / delivery customers&rdquo / demanding goods from depot and &ldquo / pickup customers&rdquo / sending goods to depot. The objective is to minimize the cost of the tour that visits every customer once without violating the side constraints. In TSPB, delivery customers should precede the pickup customers, whereas the vehicle capacity should not be exceeded in TSPPD. The aim of the study is to propose good Evolutionary Algorithms (EA) for these two problems and also analyze the adaptability of an EA, originally designed for the standard TSP, to the problems with side constraints. This effort includes commenting on the importance of feasibility of the solutions in the population with respect to these side constraints. Having this in mind, different EA strategies involving feasible or infeasible solutions are designed. These strategies are compared by quantitative experiments realized over a set of problem instances and the results are given.

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.

[pt] Em vários problemas de distribuição e logística, os produtos devem ser coletados em uma origem e entregues em um destino. Exemplos incluem o transporte de pessoas com deficiência, serviços de correio expresso, logística de suprimentos médicos, etc. O problema de roteamento abordado neste trabalho, conhecido como Traveling Salesman Problem with Pickup and Delivery (TSPPD), é da classe de problemas do caixeiro viajante com restrições de precedência. Neste problema, existe um mapeamento um-para-um entre coleta-entrega no qual cada cliente do tipo coleta possui um cliente do tipo entrega associado. Os clientes do tipo entrega somente podem ser visitados posteriormente à coleta associada. O TSPPD é um problema NP-difícil uma vez que generaliza o Traveling Salesman Problem (TSP). O TSP pode ser visto como um caso particular do TSPPD onde cada coleta coincide espacialmente com a respectiva entrega. As variantes com restrições de capacidade, janelas de tempo e diferentes políticas de carregamento têm recebido maior atenção na última década, embora ainda existam significantes avanços a serem realizados em termos de qualidades de soluções na versão básica do problema. Para resolver este problema, propomos um algoritmo meta-heurístico híbrido com vizinhanças largas exploradas eficientemente em O(n2). Nossos experimentos demonstram uma redução significativa no tempo computacional e também melhoria na qualidade de soluções previamente conhecidas na literatura. / [en] In various distribution and logistics issues, products must be collected at one source and delivered to a destination. Examples include disabled people transportation, express mail services, medical supplies logistics, etc. The routing problem addressed by this work, known as Traveling Salesman Problem with Pickup and Delivery (TSPPD), belongs to the class of traveling salesman problems with precedence constraints. In this problem, there is a one-to-one pickup-delivery mapping in which, for each pickuptype client, there is exactly one associated delivery-type client. Delivery clients can only be visited after the associated pickup. Since the TSPPD generalizes the TSP it is also a NP-hard problem, as the TSP is a particular casa of TSPPD where each pickup matches spatially with it s respective delivery. Variants with capacity constraints, time windows and different loading policies have received more attention in the last decade, although there are still significant advances to be made in terms of solution quality for the basic version of the problem. To solve this problem, we propose a hybrid metaheuristic algorithm with large neighborhoods efficiently explored in O(n2). Our experiments demonstrate a significant computational time reduction and also solutions quality improvement compared to the previous works.

La logistique collaborative est récemment devenue un élément important pour beaucoup d'entreprises afin d'améliorer l'efficacité de leur chaîne logistique. Dans cette thèse, nous étudions les possibilités offertes par les problèmes de collectes et livraisons pour améliorer les performances des chaînes logistiques grâce au transport collaboratif. La thèse est inscrite dans un projet européen nommé SCALE (Step Change in Agri-food Logistics Ecosystem). Dans un premier temps, deux métaheuristiques sont proposées et étudiées pour résoudre le problème de collectes et livraisons avec transbordements. Celles-ci sont comparées aux travaux de la littérature et permettent d’améliorer les résultats sur certaines instances. Dans un deuxième temps, un modèle pour un problème de collectes et livraisons (PDVRP) est proposé. Celui-ci est utilisé pour étudier les bénéfices de la collaboration sur le transport. Il est appliqué sur des données générées aléatoirement et sur des données réelles issues du projet SCALE. Enfin troisièmement, un modèle pour un PDVRP particulier est présenté. Dans ce modèle, les marchandises doivent passer par exactement deux points de transbordement entre les points de collecte et les points de livraison. Ce problème est inspiré d'une seconde étude de cas réalisée dans le cadre du projet SCALE. Ceci permet de mettre en évidence l’intérêt de la collaboration et du transbordement dans le domaine du transport de marchandises. / Collaborative logistics have become recently an important element for many companies to improve their supply chains efficiency. In this thesis, we study pickup and delivery problems to improve supply chains efficiency thanks to collaborative transportation. The thesis was part of the European project SCALE (Step Change in Agri-food Logistics Ecosystem). Firstly, two metaheuristics are proposed and studied to solve the Pickup and Delivery Problem with Transshipments. These metaheuristics are compared with literature works and the results of several instances are improved. Secondly, a mathematical model for a pickup and delivery problem (PDVRP) is proposed. This model is used to study the benefits of collaboration on transportation. It is applied on random data and on a case study from SCALE with real data. Finally, a model for a particular PDVRP is presented. In this model, the shipments have to cross exactly two transshipments nodes between their pickup and delivery points. This problem is inspired by a second case study made during the project SCALE. This allows to highlight the importance of collaboration and transshipment in the field of goods transportations.

Made available in DSpace on 2016-06-02T19:52:05Z (GMT). No. of bitstreams: 1 6045.pdf: 14667118 bytes, checksum: f13a2c0983ea271f2e60ed298b158806 (MD5) Previous issue date: 2014-05-26 / Agência Nacional de Petróleo / This work studies the ship routing and scheduling problem in oil transportation from offshore platforms to inland terminals. It is motivated by a real situation in a Brazilian oil company. Brazil is one of the world's greatest oil producers and has around 80% of its oil explored in offshore mode. Thus, transportation costs play an important role in achieving operational excellence, and the recent growth trends for oil exploration in Brazil has transformed its operations and demanded agile and effective decision support systems for addressing the oil sector dynamism. This work's goal consists in developing and applying an optimization-based approach using a mixed integer linear programming model in real decision-making situations, along with a solution method based on mathematical programming (MIP-heuristics) in order to solve the model, such as relax-and-fix. The proposed model is inspired in a problem formulation for pickup and delivery with time windows (PDPTW) and heterogeneous fleet, where costs incurred for fuel consumption and fleet contracts is the objective function to be minimized. The pickup and delivery pairs are predetermined and the model's main decision refers to ship allocation to these pairs compounding a route. Furthermore, some additional constraints are modeled and proposed, such as terminal access and platform mooring limitation according to ship types, as well as product blend incompatibility. The model was implemented in a modeling language along with an optimizarion software. Computational experiments with the model and the heuristics are presented for different data sets supplied by the case study company. These experiments show the potential benefits of this approach for finding good solutions for the problem as well as the dificulty in finding solutions for realistic instances due to its NP-hard characteristics. / Este trabalho estuda o problema de roteirização e programação de navios que realizam o escoamento de petróleo das plataformas marítimas para terminais terrestres, motivado por uma situação real de uma empresa brasileira da indústria petrolífera. O Brasil é um dos maiores produtores mundiais de petróleo, e cerca de 80% de seu petróleo é explorado no mar. Dentro deste contexto, os custos de transporte desempenham um papel importante na busca pela excelência operacional e as tendências de crescimento da exploração de petróleo no Brasil têm tornado as operações mais complexas e demandantes de sistemas de apoio à decisão ágeis e eficazes que contemplem o dinamismo do setor petrolífero. O objetivo deste trabalho consiste em desenvolver e aplicar uma abordagem de otimização baseada em um modelo de programação linear inteira mista em situações reais de tomada de decisão, em conjunto com métodos de solução baseados em programação matemática (MIP-Heuristics) para resolver o modelo, como relax-and-fix. O modelo proposto é inspirado em uma formulação de problemas de coleta e entrega com janelas de tempo (pickup and delivery with time windows PDPTW) e frota heterogênea, no qual busca-se minimizar os custos decorrentes do consumo de combustível dos navios e contratos de afretamento. O modelo é do tipo origem-destino, no qual os pares coleta/entrega são pré-determinados e a decisão do modelo refere-se à alocação de navios para os diferentes pares, compondo uma rota. Além disso, são propostas restrições adicionais que contemplam limitações de acesso a terminais e de atracação em plataformas de acordo com os tipos de navio, além da incompatibilidade de mistura de produtos, entre outros. O modelo foi implementado utilizando uma linguagem de modelagem em conjunto com um software de otimização. Experimentos computacionais com o modelo e as heurísticas são apresentados para diferentes conjuntos de dados fornecidos pela empresa e comprovam o potencial das abordagens para encontrar boas soluções para o problema, mas também suas dificuldades para encontrar soluções para exemplares de tamanho realista, por tratar-se de um problema NP-difícil do ponto de vista de teoria de complexidade.