EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3864. Lagrangian and Other Relaxations for the Urban Snow Removal Problem

Invited abstract in session TB-64: Arc Routing, stream VeRoLog - Vehicle Routing and Logistics.

Tuesday, 10:30-12:00
Room: S16 (building: 101)

Authors (first author is the speaker)

1. Kaj Holmberg
Optimization, Mathematics, Linkoping University
2. Roghayeh Hajizadeh
Department of Mathematics, Linköping University

Abstract

Snow removal problem in cities is a challenging task in nordic countries. Doing the snow removal efficiently is important. Since the amounts of snow vary a lot from day to day, and from year to year, fixed plans are not the best. Optimization of the snow removal tours could save much time and money.

We study the multi-vehicle urban snow removal problem from a mixed integer programming perspective. It is a very hard problem, and obtaining the exact optimum seems to be out of reach. Therefore, we study relaxations of the problem. Our goal is simply to find the best bounds for the optimal objective function value that is possible in limited time.

Since the problem has many sets of constraints with complicated structures, using Lagrangian relaxation might be beneficial. 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.

Extensive computational tests show that the lower and upper bounds can be improved.

Keywords

Status: accepted

Back to the list of papers