Salesman problem with additional conditions and features
I couldn't tell for sure if it is applicable without seeing the exact program, but you could look into constraint programming for a solution. 

Constraint programming aims to find the best solution to an optimization problem with a series of constraints, which can be hard or soft. Hard constraints rule out a possible solution (for example, no more than 10 hours drive on the same day), while soft constraints would dictate which of the remaining solution is the best, for instance awarding points for staying the night in cities with good acommodation, or having roughly the same amount of miles every day.

Constraint programming is based on backtracking, so it doesn't scale well at all for problems with many possible solutions, so it might not be for you. Worth taking a look at at least. Hope it helps!