Dissertations / Theses on the topic 'Stochastic Vehicle Routing Problem (SVRP)'

This paper deals with optimal distribution issues. One may find listed problems of real life linked to distribution. Moreover, there are explained travelling salesman problem, vehicle routing problem and its variants. This work brings an overview of different ways how to solve vehicle routing problem. In practical part, there is an analysis of distribution of real company. The concept of application is presented in the second part of this paper. This concept could reduce costs of distribution in analyzed company. Testing is aimed mainly on the variant VRPCL (Vehicle Routing Problem with Continuos Loading).

The Vehicle Routing Problem with Stochastic Demand (VRPSD) is a fundamental problem underlying many operational challenges in the field of logistic and supply chain management. The VRPSD is a well-known NP-hard problem whereby a fleet of vehicles is located at a single depot. Each vehicle has a limited capacity and has to serve a number of customers whose actual demands are known only when the vehicle arrives at the customers’ locations. The VRPSD arises in practice whenever a company faces the problem of delivering to a set of customers, whose demands are uncertain. The solution to the VRPSD includes the optimisation of complete routing schedules whilst minimising the transportation costs (fixed costs and variable costs) to satisfy all the constraints in the problem. This study proposes three approaches: the robust routing model with sim-heuristic, randomised Iterated Greedy (IG) algorithm with Monte Carlo Simulation (MCS) and finally IG algorithm with local search to solve the VRPSD. The main aim of using the robust routing model with sim-heuristics is to build robust solutions by combining simulation and optimisation using heuristic methods. This is to handle uncertainty as well as to optimise against any worst instance that might arise due to data uncertainty. Several heuristics have been combined with simulation to deal with stochastic demand. In our version of the approach, the first one is a randomised Clarke and Wright Saving (CWS) algorithm step after which an MCS is incorporated in order to improve the final solutions of VRPSD. The second approach proposed the combination of randomised IG algorithm with MCS to be applied on the VRPSD. The final approach is to use an IG algorithm with local search, based on the aforementioned first approach, in order to improve the solutions generated. Local search has been proven to be an effective technique for obtaining good solutions. The developed robust routing model and sim-heuristic algorithms are tested on well-known benchmark instances and a real-life case study is considered in order to evaluate the effectiveness of the proposed methodologies. The computational results showed that the proposed methodologies are capable of finding useful solutions for the VRPSD and that they are good/robust for the stochastic nature of the problem instances. After computing the average costs from each instance, we also computed the best solution and found that they both could be highly promising and useful for decision makers. The results obtained are quite competitive when compared to the other algorithms found in the literature.

We analyze the problem of distributing units of a product, by a capacitated vehicle, from one storage location (depot) to multiple retailers. The demand processes at the retailers are stochastic and time-dependent. Based on current inventory information, the decision maker decides how many units of the product to deposit at the current retailer, or pick up at the depot, and which location to visit next. We refer to this problem as the stochastic vendor managed inventory (SVMI) problem. In the Markov decision process model of the SVMI problem, we show how a retailer continues to be the vehicle's optimal destination as inventory levels of the retailers vary. Furthermore, an optimal inventory action is shown to have monotone relations with the inventory levels. The multi-period SVMI problem and the infinite horizon (periodic) SVMI problem are analyzed. Additionally, we develop three suboptimal solution procedures, complete a numerical study, and present a case study, which involves a distribution problem at the Coca-Cola Enterprises, Inc. We consider four variations of the SVMI problem, which differ in the available state information and/or the vehicle routing procedure. Analytically, we compare the optimal expected total rewards for the SVMI problem and its variations. Our computational experience suggests a complementary relationship between the quality of state information and the size of the set of retailers that the vehicle can visit.

