# Finding Optimal Route using different Paths

Operations Research Asked by Daniel on July 24, 2020

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.

## Related Questions

### How to optimize a utility function that contains step function?

1  Asked on January 5, 2022

### How to display the range of coefficients in docplex log?

1  Asked on January 1, 2022 by ehsank

### Scenario based approach to value-at-risk optimization using mixed-integer programming

1  Asked on January 1, 2022

### Multiple Knapsacks with splitting

1  Asked on December 20, 2021 by cesar-canassa

### How to balance the workload of teachers in OR-Tools (maximization of the minimum)

1  Asked on December 18, 2021 by neverletgo

### How to linearize a quadratic constraint to add it then via a callback function

2  Asked on December 9, 2021 by farouk-hammami

### Decision variable transformation in Gurobi

2  Asked on December 5, 2021

### Possibility of indexing decision variables with 2 indices using a set of tuples in Pyomo

3  Asked on November 24, 2021

### View of Constraints and Decision Variables in Pyomo

1  Asked on November 17, 2021

### CPLEX Python API Manual with References

1  Asked on November 4, 2021

### Are Python and Julia used for optimization in industry?

15  Asked on August 19, 2021

### How to improve the quality of code in OR?

3  Asked on August 19, 2021

### How would you characterize “optimization data?”

4  Asked on August 19, 2021 by marco-lbbecke

### Local optimum of dual of non-linear program

2  Asked on August 19, 2021

### Combinatorial Optimization using AMPL

2  Asked on August 19, 2021 by user3831

### Parallel nonlinear solvers

3  Asked on August 19, 2021 by josh-allen

### Tips on How to Review Operations Research Literature Effectively?

2  Asked on August 19, 2021 by ehsan

### Polynomially solvable cases of zero-one programming

1  Asked on August 19, 2021

### Error evalution for linear fits

1  Asked on August 19, 2021 by jane