Truck-based freight transportation continues to play a vital role in the delivery of goods in the United States. Despite its size and importance, the truck transportation industry continues to struggle with fulfilling transportation requests in an efficient and sustainable manner. One potential solution to alleviate many of the current truck industry problems is for transportation service providers (TSPs) to collaborate by sharing volume, resources, and facilities. This research introduces the Transportation Service Provider Collaboration Problem (TSP-CP) to demonstrate the benefits of using optimal freight routing and consolidation decisions for collaborating TSPs. A mathematical model for the TSP-CP is introduced to describe the problem in detail. Additionally, two separate adaptive large neighborhood search (ALNS) heuristics are developed to provide solutions to industry representative problem instances. Finally, the benefits and insights achieved by enabling collaboration between TSPs using the TSP-CP are identified using industry representative data sets. The representative data sets were derived from actual freight data provided by a freight pooling company that manages collaboration among TSPs. Carriers were chosen from the industry data to evaluate collaborative partnerships and to gain insights on the effects of partnership characteristics on overall benefit as well as the benefits obtained by individual carriers. The computational results suggested collaboration among TSPs offers the potential for substantial reductions in the total distance required to deliver all loads, in the number miles that were traveled completely empty, and the number of containers required for delivery compared to individual performance. Additionally, collaboration increased delivery resource capacity utilization as measured by the percentage of weighted full miles. Detailed analysis of the results from the TSP-CP revealed new insights into the collaboration between full truckload and less-than truckload carriers that have not been quantified or highlighted in previous research. These insights included the effect that an individual carrier's type and size had on the amount of benefit received to each carrier. Finally, the results highlighted the importance of building collaborative partnerships that consider a carrier's geographic location. / Ph. D. / Truck-based freight transportation continues to play a vital role in the delivery of goods in the United States by carrying nearly 70% of all freight tonnage. Despite its size and importance, the truck industry continues to struggle with transporting freight in an efficient, timely, and sustainable manner. One potential solution to alleviate many of the current truck industry problems is for transportation service providers (TSP) to collaborate by sharing resources, facilities, and freight volume. This research introduces the Transportation Service Provider Collaboration Problem (TSP-CP) to demonstrate the benefits of using optimal freight routing and consolidation decisions for collaborating TSPs. The benefits and insights achieved by enabling collaboration between TSPs using the TSPCP are identified using industry representative data sets. The representative data sets were derived from actual freight data provided by a freight pooling company that manages collaboration among TSPs. The computational results suggested collaboration among TSPs offers the potential for substantial reductions in the total distance required to deliver all freight, in the number of miles that were traveled by containers completely empty, and in the number of containers required for delivery compared to individual performance. Additionally, collaboration increased delivery resource capacity utilization. Detailed analysis of the results from the TSP-CP also revealed new insights into TSP collaboration. These insights included the effect that an individual carrier’s type and size had on the amount of benefit received to each carrier. Finally, the results highlighted the importance of building collaborative partnerships that consider a TSP’s geographic location.

We consider the daily transportation problem in forestry which arises when transporting logs from forest sites to customers such as sawmills and pulp and paper mills. Each customer requires a specific amount of a certain assortment, and the deliveries to the customers can be made within time intervals, known as time windows. Further, there are a number of supply points, each with a certain assortment, and a number of vehicles of a given capacity, to be used for transport. The log truck scheduling problem consists of finding a set of minimal costs routes, one for each vehicle, such that the customers’ demands are satisfied without exceeding the supplies available at the supplies. Each route has to satisfy a number of constraints concerning time windows, truck capacity, timetable of the driver, lunch breaks, et cetera. The model used to describe the log truck scheduling problem is based on the route concept, and each variable, or column, represents one feasible route. Since the number of feasible routes is huge, we work only with restricted versions of this problem, which are similar to restricted master problems in a Dantzig-Wolfe decomposition scheme. We use three solution methods based on the column generation principle, together with a pool strategy which allows us to deal with the feasible routes outside the restricted master problem. The three methods proposed have a common structure; they use branch-andprice together with a column generator, followed by branch-and-bound. The column generators in the three methods differ. In the first method, the subproblem is based on a cluster-first-route-second strategy. The column generator in the second method involves solving a constrained shortest path problem, and finally, the third method builds on a repeated generation of clusters and routes. The three methods are tested on real cases from Swedish forestry companies, and the third method has been adapted to a computerised system that utilises the Swedish national road data base, for computing travelling distances. The results obtained show that the optimisation methods succeed in finding significantly better solutions than those obtained by manual planning, and in a reasonable computing time.