In this thesis, the vehicle routing problem with stochastic, and time dependent, travel times is studied. The stochastic travel times are estimated from historical drive data. The variation of the drive times, as well as that of the variance, during the day was modeled.   The purpose of the thesis was to propose a method of handling the congestion related traffic impediments in an urban setting. Since the majority of times of delivery in the empirical test cases studied correlate with the time period of high traffic load, an efficient and robust handling of such traffic scenarios is of high importance.  It is shown that the stochastic models will shift the estimated arrivals to customers from the more volatile early and late extremes to more central regions of the time window. Previously delivered routes were evaluated both with the standard algorithm and the proposed stochastic algorithm. The difference between the actual drive times and the calculated drive times were analyzed by studying the correlation of the drive times between each customer in the route. It was shown that the routes of the proposed stochastic method increased this correlation. The drive times between nodes where also perturbed with a Gamma distributed noise. The results from the stochastic algorithm showed higher resilience to this disturbance than did the deterministic models.<br>I detta examensarbete har fordonsruttningsproblemet, VRP, med stokastiska och tidsberonds körtider behandlöats. De stokastiska körtiderna har estimerats från tidigare insamlad hasighetsdata. Modeller för körtidernas och variansernas förändring under dagen har tagits fram.   Syftet med examensarbetet var att föreslå en metod för hur påverkan på körtider av förutsägbar trafikträngsel i en urban trafikmiljö kan hanteras. Eftersom huvuddelen av alla leveranser sammanfaller med de tider på dygnet då trafikbelastning är som högst, ar är en effektiv och robust metod för att hantera sådana störningar av stor vikt. Det visas att den stokastiska modellen kommer att förflyttar ankomster från början och slutet av tidsfönstret till den mer okänsliga mittregionen. Tidigare, utförda leveranser studerades både med den ursprungliga deterministiska modellen och här framtagna stokastiska modellen. Skillnaden mellan de två analyserades genom att studera korrelationen mellan körtiderna som de beräknats av de två modellerna och de upmätta tiderna som de loggats av leveransfordonen. Det visas att korrelationen mellan körtiderna mellan de stokastiska körtiderna och de verkliga körtiderna är högre än korrelationen mellan de deterministiska körtiderna och de verkliga. Rutterna som föreslagits av den stokastiska modellen var också mer tlig mot störningar.

Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2009.<br>Committee Co-Chair: Erera, Alan L.; Committee Co-Chair: Savelsbergh, Martin W. P.; Committee Member: Ergun, Ozlem; Committee Member: Ferguson, Mark; Committee Member: Kleywegt, Anton J.. Part of the SMARTech Electronic Thesis and Dissertation Collection.

