| Abstract : | This dissertation is entitled \Optimization Methods for Complex Vehicle Routing and Scheduling problems". The term \optimization methods" refers to hybrid methodologies that combine heuristic and metaheuristic algorithms to produce effective and robust solution methods for combinatorial optimization problems. The term \complex" denotes the computational complexity and the large-scale nature of the problems considered. Finally, the term \vehicle routing and scheduling problems" describes a subclass of problems emanating from the broader family of Vehicle Routing Problems (VRP). The VRP is the problem of finding a set of optimal routes for a fleet of vehicles to serve a given set of customers. The vehicles are often assumed to have a common home base, called the depot. The cost of traveling between each pair of customers and between the depot and each customer is given. The goal is to find the optimum \assignment" and service \schedule" of customers for each vehicle route, such that the total traveling cost is minimized and all customers are served by exactly one vehicle. Typically the solution has to satisfy several other restrictions, such as total capacity of vehicles, route durations and other operational constraints. In this thesis, the term VRP is used to describe a broad class of problems and not a specific problem with a limited set of restrictions or constraints; thus, in the remainder of the thesis the term VRP includes all problems that involve creating one or more routes, starting and ending in one or more common depots or at predefined start and end terminals, in contrast to most archival literature where VRP is mainly used for the Capacitated Vehicle Routing Problem (CVRP). A subclass of VRPs is the Vehicle Routing Problem with Time Windows (VRPTW); this is the core problem studied in this thesis along with its variants. In the VRPTW, a desired visit time (time window) at each customer is given. Also, a number of additional constraints are often enforced, e.g. heterogeneous fleets of vehicles, open routes, multiple depots, etc. The VRPTW is a classical and well-studied vehicle routing problem. It is an NP-hard combinatorial optimization problem that has attracted the interest of both researchers and practitioners. For many of the problem instances considered in this thesis, the set of feasible solutions is so large that even if we had a computer that in a systematic way could construct and evaluate the cost of a trillion (1012) solutions per second, and we had started that computer right after the big bang, 14 billion years ago, it would still not have evaluated all the feasible solutions today. Consequently we have to resort to other methods and forget simple enumeration. Engineering and technology have been continuously providing examples of difficult optimization problems, with practical as well as theoretical importance. Optimization problems are concerned with the search for the \best" configuration of a set of variables to achieve some goals. A huge collection of optimization techniques has been suggested by several researchers from different fields; an immense number of refinements has made these techniques work for specific types of applications. All these procedures are based on some common ideas, which are being characterized by additional specific features. However, for most optimization problems no procedure is known, in general, to get directly an \optimal" solution. Three types of solution methods are typically employed to solve problems such as the VRPTW: Heuristics, Approximate Algorithms and Exact Methods. Heuristics are solution methods that relatively quickly can _nd a feasible solution with reasonable quality. Approximation algorithms are special heuristics that can provide a solution and an errorquality guarantee. Exact methods guarantee that the optimal solution is found subject to sufficient time and memory space. Although in recent years significant algorithmic achievements have been reached and highly sophisticated exact methods have been proposed, heuristics remain the only reliable and viable approach for the solution of practical large-scale instances. Towards this end, a special class of heuristics that has received special attention during the last two decades is the so-called metaheuristics. Such algorithms provide general frameworks for heuristics that can be applied to different problems, while high quality solutions are often obtained within reasonable computational burdens. This PhD thesis focuses on the exploration of the computational power of metaheuristics, not only in terms of solving effectively and efficiently the VRPTW and other real-life industrial variants of the problem in a limited amount of time, but also developing cooperative and competitive optimization methods that are characterized by simplicity, exibility and robustness. The problems studied have been inspired from real-world applications and the last part of the thesis describes the application of some of the solution methods developed in a real-life industrial environment.
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.