Many real-world vehicle routing problems are dynamic optimization problems, with customer requests arriving over time, requiring a repeated reoptimization. In this paper, we consider a dynamic vehicle routing problem where one additional customer arrives at a beforehand unknown location when the vehicles are already under way. Our objective is to maximize the probability that the additional customer can be integrated into one of the otherwise fixed tours without violating time constraints. This is achieved by letting the vehicles wait at suitable locations during their tours, thus influencing the position of the vehicles at the time when the new customer arrives. For the cases of one and two vehicles, we derive theoretical results about the best waiting strategies. The general problem is shown to be NP-complete. Several deterministic waiting strategies and an evolutionary algorithm to optimize the waiting strategy are proposed and compared empirically. It is demonstrated that a proper waiting strategy can significantly increase the probability of being able to service the additional customer, at the same time reducing the average detour to serve that customer.

Interlibrary Loan entails obtaining copies of library materials not found in the library's collection on behalf of the library's patrons (borrowing), as well as providing copies of library materials requested by other libraries (lending). The dynamic nature of today's library environment is well illustrated by the rapid changes occurring in the role of interlibrary loan. The vision statement of the University of Central Florida Library is: The library performs a central role of adding value to information for the academic community by creatively improving and providing information resources and services. The library strives to create an environment that encourages the pursuit of intellectual endeavors and the creation of new knowledge. In an endeavor to fulfill this vision, the Interlibrary Loan Department at the UCF main library wants to set up a document delivery service within the UCF main campus in order to facilitate research efforts on campus. The document delivery service will include delivery and pickup of library materials for ILL requests by faculty online (via computers). In this study, we build a Traveling Salesperson model for obtaining a routing sequence for the document delivery service. Next, we analyze this model in order to check the feasibility of the routing sequence in presence of demand (delivery and pickup) by simulating the demand over the route using computer simulation software. We conclude by validating the model under given conditions and providing route sequence recommendations in the case of extreme demands.

No description available.

In this work we present a multiagent Fleet Coordination Problem (FCP). In this formulation, agents seek to minimize the fuel consumed to complete all deliveries while maintaining acceptable on-time delivery performance. Individual vehicles must both (i) bid on the rights to deliver a load of goods from origin to destination in a distributed, cooperative auction and (ii) choose the rate of travel between customer locations. We create two populations of adaptive agents, each to address one of these necessary functions. By training each agent population in separate source domains, we use transfer learning to boost initial performance in the target FCP. This boost removes the need for 300 generations of agent training in the target FCP, though the source problem computation time was less than the computation time for 5 generations in the FCP. / Graduation date: 2012

This paper considers a real world waste collection problem in which glass, metal, plastics, or paper is brought to certain waste collection points by the citizens of a certain region. The collection of this waste from the collection points is therefore a node routing problem. The waste is delivered to special sites, so called intermediate facilities (IF), that are typically not identical with the vehicle depot. Since most waste collection points need not be visited every day, a planning period of several days has to be considered. In this context three related planning problems are considered. First, the periodic vehicle routing problem with intermediate facilities (PVRP-IF) is considered and an exact problem formulation is proposed. A set of benchmark instances is developed and an efficient hybrid solution method based on variable neighborhood search and dynamic programming is presented. Second, in a real world application the PVRP-IF is modified by permitting the return of partly loaded vehicles to the depots and by considering capacity limits at the IF. An average improvement of 25% in the routing cost is obtained compared to the current solution. Finally, a different but related problem, the so called multi-depot vehicle routing problem with inter-depot routes (MDVRPI) is considered. In this problem class just a single day is considered and the depots can act as an intermediate facility only at the end of a tour. For this problem several instances and benchmark solutions are available. It is shown that the algorithm outperforms all previously published metaheuristics for this problem class and finds the best solutions for all available benchmark instances.

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

