Counting feasible solutions of the traveling salesman problem with pickups and deliveries is #P-complete.
Gerardo BerbegliaGena HahnPublished in: Discret. Appl. Math. (2009)
Keyphrases
- traveling salesman problem
- feasible solution
- vehicle routing problem
- valid inequalities
- tabu search
- optimization problems
- benchmark instances
- objective function
- combinatorial optimization
- ant colony optimization
- linear programming
- optimal solution
- linear programming relaxation
- metaheuristic
- hamiltonian cycle
- solution space
- traveling salesman
- mixed integer
- solution quality
- mathematical model
- lagrangian relaxation
- convex hull
- travel time
- crossover operator
- integer solution
- transportation networks
- lp relaxation
- knapsack problem
- genetic algorithm
- neural network