1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Clarification question: when you say "only use the k-th shortest path", do you mean that literally (use the k-th shortest path but not any shorter paths), or do you mean use the k shortest paths (shortest, second shortest, ..., up to k-th shortest)? $\endgroup$
    – prubin
    Apr 5, 2023 at 15:23
  • $\begingroup$ If you are thinking about a rider switching from the car driven by $d$ to the car driven by $d'$ at point $i$ (with $i$ presumably on both drivers' paths), you need to consider whether $d'$ passes through $i$ before $d$ arrives at $i.$ $\endgroup$
    – prubin
    Apr 5, 2023 at 15:25
  • $\begingroup$ @Prubin I meant using the k shortest paths (shortest, second shortest, ..., up to k-th shortest). sorry for the confusion. $\endgroup$
    – Rainbow
    Apr 5, 2023 at 15:46
  • $\begingroup$ @prubin With this variables is it even possible to force whether d′ passes through i before d arrives at i? Is there a good way to implicitly satisfy time and left roting to model only? Or modeling time effectively? $\endgroup$
    – Rainbow
    Apr 5, 2023 at 15:49
  • $\begingroup$ Is a driver limited to at most one rider? $\endgroup$
    – prubin
    Apr 5, 2023 at 18:29

2 Answers 2

0
$\begingroup$

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'.$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What is $P(i,r)$ the merged path from $i$? $\endgroup$
    – Rainbow
    Apr 5, 2023 at 21:45
  • $\begingroup$ Thank you very much @prubin This is very informaive. The difficulty to test this one is how to come up with $\alpha$ efficiently. The algorithem that looks into each nodes and their time and wants to put the value in $\alpha$ is quite costly (based on what I think on using loops) $\endgroup$
    – Rainbow
    Apr 5, 2023 at 22:32
  • $\begingroup$ @Rainbow Yes, merged path $\endgroup$ Apr 5, 2023 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.