This dissertation details an algorithm to solve the Intratheater Airlift Operations Problem (IAOP) using advanced tabu search. A solution to the IAOP determines the routes and assignment of customer requests to a fleet of aircraft over a given time horizon. This problem and other variants comprise an ongoing challenge for United States Air Force (USAF) planners who manage detailed logistics throughout many theaters of operations. Attributes of the IAOP include cargo time windows, multiple cargo types, multiple vehicle cargo bay configurations, vehicle capacity, route duration limits, and port capacities. The IAOP multi-criteria objective embraces several components with the primary goal of satisfying as much of the demand as possible while minimizing cost. The algorithm is extended to allow split load deliveries of customer requests, allowing a shipment to be split into two or more sub-loads which are delivered separately to the customer. The split load relaxation, while significantly increasing the complexity of the problem, allows for possible improvement in the solution. The necessary changes to the model and algorithm are detailed, providing a foundation to extend any local search algorithm solving a vehicle routing problem to allow split loading. Results allowing split loading are presented and compared with results without split loading. The algorithm is also extended to include a rolling time horizon. Starting from a solution found at a previous time step, the algorithm is limited on how the solution can be modified. This reflects the reality of operations in which near-term plans are locked as they approach and enter execution while longer-term plans are continually updated as new information arrives. / text

Dans le cadre de cette thèse, nous nous intéressons au traitement des problèmes d’optimisation combinatoire liés à la conception d’outils de gestion des systèmes de véhicules partagés. Ces problèmes sont proches des problèmes de collecte et de livraison. Après avoir réalisé une étude théorique sur des problèmes d’optimisation combinatoire autour du transport et des méthodes de résolutions, nous nous sommes intéressés ici à trois problèmes particuliers : le PPRV, le PPRV-PM et le PPRV-T. Le premier problème est le Problème de Planification du Redéploiement de Véhicules partagés (PPRV). C’est une extension du One-commodity Pickup-and-Delivery Problem (1-PDP) car les véhicules partagés sont indifférenciés. Nous avons proposé un modèle linéaire et une heuristique utilisant le schéma hybride ILS/VND. L’approche développée repose sur la stratégie « route-first, cluster-second » : on commence par construire une tournée géante, puis on l’améliore par une procédure de perturbation et une recherche locale. Pendant la recherche locale, la contrainte de capacité des véhicules est momentanément relaxée et progressivement restaurée ; la tournée géante obtenue est ensuite transformée en plusieurs tournées à l’aide de la procédure Split. Les deux problèmes suivants sont considérés comme des extensions du PPRV en autorisant des livraisons partielles : PPRV avec Passage Multiple (PPRV-PM) et PPRV avec Transfert d’objets (PPRV-T). Nous proposons une approche de type « divide-first, route-second » pour la résolution du PPRV-PM. Elle consiste à effectuer d’abord un fractionnement de la demande, puis la résoudre à l’aide d’un schéma hybride de type GRASP/VND. Le PPRV-T étend le PPRV-PM au transfert d’objets entre les transporteurs lors du passage sur un sommet. Nous avons reformulé le PPRV-T comme un problème de multi-flots couplés sur un réseau dynamique. Nous avons proposé une méthode d’insertion basée sur cette modélisation. / In this thesis, we are interested to deal with combinatorial optimization problems related to design management tools for vehicle-sharing systems. These problems are close to the Pickup-and-Delivery Problems (PDP) in the literature. After performing a survey on the problems area and on the resolution methods, we focused on three specific problems and we proposed one approach for each problem. The first one is the sharing Vehicles Redeployment Planning Problem (VRPP), which is considered as a multi-vehicles extension of the One-commodity Pickup-and-Delivery Problem (1-PDP). We proposed a linear model and a hybrid heuristic which combines the ILS and VND. The proposed approach uses the rout-first, cluster-second strategy: we construct a Hamiltonian route, and then improve it using a procedure combines a shacking step and a VND local search. The used neighborhoods are adapted to the relaxation of capacity; the obtained route would be then split into several vehicles tours in the clustering phase.The two following problems are considered as extensions of VRPP introducing the split demand constraint : VRPP with Multi-Passage (VRPP-MP) and VRPP with Transferring objects (VRPP-T). We proposed an approach with the divide-first, route-second strategy for VRPP-MP. It consists of dividing in advance the demand, and then solves it using a hybrid scheme of GRASP/VND. In the VRPP-T, the objects carried could be exchanged between carriers when crossing on the sites. The VRPP-T is modeled here as a multi-flows problem on a dynamic network. We proposed an insertion method based on this modeling.

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T12:38:24Z (GMT). No. of bitstreams: 1 Goraieb_Elias_M.pdf: 21259035 bytes, checksum: 5e5d4e69c800350a20727695a2f33647 (MD5) Previous issue date: 2005 / Resumo: Este trabalho aborda o problema de roteamento de veículos com coleta e entrega, visando à minimização do número de veículos utilizado e a distância total percorrida. O pedido de serviço é atendido por um veículo na janela de tempo imposta pelo cliente, e envolve uma coleta na origem que precede a entrega no destino. A capacidade dos veículos é limitada e uma rota tem duração máxima. Um algoritmo de busca tabu é proposto para a resolução deste problema. Diversas estratégias avançadas são incorporadas ao algoritmo, tais como redução de vizinhança, diversificação da busca, e utilização da metodologia path relinking / Abstract: This work considers the vehicle routing problem with pickup and delivery with the objectives of minimizing the fleet size and the total traveI distance. Each service request is served by a vehicle within time windows imposed by the clients, and involves a pickup origin that precedes a delivery destination. The capacity of the vehicle and the total route duration are limited. A tabu search algorithm is proposed to solve this problem. Several advanced strategies are incorporated in the algorithm, such as neighborhood reduction, search diversification, and path relinking / Mestrado / Engenharia de Sistemas / Mestre em Engenharia Elétrica

