Optimizers are very good. Any "smart" change of the loss function will be equally smartly exploited by the optimizer.

Only way to optimize well is to include the uncertainty of your world model into the model.

For travelling salesman, you obviously want to model that certain roads take longer time to travel at different times of day. No tweak of the loss function would allow you to get realistic/robust solutions to TSP.