0

I'm trying to model a pickup and delivery problem under some constraints. In addition to a binary variable $ x_{i}^{pd}$ which is for pickup, I have another binary variable like $ y_{i}^{pd}$ for drop off.

x(i,p,d) = 1 if product p be picked up by driver d at node i 
y(i,p,d) = 1 if product p be dropped off by driver d at node i

is it possible to write some constraints that model dropp off without having any order dependency?

yaodao vang
  • 197

1 Answers1

1

It is common to use binary variables for arc traversals in the network. So, for instance, you might introduce $z_{i,j}^d\in \lbrace 0,1\rbrace$ with value 1 if driver $d$ visits node $j$ immediately after node $i$ and 0 otherwise, along with constraints to ensure that the nodes form a path (each node is followed by exactly one node). I am assuming here that, in your problem, each driver visits each node at most once.

Addendum: Based on a comment below, you can add continuous variables $u_i^d \ge 0$ together with constraints of the form $$u_j^d \ge u_i^d + z_{i,j}^d - M(1 - z_{i,j}^d) \quad \forall i,j,d,$$ where $M$ is a sufficiently large constant. ($M$ can be the maximum number of stops.) The $u$ variables basically act as counters for the stops, with the counter going up by (at least) 1 each time an arc is crossed. Now add constraints of the form $$u_j^d \ge u_i^d + 1 - M(2 - y_{j,p}^d - x_{i,p}^d)\quad \forall i,j,d,p.$$ This says that if product $p$ is picked up at location $i$ by driver $d$ ($x_{i,p}^d = 1$) and dropped off at location $j$ by the same driver ($y_{j,p}^d =1$) then node $j$ must have a higher count than node $i$ on the route driven by driver $d.$

prubin
  • 4,923
  • I've extended my answer based on this comment. – prubin Sep 07 '22 at 02:44
  • Thanks again @prubin. I didn'r get the first part though. basically, $z_{i,j}^d $ is a binary variable that takes one if d drives an edge (i,j). Right? So, why and how $u_i^d$ variable could be nonnegative when assumingthat each driver visits each node at most once? Isn't $u$ a binary too? I understood $u$ like a vraible saying if d visit $i$, is that right? – yaodao vang Sep 08 '22 at 11:28
  • 1
    Sorry, the superscript 2 was a typo (should have been "d") which I have fixed. – prubin Sep 08 '22 at 15:54
  • 1
    No, $u$ is not binary; it acts as a counter. The first inequality says that if $z_{i,j}^d=1$ (driver $d$ leaves $i$ and goes to $j$) then $u_j^d \ge u_i^d +1$ (the counter for driver $d$ increases by at least one when the driver arrives at $j$). This means the counter increases monotonically along the route. The second constraint says that a necessary condition for driver $d$ to pick up at $i$ and deliver to $j$ is that the driver's counter be higher at $j$ than at $i.$ – prubin Sep 08 '22 at 15:59
  • 1
    As for the "if and only if" constraint, what you wrote says that driver $d$ picks up a product at node $i$ if and only if they also deliver the same product to node $i,$ which does not make any sense. – prubin Sep 08 '22 at 16:01
  • 1
    That will work; it just needs a slightly larger value of $M.$ If $K$ is the maximum possible value of $u_i^d - u_j^d,$ then your $M$ needs to be at least $K+1$ and my $M$ needs to be at least $K.$ – prubin Sep 08 '22 at 20:41