Iterative Assignment for Pooling Strategy

This strategy is an optimization-based one that assigns multi-party requests to TNC vehicles at fixed time intervals aiming at reducing a cost function that can flexibly weigh operator and request costs. Formally, the algorithm at fixed steps solves the following optimization problem:

\[\begin{split}Minimizes \sum_{(r, v) \in E} T_{rv} x_{rv} \\ {\text{subject to}} \sum_{v : (r, v) \in E} x_{rv} = 1,\ \forall r \in R \\ \sum_{r: (r, v) \in E} Q_r x_{rv} \leq \overline{Q}_v,\ \forall v \in V \\ x_{rv} \geq 0,\ \forall (r, v) \in E\end{split}\]

Here, $G = (R \cup V, E)$, where $V = \cup_{r \in R} V_r$ is the set of all vehicles considered in the batch and $E = {(r, v): r \in R, v \in V_r }$ is the set of edges in $G$.

Binary variables $x_{rv} \in {0,1}, \forall (r, v) \in E$ will be used to denote whether request $r$ is assigned to vehicle $v$ in the integer program. We let LP($G$) be the linear relaxation (allowing for fractional values for $x_{rv}$) of this integer linear assignment program on $G$ where the objective function minimizes the total additional duration vehicles need to travel to serve their corresponding requests.

Constraints impose that every request should be matched to only one vehicle (if $x_{rv}\in {0,1}, \forall (r, v) \in E$), and ensures that vehicle capacities are not exceeded.

A sequence of relaxations of the binary constraint reaches the optimal solution in a limited number of steps. Since, this algorithm undertakes optimization problems, the CPU time is expected to be higher compared to the default assignment.

Important

For details and numerical experiments, refer to:

Vakayil, A., de Souza, F., Cokyasar, T., Gurumurthy, K.M. and Larson, J., 2023. Large-Scale Dynamic Ridesharing with Iterative Assignment. arXiv preprint arXiv:2311.06160.