## 2 Problem Definition
### Ant-Based Solution Construction  
In any ACO algorithm, the phase of construction of solutions for the optimization problem is centered around a cycle executed by a set of agents (corresponding to ants) in which every agent/ant iteratively builds a solution moving from state to state. Each state corresponds to a partial solution of the optimization problem and an ant can make a move to another state to reach a complete solution by choosing moves from an available set. Talking more in mathematical optimization terms, a solution is said to be partial only if a subset of the decision variables has been assigned a value; instead, a solution is said to be complete if all the variables have been assigned a value. When an agent/ant executes a move, one or more decision variables are assigned a value and thus a partial solution becomes \"more complete\". The selection of a move happens probabilistically: each move available to an ant in a state is associated with a probability computed on the basis of the attractiveness of choosing that move. Such attractiveness is called the pheromone measure and resembles the pheromone released by ants for marking promising food foraging paths: this pheromone measure is updated at the end of each construction phase by incrementing it for moves that have brought solutions of high quality and by decrementing it for moves that have brought solutions of bad quality.  
To illustrate the algorithmic principles informally presented above more rigorously, we formally proceed to define the concept of state for the problem BLP-ESPLR. To conduct this, we must first remark that BLP-ESPLR is a purely binary linear program and consequently, constructing a complete solution requires an ant to fix the value of each decision variable \(x_{ds\ell}\) to either 0 or 1. Then, we can define a Parking Lot State as follows:  
**Definition 2** (Parking Lot State-PLS).: _Let \(D\times S(d)\times L(d,s)\) be the set of triples \((d,s,\ell)\) that represent the rental of a lot \(\ell\) in subdistrict \(s\) of district \(d\). A Parking Lot State (PLS) identifies all the lots that are rented (thus, including triples corresponding to the decision variables \(x_{ds\ell}\) with the value set to 1). Given a PLS, we can easily compute the corresponding number of e-scooter parking places and lots that are rented and the number of car parking places that are subtracted, thus having the possibility of easily verifying whether the constraints (2)-(4) are satisfied. We say that a PLS is partial when it does not satisfy the lower bounds \(\mathrm{LB}_{d}^{7}\), \(\mathrm{LB}_{ds}^{\mathrm{TOT}}\) of constraints (2), (4) and is instead complete when it satisfies them._If an ant is in a partial PLS, it can execute a move with the aim of reaching a (more) complete PLS. The move corresponds to renting one additional parking lot and consists of setting the value of a binary variable \(x_{ds\ell}\) to 1, whose value has not yet been set. If we indicate by \(T\) the set of all triples \((d,s,\ell)\) representing all lots in subdistricts of districts and by \(T^{\text{PLS}}\) the triples rented in the state PLS, an ant in state PLS may execute a move choosing a triple \(t=(d,s,\ell)\in T\backslash T^{\text{PLS}}\) with probability \(p_{t}\) set as:  
\[p_{t}=\frac{\phi_{t}}{\sum_{\tau\in T}\phi_{\tau}}\qquad\qquad\forall t\in T \backslash T^{\text{PLS}} \tag{6}\]  
in which \(\phi_{t}\) is the pheromone value of a move associated with triple \(t\in T\). Executing the move of triple \(t=(d,s,\ell)\) is equivalent to set \(x_{ds\ell}=1\).