Abstract
The traveling salesman problem with precedence constraints (TSPPC) is one of the most difficult combinatorial optimization problems. In this paper, an efficient genetic algorithm (GA) to solve the TSPPC is presented. The key concept of the proposed GA is a topological sort (TS), which is defined as an ordering of vertices in a directed graph. Also, a new crossover operation is developed for the proposed GA. The results of numerical experiments show that the proposed GA produces an optimal solution and shows superior performance compared to the traditional algorithms.
| Original language | English |
|---|---|
| Pages (from-to) | 606-617 |
| Number of pages | 12 |
| Journal | European Journal of Operational Research |
| Volume | 140 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 2002 Aug 1 |
| Externally published | Yes |
Keywords
- Genetic algorithm
- Optimization
- Topological sort
- Traveling salesman problem with precedence constraints
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research
- Information Systems and Management