6

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 ?

Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • 1
    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 ! – Kuifje Nov 20 '20 at 16:11
  • 1
    I'm wondering if it is easier to change the formulation to a min-cost/max-flow formulation. – Andy W Nov 21 '20 at 14:38
  • 1
    @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. – Kuifje Nov 21 '20 at 16:17
  • 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? – Matheus Diógenes Andrade Jul 25 '21 at 17:31
  • 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 https://www.sciencedirect.com/science/article/pii/0166218X9200172I. – Matheus Diógenes Andrade Jul 25 '21 at 17:50

1 Answers1

5

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

Laurent Perron
  • 2,690
  • 1
  • 6
  • 18