No description available.

In this paper we propose a hybrid approach for solving vehicle routing problems. The main idea is to combine an Ant System (AS) with a problem specific constructive heuristic, namely the well known Savings algorithm. This differs from previous approaches, where the subordinate heuristic was the Nearest Neighbor algorithm initially proposed for the TSP. We compare our approach with some other classic, powerful meta-heuristics and show that our results are competitive. / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

In this project the optimization of transport planning has been studied. The approach was that smaller transport companies do not have the capability to fully optimize their transports. Their transport optimization is performed at a company level, meaning that the end result might be optimal for their company, but that potential for further optimization exists. The idea was to build a collaboration of transport companies, and then to optimize the transports globally within the collaboration. The intent was for the collaboration to perform the same driving assignments but at a lower cost, by using fewer vehicles and drivers, or travel shorter distance, or both combined. This should be achieved by planning the assignments in a smarter way, for example using a company's empty return journey to perform an assignment for another company. Due to the complexity of these types of problems, called Vehicle Routing Problem (VRP), shown to be NP-complete, search methods are often used. In this project the method of choice was a PDDL-based planner called LPG-td. It uses enforced hill-climbing together with a best-first search to find feasible solutions. The method was tested for scaling, performance versus another method and against time, as well as together with a real-life based problem. The results showed that LPG-td might not be a suitable candidate to solve the problem considered in this project. The solutions found for the collaboration were worse than for the sum of individual solutions, and used more computational time. Since the solution for the collaboration at most should be equal to the sum of individual solutions, in theory, this meant that the planner failed.

Thesis (Ph. D.)--Lehigh University, 2005. / Includes vita. Includes bibliographical references (leaves 184-192).

In this paper we present and analyze the application of an Ant System to the Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW). At the core of the algorithm we use an Insertion procedure to construct solutions. We provide results on the learning and runtime behavior of the algorithm as well as a comparison with a custom made heuristic for the problem. / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

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 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

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