# Triangular inequality in Routing or Pickup/Drop off problem

I have a multi-pickup dropoff problem where orders from pickup locations need to be dropped off at delivery locations. I converted the problem into a three-index pickup drop-off problem with time windows (PDPTW). A standard formulation of PDPTW can be found here https://www.dep.ufscar.br/munari/pdptw/supplementary_material.pdf

However, since my delivery location is fixed for all orders that are coming from multiple pickup locations, I had to create $$(n-1)$$ instances of the single delivery location, where n is the total number of orders or pickup locations. The distance and travel time between these dummy delivery locations are $$0$$ and hence do not hold the triangular inequality condition $$t[i,k]>t[i,j]+t[j,k]$$

I was able to solve a PDPTW problem where all pickups and dropoffs were located at different locations using a solver. However, when I try to solve this multi-PDPTW, where I create these dummy locations, the solver shows its feasible problem, but the feasible solution does not improve even after a long time. I am trying to understand whether this is happening because of the creation of the dummy variables. I know that sub-tour is eliminated because there are time windows and capacity constraints. But I was wondering if this was happening because the triangular inequality among those delivery locations is not met.

Edit: In a PDPTW each order has a unique origin and destination pair associated with it. For multi-PDPTW, some delivery locations are the same for some orders. The following figure is from a paper. They are creating one copy of $$d_1$$ to create $$d_1'$$ and $$d_1''$$ to convert the multi-PDPTW into a PDPTW formulation.

• First, the triangle inequality is typically expressed as a weak inequality ($\ge$) rather than a strict inequality ($>$). So that should not be a problem. Second, it's unclear why you are creating the clones of the single delivery location.
– prubin
Commented Feb 10, 2023 at 21:26
• @prubin, Thanks for the weak vs strict inequality comment. That was helpful. I edited my questions to include why I was cloning a single delivery location.
– mars
Commented Feb 12, 2023 at 18:55