Back to search

University of Southampton

Routing products or people: single and multiobjective constrained shortest path and related problems

Abstract

dc:description.abstract

The aim of this thesis is to define, model and solve three research questions at the tactical and operational levels of decision making, the former arising in the context of intermodal service network design and the latter two in passenger transportation, by using integer programming, dynamic programming and heuristics. The first research question concerns intermodal freight transportation, which is concerned with the shipment of commodities from their origin to destination using combinations of transport modes. Traditional logistics models have concentrated on minimising transportation costs by appropriately determining the service network and the transportation routing. The first chapter considers an intermodal transportation problem with a detailed consideration of greenhouse gas emissions and intermodal transfers. Two mathematical models, one time-invariant and the other time-dependent, are described for the problem, which are both in the form of a non-linear integer programming formulation, but which are linearised. <br/><br/>A hypothetical but realistic case study of the UK forms the test instances for our investigation, where uni-modal with multimodal transportation options are compared using a range of fixed costs. The second and third research questions concern the multiobjective shortest path problem (MSPP) and the constrained multiobjective shortest path problem (CMSPP), extensions of the classical shortest path problem, with a wide range of practical applications particularly in passenger transportation. The second and third research questions are studied in two different chapters. The first of these presents several labelling algorithms for the MSPP and the CMSPP. Extensive testing is performed on different types of networks, including randomly generated and grid networks. The results show that label correcting algorithms are more efficient than label setting algorithms for solving both the MSPP and the CMSPP. The second of these two chapters proposes two fast local search algorithms for the MSPP. Four performance indicators are used to evaluate the local search solutions. Computational results demonstrate that local search algorithms are faster than all heuristic methods for the MSPP presented in literature, and able to produce reasonably good-quality solutions.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Qu, Yi
Advisor dc:contributor.advisor
  • Bektas, Tolga

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

Qu, Yi. Routing products or people: single and multiobjective constrained shortest path and related problems. doctoral thesis, University of Southampton, 2016.