The following work concerns the study of the evolutionary algorithm, which optimizes freight transport planning. The demand for freight transport is constantly increasing nowadays and with creating, implementing and using proper route planning we are able to significantly reduce transportation costs. However, it is preferably to implement it in companies with large numbers of served customers and with a sufficiently large fleet of vehicles.   The study starts by defining what fright transport planning problem is and by characterizing its existing specifications and variants. My work proceeds to give a background of the possible solutions to the multifaceted aspects of the problem. The specific subproblem I choose to focus on is the Vehicle routing problem with Pickup and Delivery for which I apply the optimization solution. In the main body of my thesis, I will elaborate on the chosen optimization solution which encompasses the genetic algorithm and evolutionary strategy. The aim of the study is to measure the suitability of the algorithms and techniques used, for which reason the final part of my work will deal with the analysis and evaluation of the experiments.

Résumé indisponible. / The VIPAFLEET project aims at developing a framework to manage a fleet of IndividualPublic Autonomous Vehicles (VIPA). We consider a fleet of cars distributed at specifiedstations in an industrial area to supply internal transportation, where the cars can beused in different modes of circulation (tram mode, elevator mode, taxi mode). The goalis to develop and implement suitable algorithms for each mode in order to satisfy all therequests either under an economic point aspect or under a quality of service aspect, thisby varying the studied objective functions.We model the underlying online transportation system as a discrete event basedsystem and propose a corresponding fleet management framework, to handle modes,demands and commands. We consider three modes of circulation, tram, elevator andtaxi mode. We propose for each mode appropriate online algorithms and evaluate theirperformance, both in terms of competitive analysis and practical behavior by computationalresults. We treat in this work, the pickup and delivery problem related to theTram mode and the Elevator mode the pickup and delivery problem with time windowsrelated to the taxi mode by means of flows in time-expanded networks.

In this paper we consider a rich vehicle routing problem where transportation requests are characterised by multiple pickup and delivery locations. The problem is a combined load acceptance and generalised vehicle routing problem incorporating a diversity of practical complexities. Among those are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, and different start and end locations for vehicles. We propose iterative improvement approaches based on Large Neighborhood Search and a relatedness measure for transportation requests with multiple pickup and delivery locations. Our algorithms are characterised by very fast response times and thus, can be used within dynamic routing systems where input data can change at any time.

[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.