Optimization of Stochastic Vehicle Routing with Soft Time Windows

This dissertation, "Optimization of Stochastic Vehicle Routing With Soft Time Windows" by Zigang, Guo, 郭自剛, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled Optimization of Stochastic Vehicle Routing with Soft Time Windows submitted by GUO ZIGANG for the degree of Doctor of Philosophy at the University of Hong Kong in July 2006 Routing vehicles to service customers is an important and economically- significant component of many distribution systems. This study seeks to develop efficient methodologies to solve stochastic vehicle routing problems, so that distribution systems can be designed with more cost-effective delivery plans. The study considers a stochastic vehicle routing problem with soft time windows (SVRPSTW). This problem involves utilizing a fleet of vehicles with finite capacity to establish a set of minimum-cost vehicle routes for servicing a set of geographically scattered customers. All routes start and end at a central depot, while each customer is visited once by exactly one vehicle. Both the demand and the presence of a customer are stochastic. Each customer also has a corresponding "time window" defining the period in which it can be serviced. A vehicle arriving early has to wait until the window opens, while a vehicle arriving late is permitted to service the customer subject to an appropriate penalty. A new mathematical model is developed to describe the characteristics of the distribution system. The objective is to minimize the expected total cost associated with the number of vehicles employed, the total distance travelled to service the customers, the additional distance travelled due to ivroute failures, the penalty for violating time window constraints, and the cost-savings due to the omission of absent customers. The SVRPSTW is a complex combinatorial optimization problem which is NP- hard, and a genetic algorithm (GA) is proposed to address it. A novel heuristic edge- based crossover operator is proposed and incorporated in the GA, so that the crossover operation depends not only on the apparent contents of the parent chromosomes, but also some instance-specified information embedded in them. The algorithm performs well, and is used to establish a coarse-grained parallel GA to perform even better. A Tabu Search (TS) algorithm is also designed to solve the SVRPSTW. The algorithm is then combined with the aforementioned GA to develop a hybrid algorithm which is subsequently used to establish a parallel hybrid TS-GA. A distributed computing platform is developed to implement the parallel algorithms. Since no benchmark problems are available in the literature, the study also introduces an approach that can generate test problems for evaluating the performance of the algorithms. Indeed, results obtained from solving some randomly generated problems clearly show that the proposed parallel algorithms are efficient and robust optimization tools for solving the SVRPSTW. Sensitivity analyses are also performed to study the effects of the genetic parameters on the performance of the GA, the communication topology, the migration interval and size on the performance of the parallel GA, and the communication topology and the migration interval on the performance of the parallel hybrid TS-GA. The convergence characteristics of the parallel GA and the parallel hybrid TS- GA are also studied theoretically using the Markov chain model and the axiomatic model respectively. A common conclusion from both studies is that when the overall best candidate solution is maintained over time, the search processes eventually conv