dissertation · Summit (Simon Fraser University) · 2019

The quadratic shortest path problem

Cited by 0Open access

Abstract

Quadratic Shortest Path Problem (QSPP) is a variation of the Shortest Path problem, where the objective function is quadratic. In addition to a cost associated with each edge in a graph, there is a cost with each pair of edges in the graph. The cost of a path is the sum of the costs of each edge in the path and the quadratic costs for each pair of edges in the path. This makes the problem NP-hard. polynomial-time algorithms are known for restricted versions of QSPP, such as Adjacent-QSPP, where the quadratic cost is only considered between adjacent pairs of vertices in the path. Integer programs with different bounds have also been discussed for QSPP with non-negative cost matrices. In this thesis, we provide integer programs for solving QSPP with arbitrary cost matrices. We compare our formulation where sub-tours are eliminated with the well-known MTZ constraints with one where sub-tours are eliminated iteratively by introducing the violated constraints only. We also provide two heuristic polynomial time solutions to the QSPP, the Basic Algorithm and the Multi Start Algorithm. We compare the Multi Start Algorithm with solutions obtained from the integer programs with MTZ constraints and show that the Multi Start Algorithm is a good heuristic to QSPP.

Cite this paper

APA 7

Ali, S. (2019). The quadratic shortest path problem. Summit (Simon Fraser University).

MLA 9

Ali, Salman. “The quadratic shortest path problem.” Summit (Simon Fraser University), 2019.

Chicago

Ali, Salman. 2019. “The quadratic shortest path problem.” Summit (Simon Fraser University).

Harvard

Ali, S. (2019) ‘The quadratic shortest path problem’, Summit (Simon Fraser University).

BibTeX

@phdthesis{ali2019quadratic,
  title = {{The quadratic shortest path problem}},
  author = {Ali, Salman},
  school = {Summit (Simon Fraser University)},
  year = {2019}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.