I’m working on an assignment in my CS class and the gist of the problem is as follows.
A salesman has a map of some apartments (over 300 blocks). I am given the (x,y) coordinates of each block as well as the “money” he will earn by visiting each block. I need to find the shortest route for the salesman to take such that he will earn x amount of money. He does not have to visit all the blocks. At the end of the day he will have to return to the origin (0,0).
I used a greedy algorithm by finding the shortest possible path he can take at each step. E.g from the origin I find the block with the lowest euclidean distance from the origin. Lets say this block is (2,2). I then find the block with the lowest euclidean distance from (2,2) until I have x amount of money. Using this greedy algorithm I then performed a 2-opt local search to improve my solution further.
The problem lies here though: when I perform a 3-opt local search using the implementation from wikipedia (https://en.wikipedia.org/wiki/3-opt), I get a much worse result than either the greedy or the 2-opt. Is there something wrong with the wiki code and if not, what did I do wrong? Thanks.