0
$\begingroup$

I am working through the Udemy course "Optimizing Travelling Salesman and Vehicle Routing Problems".

A part of the course is looking at Tabu search as a solution to the vehicle routing problem.

I am wondering whether the last line of code below might be a mistake - i.e. it seems to say that if the best result from the most recent neighbourhood search is not in the Tabu list, then we get rid of it in favour of the best solution so far. Should we not be doing the reverse?

# Aspiration Criteria
    if len(Save_Solutions_Here) >= 1:
        if Solution_in_Hand in Tabu_List: # If the solution is already in the tabu list
            while Solution_in_Hand[0] in Tabu_List[:,0]: # The distance of the solution is the same as one in the tabu list
                if Solution_in_Hand[0] < Best_So_Far[0]: # If it is less, then...
                    Solution_in_Hand = Best_So_Far # It becomes best so far
                    break # Then break
                else:
                    Solution_in_Hand = OF_Values_all_N_Ordered[t] # If it wasn't less, the current solution becomes what was chosen in the list
                    t = t+1 # Add one to move to the next element
        else:
            Solution_in_Hand = Best_So_Far # If solution was not in tabu list, the best so far becomes the current solution*****

Variables:

Save_Solutions_Here = saving the best solutions as the search iterates

Best_So_Far = the best of the best solutions as the search iterates

Solution_in_Hand = the best result from the current neighbourhood search

OF_Values_all_N_Ordered[t] = the t-best result from the current neighbourhood search

Tabu_List = the usual tabu list

Improve this question
$\endgroup$
6
  • $\begingroup$ The code is incomplete i have a hard time following, i don't even see where the objective gets called. Can you provide more code? $\endgroup$ Commented Feb 10, 2022 at 16:47
  • $\begingroup$ Add more code so we can help you $\endgroup$ Commented Feb 10, 2022 at 19:10
  • $\begingroup$ 95% of code added - all that is missing are functions that calculate # of route miles and penalties on the objective function for non-legal solutions. $\endgroup$ Commented Feb 10, 2022 at 21:53
  • $\begingroup$ Honestly, I find this code overly complex $\endgroup$ Commented Feb 11, 2022 at 23:01
  • 1
    $\begingroup$ I made 2 changes and seem now to have both good results and an intuitive algorithm: (1) reverse the operator in: if Solution_in_Hand[0] < Best_So_Far[0]: and (2) delete: else: Solution_in_Hand = Best_So_Far. I'll accept this as an answer if you would like to post it. $\endgroup$ Commented Feb 14, 2022 at 0:43

1 Answer 1

Reset to default
2
$\begingroup$

Your doubt is right: you should NOT go back to your best solution if the current solution is not in the tabu list. You should invert the if statement and see if the tabu search leads to better solutions. A nice summary including tips for the design of a tabu search is available here:

Gendreau, M. (2003). An Introduction to Tabu Search. In F. Glover & G. A. Kochenberger (Reds), Handbook of Metaheuristics (bll 37–54). doi:10.1007/0-306-48056-5_2 https://nats-www.informatik.uni-hamburg.de/pub/WS2020/HinweiseZurSeminararbeit/Gendreau-Potvin2019_Chapter_TabuSearch.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.