I have a simple pickup and delivery (PDP) model operating on a service provider that has multiple locations for providing service. My decision variables and parameters are as follows:
$\delta_{i,j}^d$: a binary variable indicating whether taxi driver $d$ drives on edge (i,j). The operating cost for each taxi is different due to the location of the provider and their car model, and we indicate the operation cost by $e_{i,j}^d$.
$x_{i,j}^{d,c}$: a binary variable indicating whether taxi driver $d$ serves customer $c$ on edge (i,j). The price charged by each taxi to serve is different, and we indicate the fee by $f_{i,j}^{c,d}$. Because there are many service providers, taxi drivers can exchange customers with each other. Therefore, I considered $x$ with four indices to control these situations.
$y_{i}^{d,c}$ and $z_{i}^{d,c}$ are also take one if $d$ picksup and drop off $c$
The objective function is to minimize the operation cost (for the service provider) and serving cost (to encourage customers).I wrote it as follows:
$Min \sum_{i,j} \sum_{d} e_{i,j}^{d} \delta_{i,j}^d+ \sum_{i,j} \sum_{c,d} f_{i,j}^{c,d} x_{i,j}^{d,c}$
Currently, I am working on a variant of the PDP problem. We have a set of hired taxi drivers who receive a monthly salary (not per service). Therefore, for each customer call, they must initially serve a customer, driving them from their origin to their destination. However, if it is profitable and time allows, they can also take a detour to serve an extra customer and keep that extra earning for themselves. They can naturally take no detour if the extra costumer happens to have a perfect sub-path with the original ones (which is mostly the case in our setup).
For example, if the actual customer origin-destination locations are 1 and 7, and if we run the original simple PDP, the best path is 1,2,3,4,5,6,7. Now, in the variant of the PDP problem, suppose there is a profitable customer that we can serve by taking a detoured path 1,2,8,9,10,11,5,6,7, allowing us to serve two people and earn extra money for our taxi driver.
In the above example, the taxi driver must drive from 1 to 2 and 5,6,7 regardless of having an extra served customer. So, when it comes to calculating the final profit, I am interested in including only the cost of driving on non-overlapping edges as the operation cost of the drivers. At the same time, the fee charge of traveling on these edges in the extra earning for the taxi driver. How can I translate this into equations to be considered as the objective function? That is, how to consider the operation cost as well as the extra earning as just the cost of non-overlapping detoured edges? I don't want to consider another binary variables that accounts for taking detour(since this couldn't compute cases with perfect sub-path and I think these variables kind of allow for detour if earning of extra costumer is high). However, I cannot see how to do this on the fly while the model is deciding whether to serve an extra customer or not (without knowing the direct and detoured path).
Your detour is determined by these two variables $y,z $. If these two variables are more than $1$ along the same route, it will mean an extra pickup-drop.
So try with\
(1) $ \sum_i x_{ij}^{dc} \le \sum_k x_{jk}^{dc} \le E\sum_i x_{ij}^{dc} \quad \forall d,c \quad \forall j$
(2) $ y_{i}^{dc}-\sum_j\sum_c (x_{ij}^{dc}-x_{ji}^{dc}) \le \sum_j x_{ij}^{dc} \quad \forall i,c,d $
(3) $ \sum_i x_{ji}^{dc} \le M(1 + \sum_i\sum_c (x_{ij}^{dc}-x_{ji}^{dc}) - z_{j}^{dc}) \quad \forall j,c,d$
(4) $ \sum_c x_{ij}^{dc} \le 1 \quad \forall d \ \ \forall i,j$
(5) $ \sum_c x_{ij}^{dc} \le \delta_{ij}^d \le M\sum_c x_{ij}^{dc} \ \ \forall d$
Basically what I am trying to do is:
Restrict the model to choose one of the customers for any edge traversed.
Using flow balance (a source node will have outgoing while destination will have only incoming) ensure only the 2nd customer has its edge variable turned on. 2nd customer's source/destination while has its indicator variables $y,z$ turned on, still flow balance is $0$. So edge indicator for 2nd customer is forced to turn on and when its destination is reached, is turned off.
First pair of constraints ensure an edge is turned on only when its predecessor edge is turned on. This will prevent any additional edge to turn on after 2nd customer is dropped off.
Since objective is to minimize the model will not turn on any edge unless enforced.