Back to search

University of Southampton

2-period travelling salesman problem

Abstract

dc:description.abstract

<p>The 2-period travelling salesman problem originates from the collection of milk from dairy farmers in County Dublin, Ireland. Specifically, a group of dairy farms is allocated to a milk tanker. Of these farms some require every day collection, and others require collection every other day. The problem is to identify two tours with a combined distance that is minimised such that each farm requiring collection every day is visited by both tours, and each farm requiring collection every other day is visited by exactly one tour.</p><p>Optimal solution procedures are developed for examples of the problem. These procedures are based on integer programming formulations. These formulations are solved directly for small problems. The solution of medium sized problems, up to 100 nodes, requires LP relaxation, subtour and comb constraints, and ultimately the solution of a considerably constrained {0, 1} model. The solution process identifies an important group of inequalities whose explicit presence in the model dramatically improves our ability to solve medium sized problems.</p><p>For problems with over 100 nodes the search time for an optimal solution becomes excessive. In these cases heuristic procedures, which provide good, but not necessarily optimal solutions, are used. A range of heuristic procedures are developed and empirically analysed. In the absence of an optimal answer, the heuristic solutions are compared with a lower bound on the optimal answer. Three classes of bounds are developed. The first class is based on increasingly constrained LP relaxations. The second class is based on an extension of the 1-tree concept. The third class is based on Lagrangian relaxation.</p>

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Butler, Martin Joseph

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

Butler, Martin Joseph. 2-period travelling salesman problem. doctoral thesis, University of Southampton, 1997.