A branch‐and‐dive heuristic for single vehicle snow removal

Authors:
Open Access
Publisher website
Google Scholar
Abstract
This paper deals with planning of a tour for a vehicle to clear a certain set of streets in a city of snow. Our previous results on the problem contain a heuristic based on reformulation to an asymmetric traveling salesman problem (ATSP) which yields feasible solutions and upper bounds, and a relaxation of a MIP model for obtaining lower bounds. The goal now is to try to improve the solutions and bounds. In this paper we describe a branch‐and‐dive heuristic which is based on branch‐and‐bound principles. We discuss how branching can be done so that the fixations can be utilized in both the relaxation and the ATSP model, and how the search for better solutions can be done. The heuristic has been implemented and applied to real life city networks. The method is shown to outperform two other heuristics for the ATSP with precedence constraints.
Funding Information
  • Vetenskapsrådet (2015‐04313)

This publication has 17 references indexed in Scilit: