Snow plow routing problem

The snow plow routing problem is an application of the structure of Arc Routing Problems (ARPs) and Vehicle Routing Problems (VRPs) to snow removal that considers roads as edges of a graph.

The problem is a simple routing problem when the arrival times are not specified. Snow plow problems consider constraints such as the cost of plowing downhill compared to plowing uphill. The Mixed Chinese Postman Problem is applicable to snow routes where directed edges represent one-way streets and undirected edges represent two-way streets.

Background

The routing and scheduling of snow removal vehicles is an important topic for transportation planners and operation researchers This set of problems is part of a larger field of problems referred to as Arc Routing Problems, which is a subset of a larger field named Vehicle Routing Problems. Vehicle routing and scheduling include snow removal, a postman delivering the mail, meter reading to collect money for the city, school bus routing, garbage waste and refuse collection, and street maintenance.

Context

The snow removal problem is to clear a set roads in a minimum amount of time. The problem of snow vehicle routing incorporates higher salaries for vehicle drivers and high fuel costs and high costs of purchasing and maintaining snow vehicles. In the public sector, the objective is less often minimizing cost and more often maximizing safety and convenience, for example by reducing the number of left turns on major roads which are hazardous for vehicles to make.