6
$\begingroup$

I am working on a vehicle routing problem with or-tools.

Is it possible to partially fulfill a demand? I know it is possible to drop nodes with the disjunction constraints. But in this case, a node is either visited, or not. I would like to allow a node to be visited, with the possibility to deliver only a fraction of its demand, if it is profitable. For example, for a given customer with demand $2$, there might not be enough resources (vehicles/capacity) to complete its delivery, but there may be enough to deliver $1$ unit, and in this case the customer would be more happy than without any visit at all.

Another way of saying this is that I would like to maximize the quantity that is delivered, while minimizing transportation costs.

One option would be to duplicate nodes, each node having a given fraction of the demand. But this will quickly lead to very big networks and I don't think it is a good idea. Also, determining the values of the fractions may not be simple. The ideal fraction would be "whatever spare space there is in the truck," but this is not straighforward to compute before hand.

Is this possible with or-tools ?

$\endgroup$
  • 1
    $\begingroup$ Thanks @BCLC I appreciate the bounty, but I think the answer is : no, it is not possible :). On the other hand, I know that the question here has a positive answer ! $\endgroup$ – Kuifje Nov 20 at 16:11
  • 1
    $\begingroup$ I'm wondering if it is easier to change the formulation to a min-cost/max-flow formulation. $\endgroup$ – Andy W Nov 21 at 14:38
  • 1
    $\begingroup$ @AndyW I agree the problem by itself could probably be handled differently but in my case it is in a vehicle routing context with many other constraints, and the obligation to use ortools. $\endgroup$ – Kuifje Nov 21 at 16:17
4
+50
$\begingroup$

You can split the demand in two visits. You will need to duplicate the node in two, and add a disjunction on each visit.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This was my initial idea. But splitting the demand in 2 may not be useful. $\endgroup$ – Kuifje Nov 17 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.