Derived variables of when a decision variable appears?

Question

I am dealing with a multi-travelling passenger problem.

• $x_{i,j}$ is a binary variable that allocate a passenger $i$ to a vehicle $j$, every vehicle can carry only $n_{pv}$ passenger where $i \in \{1,2,\dots,n\}$ and $j \in \{1,2,\cdots,n_v\}$, $(n_v = n/n_{pv})$

where $n$ is the number of passengers, $n_v$ is the number of vehicles and $n_{pv}$ is the number of passenger per vehicle.

The mathematical model to allocate each passenger to a vehicle to minimize the total cost. The decision variable is $x_{i,j}$ where \begin{align}x_{i,j}=\begin{cases} 1 &&\text{if passenger $i$ is allocated to vehicle $j$}\\0 &&\text{otherwise.}\end{cases}\end{align}

The objective is \begin{align}\min&\quad\sum_i \sum_j c_{i,j}\cdot x_{i,j} &&\text{$c_{i,j}$ is the cost of travelling passenger $i$ by vehicle $j$}\\\text{s.t.}&\quad\sum_j x_{i,j}= 1 &&\text{for each $i$}\\&\quad\sum_i x_{i,j} = n_{pv} &&\text{for each $j$}.\end{align}

The passengers are allocated by the order of $i$; i.e. $i = 1$ will be allocated before $i = 2$ and so on.

I want to formulate a decision variable indicating the order of passengers in each vehicle denoted by $y_i$; i.e. $y_i = 1$ if he is the first passenger assigned to his vehicle, $y_i = 2$ if he is the second assigned to his vehicle and so on.

For example if we have $n = 9$ passengers and $n_{pv} = 3$, if the values of the decision variables were \begin{align} x_{1,1} = 1, &&x_{1,2} = 0, &&x_{1,3} = 0 \\ x_{2,1} = 1, &&x_{2,2} = 0, &&x_{2,3} = 0 \\ x_{3,1} = 0, &&x_{3,2} = 1, &&x_{3,3} = 0 \\ x_{4,1} = 0, &&x_{4,2} = 0, &&x_{4,3} = 1 \\ x_{5,1} = 1, &&x_{5,2} = 0, &&x_{5,3} = 0 \\ x_{6,1} = 0, &&x_{6,2} = 0, &&x_{6,3} = 1 \\ x_{7,1} = 0, &&x_{7,2} = 1, &&x_{7,3} = 0 \\ x_{8,1} = 0, &&x_{8,2} = 0, &&x_{8,3} = 1 \\ x_{9,1} = 0, &&x_{9,2} = 1, &&x_{9,3} = 0 \end{align} then the values of $y_i$s will be \begin{align} y_1 &= 1\\ y_2 &= 2\\ y_3 &= 1\\ y_4 &= 1\\ y_5 &= 3\\ y_6 &= 2\\ y_7 &= 2\\ y_8 &= 3\\ y_9 &= 3. \end{align}

How can I derive the values of $y_i$s through linear equations? I have a previous generous answer for another model, I used the same concept to derive the vehicle number for each passenger $v_i$ using \begin{align}\sum_j j\cdot x_{i,j} = v_i\quad\forall i\end{align} where $v_i \in \{1,2,\dots,n_v\}$ but I don't know if that is the right way to derive $y_i$ or not.

I appreciate your help.

Answer 1

You want to enforce $x_{i,j}=1 \implies y_i=\sum_{k \le i} x_{k,j}$. One way to do that is as follows: $$-\min(n_{pv},i)(1-x_{i,j}) \le y_i - \sum_{k \le i} x_{k,j} \le \min(n_{pv},i)(1-x_{i,j})$$ for all $i$ and $j$. Here, we have used big-M values based on $0 \le y_i \le \min(n_{pv},i)$ and $0 \le \sum_{k \le i} x_{k,j}\le \min(n_{pv},i)$.