Snow plow routing problem
{{Short description|Application of Arc- and Vehicle Routing Problems to snow removal}}
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.{{Cite web |last=Omer |first=Masoud |date=2007 |title=Efficient routing of snow routing of snow removal vehicles |url=https://researchrepository.wvu.edu/cgi/viewcontent.cgi?article=5362&context=etd}} Snow plow problems consider constraints such as the cost of plowing downhill compared to plowing uphill.{{Cite journal |last1=Dussault |first1=Benjamin |last2=Golden |first2=Bruce |last3=Wasil |first3=Edward |date=October 2014 |title=The downhill plow problem with multiple plows |url=https://www.tandfonline.com/doi/full/10.1057/jors.2013.83 |journal=Journal of the Operational Research Society |language=en |volume=65 |issue=10 |pages=1465–1474 |doi=10.1057/jors.2013.83 |s2cid=36977043 |issn=0160-5682|url-access=subscription }} The Mixed Chinese Postman Problem is applicable to snow routes where directed edges represent one-way streets and undirected edges represent two-way streets.{{Cite book |last=Corberán |first=Ángel |title=Arc Routing: Problems, Methods, and Applications |year=2015 |isbn=978-1-61197-366-2}}
Background
The routing and scheduling of snow removal vehicles is an important topic for transportation planners and operation researchers{{Cite journal |last1=Bodin |first1=Lawrence |last2=Golden |first2=Bruce |date=Summer 1981 |title=Classification in vehicle routing and scheduling |url=https://onlinelibrary.wiley.com/doi/10.1002/net.3230110204 |journal=Networks |language=en |volume=11 |issue=2 |pages=97–108 |doi=10.1002/net.3230110204|url-access=subscription }} 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.