how to satisfy time constraints with meeting points?

Question

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.

Answer 1

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 $

Answer 2

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.