I am attempting to frame a problem based on the following assumptions:
There is a group of families $F$ of varying sizes, each owning a car, and requiring transportation for their daily needs, such as work, shopping, and school. In a small area, some families are interested in carpooling, but their schedules are unpredictable, varying each day and hour, making it impossible to prearrange rides on a daily or weekly basis. Therefore, I am looking to formulate a problem that involves a group of families with transportation needs, interested in sharing their rides with other families if their routes overlap. For example, a parent might drive to work and pick up a classmate of their child on the way to school. However, on other days, they may work from home and not require the same route. Given this uncertain scenario, where the positions are not fixed but need to remain constant once assigned; how can I formulate this problem as an MILP?
Previously I though to have two Dynamic subset $D$ and $R$ from $F$. But based on the comments (thanks for that) I think this way of formulating is beeter.
Decision variables:
$x_{i,j,f} =1 \quad$ if family $f$ drives from $i$ to $j$
$y_{i,j,f,f'} =1 \quad$ if family $f'$ be driven by $f$ from $i$ to $j$
$z_{f} =1 \quad$ if family $f$ plays a roles of driver
$\hat z_{f}=1 \quad$ if family $f$ palys a role of rider
Constraints :
a family could be either driver or be driven by other $z_{f}+ \hat z_{f} \le 1$
every one should leaves their origin
- For drivers: $\sum_{j} x_{o_f,j,f} =1 \quad \forall f \quad$
- and for those who are driven $\quad \sum_f \sum_{j} y_{o_f,j,f,f'} =1 \quad \forall f'$
a family can drive if they assigned to $x_{i,j,f} \le z_{f}$
capacity should be controled $\quad \sum_{f'} \sum_{j} y_{i,j,f,f'} \le M x_{i,j,f} \quad \forall f$
flow constraint
- for family who drive $\sum_{j} x_{i,j,f} = \sum_{k} x_{j,k,f}$
- for family who are driven $\sum_{j} x_{i,j,f,f'} = \sum_{k} x_{j,k,f, f'}$
Now the question is how to use $\hat z_{f}$? Do I even need this?
Why not try something like this
Let $p$ represent a ride/route/path for the day, then
$d_{f}^p + r_{f}^p \le 1 $ where $ d,r$ are binary variables that indicate if a family $f$ is playing role of driver $ d_{f}^p = 1$ or rider $ r_{f}^p = 1$ for route $p$.