4
$\begingroup$

I have an industrial problem which I'm trying to cast as a Traveling Salesman problem (TSP) in 3D euclidian space. There are physical limitations which implies that some subpaths may or may not be valid based on simple rules.

What algorithm is best to deal with the TSP given that there are rules/model/constraints?

It could be done with Genetic algorithms for example, but the only way i see how to incorporate those rules is by including them somehow within the fitness function. But i feel there should be more suitable approaches.

Would reinforcement Q-learning or other algorithms be more appropriate for a rule-based euclidian TSP?

Improve this question
$\endgroup$
2
  • $\begingroup$ Probably depends if those rules mean you have O(nodes) recognition, O(nodes) neighbor generation, O(nodes) solution generation, or something else. (I say O(n) but I mean comparative complexity in general) $\endgroup$
    – Harrichael
    Aug 11, 2017 at 15:11
  • 2
    $\begingroup$ How many nodes does a typical problem have? Did you consider heuristics tailored to the specific problem? $\endgroup$
    – BKE
    Dec 17, 2017 at 13:25

1 Answer 1

Reset to default
-1
$\begingroup$

If you have lots of rules then you should be able to come up with lots of heuristics for A*. If I were you I would try A* first, and come up with as many heuristics as I could. You can also use Deep Q learning. I don't think you want to just throw coordinates into a Deep Q network. You want a simpler representation. I would probably give the nodes symbolic identifiers like sparse matrices, integers or sigmoids, and then craft the loss function to reflect the actual cost of moving from node to node and ascribe a high cost to illegal moves.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .