1
$\begingroup$

I have a specific pickup and delivery problem to work on and am thinking how to incorporate time windows effectively. The problem has some driver with some time window [$a_d, b_d$] which is the start time and end time. They also have a start and end locations $[s_d,e_d]$ roaming around the city to along the way (as much as time allows) to pickup and drop off some people to earn some extra money. However, people (as riders) also have time window [$a_r, b_r$] and locations $[s_r,e_r]$. $a_r$ is the desired start time of rider and $b_r$ is the desired end time. I know how to model the routing parts as an IP to allow for multiple pickup for drivers and also a possibility of switching between cars for passengers. but because of the same reason I don't know how to include time constraints to ensure that all individuals are within with their time limits and when meeting at locations the time is correct. Is there any trick to apply? My try so far: decision variable are $x_{i,j,d}$ if a driver travel and edge. $y_{i,j,r,d}$ if a rider travel one edge with $d$. And finally $z_r$ if riders were driven (not important how many times or by whom) then satisfying routing constraint like; every rider/drivers leave s and reach e and meet flow of path.

$\endgroup$
3
  • $\begingroup$ Are you assuming that a driver never crosses the same edge twice? That seems a bit risky if drivers are "roaming around the city". Also, how are your time windows defined? Does $[a_r,b_r]$ mean that rider $r$ must be picked up at node $s_r$ at exactly time $a_r$ and dropped off at node $e_r$ at exactly time $b_r?$ $\endgroup$
    – prubin
    May 11 at 21:48
  • $\begingroup$ Multiple crossings of the same arc and/or multiple visits to the same node would make the model more complex. $\endgroup$
    – prubin
    May 13 at 16:15
  • $\begingroup$ Not a full answer, but given the characteristics of your problem you might want to look at the literature around the Pickup-and-Delivery Problem with transshipment or pickup and delivery problem with transfers. Which is quite literally the pickup and delivery problem with the possibility for your passenger/goods to be moved from one vehicle to another. $\endgroup$
    – Renaud M.
    May 15 at 9:55

2 Answers 2

2
$\begingroup$

You can refer to Google OR example for more information but it seems you'd need a time matrix $T$ between locations $(i,j)$
Then for each driver it will be set of constraints
$ a_d+\sum_{i,j}x_{i,j}^d T_{i,j} \le b_d$ where $ a_d,b_d$ is the time window for driver $d$.
Also you can avoid creating more variables & constraints by creating pre-defined combinations of riders & drivers with compatible time windows, like $ (d,r): a_d \le a_r \land b_r \le b_d$

for the meeting point time there can be another variable $t_{rd}^{s_r}$ with bounds as $ a_r \le t_{r,d}^{s_r} \le b_r$ or
Using time matrix:
$ a_r \le a_d+\sum_{i,j}y_{i,j}^{r,d}T_{i,j} \le b_r$ where $ t_d$ is start time of the day for the driver.

And other constraints will be needed like
$ \sum_r y_{ij}^{rd} \le Mx_{ij}^d \quad \forall d \ \forall i,j$

EDIT:
Referring to slightly older but probably pretty fundamental & relevant article. So the constraints will be
$ z_ra_r \le t_{i}^{rd} \le z_rb_r \quad \forall r,d \ \forall i$
and
$ t_{i}^{rd} + T_{i,j} - t_{j}^{rd} \le (a_r+b_r)(1-y_{i,j}^{r,d}) \quad \forall i,j \ \forall r,d$
The above constraint can be reduced as only one driver is riding with $r$ along an edge $i,j$

$ \sum_d t_{i}^{rd} + T_{i,j} - \sum_d t_{j}^{rd} \le (a_r+b_r)(1-\sum_d y_{i,j}^{r,d}) \quad \forall i,j \ \forall r$

$\sum_d y_{ij}^{rd} \le 1 \quad \forall i,j \ \forall r $

