1

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).

yaodao vang
  • 197
  • "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)". Hmmm... Can you show me how what you ask for is possible in principle? – fedja Apr 07 '23 at 22:55
  • @fedja I think including a binary variable to decide on detour could solve the issue to some extend. But it does not capture the situation in which taxi-drivers do not need to take any detour. For that perhaps having a binary indicating if taxi driver serve an extra costumer could help. However, I think it's quite inefficient and difficult to manage all possibilities. That's why I asked here – yaodao vang Apr 08 '23 at 08:45

1 Answers1

2

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.

Sutanu Majumdar
  • 458
  • does this formulation handle cases with more than one extra costumers? how does flow balance act when taxi drivers pickup and drop off actual costumers and two extra. I think having summation $\forall c$ cover those too? And in (1) what is big $E$, is that the totall number of edges. Thank you very much. – yaodao vang Apr 09 '23 at 08:42
  • 1
    Yes $E$:is basically like $M$, whatever suitable big number, like Total number of edges. Try this to check if it works. Are you considering time as a factor? It will be another index to existing variables, will increase the number of variables but will reduce constraints & make things simpler. Because while nodes can be random, time is always monotonic. $t+1 \gt t$ always, so easier to implement. VRP models often consider time windows. – Sutanu Majumdar Apr 09 '23 at 12:14
  • 1
    Yes, it may work. I haven't studied VRPs much but this Google OR example may be a good start. https://developers.google.com/optimization/routing/vrptw – Sutanu Majumdar Apr 09 '23 at 18:14
  • in (5) what's the reason behind $\delta \le \sum_c x$? – yaodao vang Apr 11 '23 at 18:31
  • 1
    If driver $d$ is not traversing on arc $(i,j)$ for any customers $ \sum_c$, $ x=0$,then $ \delta =0$, otherwise it can take a value – Sutanu Majumdar Apr 11 '23 at 18:34
  • Very true. Thank you @Sutanu – yaodao vang Apr 11 '23 at 18:59