3
$\begingroup$

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.

cloing delivery location

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Feb 10 at 21:26
  • $\begingroup$ @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. $\endgroup$
    – mars
    Feb 12 at 18:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.