$\endgroup$
7
  • $\begingroup$ @Hemfri updated the answer $\endgroup$
    – Sutanu
    May 10 at 16:21
  • $\begingroup$ Is there any reason why not using $a_d$ instead of $t_d$ in $ a_r \le t_d+\sum_{i,j}y_{i,j}^{r,d}T_{i,j} \le b_r$? And $t_{rd}^i$ means at what time r meets d at node i ? $\endgroup$
    – Hemfri
    May 10 at 20:57
  • $\begingroup$ @Hemfri, yes that's right $t_d=a_d$. And $t_{rd}^i$ is the variable for rider $r$ to meet driver $d$ at point $i$. Initially I used $t_d$ thinking just in case $t_d$ is the actual start time on a day as it happens in some variants of VRPTW. $\endgroup$
    – Sutanu
    May 10 at 21:23
  • $\begingroup$ If using meeting variable $ t_{r,d}^{s_r}$ then pickup node $i=s_r$ for the rider $r$. $\endgroup$
    – Sutanu
    May 10 at 21:29
  • 1
    $\begingroup$ @Hemfri yes it should read as " only one driver". I choose $a_r + b_r$ for big $M$ as $M$ should be as big as possible but within the scale of the model. So in general for big $M$ you should the max number possible for the constraint in question. $\endgroup$
    – Sutanu
    May 11 at 13:06
1
+100
$\begingroup$

I'm going to make the following assumptions.

  • No driver and no rider ever visits the same node twice. (It is possible to work around this assumption by adding arcs to the graph, but that makes the already large model even larger.)
  • The $[a, b]$ time windows are interpreted as "leave no earlier than $a$, arrive no later than $b$".
  • The time for a rider to enter/exit a vehicle is negligible. (Again, this can be worked around at the cost of expanding the size of the model.)
  • Vehicles have no capacity limits.
  • Drivers cannot go faster than the specified time for crossing an arc (denoted $t_{i,j,d}$ for the time required by driver $d$ to cross arc $(i,j)$) but can go slower or can loiter at a node as needed.

In addition to the binary variables $x_{i,j,d},$ $y_{i,j,r,d}$ and $z_r,$ let $A_{i,p}\ge 0$ denote the time that a person (driver or rider) arrives at node $i$ and $D_{i,p}\ge 0$ denote the time a person leaves node $i.$ If the person does not arrive at or depart from node $i,$ we let the solver fill in whatever value it likes (probably 0) and ignore it. Note that, in a feasible solution, $A_{i,p} \le b_p$ and $D_{i,p} \le b_p.$

I'll skip the objective function. The constraints are as follows. (To save typing, I will assume that all summations and constraints are over those combinations of subscripts that make sense, in particular those pairs of nodes that actually are connected by arcs. Any place I use $p$ means it applies to both drivers and riders.)

  • Flow balance for drivers: $$\sum_{j}x_{i,j,d}-\sum_{j}x_{j,i,d}=\begin{cases} 1 & i=s_{d}\\ -1 & i=e_{d}\\ 0 & \textrm{otherwise} \end{cases}\quad\forall d, \forall i$$
  • Flow balance for riders: $$\sum_{d}\sum_{j}y_{i,j,r,d}-\sum_{d}\sum_{j}y_{j,i,r,d}=\begin{cases} 1 & i=s_{r}\\ -1 & i=e_{r}\\ 0 & \textrm{otherwise} \end{cases} \quad \forall r, \forall i$$
  • Riders go where their drivers go: $$y_{i,j,r,d} \le x_{i,j,d} \quad \forall i,j,r,d$$
  • A rider is considered driven if and only if they reach their destination: $$z_r = \sum_d \sum_{i} y_{i,e_r,d,r} \quad \forall r$$
  • Time windows must be respected: $$A_{e_p,p} \le b_p \quad \forall p$$ $$D_{s_p, p} \ge a_p \quad \forall p$$
  • You cannot leave before you arrive: $$D_{i,p} \ge A_{i,p} \quad \forall p, \forall i\neq s_p$$
  • Drivers obey speed limits: $$A_{j,d} \ge D_{i,d} + t_{i,j,d} - (b_d + t_{i,j,d})(1-x_{i,j,d}) \quad \forall i,j,d$$
  • Riders arrive/depart when their drivers do: $$A_{i,r} \ge A_{i,d} - b_d(1 - y_{j,i,r,d}) \quad \forall i,j,r,d$$ $$A_{i,r} \le A_{i,d} + b_r(1 - y_{j,i,r,d}) \quad \forall i,j,r,d$$ $$D_{i,r} \ge D_{i,d} - b_d(1 - y_{i,j,r,d}) \quad \forall i,j,r,d$$ $$D_{i,r} \le D_{i,d} + b_r(1 - y_{i,j,r,d}) \quad \forall i,j,r,d$$

As a side note, the incorporation of arrival and departure times at nodes takes care of subtour elimination.

$\endgroup$

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.