Robust and Flexible Vehicle Routing Solutions Using Genetic Algorithms

摘要

Solutions of vehicle routing problems are generally implemented in a constantly changing environment. New customers may require service or existing customers may leave the customer list. Customer demand may change and traffic conditions may influence travel times. Most vehicle routing research however has focused exclusively on deterministic problems. Assuming that all input data can be known with perfect certainty in advance. however, is not a realistic assumption in many cases. The complexity of the vehicle routing problem, has led researchers to focus on deterministic variants of this problem and as a result, very little attempt is made to identify solutions that are robust and/or flexible. We define a robust solution to a vehicle routing problem as a solution that is relatively insensitive with regards to changes in the input variables. Two types of robustness can be distinguished: quality robustness and solution robustness, each having its own distinct properties. A solution is called quality robust if it remains close to optimal when changes in the input data occur. A solution is called solution robust if—after re-optimisation—the new solution is similar to the original solution. A solution is called flexible if it can be repaired efficiently to meet the requirements of changed input data. In this paper, we develop a general framework for finding robust and flexible solutions using meta-heuristic optimisation techniques. We apply this framework by modifying a hybrid genetic algorithm for the vehicle routing problem. The modified GA is shown to find solutions that are significantly more robust than solutions found with the unmodified GA. A distance measure is developed that is used to test the similarity of two VRP solutions.