| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 1.2 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
Consider a depot, a partition of the set of nodes into subsets, called families, and a cost matrix. The objective of the family traveling salesman problem (FTSP) is to find the minimum cost circuit that starts and ends at the depot and visits a given number of nodes per family. The FTSP was motivated by the order picking problem in warehouses where products of the same type are stored in different places and it is a recent problem. Nevertheless, the FTSP is an extension of well-known problems, such as the traveling salesman problem.
Since the benchmark instances available are in small number we developed a generator, which given a cost matrix creates an FTSP instance with the same cost matrix. We generated several test instances that are available in a site dedicated to the FTSP.
We propose several mixed integer linear programming models for the FTSP. Additionally, we establish a theoretical and a practical comparison between them. Some of the proposed models have exponentially many constraints, therefore we developed a branch-and-cut (B&C) algorithm to solve them. With the B&C algorithm we were able to obtain the optimal value of open benchmark instances and of the majority of the generated instances.
As the FTSP is an NP-hard problem we develop three distinct heuristic methods: a genetic algorithm, an iterated local search algorithm and a hybrid algorithm. With all of them we were able to improve the best upper bounds available in the literature for the benchmark instances that still have an unknown optimal value.
We created a new variant of the FTSP, called the restricted family traveling salesman problem (RFTSP), in which nodes from the same family must be visited consecutively. We apply to the RFTSP the methods proposed for the FTSP and develop a new formulation based on the interfamily and the intrafamily relationships
Description
Keywords
Family traveling salesman problem Multicommodity flow Projections Branch-andcut algorithm Metaheuristics