Lagrangian relaxation for the urban snow removal problem

Snow removal problem in cities is a challenging task in Nordic countries. The problem is finding optimal tours for a certain number of vehicles with some circumstances in order to clear a number of streets in a city. We have formulated the urban snow removal problem as a time-indexed mixed integer linear programming model which is huge and complicated. In our previous work, we studied the model and its different relaxations which show that the problem is not solvable in practice. Since the problem has many sets of constraints with complicated structures, relaxing them with Lagrangian relaxation might be beneficial. In this paper, we discuss different possibilities of relaxing sets of constraints and develop a Lagrangian heuristic which consists of a suitable Lagrangian relaxation of the problem, a subgradient optimization method for solving the Lagrangian dual, and procedures for obtaining feasible solutions. The heuristic has been implemented and applied to artificial and real life city networks. The results show that the bounds have been improved.

• Record URL:
  • http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-194246
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/03482960
• Authors:
  • Hajizadeh, Roghayeh
  • Holmberg, Kaj
• Publication Date: 2023

Language

• English

Media Info

• Pagination: 39
• Serial:
  • LITH-MAT-R
  • Issue Number: 2023/04
  • Publisher: Linköping University, Sweden
  • ISSN: 0348-2960

Subject/Index Terms

• TRT Terms: Calculation; Itinerary; Mathematical models; Optimization; Snow removal
• ITRD Terms: 6464: Calculation; 6473: Mathematical model; 6474: Optimisation; 699: Route (itinerary); 2542: Snow clearance
• Subject Areas: I62: Winter Maintenance;

Filing Info

• Accession Number: 01910116
• Record Type: Publication
• Source Agency: Swedish National Road and Transport Research Institute (VTI)
• Files: ITRD, VTI
• Created Date: Feb 27 2024 2:27PM