In all countries road maintenance is a time-consuming and costly process. In countries with heavy snowfall, winter road maintenance includes salt spreading, gritting, snow removal and snow disposal. Currently, most regions manually route their snowplows. Optimizing these processes can decrease expenditure by minimizing the time and the number of vehicles needed to maintain the roads during the winter season. Optimization can occur both during and after snowfall through resource allocation, routing and crew scheduling. During snowfall snowplows must plow continuously, whereas after snowfall snowplows return to their depots when the clearance of the routes is completed. This thesis looks at the case of routing snowplows after snowfall, specifically finding combinations of given routes which minimize the total cost.
Contents
1 Introduction
1.1 Background
1.2 Purpose
1.3 Delimitations
1.4 Outline of the Thesis
2 Problem Background
2.1 The Swedish Road Transport System
2.1.1 Standard Classes
2.2 Winter and Snow Removal in Sweden
2.2.1 Winter Maintenance Regulations
2.2.2 Cost of Winter Maintenance
3 The Case
3.1 The Operation District of Eskilstuna
3.2 The Network
3.3 Modifications of the Network
4 Theoretical Framework
4.1 Route Planning
4.1.1 The Vehicle Routing Problem
4.2 Set Covering Problem
4.2.1 Column Generation
4.3 Lagrangian Relaxation
4.3.1 Lagrangian Heuristics
4.4 Subgradient Optimization
4.5 Heuristic Solution Techniques
4.5.1 Heuristics
4.5.2 Greedy Heuristics
5 Mathematical Formulation
5.1 Indices
5.2 Parameters
5.3 Variables
5.4 The Primal Mathematical Model
5.5 The Lagrangian Relaxation
5.6 The Column Generation Subproblem
6 Solution Method
6.1 The Program
6.2 Algorithm CJ
6.2.1 Lagrangian Relaxation
6.2.2 Update Multipliers
6.2.3 Heuristic Procedure Greedy
7 Results
7.1 Initial Data and Parameters
7.2 Computational Results
8 Analysis
8.1 General Observations
8.2 The Routes
8.3 Allocation of Vehicles
8.4 Performance Guarantee
8.5 Potential Improvements
8.6 Results From Golbaharan’s Column Generation Approach
9 Conclusions and Further Research
9.1 Conclusions
9.2 Further Research
Bibliography
Author: Sochor, Jana,Yu, Cecilia
Source: Linköping University
Download URL 2: Visit Now