This dissertation introduces and analyzes the Bus Evacuation Problem (BEP), a unique Vehicle Routing Problem motivated both by its humanitarian significance and by the routing and scheduling challenges of planning transit-based, regional evacuations. First, a variant where evacuees arrive at constant, location-specific rates is introduced. In this problem, a fleet of capacitated buses must transport all evacuees to a depot/shelter such that the last scheduled pick-up and the end of the evacuee arrival process occurs at a location-specific time. The problem seeks to minimize their accumulated waiting time, restricts the number of pick-ups on each location, and exploits efficiencies from service choice and from allowing buses to unload evacuees at the depot multiple times. It is shown that, depending on the problem instance, increasing the maximum number of pick-ups allowed may reduce both the fleet size requirement and the evacuee waiting time, and that, past a certain threshold, there exist a range of values that guarantees an efficient usage of the available fleet and equitable reductions in waiting time across pick-up locations. Second, an extension of the Ritter (1967) Relaxation Algorithm, which explores the inherent structure of problems with complicating variables and constraints, such as the aforementioned BEP variant, is presented. The modified algorithm allows problems with linear, integer, or mixed-integer subproblems and with linear or quadratic objective functions to be solved to optimality. Empirical studies demonstrate the algorithm viability to solve large optimization problems. Finally, a two-stage stochastic formulation for the BEP is presented. Such variant assumes that all evacuees are at the pick-up locations at the onset of the evacuation, that the set of possible demands is provided, and, more importantly, that the actual demands become known once buses visit the pick-up locations for the first time. The effect of exploratory visits (sampling) and symmetry is explored, and the resulting insights used to develop an improved formulation for the problem. An iterative (dynamic) solution algorithm is proposed. / Ph. D.

No description available.

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

In this study we consider an inventory routing problem in which a supplier distributes a single product to multiple retailers in a finite planning horizon. Retailers should satisfy the deterministic and dynamic demands of end customers in the planning horizon, but the retailers can backorder the demands of end customers considering the supply chain costs. In each period the supplier decides the retailers to be visited, and the amount of products to be supplied to each retailer by a fleet of vehicles. The decision problems of the supplier are about when, to whom and how much to deliver products, and in which order to visit retailers while minimizing system-wide costs. We propose a mixed integer programming model and a Lagrangian relaxation based solution approach in which both upper and lower bounds are computed. We test our solution approach with test instances taken from the literature and provide our computational results.

Thesis (M.S.)--Oregon State University, 2008. / Printout. Includes bibliographical references (leaves 72-79 ). Also available on the World Wide Web.

