search

graphhopper / jsprit

jsprit is a java based, open source toolkit for solving rich vehicle routing problems
https://www.graphhopper.com/open-source/
Apache License 2.0
1.62k stars 604 forks source link

implement simulated annealing #145

Closed yangyangyyy closed 9 years ago

yangyangyyy commented 9 years ago

I was trying to solve this problem https://github.com/yangyangyyy/tsp_problem/wiki

even given the help of regretInsertion, the current code couldn't find the correct (though simple) solution.

I tried to implement simulated annealing , and it works. this is a placeholder to clean out the code and formally put it into the repo.

the basic idea is that currently either BestInsertion or RegretInsertion always inserts a node in the position with the lowest incremental cost (RegretInsertion only changes the order to consider each candidate node, and the rest are the same as BestInsertion), instead of this fixed decision, simulated annealing changes that to be a probablistic decision, with a probability very random at first, and gravitating more towards the fixed decision as "temperature cools down"

oblonski commented 9 years ago

the meta-heuristic is simulated annealing like