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?

$\endgroup$
  • $\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 '17 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 '17 at 13:25
-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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.