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

The diploma thesis focuses on optimization of collection service distribution routes in specific company in Moravia region. Failure to evaluate the effects of transportation organization can lead to inefficient planning of routes, which can in turn lead to time or financial losses. Professional approach to distribution route planning leads to a smooth operation of the collection service and to a successful compliance with the evaluation criteria. At first, the diploma thesis will analyse and evaluate the current condition using the evaluation criteria and then it will attempt to propose new solution to improve the current state of affairs.

This thesis deals with real logistic problem of the Heineken CZ Company. The company sets down an itinerary for each vehicle to distribute its goods to particular customers on daily basis. These itineraries are created manually, only with the skill of experienced driver. The goal of this thesis is to find a solution with an algorithm, which will be able to set optimal itineraries of all vehicles, so the total distance and therefore operating costs are minimized, with only the knowledge of distances between each two nodes.

Un modèle structurel est fourni afin d'appréhender les phénomènes de capacité dans un modèle d'affectation de flux de voyageurs sur un réseau de transport collectifs. Cela a été fondé sur une représentation du réseau de transports collectifs en deux couches : sur la couche inférieure, le modèle traite séparément chaque sous système du réseau (ligne, station et rabattement) en fonction des effets de capacité spécifiques ; sur la couche supérieure, le choix d'itinéraire d'un voyageur individuel est adressée par une représentation du réseau en leg (ou segment de ligne) en utilisant le coût et les caractéristiques opérationnelles des sous-systèmes respectifs. On établit une cadre novateur pour modéliser les effets de capacité et on développe le modèle CapTA (pour Capacitated Transit Assignment). Il s'agit d'un modèle d'affectation de flux systémique et modulaire. Il adresse les phénomènes de capacité ci dessous : La qualité du service en véhicule est liée au confort de voyageurs à bord. L'occupation d'états de confort hétérogènes (places assises, strapontins et debout à de densités de voyageurs variables) influence la pénibilité perçu du voyage ; La capacité du véhicule à la montée impacte le temps d'attente de voyageurs et leur distribution aux missions disponibles ; La capacité de l'infrastructure de la ligne établit une relation entre le temps de stationnement des véhicules (and par extension les flux de voyageurs en montée et en descente) et la performance des missions et leur fréquence de service. Ces phénomènes sont traités par ligne d'exploitation sur la base d'un ensemble des modèles locaux qui rendent de flux et de coût spécifiques. Par conséquent, ils modifient les conditions locales d'un trajet en transports collectifs pour chaque voyageur individuel. Cependant, ils doivent être adressés dans le cadre d'un réseau de transports collectifs afin de recueillir leur effet sur les choix d'itinéraire sur le réseau ; essentiellement sur les arbitrages économiques qui impactent le choix entre itinéraires alternatifs. Leur traitement sur la couche réseau garantir la cohérence du choix d'itinéraire. Le modèle de station traite de contraintes de capacité spécifiques et évalue les conditions locales de marche, qui est sensible aux interactions des voyageurs à l'intérieur de la station : le goulot instantané à l'entrée d'un élément de circulation retard l'évacuation de la plateforme ; la densité de voyageurs et l'hétérogénéité des leur flux ralenti les voyageurs qui circulent dans une station ; la présence de l'information en temps réel influence le processus de décision des voyageurs. Ces effets n'ont pas seulement un impact sur le choix d'itinéraire à l'intérieure de la station, mais notamment ils modifient les choix de service sur le niveau du réseau. La Région Ile-de-France fournit un champ d'application idéal pour un modèle d'affectation de flux de voyageurs en transport collectifs sous contraintes de congestion. Plus précisément, il est utilisé dans le cadre du modèle CapTA pour illustrer les capacités de simulation et la finesse de l'approche de modélisation adoptée. Le réseau de transports collectifs contient 1 500 missions de cars et autocars, tout comme 260 missions ferroviaires et inclut 14 lignes de métro et 4 lignes de tramway. L'affectation de trafic à l'heure de pointe du matin est caractérisée d'une charge importante en voyageurs sur les sections centrales de lignes ferroviaires qui traversent la ville. Un temps de stationnement élevé, en raison de flux de montée et descente, et la réduction de la fréquence de service impactent la capacité des missions et des lignes. Le temps généralisé d'un trajet est impacté notamment de sa composante de confort à bord. De résultats détaillés sont présentés sur le RER A, la ligne la plus chargée du réseau ferroviaire régional / A structural model is provided to capture capacity phenomena in passenger traffic assignment to a transit network. That has been founded on a bi-layer representation of the transit network : on the lower layer the model addresses each network sub-system (line, station and access-egress) separately, on the basis of specific capacity effects ; on the upper layer a leg-based representation is used with respect to the sub-systems' costs and operating characteristics to address the trip maker's path choices. We establish a novel framework for modelling capacity effects and develop the CapTA network model (for Capacitated Transit Assignment). It is systemic and modular and addresses in particular the following capacity phenomena, the in-vehicle quality of service is linked to the comfort of the passengers on-board. The occupation of heterogeneous comfort states (seats, folding seats and standing at different passenger densities) influences the perceived arduousness of the travel ; the vehicle capacity at boarding influences the waiting time of the passengers and their distribution to the transit services ; the track infrastructure capacity relates the dwelling time of the vehicles (and by extent the alighting and boarding flows) with the performance of the transit services and their service frequency. These phenomena are dealt with by line of operations on the basis of a set of local models yielding specific flows and costs. Accordingly, they modify the local conditions of a transit trip for each individual passenger. However, these should be addressed within the transit network in order to capture their effect on the network path choices; essentially the economic trade-offs that influence the choice between different network itineraries. Their treatment in a network level assures the coherence of the path choice. Equivalently, a station sub-model addresses specific capacity constraints and yields the local walking conditions, sensible to the interaction of the passengers in the interior of a station : the instant bottleneck created at the entry of the circulation elements delays the evacuation of the station platforms; the passenger density and presence of heterogeneous passenger flows slows down the passengers who circulate in the station; and the presence of real-time information influences the decision making process of the transit users exposed to. These effects do not only impact locally the in-station path choice, but most notably they modify the choices of transit routes and itineraries on a network level. The Paris Metropolitan Region provides an ideal application field of the capacity constrained transit assignment model. It is mainly used as a showcase of the simulation capabilities and of the finesse of the modelling approach. The transit network involves 1 500 bus routes together with 260 trains routes that include 14 metro lines and 4 light rail lines. Traffic assignment at the morning peak hour is characterized by heavy passenger loads along the central parts of the railway lines. Increased train dwelling, due to boarding and alighting flows, and reduction in the service frequency impact the route and the line capacity. The generalized time of a transit trip is impacted mainly though its in-vehicle comfort component. Detailed results have been provided for the RER A, the busiest commuter rail line in the transit network