Less-Than-Truckload (LTL) carriers generally serve geographical regions that are more localized than the inter-city routes served by truckload carriers. That localization can lead to urban freight transportation routes that overlap. If trucks are traveling with less than full loads there may exist opportunities for carriers to collaborate over such routes. That is, Carrier A will also deliver one or more shipments of Carrier B. This will improve vehicle asset utilization and reduce asset-repositioning costs, and may also lead to reduced congestion and pollution in cities. We refer to the above coordination as “collaborative routing”. In our framework for collaboration, we also propose that carriers exchange goods at logistics platforms located at the entry point to a city. This is referred to as “entry-point collaboration”. One difficulty in collaboration is the lack of facilities to allow transfer of goods between carriers. We highlight that the reduction in pollution and congestion under our proposed framework will give the city government an incentive to support these initiatives by providing facilities. Further, our analysis has shown that contrary to the poor benefits reported by previous work on vehicle routing with transshipment, strategic location of transshipment facilities in urban areas may solve this problem and lead to large cost savings from transfer of loads between carriers. We also present a novel integrated three-phase solution method. Our first phase uses either a modified tabu search, or a guided local search, to solve the vehicle routing problems with time windows that result from entry-point collaboration. The preceding methods use a constraint programming engine for feasibility checks. The second phase uses a quad-tree search to locate facilities. Quad-tree search methods are popular in computer graphics, and for grid generation in fluid simulation. These methods are known to be efficient in partitioning a two-dimensional space for storage and computation. We use this efficiency to search a two-dimensional region and locate possible transshipment facilities. In phase three, we employ an integrated greedy local search method to build collaborative routes, using three new transshipment-specific moves for neighborhood definition. We utilize an optimization module within local search to combine multiple moves at each iteration, thereby taking efficient advantage of information from neighborhood exploration. Extensive computational tests are done on random data sets which represent a city such as Toronto. Sensitivity analysis is performed on important parameters to characterize the situations when collaboration will be beneficial. Overall results show that our proposal for collaboration leads to 12% and 15% decrease in route distance and time, respectively. Average asset utilization is seen to increase by about 5% as well.

Less-Than-Truckload (LTL) carriers generally serve geographical regions that are more localized than the inter-city routes served by truckload carriers. That localization can lead to urban freight transportation routes that overlap. If trucks are traveling with less than full loads there may exist opportunities for carriers to collaborate over such routes. That is, Carrier A will also deliver one or more shipments of Carrier B. This will improve vehicle asset utilization and reduce asset-repositioning costs, and may also lead to reduced congestion and pollution in cities. We refer to the above coordination as “collaborative routing”. In our framework for collaboration, we also propose that carriers exchange goods at logistics platforms located at the entry point to a city. This is referred to as “entry-point collaboration”. One difficulty in collaboration is the lack of facilities to allow transfer of goods between carriers. We highlight that the reduction in pollution and congestion under our proposed framework will give the city government an incentive to support these initiatives by providing facilities. Further, our analysis has shown that contrary to the poor benefits reported by previous work on vehicle routing with transshipment, strategic location of transshipment facilities in urban areas may solve this problem and lead to large cost savings from transfer of loads between carriers. We also present a novel integrated three-phase solution method. Our first phase uses either a modified tabu search, or a guided local search, to solve the vehicle routing problems with time windows that result from entry-point collaboration. The preceding methods use a constraint programming engine for feasibility checks. The second phase uses a quad-tree search to locate facilities. Quad-tree search methods are popular in computer graphics, and for grid generation in fluid simulation. These methods are known to be efficient in partitioning a two-dimensional space for storage and computation. We use this efficiency to search a two-dimensional region and locate possible transshipment facilities. In phase three, we employ an integrated greedy local search method to build collaborative routes, using three new transshipment-specific moves for neighborhood definition. We utilize an optimization module within local search to combine multiple moves at each iteration, thereby taking efficient advantage of information from neighborhood exploration. Extensive computational tests are done on random data sets which represent a city such as Toronto. Sensitivity analysis is performed on important parameters to characterize the situations when collaboration will be beneficial. Overall results show that our proposal for collaboration leads to 12% and 15% decrease in route distance and time, respectively. Average asset utilization is seen to increase by about 5% as well.