The sector design and assignment problem for snow disposal operations

Winter road maintenance operations involve a host of decision-making problems at the strategic, tactical, operational, and real-time levels. Those operations include spreading of chemicals and abrasives, snow plowing, loading snow into trucks, and hauling snow to disposal sites. In this paper, we present a model and two heuristic solution approaches based on mathematical optimization for the problem of partitioning a road network into sectors and allocating sectors to snow disposal sites for snow disposal operations. Given a road network and a set of planned disposal sites, the problem is to determine a set of non-overlapping subnetworks, called sectors, according to several criteria related to the operational effectiveness and the geographical layout, and to assign each sector to a single snow disposal site so as to respect the capacities of the disposal sites, while minimizing relevant variable and fixed costs. Our approach uses single street segments as the units of analysis and we consider sector contiguity, sector balance and sector shape constraints, hourly and annual disposal site capacities, as well as single assignment requirements. The resulting model is based on a multi-commodity network flow structure to impose the contiguity constraints in a linear form. The two solution approaches were tested on data from the city of Montreal in Canada.