Minimal Arc Partitioning Problem: Formulation and Application in Snow Routing with Service Route Continuity

The present research deals with a special case of emergency truck routing for snow removal or salting (snow routing) in which the objective function is primarily to minimize the number of trucks and secondarily to minimize the number of deadhead miles while the snow network is salted as much as required and the trucks' salting capacity is not violated. An additional constraint requires each truck service route to be a connected network. This route continuity constraint helps avoid confusion for truck drivers. A three-phase approach to the problem is presented: first, minimize the number of trucks; second, balance the workloads; and third, find the best routes to minimize the number of deadhead miles. The minimal arc partitioning problem (MAP) is introduced as an abstraction of the first phase (minimization of the number of trucks). MAP is stated as determination of the minimal arc partitioning of a network so that each partition (subnetwork) constitutes a connected network and so that capacity constraints are satisfied. Balancing the trucks and routing them to each subnetwork are dealt with in the other phases. The approach is applied to a real-world snow emergency network, and the results are discussed. It is demonstrated that the number of trucks can be reduced by up to 15% and the number of deadhead miles can be reduced by up to 70% compared with the number of trucks and the number of deadhead miles with the current plan. In addition, the overall algorithm is quite fast.