Back to search

University of Southampton

Vehicle Routing and Scheduling with Synchronisation, Time Windows and Skill Levels with Applications in Lifeboat Maintenance

Abstract

dc:description.abstract

The Vehicle Routing Problem (VRP) is one of the most widely studied problems in Operational Research, due both to its complexity and vast number of possible variations and applications. In this thesis we present one such variation of the VRP with synchronisation, time windows and skill levels, designed for the application in the routing of lifeboat maintenance technicians in the Royal National Lifeboat Institution (RNLI), the largest coastal lifesaving charity in the UK. These technicians work in one of several geographical divisions and complete a mixture of planned work, known up to six months in advance, and unplanned work in response to equipment fault and failure which may<br/>need to be completed within as little as 48 hours. The objective is to produce routes of minimum cost for these technicians such that all jobs are completed within their respective time window by a technician (or pair of technicians) with the appropriate skill level, and where jobs are completed by two technicians their routes are synchronised to enable them to work together on a job with minimal time spent waiting. The contributing costs include travel, nights away for technicians working far from home and the costs incurred through lateness of jobs.<br/><br/>We formulate an integer program and propose a matheuristic algorithm, comprised of Lagrangian relaxation, brancn and bound and a local search heuristic, to solve the formulation at a divisional level across one or two weeks. We are able to prove that the iii subgradient method used with Lagrangian relaxation achieves a good lower bound after just one iteration, which provides an initial solution on which to base the local search heuristic used to find further improvements. We show that this approach achieves usable solutions within a number of minutes, a time which is sufficient for such a method to be implemented by those responsible for technician planning at the RNLI. Such short computation times also allow for the inclusion of unplanned jobs at short notice, as the problem can be resolved with the remaining jobs in a planning period to produce new routes.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Walton, Ruth
Advisor dc:contributor.advisor
  • Coniglio, Stefano
ORCID person:identifier.orcid

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Walton, Ruth. Vehicle Routing and Scheduling with Synchronisation, Time Windows and Skill Levels with Applications in Lifeboat Maintenance. doctoral thesis, University of Southampton, 2021.