# Finding Optimal Route using different Paths

I have a list of paths e.g. path 1 takes you from point A to B. A person needs to complete 5 of such paths. $$Route1 = path1 + path2 + path3 + path4 + path5$$

Objective:

$$Min: D(endP1,startP2) + D(endP2,startP3) + D(endP3,startP4) + D(endP4,startP5)$$

Where $$D(endP1, startP2)$$ represents the distance between the start point of path 2 and the end point of path 1.

Constraints:

1. Except for the first path starting point for the next path and the ending point of the first path should be within 100 meters distance. E.g. In a route, there would be 5 paths. So the starting point of path 2 and the ending point of path 1 should be within 100 meters. Similarly, the starting point of path 3 and the ending point of path 2 should be within 100 meters so on and so forth.

2. The ending point of the last path and the starting point of the 1st path should be within 100 meters.

3. Each path takes a certain time to complete, so the next path should start at least 5min after the end time of the previous path.

4. The same path should not exist in more than 1 route.

I need to find possible routes where the objective is minimised.

Available Data:

1. List of paths
2. Start Time & End time of Path.
3. Start and the end point latitude & longitude.
4. Total distance for the path. (I think that won't be useful to solve the problem)

I need to formulate this problem and know possible techniques that can be applied to solve this problem, with working examples & readings.

I need to find a list of unique routes that would contain 5 paths such that any of the path is not repeated in more than 1 route.

Edit:

Objective $$Min: \sum D(S_i,E_{i-1}) \space i \in \{2,3,4,5\}$$ where $$S_i$$ is start point of path $$i$$ & $$E_{i-1}$$ is end point of path $$i-1$$.

Constraints: $$\sum P_i = 5$$ where: $$\sum P_i = \cases{0, if \space path \space not \space selected \cr 1, if \space path \space selected} \space i \in Z^+$$

$$D(S_i,E_{i-1}) \le 100 \space i \in \{2,3,4,5\}$$ $$D(E_5,S_1) \le 100$$ $$S_{t,i} - E_{t,i-1} >= 15 \space \forall \space t \in T, \space i \in \{2,3,4,5\}$$

I've formulated my first 3 constraints, I can't figure out how would the last constraint would be formulated.

Then I need to know how such optimization problem can be solved. I know about simplex method but I don't think it will solve the problem.

A working example along with a method to solve such problem would be appreciated.

• Welcome to OR.SE! I would encourage you to edit your question and show what you have done (your formulation) and where you're stuck.
– EhsanK
Jul 15 '20 at 18:24