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.

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.

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

Pickup and delivery problems (PDPs) have been studied extensively in past decades. A wide variety of research exits on both exact algorithms and heuristics for generic variations of the problem as well as real-life applications, which continue to spark new challenges and open up new opportunities for researchers. In this dissertation, we study two variations of pickup and delivery problem that arise in industry and develop new computational methods that are shown to be effective with respect to existing algorithms and scheduling procedures found in practice. The first problem is the pickup and delivery problem with transshipment (PDPT). The work presented here was inspired by a daily route planning problem at a regional air carrier. In structuring the analysis, we describe a unique way to model the transshipment option on a directed graph. With the graph as the foundation, we implemented a branch and price algorithm. Preliminary results showed that it has difficulty in solving large instances. As an alternative, we developed a greedy randomized adaptive search procedure (GRASP) with several novel features. In the construction phase, shipment requests are inserted into routes until all demand is satisfied or no feasible insertion exists. In the improvement phase, an adaptive large neighborhood search algorithm is used to reconstruct portions of the feasible routes. Specialized removal and insertion heuristics were designed for this purpose. We also developed a procedure for generating problem instances in the absence of any in the literature. Testing was done on existing PDP data sets and generated PDPT data set. For the former, the performance and solution quality of the GRASP were comparable to the best known heuristics. For the latter, GRASP found the near optimal solution in most test cases. In the second part of the dissertation, we focus on a new version of the heterogeneous PDP in which the capacity of each vehicle can be modified by reconfiguring its interior to satisfy different types of customer demands. The work was motivated by a daily route planning problem arising at a senior activity center. A fleet of configurable vans is available each day to transport participants to and from the center as well as to secondary facilities for rehabilitative and medical treatment. To find solutions, we developed a two-phase heuristic that makes use of ideas from greedy randomized adaptive search procedures with multiple starts. In phase I, a set of good feasible solutions is constructed using a series of randomized procedures. A representative subset of those solutions is selected as candidates for improvement by solving a max diversity problem. In phase II, an adaptive large neighborhood search (ALNS) heuristic is used to find local optima by reconstructing portions of the feasible routes. Also, a specialized route feasibility check with vehicle type reassignment is introduced to take full advantage of the heterogeneous nature of vehicles. The effectiveness of the proposed methodology is demonstrated by comparing the solutions it provided for the equivalent of several weeks with those that were used in practice and derived manually. The analysis indicates that anywhere from 30% to 40% savings can be achieved with the multi-start ALNS heuristic. An exact method is introduced based on branch and price and cut for settings with more restricted time windows. In the procedure, the master problem at each node in the search tree is solved by column generation to find a lower bound. To improve the bound, subset-row inequalities are applied to the variables of the master problem. Columns are generated by solving the pricing subproblems with a labeling algorithm enhanced by new dominance conditions. Local search on the columns is used to quickly find promising alternatives. Implementation details and ways to improve the performance of the overall procedure are discussed. Testing was done on a set of real instances as well as a set of randomly generated instances with up to 50 customer requests. The results show that optimal solutions are obtained in majority of cases. / 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.