This dissertation presents a cartographic approach to the dynamic vehicle routing problem with time windows and stochastic customers (DVRPTWSC). The objectives are to minimize the total travel time and maximize the number of new requests served. Addressing the DVRPTWSC requires solving the vehicle routing problem with time windows (VRPTW). A memetic algorithm (MA) for the VRPTW is proposed. The MA prunes the search space using the information gathered by a clustering procedure, which is applied to customers spatial data. The cartographic approach to the DVRPTWSC is incorporated into a multiagent system where a dispatcher agent plans the routes for vehicle agents. Before creating the initial routing plan, a cartographic processing is applied. This procedure uses hierarchical clustering to divide the region where customers are located into a hierarchy of nested regions. The initial routing plan considers known requests and potential requests sampled from known probability distributions. It is created using the search operators of the MA, which in turn use the information obtained from the hierarchical clustering to perform the search. Over the planning horizon, the dispatcher updates the routing plan: Potential requests that were included in the initial routing plan and do not materialize are removed and new requests are processed using the assignation of requests based on nested regions (ARNR). The ARNR procedure is aimed at reducing the number of vehicles considered for serving new requests. It tries to assign the requests among the vehicles that can serve them at low detour costs. The nested regions created in the cartographic processing are used to identify such vehicles. Experimental results show that the proposed MA performs competitively with state-of-the-art heuristics for the VRPTW. The proposed approach to the DVRPTWSC outperforms approaches that do not include potential requests in the initial routing plan. The use of the ARNR procedure significantly reduces the number of vehicles considered for serving new requests, and it yields solutions similar to those obtained when considering all vehicles in operation. The proposed approach performs consistently under three levels of dynamism: low, medium, and high.<br>Esta dissertação apresenta uma abordagem cartográfica para o problema de roteamento de veículos dinâmico com janelas de tempo e clientes estocásticos (DVRPTWSC, por sua sigla em inglês). Os objetivos considerados são minimizar o tempo total de viagem e maximizar o número de pedidos novos atendidos. Para abordar o DVRPTWSC é necessário resolver o problema de roteamento de veículos com janelas de tempo (VRPTW, por sua sigla em inglês). Assim, para tratar o VRPTW propõe-se um algoritmo memético (MA, por sua sigla em inglês). O MA reduz o espaço de busca usando informação obtida por meio de um procedimento de clusterização, o qual é aplicado aos dados espaciais dos clientes. Para o DVRPTWSC, a abordagem cartográfica é incorporada em um sistema multiagente, no qual um agente roteirizador planeja as rotas para os agentes veículos. O processamento cartográfico é aplicado antes de criar o plano de rotas inicial para o DVRPTWSC. Este procedimento usa clusterização hierárquica para dividir a região onde estão os clientes em uma hierarquia de regiões encaixadas. O plano de rotas inicial considera pedidos conhecidos e pedidos potenciais amostrados de distribuições de probabilidade conhecidas. Para obter o plano de rotas inicial, usam-se os operadores de busca do MA, os quais utilizam a informação obtida da clusterização hierárquica para fazer a busca. Ao longo do horizonte de planejamento, o roteirizador atualiza o plano de rotas: Pedidos potenciais que foram considerados no plano de rotas inicial e que não foram consolidados são removidos e novos pedidos são incluídos usando o procedimento assignation of requests based on nested regions (ARNR). O procedimento ARNR visa reduzir o número de veículos considerados para atender novos pedidos. Para isso, tenta designar os novos pedidos aos veículos disponíveis para o atendimento que possuem os menores custos de desvio da rota pré-determinada. As regiões encaixadas criadas no processamento cartográfico são utilizadas para identificar esses veículos. Para o VRPTW, resultados experimentais mostram que o MA proposto é competitivo com métodos do estado da arte. A abordagem proposta para o DVRPTWSC supera abordagens que não incluem pedidos potenciais no plano de rotas inicial. O uso do procedimento ARNR reduz significativamente o número de veículos considerados para atender novos pedidos, e produz soluções similares às produzidas quando se consideram todos os veículos em operação. A abordagem desenvolvida para o DVRPTWSC tem um desempenho consistente para três níveis de dinamismo: baixo, médio e alto.

Le problème de tournées de véhicules avec contrainte de capacité est un problème important en optimisation combinatoire. L'objectif du problème est de déterminer l'ensemble des routes, nécessaire pour servir les demandes déterministes des clients ayant un cout minimal, tout en respectant la capacité limite des véhicules. Cependant, dans de nombreuses applications réelles, nous sommes confrontés à des incertitudes sur les demandes des clients. La plupart des travaux qui ont traité ce problème ont supposé que les demandes des clients étaient des variables aléatoires. Nous nous proposons dans cette thèse de représenter l'incertitude sur les demandes des clients dans le cadre de la théorie de l'évidence - un formalisme alternatif pour modéliser les incertitudes. Pour résoudre le problème d'optimisation qui résulte, nous généralisons les approches de modélisation classiques en programmation stochastique. Précisément, nous proposons deux modèles pour ce problème. Le premier modèle, est une extension de l'approche chance-constrained programming, qui impose des bornes minimales pour la croyance et la plausibilité que la somme des demandes sur chaque route respecte la capacité des véhicules. Le deuxième modèle étend l'approche stochastic programming with recourse: l'incertitude sur les recours (actions correctives) possibles sur chaque route est représentée par une fonction de croyance et le coût d'une route est alors son coût classique (sans recours) additionné du pire coût espéré des recours. Certaines propriétés de ces deux modèles sont étudiées. Un algorithme de recuit simulé est adapté pour résoudre les deux modèles et est testé expérimentalement<br>The capacitated vehicle routing problem is an important combinatorial optimisation problem. Its objective is to find a set of routes of minimum cost, such that a fleet of vehicles initially located at a depot service the deterministic demands of a set of customers, while respecting capacity limits of the vehicles. Still, in many real-life applications, we are faced with uncertainty on customer demands. Most of the research papers that handled this situation, assumed that customer demands are random variables. In this thesis, we propose to represent uncertainty on customer demands using evidence theory - an alternative uncertainty theory. To tackle the resulting optimisation problem, we extend classical stochastic programming modelling approaches. Specifically, we propose two models for this problem. The first model is an extension of the chance-constrained programming approach, which imposes certain minimum bounds on the belief and plausibility that the sum of the demands on each route respects the vehicle capacity. The second model extends the stochastic programming with recourse approach: it represents by a belief function for each route the uncertainty on its recourses (corrective actions) and defines the cost of a route as its classical cost (without recourse) plus the worst expected cost of its recourses. Some properties of these two models are studied. A simulated annealing algorithm is adapted to solve both models and is experimentally tested

