Moments over the solution space of the travelling salesman problem

Sutcliffe, PJ

Moments over the solution space of the travelling salesman problem

Sutcliffe, PJ

Permalink

Publication Type:: Thesis
Issue Date:: 2009

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download contents and abstractAdobe PDF (74.42 kB)

Adobe PDF

Download thesisAdobe PDF (1.89 MB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Sutcliffe, PJ
dc.date.accessioned	2010-08-06T06:44:26Z
dc.date.accessioned	2012-12-15T03:53:16Z
dc.date.available	2010-08-06T06:44:26Z
dc.date.available	2012-12-15T03:53:16Z
dc.date.issued	2009
dc.identifier.uri	http://hdl.handle.net/10453/20302
dc.description	University of Technology, Sydney. Faculty of Engineering and Information Technology.
dc.description.abstract	In this thesis we consider the statistical properties of the symmetric travelling salesman problem (TSP). Previous work on the statistical properties of the problem has been largely limited to the Euclidean case with vertex coordinates as random variables with known distribution embedded in Rd, and to the case of independent identically distributed random edge costs. Furthermore, this previous work did not extend to computing the moments, beyond the mean. In the work presented here we consider the more general case of problem instances specified as a set of edge costs and with no (known) embedding or coordinate system available. For an instance of the problem on n vertices with fixed edge costs we give constructive proofs that the population variance of tour costs over the solution space can be computed in O(n2), the third central moment can be computed in O(n4) and the fourth central moment can be computed in O(n6). These results provide direct methods to compute the moments about the origin and factorial moments of these orders with the corresponding computational complexity. In addition the results provide tractable methods to compute, among other statistics, the standard deviation of tour costs, the skewness of the probability distributions of tour costs over the solution space and kurtosis of this distribution. In the case of the stochastic TSP with edge costs defined as independently distributed random variables with (not necessarily identical) known mean and variance we provide a O(n4) algorithm to compute the variance of tour costs. Given a subgraph S of a tour in an n city TSP, we provide an O(n2) algorithm to compute the expected tour costs over the solution space of those tours containing S. This is useful in analysing and constructing algorithms such as Gutin's greedy expectation heuristic. We demonstrate that the probability distribution of gains over the 2-opt landscape of an n city TSP can be computed in O(n4 log(n)). This result provides a tractable algorithm to compute, among other statistics the moments of gains over the landscape. The result also provides the 2-opt neutrality (the number of neighbouring solutions with identical cost) of a instance. The result has natural generalisation to the 3-opt landscape (at higher computational complexity). We relate the variance of tour costs over the solution space to that of the gains over the 2-opt landscape of a problem, providing an O(n2) method to compute the variance of gains over the landscape. We apply our method to compute the low order moments of the distribution of tour costs to several empirical studies of the solution space. Among other results we: con¯rm the known relationship between the standard deviation of tour costs and the optimal tour cost; we show a correlation between the skewness and the optimal tour cost; we demonstrate that the moments can be used to estimate the complete probability distribution of tour costs.	en
dc.format	Thesis (PhD)	en
dc.language.iso	en	en
dc.relation	https://opus.lib.uts.edu.au/bitstream/10453/20302/2/02Whole.pdf
dc.relation.replaces	http://hdl.handle.net/2100/1128
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.rights	au.edu.uts.lib/ppc
dc.subject	Combinatorial analysis.	en
dc.title	Moments over the solution space of the travelling salesman problem	en
dc.type	Thesis
utslib.copyright.status	open_access

Abstract:

In this thesis we consider the statistical properties of the symmetric travelling salesman problem (TSP). Previous work on the statistical properties of the problem has been largely limited to the Euclidean case with vertex coordinates as random variables with known distribution embedded in Rd, and to the case of independent identically distributed random edge costs. Furthermore, this previous work did not extend to computing the moments, beyond the mean. In the work presented here we consider the more general case of problem instances specified as a set of edge costs and with no (known) embedding or coordinate system available. For an instance of the problem on n vertices with fixed edge costs we give constructive proofs that the population variance of tour costs over the solution space can be computed in O(n2), the third central moment can be computed in O(n4) and the fourth central moment can be computed in O(n6). These results provide direct methods to compute the moments about the origin and factorial moments of these orders with the corresponding computational complexity. In addition the results provide tractable methods to compute, among other statistics, the standard deviation of tour costs, the skewness of the probability distributions of tour costs over the solution space and kurtosis of this distribution. In the case of the stochastic TSP with edge costs defined as independently distributed random variables with (not necessarily identical) known mean and variance we provide a O(n4) algorithm to compute the variance of tour costs. Given a subgraph S of a tour in an n city TSP, we provide an O(n2) algorithm to compute the expected tour costs over the solution space of those tours containing S. This is useful in analysing and constructing algorithms such as Gutin's greedy expectation heuristic. We demonstrate that the probability distribution of gains over the 2-opt landscape of an n city TSP can be computed in O(n4 log(n)). This result provides a tractable algorithm to compute, among other statistics the moments of gains over the landscape. The result also provides the 2-opt neutrality (the number of neighbouring solutions with identical cost) of a instance. The result has natural generalisation to the 3-opt landscape (at higher computational complexity). We relate the variance of tour costs over the solution space to that of the gains over the 2-opt landscape of a problem, providing an O(n2) method to compute the variance of gains over the landscape. We apply our method to compute the low order moments of the distribution of tour costs to several empirical studies of the solution space. Among other results we: con¯rm the known relationship between the standard deviation of tour costs and the optimal tour cost; we show a correlation between the skewness and the optimal tour cost; we demonstrate that the moments can be used to estimate the complete probability distribution of tour costs.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/20302