## 3 The Negotiation-Based Approach
### The Bid Generation Problem  
The bid is the vector \((\gamma,\tau)\) where \(\gamma\) is a row vector of dimensions \(|I|\) that corresponds to the quantities to be processed from each customer and \(\tau\) is a vector of dimensions \(|I|\) of the time slots chosen in the bid to serve each customer. A set of \(K\) bids is generated by iteratively solving the problem P2. In particular, at each iteration \(k\), the solution obtained in iteration \((k-1)\) is totally or partially prohibited in problem P2 by adding a specific constraint in the \(k\)-th bid generation problem. The proposed bid generation scheme guarantees different bids that are feasible for the logistics operator and near-optimal. At each iteration \(k\), let \(N^{k-1}=\{(i,h,t):z^{*}_{iht}=1\}\) in bid \(k-1\) (clearly \(N^{0}=\emptyset\)). To generate a bid at iteration \(k\geq 1\), we introduce a tabu list \(L^{k}_{iht}\) such that  
\[L^{k}_{iht}= \begin{cases}0,&\text{if }k=1,\\ L^{k-1}_{iht}-1,&\text{if }k>1\text{ and }(i,h,t)\in N^{k-1}\text{ and }L^{k-1}_{iht}>1,\\ r,&\text{if }k>1\text{ and }L^{k-1}_{iht}=0.\end{cases} \]  
List \(L\) acts as a tabu list; in fact, the idea is to prevent client \(i\) from being serviced by vehicle \(h\) at time \(t\) in iteration \(k\) if it has been serviced by the same vehicle at the same time in the previous iteration. This allows for diversifying the solutions associated with the bids to be given in input to the collection problem in the next winner-determination problem. However, in order not to possibly prohibit all the assignments of the previous iteration, guaranteeing both diversification and intensification, we define an aspiration criterion such that  
\[z_{iht}\leq\rho^{k}_{iht}+\zeta^{k}_{iht} \tag{15}\]  
where  
Figure 3: Scheme of the auction-based negotiation. \[\rho_{iht}^{k}= \begin{cases}0,&\text{if }L_{iht}^{k}>0,\\ 1,&\text{if }L_{iht}^{k}=0.\end{cases} \]  
and  
\[\zeta_{iht}^{k}= \begin{cases}1,&\text{if }Uniform(0,1)>1-\frac{Z_{c}^{(k-1)}-Z_{ c}^{(k-2)}}{Z_{c}^{(k-2)}},\\ 0,&\text{otherwise}.\end{cases} \]  
Parameter \(\zeta_{iht}^{k}\) has the following effect: assume that the algorithm is processing iteration \(k\) in the bid generation problem. Let \(Z_{c}^{(k-1)}\) and \(Z_{c}^{(k-1)}\) be the optimal solution value of the bid generation problem in iterations \((k-1)\) and \((k-2)\), respectively. The ratio \(\frac{Z_{c}^{(k-1)}-Z_{c}^{(k-2)}}{Z_{c}^{(k-2)}}\) is the percentage of variation of the optimal objective of the bids associated with the iterations mentioned. If the variation is positive and large, that is, the cost is increased by a sufficiently large amount, the algorithm is not prone to intensify this solution; therefore, if an assignment that may restore a previous more profitable solution is prohibited, the algorithm tries to activate an aspiration criterion to override the tabu list status. As can be seen, if \(\rho_{iht}^{k}\) is zero and the ratio \(\frac{Z_{c}^{(k-1)}-Z_{c}^{(k-2)}}{Z_{c}^{(k-2)}}\) is large, \(1-\frac{Z_{c}^{(k-1)}-Z_{c}^{(k-2)}}{Z_{c}^{(k-2)}}\) is small, say close to zero, and there is a greater chance that \(\zeta_{iht}^{k}\) becomes \(1\) by its definition. The overall problem to solve to find the \(k\)-th bid is the following. \[\min\sum_{i\in I}\sum_{h\in H}\sum_{t\in T_{c}}c_{it}^{c}\cdot z_{iht}+\sum_{ t\in T_{c}}\max\{0,[a_{t}-\sum_{j\in I}(LC_{j}-I_{jt})]\}\] (16) s.t. \[\sum_{h\in H,t\in T_{c}}z_{iht}=1,\forall i\in I, \tag{17}\] \[\sum_{i\in I}q_{i}\cdot z_{iht}=a_{t},\forall h\in H,\forall t\in T _{c},\] (18) \[a_{t}\leq C,\forall t\in T_{c},\] (19) \[z_{iht}\leq\rho_{iht}^{k}+\zeta_{iht}^{k},\forall i\in I,\forall h \in H,\forall t\in T_{c},\] (20) \[z_{iht}\in\{0,1\},\forall i\in I,\forall h\in H,\forall t\in T _{c}. \tag{21}\]  
Note that the objective function takes into account two components. The first component is exactly the collection cost; the second part of the objective tries to infer the state of occupancy of the resources that the sorting operator will use.