Chen, Jian.<br>Thesis (M.Phil.)--Chinese University of Hong Kong, 2007.<br>Includes bibliographical references (leaves 81-85).<br>Abstracts in English and Chinese.<br>Chapter 1 --- Introduction --- p.1<br>Chapter 1.1 --- Background --- p.1<br>Chapter 1.2 --- Literature Review --- p.4<br>Chapter 1.2.1 --- Vehicle Routing Problem with Stochastic Demands --- p.5<br>Chapter 1.2.2 --- Vehicle Routing Problem with Stochastic Travel Times --- p.8<br>Chapter 1.3 --- The Vehicle Routing Problem with Time Windows and Stochastic Travel Times --- p.10<br>Chapter 2 --- Notations and Formulations --- p.12<br>Chapter 2.1 --- Problem Definitions --- p.12<br>Chapter 2.2 --- A Two-Index Stochastic Programming Model --- p.14<br>Chapter 2.3 --- The Second Stage Problem --- p.17<br>Chapter 3 --- The Scheduling Problem --- p.20<br>Chapter 3.1 --- The Overtime Cost Problem --- p.22<br>Chapter 3.2 --- The Waiting and Late Cost Problem --- p.27<br>Chapter 3.3 --- The Algorithm --- p.37<br>Chapter 4 --- The Integer L-Shaped Method --- p.40<br>Chapter 4.1 --- Linearization of the Objective Function --- p.41<br>Chapter 4.2 --- Handling the Constraints --- p.42<br>Chapter 4.3 --- Branching --- p.44<br>Chapter 4.4 --- The Algorithm --- p.44<br>Chapter 5 --- Feasibility Cuts --- p.47<br>Chapter 5.1 --- Connected Component Methods --- p.48<br>Chapter 5.2 --- Shrinking Method --- p.49<br>Chapter 6 --- Optimality Cuts --- p.52<br>Chapter 6.1 --- Lower Bound I for the EOT Cost --- p.53<br>Chapter 6.2 --- Lower Bounds II and III for the EOT Cost --- p.56<br>Chapter 6.3 --- Lower Bound IV for the EWL Cost --- p.57<br>Chapter 6.4 --- Lower Bound V for Partial Routes --- p.61<br>Chapter 6.5 --- Adding Optimality Cuts --- p.66<br>Chapter 7 --- Numerical Experiments --- p.70<br>Chapter 7.1 --- Effectiveness in Separating the Rounded Capacity Inequalities --- p.71<br>Chapter 7.2 --- Effectiveness of the Lower Bounds --- p.72<br>Chapter 7.3 --- Performance of the L-shaped Method --- p.74<br>Chapter 8 --- Conclusion and Future Research --- p.79<br>Bibliography --- p.81<br>Chapter A --- Generation of Test Instances --- p.86

Dimitris J. Bertsimas, Garrett van Ryzin.<br>"February 1990."<br>Includes bibliographical references (p. 29-31).<br>Research supported by the National Science Foundation. DDM-9014751 Research supported by a grant from Draper Laboratory.

