# Area of Operation Planning for Free-Floating Car Sharing Systems
## 2 Methodology
### MILP Formulation  
We formulate a Mixed-Integer Linear Program (MILP) to describe the problem, which uses two single-commodity flows (SCF) to ensure  
* The connectedness of the selected AoO;
* The avoidance of enclosing non-selected vertices. The latter can be enforced by ensuring that each non-selected vertex is connected to the so-called boundary \(W\subseteq V\), which is defined as the set of outermost sub-districts, see Figure 1b for an example. We refer to the flow ensuring connectedness of \(S\) (i.e., the selected AoO) as \"\(f\)-flow\", whereas the flow used to ensure connectedness of the non-selected area is called \"\(g\)-flow\". As both flows operate on directed edges, we create an auxiliary graph \(G^{\prime}=(V^{\prime},A^{\prime})\) to work with. The extended vertex set \(V^{\prime}=V\cup\{s\}\) includes the additional vertex \(s\) that acts as the source of the \(g\)-flow. The extended arc set \(A^{\prime}\) consists of two parts: the set of directed copies of the original graph's edges, which we refer to as \(A\), and arcs \((s,i)\) connecting the source vertex \(s\) to each vertex \(i\in W\) on the boundary. Formally, \(A^{\prime}=A\cup\{(s,i)\mid i\in W\}\), where \(A=\{(i,j),(j,i)\mid\{i,j\}\in E\}\). The former arcs are required to allow for multiple, pairwise disconnected non-selected areas, as long as they are individually connected to the boundary. We introduce the following variables:  
* Binary variable \(x_{ij}\) indicates whether both vertices \(i\) and \(j\) are included in the solution (and thus, their associated revenue can be collected). * Binary variable \(y_{i}\) indicates that vertex \(i\) is part of the solution, i.e, \(i\in S\). * Binary variable \(r_{i}\) indicates that \(i\in S\) is the source (\"root-vertex\") of the \(f\)-flow. * Fractional variable \(f_{ij}\) is the amount of \(f\)-flow on arc \((i,j)\in A\). * Fractional variable \(g_{ij}\) is the amount of \(g\)-flow on arc \((i,j)\in A^{\prime}\). Figure 1: (**a**) Example graph for the sub-districts of Vienna’s third district. (**b**) The boundary sub-districts \(W\) of Vienna. The MILP formulation for our problem is as follows:  
\[\max\sum_{i\in V}\sum_{j\in V}p_{ij}x_{ij}\] (1) s.t. \[x_{ij}\leq y_{i} \forall i,j\in V \tag{2}\] \[x_{ij}\leq y_{j} \forall i,j\in V\] (3) \[\sum_{i\in V}c_{i}y_{i}\leq B\] (4) \[\sum_{i\in V}r_{i}=1\] (5) \[r_{i}\leq y_{i} \forall i\in V\] (6) \[B\cdot r_{i}-c_{i}\cdot y_{i}+\sum_{(h,i)\in A}f_{hi}\geq\sum_{( i,j)\in A}f_{ij} \forall i\in V\] (7) \[\sum_{(i,j)\in A}f_{ij}\leq B\cdot y_{i} \forall i\in V\] (8) \[\sum_{j\in W}g_{ij}=|V|-\sum_{i\in V}y_{i}\] (9) \[\max\sum_{i\in V}\sum_{j\in V}p_{ij}x_{ij}\]0 (10) \[\max\sum_{i\in V}\sum_{j\in V}p_{ij}x_{ij}\]1 (11) \[\max\sum_{i\in V}\sum_{j\in V}p_{ij}x_{ij}\]2 (12) \[\max\sum_{i\in V}\sum_{j\in V}p_{ij}x_{ij}\]3 (13) \[\max\sum_{i\in V}\sum_{j\in V}p_{ij}x_{ij}\]4 (14) \[\max\sum_{i\in V}\sum_{j\in V}p_{ij}x_{ij}\]5 (15) \[\max\sum_{i\in V}\sum_{j\in V}p_{ij}x_{ij}\]6  
The objective function (1) maximizes the revenue collected from all trips between pairs of selected vertices. Constraints (2) and (3) ensure that the revenue \(p_{ij}\) for trips from \(i\) to \(j\) can only be collected (\(x_{ij}=1\)) if both vertices \(i\) and \(j\) are selected to be in \(S\) (\(y_{i}=y_{j}=1\)). The budget Constraint (4) ensures that the accumulated costs \(c_{i}\) of all selected vertices do not exceed the available budget \(B\). Constraints (5)-(8) ensure the connectivity of the selected AoO by means of a SCF formulation. Constraint (5) ensures that exactly one root vertex is selected, while (6) ensures that it is also contained in the solution. Constraint (7) ensures that each selected vertex \(i\) consumes at least \(c_{i}\) units of \(f\)-flow, while also ensuring that if \(i\) is the selected root vertex (i.e., \(r_{i}=1\)), it instead sends out up to \(B-c_{i}\) units of \(f\)-flow.