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.
Minimal Arc Partitioning Problem: Formulation and Application in Snow Routing with Service Route Continuity
Transportation Research Record
Transportation Research Record: Journal of the Transportation Research Board ; 1882 , 1 ; 167-175
2004-01-01
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
British Library Conference Proceedings | 2004
|Snow Emergency Vehicle Routing with Route Continuity Constraints
Online Contents | 2002
|Snow Emergency Vehicle Routing with Route Continuity Constraints
Transportation Research Record | 2002
|Snow Emergency Vehicle Routing with Route Continuity Constraints
British Library Conference Proceedings | 2002
|