碩士<br>大葉大學<br>工業工程研究所<br>87<br>Vehicle routing problem (VRP) and its variants have been widely studied for several decades. Since they are of the class of NP-Hard problems, it is very difficult to obtain optimal solutions within acceptable amount of time. Heuristic algorithms are thus applied for solving VRP with large scale. Several assumptions are usually made in the modeling of VRP and its variants including: 1. demand of each customer is constant, 2. fleet type is homogeneous, 3. unlimited number of vehicles can be used. The above assumptions obviously conflict with the reality. We hence study four types of VRP variants: general VRP with single type of fleet, general VRP with mix fleet type, VRP considering stochastic demands with single fleet type, and VRP considering stochastic demands with multiple type of fleet to reflect the real situations. As far as the solution method is concerned, tabu search is used for solving the SVRP. The results indicate that the size of tabu list does not play an important role in the solving process for all types of problems. When solving the SVRP, the objective function gets better as the route failure probability α increases, and besides, the objective function gets better as the capacity filling coefficient f decreases.

碩士<br>中原大學<br>工業工程學系<br>87<br>This paper is established on the Stochastic Vehicle Routing Problem(SVRP). In the Stochastic Vehicle Routing Problem(SVRP), we consider the stochastic demand and the stochastic travel time concurrently. We dispatch the Fleet Size and Multicommodity Mix Vehicle Routing Problem . The purpose of this paper is to decide a dispatch of fixed fleet size and Multicommodity routing in the stochastic conditions. The combination of dispatch is to minimum the expectation cost with satisfying the customer-service level.

碩士<br>國立高雄科技大學<br>運籌管理系<br>107<br>This study focuses on the Open Vehicle Routing Problem with Stochastic Demand (OVRPSD). OVRP generally occurs when a company hires a fleet or entrusts a distribution business to a third-party logistics providers. The vehicle departs from the station. After the delivery, it ends at a customer point. The customer's demand belongs to the Random Variable, and it is now possible to know the customer's demand. Therefore, it is possible that the vehicle capacity is insufficient during the journey and it is closer to the real life situation. The open vehicle routing problem in two situations is proposed. The first one is the traditional OVRP problem, called Depot to Customer (DtoC). The second type is called Home Company to Collection Site (HtoC), which means that the vehicle starts from the company location and ends at the collection site. For example, the garbage truck starts from the company location and transports the garbage to the incinerator after the last customer point is collected. Therefore, the ant colony optimization is applied to solve this problem. Firstly, the optimal path is finding by minimizing the number of vehicles and then calculating the minimum travel cost. At the same time, all the ants will compete with one another to win the chance to serve the next customer, making the results more competitive. Keywords: open vehicle routing problem, ant colony optimization, stochastic demand

碩士<br>國立高雄第一科技大學<br>運籌管理研究所<br>105<br>A carrier has difficulties on controlling the delivery time because of complex and dynamic traffic conditions. It is essential to take the uncertainty of the traffic into account so that the vehicle dispatching can be well planned. The time window constraint for each customer is considered in this research. The travel time of one link is varying because of various traffic flow. The delivery time is set to be 8 hours, which is divided into 5 time zones in this research. Each time zone has a different travel time function for each link. This function is used to calculate the link travel time for different entering time. The Ant Colony Optimization method is employed to solve this VRP with dynamic link travel time. A parameter γ is set to reflect the influence of uncertainty of traffic during distributing and will be used to help in improving the routing process. The output results indicated that the solving process can yield a good solution while (α,β) is equal to (1, 2) and γ=3. The contribution of this study is to take the traffic situation into consideration and figure out how the dispatching can response for that. It is expected to be a valuable reference of the practical vehicle route planning for the industry.

碩士<br>國立雲林科技大學<br>工業工程與管理系<br>105<br>The goals of this research are to develop a mathematical model and an effective solution technique for the Fleet Size and Mix Vehicle Routing Problem with Stochastic demands. This model is based on the published VRPSD and FSMVRP formulations. And using an advanced particle swarm optimization (PSO) to find an approximate optimal solutions. This research investigates a variant of an uncertain VRP in which the customers’ demands are supposed to be a discrete random variable, and when vehicle before sevices the costumers, the demands was unknown, and considers a fleet size with different capacities and variable costs of vehicles. We develop a mathematical model and using PSO to minimize the total cost. Finally, testing examples are generated from the existing benchmark instances of VRPSD and FSMVRP.