Submitted by Maike Costa (maiksebas@gmail.com) on 2016-04-27T12:05:09Z No. of bitstreams: 1 aquivo total.pdf: 6385698 bytes, checksum: e405abafe77b914dfaead617fb32ee44 (MD5) / Made available in DSpace on 2016-04-27T12:05:09Z (GMT). No. of bitstreams: 1 aquivo total.pdf: 6385698 bytes, checksum: e405abafe77b914dfaead617fb32ee44 (MD5) Previous issue date: 2015-06-18 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / The bi-objective Pollution-Routing Problem (b-PRP) is a PRP (Pollution-Routing Problem Bekta¸s e Laporte (2011)) extension that considers separately two conflicting objectives: minimization of carbon emission costs and minimization of operational costs. To the best of our knowledge, only few papers in the literature present multi-objective analysis concerning transportation environmental issues. Due to the lack of specific methods that are capable of finding good results for this kind of problem, this dissertation aims to propose a new heuristic method for solving the b-PRP. In this method, solution sets are generated so as to represent possible scenarios for the problem. The proposed method is based on the Two-Phase Pareto Local Search (2PPLS) proposed by Lust e Teghem (2009). During the first phase of the method, efficient solutions are generated solving parametrized problems. In the second phase, each solution is explored by means of a Pareto Local Search procedure. In other to speed up the method, an efficient scheme is employed for assessing the news solutions. Despite of its simplicity, the proposed method was capable of finding a large number of efficient solutions in a reasonable time. Computational results show that the proposed approach leads to better results than those obtained by multiobjective techniques available in the literature. The quality indicators Hypervolume (H) and R Measure (R) have been used for assessing the efficient solutions sets. Because of the random behavior presented in the sequential method used to solve the parametrized problems, Mann-Whitney Nonparametric Test has been used for comparing the results. Outperformance Relations have also been used on the results analysis. We concluded that the majority of solutions generated by 2PPLS dominates those generated by others multi-objective methods found in the literature. / O Pollution-Routing Problem bi-Objetivo (b-PRP) ´e uma extens˜ao do PRP (Pollution- Routing Problem proposto por Bekta¸s e Laporte (2011)) que considera separadamente dois objetivos conflitantes: minimiza¸c˜ao dos custos com as emiss˜oes de carbono e minimiza¸c˜ao dos custos operacionais. Na literatura, poucos trabalhos apresentam an´alises multiobjetivo relacionadas aos problemas de transporte resolvidos no contexto ambiental. Devido `a aus ˆencia de m´etodos capazes de encontrar bons resultados para esses tipos de problemas, esta disserta¸c˜ao tem por objetivo desenvolver um m´etodo heur´ıstico para a resolu¸c˜ao do b-PRP. S˜ao gerados conjuntos de solu¸c˜oes eficientes, que representam os poss´ıveis trade-offs entre os objetivos. A abordagem heur´ıstica proposta ´e baseada no m´etodo Two-Phase Pareto Local Search (2PPLS). A primeira fase do m´etodo ´e dedicada `a gera¸c˜ao de um conjunto de solu¸c˜oes eficientes suportadas, atrav´es da resolu¸c˜ao de problemas multiobjetivo agregados. Na segunda fase, as solu¸c˜oes geradas na primeira fase s˜ao exploradas aplicando-se um procedimento de Pareto Local Search. Nessa fase, emprega-se uma estrutura eficiente para a avalia¸c˜ao das novas solu¸c˜oes geradas. Apesar da simplicidade do m´etodo empregado, ele foi capaz de gerar um elevado n´umero de solu¸c˜oes eficientes e em um tempo computacional aceit´avel. Os resultados computacionais mostraram que a abordagem utilizada leva a resultados melhores do que os obtidos pelas t´ecnicas dispon´ıveis na literatura. Os indicadores de qualidade Hipervolume (H) e Medida R (R) foram considerados na avalia¸c˜ao dos conjuntos de solu¸c˜oes eficientes. Devido `a natureza aleat´oria do m´etodo, os resultados foram comparados por meio do Teste N˜ao Param´etrico de Mann-Whitney. Rela¸c˜oes de desempenho ainda foram empregadas na an´alise dos resultados, e mostraram que as Fronteiras de Pareto geradas pelo 2PPLS dominam, na grande maioria dos casos, aquelas geradas por outros m´etodos existentes na literatura.

This report presents a solution procedure to accomplish efficient routing of vehicles. Specifically, the routing of delivery trucks to transport bulk poultry feed from a single feed mill to various customer farms located in the surrounding region at nearly 50 miles radius was studied. The goal was to minimize the total distance traveled for all routes. The project was divided into two phases. In the first phase, truck delivery records were developed through a system of forms over a period of one week at Purdue, Inc. of Salisbury, Maryland. These records were used for preparation of the data required in the second phase of the project. In the second phase, the 'Sweep' Algorithm by Gillette and Miller was used to generate truck routes on a digital computer. The results obtained through the recommended solution procedure were compared with the routes designed by the dispatcher at Purdue, Inc. These results showed significant savings in total distance traveled over all routes. / Master of Science

This dissertation is submitted in fulfillment of the requirements for the degree of Master of Science, University of the Witwatersrand, Johannesburg, August 2018 / Abstract. The vehicle routing problem is a common combinatorial optimization, which is modelled to determine the best set routes to deploy a fleet of vehicles to customers, in order to deliver or collect goods efficiently. The vehicle routing problem has rich applications in design and management of distribution systems. Many combinatorial optimization algorithms which have been developed, were inspired through the study of vehicle routing problems. Despite the literature on vehicle routing problems, the existing techniques fail to perform well when n (the number of variables defining the problem) is very large, i.e., when n > 50. In this dissertation, we survey exact and inexact methods to solve large problems. Our attention is on the capacitated vehicle routing problem. For exact methods, we investigate only the Cutting Planes method which has recently been used in conjunction with other combinatorial optimization problem algorithms (like the Branch and Bound method) to solve large problems. In this investigation, we study the polyhedral structure of the capacitated vehicle routing problem. We compare two metaheuristics, viz., the Genetic Algorithm and the Ant Colony Optimization. In the genetic algorithm, we study the effect of four different crossover operators. Numerical results are presented and conclusion are drawn, based on our findings. / XL2019

The vehicle routing problem (VRP), is a classic optimization problem that aims to determine the optimal set of routes for a fleet of vehicles to meet the demands of a set of customers. The VRP has been studied for many decades and as such, there are many variants and extensions to the original problem. The research presented here focuses on two different types of vehicle routing and scheduling planning problems: car shipping and fatigue-aware scheduling. In addition to modeling and solving the car shipping problem, this research presents a novel way for ways in which drivers can describe their route preferences in a decision support system. This work also introduces the first fatigue-aware vehicle scheduling problem called the Truck Driver Scheduling Problem with Fatigue Management (TDSPFM). The TDSPFM is utilized to produce schedules that keep the drivers more alert than existing commercial vehicle regulations. Finally, this work analyzes the effect of the starting alertness level on driver alertness for the remainder of the work week and examines a critical shortcoming in existing regulations. / Ph. D.

The global energy requirement is increasing at a rapid pace and fossil fuels have been one of the major players in meeting this growing energy demand. However, the resources for fossil fuels are finite. Therefore, it is essential to develop renewable energy sources like biofuels to help address growing energy needs. A key aspect in the production of biofuel is the biomass logistics chain that constitutes a complex collection of activities, which must be judiciously executed for a cost-effective operation. In this thesis, we introduce a two-phase optimization-simulation approach to determine tactical biomass logistics-related decisions cost effectively in view of the uncertainties encountered in real-life. These decisions include number of trucks to haul biomass from storage locations to a bio-refinery, the number of unloading equipment sets required at storage locations, and the number of satellite storage locations required to serve as collection points for the biomass secured from the fields. Later, an operational-level decision support tool is introduced to aid the "feedstock manager" at the bio-refinery by recommending which satellite storage facilities to unload, how much biomass to ship, how to allocate existing resources (trucks and unloading equipment sets) during each time period, and how to route unloading equipment sets between storage facilities. Another problem studied is the "Bale Collection Problem" associated with the farmgate operation. It is essentially a capacitated vehicle routing problem with unit demand (CVRP-UD), and its solution defines a cost-effective sequence for collecting bales from the field after harvest. / Master of Science