1
$\begingroup$

Suppose we have a transportation problem similar to pickup and delivery problems. So, we have a set of drivers and a set of passengers. each passenger has predefined origins and destinations. I'd like to know if we could compute the distance between a passenger's destinations and the drop-off nodes without having access to the solver's output.

Every riders could be picked-up and drooped-off by multiple drivers. And there's no particular order on nodes of the graph which is denoted by $N$.

We have a binary variables of $ x_{i,j}^{d,r}$ if driver $d$ drives $r$ on edge $(i,j)$ and we already know for each $r$ their start's $s_r$ and their destination's $d_r$ points ($s_r \in N$ and $d_r in N$). I'm wondering without knowing the path and values of variables from the solver how to minimize the objective as a distance between the last drop-off point and the destinations of each rider. Is this possible to compute this value implicitly and have it as an objective function or do we simply need more information?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Define binary $e_{i}^r,s_{i}^r$ as drop-off & pickup nodes for rider $r$.
Then assuming a rider $r$ is picked/dropped by same driver
$\sum_d(\sum_j x_{j,i}^{d,r} -\sum_jx_{i,j}^{d,r}) = e_{i}^r - s_{i}^r$

$ s_{i}^r+ e_{i}^r \le 1 \quad \forall i \ \forall r$: A node $i$ can either be origin/destination.

If you don't want to use $ s_i$ then (as used in another response by Dr. Rob)
$ 2e_{i}^r - 1 \le \sum_d(\sum_j x_{j,i}^{d,r} -\sum_jx_{i,j}^{d,r}) \le e_{i}^r$

Then distance is:
if $ d_r$ may either be a node or 2-D location coordinates, then every node $i$ will also have location coordinates. So predefine distance matrix to compute
$ \sum_r \sum_i dist_{d_r,i}e_{i}^r $

Improve this answer
$\endgroup$
10
  • $\begingroup$ @linkho yes they are binary variables. If drivers are changing, so summing over driver $d$ makes sense. This is what I have done to make it work because if you imagine a node $i$ with its edges over $j$, along that arc it should be 1 driver. Summing over drivers $d$, basically summing means 'any' driver, should make all incoming edges $\le 1$ & similarly outgoing edges $\le 1$. Then destination is always the node with only incoming edge, no outgoing. Similarly for start its only outgoing. So the relation will be either $ 1-0$ or $ 0-1$ or $ 1-1$: route, $ 0-0$: no travel. $\endgroup$
    – Sutanu Majumdar
    Mar 19 at 21:26
  • $\begingroup$ @linkho right, my bad, no summing over $d$ in 2nd constraint. $\endgroup$
    – Sutanu Majumdar
    Mar 19 at 21:28
  • $\begingroup$ @linkho, I assumed drop-off node $i$ is part of the arc that solver needs to figure out. Pickup node will be presented by $ s_i$. Final destination for rider $r$ is given by predefined parameter $d_r$. Is $ d_r$ one of the nodes $ i$? Or its a location coordinate? Either way need to preset a distance matrix between all $d_r$ and nodes. Then distance becomes $\sum_i dist[d_r, i]*e_i$ where $ dist[d_r,i]$ is predefined distance between $ d_r$ & every node $i$. I have updated the answer $\endgroup$
    – Sutanu Majumdar
    Mar 19 at 22:00
  • 1
    $\begingroup$ Yes, still for a rider $r$, if dropped off by driver $d1$, then picked up by driver $d2$, at node say $i$ still there's going to be incoming & outgoing. That's why summing over drivers. Only final drop-off node $i$ will have only 1 incoming, even when summed over all drivers and summing over all other nodes $j$ connected to that node $i$. $\endgroup$
    – Sutanu Majumdar
    Mar 20 at 16:26
  • 1
    $\begingroup$ So the node $i$ with only 1 incoming, no outgoing (1-0) will turn $e$ to 1. $\endgroup$
    – Sutanu Majumdar
    Mar 20 at 16:32

Your Answer

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

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