What you are solving is a variation of the traveling salesman problem. Specifically, what you are getting are called subtours, which is a closed path that involves fewer than all of the nodes (shops in your case.)
There are an exponential number of subtours for a given set of nodes. A huge body of literature exists around subtour elimination constraints. Fortunately, for smallish problems in practice, we can get away with adding subtour elimination constraints on an as needed basis.
Subtour Elimination
Here's the idea for how to eliminate a subtour S that involves s shops (s < num_stores):
In English: We start off by partitioning the set of nodes (shops) into two groups S and T. Let S be the set of shops in the subtour. Let T be the set of shops outside of S, i.e. all the other shops. We want to break the single-loop path which involves just the shops in S.
Pseudocode
Do while:
Solve the current problem
If you don't find any subtours, you are done. Exit.
If there are subtours, add the subtour elimination constraints (see details below)
Continue
Implementing a set of constraints to eliminate current subtour
For each subtour ("island") you have to first create a set of shops_in_subtour
. All the other nodes (shops) go into the other set (T) shops_not_in_subtour
Add the following to the your constraints set:
forall(s in shops_in_subtour)
forall(t in shops_not_in_subtour)
sum y[s,t] > = 1; // at least one edge must leave S and go to T
sum y[t,s] > = 1; // at least one edge must enter the set S from T
If your problem is small, you will see that adding a few of these sets of constraints will suffice. Hope that helps you move forward.
Update based on OP's follow-up question
How to Detect Subtours
You will check of the existence of subtours outside of CPLEX/Solver
Idea in English: You start from the origin shop and traverse the path, keeping track of each visited
shop. If you come back to the origin, and there are still some binary Y variables left, you have one or more subtours. (Technically, you can start from any shop, but starting from one is easier to understand.)
Initialize visited_shop = NULL;
Find the Yij that is 1. (Starting edge for the path)
Do while (There are more Y variables = 1 remaining)
Add the destination of the new binary variable to list of visited_shops
Check if you are done (are you back at shop 1):
if Yes:
If no more binary variables left, you are done. Exit.
If there are some more non-zero binary variables, subtour detected
if No:
pick the next Y variable whose origin is current Y_variable's destination
Continue