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 ?

Improve this question
$\endgroup$
5
  • 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
    Commented Nov 20, 2020 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
    Commented Nov 21, 2020 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
    Commented Nov 21, 2020 at 16:17
  • $\begingroup$ Does a serviced partial demand require to be an integer? That is, is it possible to service 0.5 or even 1/3 of demand? $\endgroup$
    – Matheus Diógenes Andrade
    Commented Jul 25, 2021 at 17:31
  • $\begingroup$ Well, If it is possible to serve fractional demands, then we are dealing with a Vehicle Routing with Split Deliveries. I do not know how to do this by using the Google OR-TOOLS routing library. But, there's one way of solving it, by integer programming. Take a look at the formulation on pages 2 and 3 of the paper sciencedirect.com/science/article/pii/0166218X9200172I. $\endgroup$
    – Matheus Diógenes Andrade
    Commented Jul 25, 2021 at 17:50

1 Answer 1

Reset to default
5
+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
  • 1
    $\begingroup$ This was my initial idea. But splitting the demand in 2 may not be useful. $\endgroup$
    – Kuifje
    Commented Nov 17, 2020 at 17:42

Your Answer

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

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