# Replaning

Signature: `replanning(self, veh: Vehicle, new_activities: Optional[Set[VehicleActivity]] = None) -> Queue[VehicleActivity]`

Returns a new `Queue[VehicleActivity]` with the `new_activities` in it. Optimize the order of `Queue[VehicleActivity]` following criteria such as distance.

Note that:

* We choose that replanning function should be able to insert several new activities, in the code, if this list contains only one element, we may use a more specific and efficient method than the generic case
* In the replanning function, we take into account the two types of constraint for travelers, namely pickup_dt and max_detour_ratio. The pickup_dt constraint is integrated as a **time window for the pickup nodes** and the max_detour_ratio constraint is converted into a **temporal deadline for the dropoff** (in fact into a time window for the dropoff node with a dummy lower bound). The motivation for this conversion is to treat homogeneous constraints. It is more classical to have time windows than "distance windows".
* Objective function: we would like to define several objective function available (e.g. sum of distances, sum of travel times, min of the max the service time, profit for the service, ...). But in a first implementation, we consider the total traveled distance as the objective function to minimize.
* The activities already planned for vehicle are mandatory, they should appear in the new plan but not necessarily in the same order

## Problem description

This corresponds to a single vehicle pickup and delivery problem. Let us note $n$ the number of new requests to add in vehicle's plan (then there are $2n$ new activities given that a request has one pickup and one dropoff activity), $m$ the number of requests currently planned in vehicle's activities for which the user has not been picked up yet, $p$ the number of requests currently planned in vehicle's activity for which the user has been picked up (only dropoff activity is to be achieved, user is a passenger of the vehicle). An activity is identified with a unique integer id.
The replanning function returns an optimized plan including the following activities:
* 0: vehicle's current location, it acts as the departure depot
* $1, ..., n, n+1, ..., 2n$: pickups and dropoffs associated with the new requests to add in plan, where $n+i$ is the dropoff associated with pickup $i$
* $2n+1$, ..., $2n+m$, $2n+m+1$, ..., $2n+2m$: pickups and dropoffs associated with the requests currently planned in vehicle's activities for which user has not been picked up yet
* $2n+2m+1$, ..., $2n+2m+p$: dropoffs associated with the passengers currently in vehicle

With each activity $i$, we define:
* $e_i$: earliest pickup/dropoff time
* $e_0$ = current time
* $e_i$ = max(request time, current time) for $1 <= i <= 2n+2m$
* $e_i$ = current time for $2n+2m+1 <= i <= 2n+2m+p$
* $l_i$: latest pickup/dropoff time
* $l_0$ = current time + dt_matching
* $l_i$ = request time + pickup_dt for $1 <= i <= n$ and $2n+1 <= i <= 2n+m$
* $l_i$ = ( request time + pickup_dt + shortest path travel time * max_delay_ratio) for $n+1 <= i <= 2n$ and $2n+m+1 <= i <= 2n+2m$ and $2n+2m+1 <= i <= 2n+2m+p$ where would be formally defined as max_delay_ratio = (mean speed on shortest path / mean speed on detoured path) * max_detour_ratio but should be approximated to be defined a priori
* $q_i$: load, if positive it's a pickup, if negative it's a dropoff
* $q_i=-q_{n+i}$ for $1 <= i <= n$
* $q_i = -q_{m+i}$ for $2n+1 <= i <= 2n+m$
* $q_i$ = -1 for $2n+m+1 <= i <= 2n+2m+p$

We note $D_{ij}$ and $T_{ij}$ the distance and travel time between activities $i$ and $j$.
Vehicle has a capacity $Q$.

The best plan for mobility service corresponds to the plan that respects all constraints and minimizes the total distance traveled. We define variables $x_{ij}$ (1 if vehicle travels from $i$ to $j$, 0 otherwise), $t_i$ (arrival time at $i$) and $y_i$ (number of passengers in vehicle just after activity $i$). The problem can be formulated as follows:


Constraints that should be ensured:
* Vehicle leaves the "depot" (current location)
* All nodes should be visited once
* **time windows**: arrival time at $i$ is within the time window
* **precedence**: a pickup is served before the corresponding dropoff
* If vehicle arrives before earliest pickup time at node, it should wait
* **capacity**: number of passengers remains lower or equal to vehicle's capacity

## Resolution approaches

Here is a coding environment to test your own approaches: https://github.com/kit4a/ridesharing_tools.git

### Exhaustive

Exhaustive resolution is possible in a reasonable execution time for $2*n+m < 10$.

### Hill climbing

This approach does not necessarily produce valid solutions. It is interesting for large instances only (more than 30 activities).

### A Mixed Integer Linear Programming (MILP) formulation:
In the following, we state a MILP formulation for the ride sharing problem where both the assignments of the requests over the vehicles as well as the routing for each vehicle is determined.

Let $\mathcal{R}$ be a set of requests to be assigned. For each $r \in \mathcal{R}$ a pick-up and dropoff activities are associated to it. Let $\mathcal{P} = \{1,2,...,|\mathcal{R}|\}$ be the set of pick-ups and $\mathcal{D} = \{ |\mathcal{R}|+1, |\mathcal{R}|+2, ..., 2\times |\mathcal{R}|\}$ the set of dropoffs.

Let $\mathcal{K}$ be a set of vehicles. Each vehicle $k \in \mathcal{K}$ has a capacity $Q_{k}$, an initial load $q_{0}^{k}$ and $\mathcal{P}^{k}$ and $\mathcal{D}^{k}$ which respectively represent the set of already planned pick-ups and dropoffs for vehicle $k$.

