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