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.

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

Thesis (PhD)--Stellenbosch University, 2012. / Please refer to full text for abstract.

The subject of my diploma thesis is design and realization of a five strings electric violin. This work builds on my theoretical diploma work named Development of the violin up to the present. The body of the violin is made of solid wood (beech) as same as the chin rest, fingerboard and bridge (walnut). The body is white coloured and varnished. In the left rib is placed el. sound output – 6.3 mm jack. The violin is equipped with piezo pickup Shadow SH SV1. Removable part of the violin is the shoulder rest. It has two support points.

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.

Vehicle ownership and utilization have a profound influence on activity-travel patterns of individuals, vehicle emissions, fuel consumption, highway capacity, congestion and traffic safety. The influence could be further skewed by the diversity of the vehicle fleet. This thesis presents a detailed analysis of the 2001 National Household Travel Survey data to understand the vehicle ownership patterns, fleet mix, allocation and utilization in the context of household and person socio-demographic characteristics. Along with a rich descriptive analysis, models of vehicle ownership and utilization are estimated to distinguish four vehicle types; cars, SUVs (sport utility vehicles), vans and pickup trucks based on their ownership by households and utilization patterns by household members. The primary driver level vehicle utilization analysis provides insights into the extent of allocation of a vehicle to a single person. In addition to confirming many perceptions about the ownership, acquisition and utilization patterns of different types of vehicles, this analysis brings out some subtle differences and similarities among the vehicle types. The analysis results indicate a greater propensity to acquire and use larger vehicles such as minivans, sports utility vehicles and pickup trucks among certain socio-demographic segments of population. Increased ownership and use of vans and SUVs, and their usage as personal vehicles rather than just work vehicles warrants a need to revise vehicle type specific policies, transportation planning and control measures.

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.