Robust salting route optimization using evolutionary algorithms

In winter, roads need to be salted and gritted when temperature drops to around the freezing point, in order to ensure the safety of road users (especially motor vehicles). In the UK, there are approximately 3000 salting routes covering about 120,000km (approximately 30% of the road network). Given limited resources and severe time constraints, it is imperative that salting routes are planned in advance for efficient and effective treatment. Unfortunately, there is no automatic route optimization system for salting trucks that can deal with different road conditions and constraints. Almost all published systems make unrealistic assumptions that do not hold in practice. This chapter describes a novel route optimization system based on newly proposed memetic algorithms. The system is designed with dynamic problems in mind. That is, given different road temperatures and different temperature distributions in a road network, the system can produce optimised routes for a fleet of salting trucks. The system has been evaluated using real world data from the South Gloucestershire council in England and obtained 10% improvement over their existing solution in terms of distances travelled by the salting trucks. © Springer-Verlag Berlin Heidelberg 2007.