A branch‐and‐dive heuristic for single vehicle snow removal. Issue 4 (7th September 2020)

• Record Type: Journal Article
• Authors: Hajizadeh, Roghayeh; Holmberg, Kaj
• Is Part Of: Networks. Volume 76:Issue 4(2020)
• Page Start: 509
• Page End: 521
• Publication Date: 2020-09-07
• Subjects: arc routing -- asymmetric traveling salesman -- branch‐and‐bound -- heuristic -- precedences -- turning penalties; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21989
• Languages: English
• ISSNs: 0028-3045

Abstract

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.