Is it possible to route based only upon shortest path?

Question

I have a routing problem and am wondering if it is even possible to only use the $k^{th}$ shortest path? There are a set of people with cars and a set of other people with no cars, each has its own itinerary. We call them drivers (although they're not taxis), and riders. For all these people we know the k first shortest path (as if they have a car). I wanted to define a variable like $ x^{d,r}=1$ if $d$ is matched with $r$ and two other variables $y_k^r$ and $z_k^d$ take one if, respectively, $r$ and $d$ take their $k^{th}$ shortest path.

But this obviously won't work when there are no overlap between the $k^{th}$ shortest path of each people. Even if there was, how to cover cases when one rider wants to switch from one person to another?

In other words, how to merge the two shortest paths with each other? Is it possible? For example, following the 1st shortest path until point $i$ and then diverging to other possible shortest paths from $i$ onward.

I have searched and did not find a good formulation that only uses the shortest path. Is this because of inefficiency?

Answer 1

I'll define a possible model other than the objective function (which should not be hard to add). A key to the model is that we focus on paths rather than drivers. If the same physical path is one of the $k$ shortest paths for two different drivers, it is considered two different paths in the model.

Assumptions

1. We have a directed graph.

2. Each driver has a fixed origin and destination and will select one of the k shortest paths between their origin and destination (and not deviate from that path).

3. Each path visits every node at most once (paths do not contain loops).

4. Riders have fixed origins and destinations but are not limited to a fixed set of paths.

5. Drivers can carry multiple riders.

6. Driving times for all paths are known with reasonable accuracy.

7. The time to pick up or drop off a rider is negligible.

Sets

• $V$ is the set of vertices

• $E$ is the set of (directed) edges

• $D$ is the set of drivers

• $R$ is the set of riders

• $P_{d}$ is the set of the $k$ shortest paths for driver $d$

• $P=\cup_{d\in D}P_{d}$ is the set of all paths

Parameters

• $o(r)\in V$ is the origin node for rider $r\in R$

• $\delta(r)\in V$ is the destination node for rider $r\in R$

• $\alpha_{p,p',i}=1$ if path $p\in P$ enters node $i\in V$ no later than path $p'\in P$ leaves $i$ (0 if $p'$ leaves $i$ first or if either $p$ or $p'$ does not visit $i$ at all)

• $\alpha_{p,p,i}=1$

• $C_{p}$ is the maximum number of simultaneous riders allowed on path $p\in P$

Variables

• $x_{p}\in\left\{ 0,1\right\}$ is 1 if path $p\in P$ is used, 0 if not

• $y_{r,e,p}\in\left\{ 0,1\right\}$ is 1 if rider $r\in R$ crosses edge $e\in E$ on path $p\in P,$ 0 if not

Constraints

• Each driver selects exactly one of their k shortest paths:$$\sum_{p\in P_{d}}x_{p}=1\quad\forall d\in D$$

• No driver can carry more than the allowed number of riders on any portion of any path:$$\sum_{r\in R}y_{r,e,p}\le C_{p}\quad\forall p\in P,\forall e\in p$$

• A rider cannot cross an edge on a path that does not contain the edge:$$y_{r,e,p}=0\quad\forall r\in R,\forall p\in P,\forall e\in E\backslash p$$

• A rider cannot cross an edge via an unused path:$$y_{r,e,p}\le x_{p}\quad\forall r\in R,\forall p\in P,\forall e\in p$$

• Each rider leaves their origin exactly once:$$\sum_{e=(o(r),j)\in E}\ \sum_{p\in P:e\in p}y_{r,e,p}=1\quad\forall r\in R$$

• Each rider enters their destination exactly once:$$\sum_{e=(j,\delta(r))\in E}\ \sum_{p\in P:e\in p}y_{r,e,p}=1\quad\forall r\in R$$

• For any node other than their origin and destination, a rider exits the node the same number of times they enter it:$$\sum_{e=(i,j)\in E}\ \sum_{p\in P:e\in p}y_{r,e,p}=\sum_{e=(j,k)\in E}\ \sum_{p\in P:e\in p}y_{r,e,p}\quad\forall r\in R,\forall j\in V\backslash\left\{ o(r),\delta(r)\right\} $$

• A rider can transfer between paths only if the paths intersect at the transfer point and the path the rider is leaving gets to the transfer point before the path the rider is joining leaves the transfer point:$$y_{r,e,p}+y_{r,e',p'}\le1+\alpha_{p,p',i}$$ where the constraint is enforced $\forall r\in R,$ $\forall i\in V,$ $\forall e=(h,i)\in E,$ $\forall e'=(i,j)\in E,$ $\forall p\in P:e\in p$ and $\forall p'\in P:e'\in p'.$

Answer 2

You can try dynamic programming like
$ P(i,r) = min\{\sum_j d_{i,j}(y_{k}^r+z_{k}^d)+ P_{k+1}(j,r) \ \ \forall j \in (i,j)\}$
where $d$ is distance matrix from nodes $i$ to $j$ and
$ y_{k}^r+z_{k}^d \le 1$ and $P$ is the efficient merged path.