TransWikia.com

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.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP