or-tools: Problem with negative capacities

Hi! While prototyping a VRP problem using this awesome library (kudos to the team) I’ve faced a problem in a kind of pickup & delivery problem.

For each node, the transit values for the capacity dimension are mixed (deliveries are positive and pickups are negative), so they can be, for example:

  • 1 = 10 deliveries & 9 pickups or only 1 delivery
  • -2 = 4 deliveries & 6 pickups or 3 deliveries & 5 pickups
  • 0 = the same number deliveries and pickups

I create the capacity dimension with fix_start_cumul_to_zero = False and slack_max = <The max capacity of a vehicle>. For checking that the capacity constraint of a vehicle is respected after optimizing, I obtain the total capacity used with something like: used_capacity = max(cumul_capacities) - min(cumul_capacities), where cumul_capacities is an array of the accumulated capacity of a vehicle while traversing its solution. But sometimes, used_capacity is greater than the max capacity of the vehicle.

How can I ensure the capacity constraint is respected?

About this issue

  • Original URL
  • State: closed
  • Created 6 years ago
  • Comments: 16 (2 by maintainers)

Most upvoted comments

Even with the basic AddDimension, the argument after slack_max is capacity (if the capacity is the same for all vehicles). Did you set it ?

On Fri, Mar 16, 2018 at 10:54 AM, Gwénaël Rault notifications@github.com wrote:

Did you define your capacity dimension using AddDimensionWithVehicleCapacity ? This way, you can define the maximum value of this dimension for each vehicle.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/622#issuecomment-373660987, or mute the thread https://github.com/notifications/unsubscribe-auth/AKjyUkDr_8cSDfRxQNL2es6pQr1Ascbsks5te4vcgaJpZM4SstOn .