I am trying to find a linear program for the open Travelling Salesman Problem, where the salesman does not need to return to the starting point. More precisely, I have to do this with multiple possible depots and multiple salesmen (trucks).
The formulation for the non open version of the problem is the following (forget about the green box):
LP for closed multi depot vehicle routing problem:
N is the number of customers, M is the number of depots, K is the number of trucks. My idea was to delete constraint (3) and (4), because still every place needs to be visited, but not from all places a truck needs to leave. But when I put this in the solver, he gives me tours with subtours.
Why is that the case and/or are there other ways to solve this?
Best Answer
The easiest way to handle the Open TSP is to consider a regular TSP, and to change the cost function such that every arc to the depot has cost $0$. Keep all the constraints, and just change $c_{i,depot}=0$ for all nodes $i$.