碩士<br>國立成功大學<br>工業與資訊管理學系碩博士班<br>95<br>We consider the multi-vehicle routing problem, in which demands of customers are stochastic. Due to this randomness, a vehicle may fail to satisfy the demand of some customers when accumulated demands of customers in a designated route exceed the capacity of the vehicle. Cost to reschedule alternative route or dispatch additional vehicle to meet customer’s demand incurred when the route failure occurs. 　　In this thesis, the stochastic vehicle routing problem is formulated as a 0-1 integer programming model with probabilistic constraint. Due to the complexity of mathematical model, a streamlined two-stage formulation is then proposed to address this difficult problem. At the first stage, each customer is assigned to a vehicle by the reformulated stochastic linear assignment model, subject to the route failure constraint. The expected operating, including vehicle routing and route failure, is then computed for each vehicle at the second stage. 　　A heuristic solution procedure is developed to solve this stochastic vehicle routing problem. A simplified assignment model, based on expected demand of customers, is solved to determine the routing zone of each vehicle. The optimum route for each vehicle to serve the customers is then determined by solving traveling salesman problem; and the expected total routing cost is finally computed. Numerical experiments, with problem sizes up to 35 customers and 8 vehicles, have been performed. Our computational tests have shown that the expected operating cost of the routes developed by the new approach is significantly lower than that of the classical dynamic approach. The new approach also outperforms the existing approaches in terms of computational times or resources.

碩士<br>國防大學理工學院<br>兵器系統工程碩士班<br>97<br>The travel time of a vehicle is varied with traffic conditions such as traffic jam, accidents or climate situations. To simulate these traffic conditions of road network, this thesis aims at active transportation in military to construct a vehicle routing model with random travel time. Furthermore, a hybrid particle swam optimization (HPSO) is proposed to optimize the constructed model and thus determine the routing path of the active transportation in military. The contributions of this thesis are expected to be capable of utilizing the limited logistics resources efficiently by shrinking routing length, reducing required number of vehicles, and improving loading rate of vehicles to enhance the logistics capacity. The proposed HPSO is on the basis of improving a developed discrete PSO at which the sweep method and nearest addition method are adopted to generate the excellent initial PSO population. Moreover, the response surface methodology (RSM) derived from designs of experiments is employed to determine the optimal settings of HPSO search parameters. The international CVRP benchmark problems are applied to verify the effectiveness of the proposed HPSO. Finally the proposed approach is employed to solve an actual military problem in active transportation.

碩士<br>國立交通大學<br>運輸科技與管理學系<br>100<br>Since Vehicle Routing Problem (VRP) was introduced by Dantzig and Ramser in 1959, numerous research efforts have been devoted to it and its variants. However, as there are full of uncertainties in real world, more and more researches have focus on stochastic versions of the VRP in recent years. According to one of global forwarding companies in Taiwan, in case of not knowing who should be responsible for some customers being omitted, each driver has been assigned a “responsible region” to satisfy every customer’s demands in his region. Besides, in practice, customer’s demand is a random variable, which means it may be zero in a certain day, in order to save traveling cost, driver doesn’t need to visit those who have zero demand, just heading to next customer directly to save traveling cost. Moreover, cars have capacity limits, whenever customer’s demand exceeds car’s capacity, we called it route failure, which will cause extra cost to take recourse action. However, it will cost a lot if global forwarder want to reschedule driver’s visiting route based on the actual situation every day. In addition, stochastic models also arise naturally in situations where routes are planned for a long planning horizon but executed repeatedly during that horizon. Therefore, in this research, we focus on a single responsible region (single vehicle) and customers have stochastic demands, under this scenario, we formulate a mathematical modal and propose a hybrid algorithm which is combined with Genetic Algorithm (GA), Monte Carlo Simulation (MCS) and Optimal Computing Budget Allocation (OCBA) trying to find a near optimal solution in a reasonable time which can suggest the global forwarder a fixed visiting route to save total cost. According to the results of numerical test, we found this algorithm preforms much better than nearest neighbor algorithm, and based on these results, we give some suggestions to the real world.

