CCE Theses and Dissertations

Campus Access Only

All rights reserved. This publication is intended for use solely by faculty, students, and staff of Nova Southeastern University. No part of this publication may be reproduced, distributed, or transmitted in any form or by any means, now known or later developed, including but not limited to photocopying, recording, or other electronic or mechanical methods, without the prior written permission of the author or the publisher.

Date of Award


Document Type

Dissertation - NSU Access Only

Degree Name

Doctor of Philosophy in Computer Science (CISD)


Graduate School of Computer and Information Sciences


Wei Li

Committee Member

Michael J. Lazlo

Committee Member

Junping Sun


The Tour Construction Framework (TCF) integrates both global and local heuristics in a complementary framework in order to efficiently solve the Travelling Salesman Problem (TSP). Most tour construction heuristics are strictly local in nature. However, the experimental method presented in this research includes a global heuristic to efficiently solve the TSP. The Global Path (GP) component and Super Node (SN) component comprise the TCF. Each component heuristic is tuned with one or more parameters. Genetic Algorithms (GA) are used to train the collection of parameters for the TCF components on subsets of benchmark TSPs. The GA results are used to run the TCF on the full TSP instances. The performance of the TCF is evaluated for speed, accuracy, and computational complexity, and it is compared against six mainstream TSP solvers: Lin-Kernighan-Helsgaun (LKH-2), 2-Opt, Greedy, Boruvka, Quick-Boruvka, and Nearest Neighbor. The empirical study demonstrates the effectiveness of the TCF in achieving near-optimal solutions for the TSP with reasonable costs.

To access this thesis/dissertation you must have a valid OR email address and create an account for NSUWorks.

  Contact Author

  Link to NovaCat