Methods for the solution of a priori traveling salesman problems
| dc.creator | Rojanasoonthon, Siwate | |
| dc.date.accessioned | 2016-11-14T23:25:53Z | |
| dc.date.available | 2011-02-18T21:56:01Z | |
| dc.date.available | 2016-11-14T23:25:53Z | |
| dc.date.issued | 1990-12 | |
| dc.degree.department | Industrial and Systems Engineering | en_US |
| dc.description.abstract | The objective of this research is to develop a heuristic method that produces a good solution to probabilistic traveling salesman problem (PTSP). The probability of requiring a service for each customer was allowed to be different from one customer to another (nonhomogeneous customers). An a priori tour approach to PTSP was adopted in this research. Heuristics for generating a basic sequence were developed, evaluated, and compared. First, a tour building algorithm using an insertion method was proposed. Next, an algorithm, modified from nearest neighbor algorithm and a branch and bound algorithm by Berman and Simchi-Levi (1986a) which is the only exact algorithm available were introduced. Also, the sequences generated by nearest neighbor algorithm and the optimal solution to the deterministic traveling salesman problem were used as a basic sequence for PTSP. Expected tour length values of basic sequences from these algorithms and computation times required by the algorithms were compared. All the algorithms were coded in the C programming language. Eight sizes of randomly generated problems which were 5-, 7-, 10-, 15-, 20-, 30-, 40-, and 50-node problems were used for the evaluation of the algorithms. The most important result of this research is the discovery of the inserting algorithm which produces a good basic sequence in a very small amount of time. This algorithm is very easy to apply. It can be used to improve the performance of Berman and Simchi-Levi's algorithm by using the heuristic solution as a trial solution in the branch and bound steps. | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/2346/17223 | en_US |
| dc.language.iso | eng | |
| dc.publisher | Texas Tech University | en_US |
| dc.rights.availability | Unrestricted. | |
| dc.subject | Traveling-salesman problem | en_US |
| dc.title | Methods for the solution of a priori traveling salesman problems | |
| dc.type | Thesis |