Linear programming of vehicle routing

Question

Need help for linear programming of vehicle routing problem. In vehicle routing problem (VRP), a vehicle will serve a set of nodes such that the total travelling cost is minimized. My decision variable is:Xij=1 if node j is visited after node i. The parameter dij is the distance between nodes i and j. So, the model is as follows:

note that the vehicle starts a tour from the warehouse (node number 0) and finally returns to the warehouse (constraints 11 and 12). All the nodes should be visited (constraint 13), and when entering a node, it should leave that node (constraint 14). But, when I solve this in cplex for a large number of nodes, sometimes the solution is invalid because of loops like this one:

In case of this solution, all the constraints are satisfied but this solution is not valid because the routes are not connected. Now, my question is what constraint I should add to complete the model.

Answer 1

As @Erwin mentioned, you need to add subtour elimination constraints. Briefly:

1. Solve the problem.
2. Analyse the solution. If there are no subtours then the solution is optimal. Otherwise, add constraints on the subtours that you have to the original problem (in your example, x_01+x_12+x_20 <= 2 and x_34+x_45+x_53 <= 2). Go to 1.