For each pick-off activity $i \in \{\mathcal{P} \cup \mathcal{P}_{k \in \mathcal{K}}^{k} \}$ a time-window $[e_{i}, l_{i}]$ and a number of passengers to to be loaded in the vehicle $q_{i}$ are associated. For each dropoff activity $i \in \{\mathcal{D} \cup \mathcal{D}_{k \in \mathcal{K}}^{k} \}$ a deadline $\tilde{d}_{i}$ and a negative number of passengers to be loaded off $q_{i}$ are associated.
* ps: Should we add a service time to account for the time where the vehicle parks to pick-up or drop-off a person? This way it is instantaneous.

Let $\mathcal{G}^{k}=\{\mathcal{V}^{k}, \mathcal{A}^{k}\}$ be the graph that represents the network for each vehicle $k \in \mathcal{K}$ where $\mathcal{V}^{k}=\{ \{o^{k}\} \cup \mathcal{P} \cup \mathcal{D} \cup \mathcal{P}_{k \in \mathcal{K}}^{k} \cup \mathcal{D}_{k \in \mathcal{K}}^{k}\}$ where the node $o^{k}$ represents the departure location of vehicle $k$. $D_{ij}^{k}$ represents the distance of travelling the arc $(ij) \in \mathcal{A}^{k}$ with vehicle $k \in \mathcal{K}$ and $\tau_{ij}^{k}$ the travelling time.

The variables of the model are as follows:

* $x_{ij}^{k} = 1$ if the arc $(ij) \in \mathcal{A}^{k}$ is taken with vehicle $k \in \mathcal{K}$, 0 otherwise.
* $y_{i}^{k} =1$ if request $i \in \mathcal{R}$ is serverd by vehicle $k \in \mathcal{K}$, 0 otherwise.
* $t_{i}^{k} \in \mathbb{R}$ represents the time of arrival of vehicle $k \in \mathcal{K}$ at location $i \in \mathcal{V}^{k}$.
* $q_{i}^{k} \in \mathbb{R}$ represents the load of vehicle $k \in \mathcal{K}$ at location $i \in \mathcal{V}^{k}$.


The objective function maximises the number of requests as a priority and minimises the distance travelled as a secondary objective. Constraints (1) state that if a request $i \in \mathcal{R}$ is performed, both the pick-up and dropoff activities are performed. Constraints (2) state that the activities already planned for a vehicle $k \in \mathcal{K}$ need to be performed. Constraints (3-4) ensure the flow of time and quantity at each node. Constraints (5-6) ensure that the time-windows for a pick-up activity are enforced. Constraints (7) ensure that if a request is performed, the dropoff activity is conducted after the pickup activity. Constraints (8) ensure that the deadline for a dropoff activity is enforced. Constraints (9-10) enforce the bounds of the load variable. Finally, constraints (11-12) ensure the integrality and positivity of the variables.

Constraints (3-4) being non-linear, they can be linearised as follows:

$t_{i}^{k} \geq t_{j}^{k} + \tau_{ji}^{k} - T_{ji}^{k} (1 - x_{ji}^{k})$ $\quad \forall k \in \mathcal{K}$ , $i, j \in \mathcal{V}^{k}$ $\quad (3^{\prime})$

$q_{i}^{k} \geq q_{j}^{k} + q_{i} - Q_{ji}^{k} (1 - x_{ji}^{k})$ $\quad \forall k \in \mathcal{K}$ , $i, j \in \mathcal{V}^{k}$ $\quad (4^{\prime})$

$T_{ji}^{k}$, $Q_{ji}^{k}$ and $M_{\text{obj}}$ are upperbounds that can be defined as follows:

$T_{ji}^{k}= \begin{cases}
\max\{0, l_{j}+\tau_{ji}^{k}-e_{i}\} \quad \forall i \in \mathcal{P} \cup \mathcal{P}^{k}_{k \in \mathcal{k}}\\
\max\{0, \tilde{d}_{j}+\tau_{ji}^{k}-(e_{i-n}+\tau_{i-ni}^{k})\} \quad \forall i \in \mathcal{D} \cup \mathcal{D}^{k}_{k \in \mathcal{k}}
\end{cases}$

$Q_{ji}^{k}=\min\{Q_{k}, Q_{k}+q_{j}\}$

$M_{\text{obj}}=4\max\limits_{k \in \mathcal{K}, (ij) \in \mathcal{A}^{k}}\{D_{ij}^{k}\}$

## Time windows definition

Time windows should be defined to minimize the discomfort of passengers that are already in the vehicle ($2n < i < 2n+m+1$). 
* A possible approach is to define sharp time windows for passengers already in vehicle (e.g.  dropoff time estimated with vehicle's current plan + alpha) and large (unrestrictive) time windows for new requests.  
* Another approach is to define distance windows instead of time windows. New variables $d_i$ could be defined as the distance traveled by vehicle at arrival at $i$. If vehicle travels between $i$ and $j$, $d_j = d_i + D_{ij}$. Precedence constrain becomes: $d_i < d_{n+i}$. For passengers already in vehicle, the lower bound of distance window is 0, and upper bound is max detour + sp distance - already traveled distance. For new activities, lower bound is 0 and upper bound is an arbitrary large number. With this strategy, feasibility of new plan is verified. 
* Or we do not try to build a feasible new plan and we use unrestrictive time windows.