# Derived variables of when a decision variable appears?

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.

• Dr @RobPratt, I appreciate always your answers to my question .. and the generous answer I talked in my post was yours of course, ... I can link $v$ to $x$ .. but I can't find a way to link $y$ to $v$ or link $y$ to $x$ directly .. I really appreciate your help May 8 '20 at 21:37
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)$$.