碩士<br>國立高雄第一科技大學<br>運籌管理所<br>98<br>Vehicle routing problem with stochastic demands is a kind of vehicle routing problem, that customer demand is a random variable, so there is likely insufficient goods or the goods on board the car just equals the demands, the situation called the route failure. This study investigate the characteristics of vending machines replenishment, the problem is multicommodity, the demand points have different products, and different products have different demand and profits, if not to the replenishment of goods may occur sold out of the situation, resulting in stockout costs. This study proposes two different ant colony optimization algorithm for solving strategy, strategy one is two-stage for solution, that singled out service targets in the customers then operations, strategy two is different, that without filter, and it directly use new ant colony optimization algorithm to plan. Finally, the study proffer the following three: (i) compared the different strategies and algorithms related parameters (ii) analysis the impact of problem definition parameters’ changes (iii) compared the merits of fixed solution and random solutions.

Cette thèse s’intéresse aux problèmes de tournées de véhicules où l’on retrouve des contraintes de chargement ayant un impact sur les séquences de livraisons permises. Plus particulièrement, les items placés dans l’espace de chargement d’un véhicule doivent être directement accessibles lors de leur livraison sans qu’il soit nécessaire de déplacer d’autres items. Ces problèmes sont rencontrés dans plusieurs entreprises de transport qui livrent de gros objets (meubles, électroménagers). Le premier article de cette thèse porte sur une méthode exacte pour un problème de confection d’une seule tournée où un véhicule, dont l’aire de chargement est divisée en un certain nombre de piles, doit effectuer des cueillettes et des livraisons respectant une contrainte de type dernier entré, premier sorti. Lors d’une collecte, les items recueillis doivent nécessairement être déposés sur le dessus de l’une des piles. Par ailleurs, lors d’une livraison, les items doivent nécessairement se trouver sur le dessus de l’une des piles. Une méthode de séparation et évaluation avec plans sécants est proposée pour résoudre ce problème. Le second article présente une méthode de résolution exacte, également de type séparation et évaluation avec plans sécants, pour un problème de tournées de véhicules avec chargement d’items rectangulaires en deux dimensions. L’aire de chargement des véhicules correspond aussi à un espace rectangulaire avec une orientation, puisque les items doivent être chargés et déchargés par l’un des côtés. Une contrainte impose que les items d’un client soient directement accessibles au moment de leur livraison. Le dernier article aborde une problème de tournées de véhicules avec chargement d’items rectangulaires, mais où les dimensions de certains items ne sont pas connus avec certitude lors de la planification des tournées. Il est toutefois possible d’associer une distribution de probabilités discrète sur les dimensions possibles de ces items. Le problème est résolu de manière exacte avec la méthode L-Shape en nombres entiers.<br>In this thesis, we study mixed vehicle routing and loading problems where a constraint is imposed on delivery sequences. More precisely, the items in the loading area of a vehicle must be directly accessible, without moving any other item, at delivery time. These problems are often found in the transportation of large objects (furniture, appliances). The first paper proposes a branch-and-cut algorithm for a variant of the single vehicle pickup and delivery problem, where the loading area of the vehicle is divided into several stacks. When an item is picked up, it must be placed on the top of one of these stacks. Conversely, an item must be on the top of one of these stacks to be delivered. This requirement is called “Last In First Out” or LIFO constraint. The second paper presents another branch-and-cut algorithm for a vehicle routing and loading problem with two-dimensional rectangular items. The loading area of the vehicles is also a rectangular area where the items are taken out from one side. A constraint states that the items of a given customer must be directly accessible at delivery time. The last paper considers a stochastic vehicle routing and loading problem with two- dimensional rectangular items where the dimensions of some items are unknown when the routes are planned. However, it is possible to associate a discrete probability distribution on the dimensions of these items. The problem is solved with the Integer L-Shaped method.