Toward Automatic Customization of Vehicle Routing Systems

Abstract

This thesis was motivated by the desire to make the state-of-the-art vehicle routing problem models and algorithms more convenient for a non-expert to use. Currently, heavy customization is required whenever route optimization technology is adapted to solve new real-life routing problems. A critical part of this tailoring process involves choosing a suitable optimization algorithm and configuring its parameters; this requires developing a deep understanding of vehicle routing problems, their solution algorithms, and the software systems built around them. However, given that such information can be captured and represented as numerical feature values, machine learning can be used to find and exploit the patterns in the variation of algorithm performance. This dissertation proposes a framework for automating the customization of different components and data transformations within a vehicle routing system. This is accompanied by a comprehensive set of empirical experiments that were conducted to verify the feasibility of the proposed approach. As such, this dissertation furthers our understanding of the vehicle routing problem instances, algorithms, and their search spaces. It also provides suggestions and evidence on how to effectively use the automatic algorithm configuration and algorithm selection techniques in an automated vehicle routing system customization context. The findings of this work indicate that meta-optimization is a promising approach that allows more convenient and effective use of existing tools and techniques for solving vehicle routing problems. Overall, logistics plays a major role in modern society, which has made vehicle route optimization an important application of combinatorial optimization. The approach developed in this dissertation can reduce the friction in customization and deployment of optimization systems, thus allowing moving toward more economical, cost-effective, and environmentally friendly road transportation. Keywords: vehicle routing problem, meta-optimization, automatic algorithm configuration, algorithm selection, feature selection