Support for mixing independent pickups and deliveries

[vaibhavmehrotra94]

I am trying to use vroom for pickup and delivery scenario is it possible to use it for the same.

For Eg. :- Let's assume my vehicle has a capacity of 200 and I have jobs for delivery which have amount 100 each and pickup with amount 70. Now is it possible to configure VROOM's input in such a way that the truck is assigned to pickup 70 amount somewhere during the trip without breaching the vehicle capacity.

The provided JSON is what I tried to input for solving the above explained situation. Here I have taken job amount in negative for pickup's. (as for job's with id 2 and 4)

  "jobs": [
    {
      "id": 1,
      "location": [77.6447257, 12.8911828],
      "time_windows": [[64800, 72000]],
      "service": 11880,
      "amount": [256]
    },
    {
      "id": 1,
      "location": [77.6447257, 12.8911828],
      "time_windows": [[64800, 72000]],
      "service": 0,
      "amount": [-82]
    },
    {
      "id": 2,
      "location": [77.6500367, 12.8892035],
      "time_windows": [[64800, 72000]],
      "service": 1620,
      "amount": [-205]
    },
    {
      "id": 3,
      "location": [77.644629, 12.8948467],
      "time_windows": [[28800, 43200]],
      "service": 3000,
      "amount": [226]
    },
    {
      "id": 3,
      "location": [77.644629, 12.8948467],
      "time_windows": [[28800, 43200]],
      "service": 0,
      "amount": [-262]
    },
    {
      "id": 4,
      "location": [77.6141978, 12.8590643],
      "time_windows": [[39600, 50400]],
      "service": 3420,
      "amount": [-247]
    },
    {
      "id": 5,
      "location": [77.6400817, 12.9048541],
      "time_windows": [[28800, 43200]],
      "service": 3540,
      "amount": [232]
    },
    {
      "id": 6,
      "location": [77.6178125, 12.853929],
      "time_windows": [[64800, 72000]],
      "service": 1680,
      "amount": [234]
    },
    {
      "id": 7,
      "location": [77.6375484, 12.9233757],
      "time_windows": [[28800, 43200]],
      "service": 1740,
      "amount": [127]
    },
    {
      "id": 8,
      "location": [77.64630199999999, 12.9004965],
      "time_windows": [[39600, 50400]],
      "service": 2400,
      "amount": [-156]
    },
    {
      "id": 9,
      "location": [77.6141978, 12.8590643],
      "time_windows": [[54000, 64800]],
      "service": 1620,
      "amount": [-93]
    }
  ],
  "vehicles": [
    {
      "id": 1000,
      "start": [77.7352604, 13.0366671],
      "end": [77.7352604, 13.0366671],
      "capacity": [305],
      "time_window": [25200, 77400]
    },
    {
      "id": 1001,
      "start": [77.7352604, 13.0366671],
      "end": [77.7352604, 13.0366671],
      "capacity": [305],
      "time_window": [25200, 77400]
    }
  ],
  "options": { "g": true }
}```

[nielsenko]

See #189

[jcoupey]

@vaibhavmehrotra94 as mentioned above, we're tracking pickup and delivery constraints in #189. In the literature, P&D means jobs are to be scheduled in the same route and in the right order (pickup along the way, then delivery at some point down the line).

But it looks like you may not really have precedence constraints, and maybe not even require that your "pickups" and "deliveries" be in the same route, am I right?

[vaibhavmehrotra94]

@jcoupey For my use case I have both kinds of pickups...one that doesn't follow the precedence constraint and the other that does.

For eg. Let's say that I have a warehouse which is the start and end point for each vehicle. Now I have jobs that belong to 4 categories Delivery, Pickup and Delivery+Pickup, Pickup+Delivery.

Delivery :- Something is loaded in the vehicle at warehouse before the trip starts and then it delivers it somewhere before returning back.

Pickup:- During the trip, vehicle can pickup one or more things which are to be brought back to the warehouse.

Pickup+Delivery:- Here the vehicle will pickup something during trip after leaving the warehouse and will deliver the same to some location before returning back. Here Nothing will be loaded at or brought back to the warehouse.

Delivery+Pickup:- Here the vehicle will deliver something at a location that was loaded in it before the trip started and will pickup some other thing from the same location that will be brought back to the warehouse.

[jcoupey]

@vaibhavmehrotra94 thanks for the clarification.

Delivery

We do that already with the current behaviour.

Pickup

Should be modelled with a negative amount. Current limitations are a known bug (#197) and the fact that we are probably missing some checks for pickups validity.

Pickup+Delivery

This is #189.

Delivery+Pickup

Could be modelled either with a single job using the amount difference, or with 2 jobs (1 pickup and 1 delivery) if performing them in different routes or at different times is fine.

Setting aside the scope of #189, the problem for this issue comes down to making sure we have all relevant validity checks for vehicle capacity when mixing pickups and deliveries.

[vaibhavmehrotra94]

@jcoupey I guess resolving thepickupissue with entering negative value will partially solve the
Delivery+Pickup issue as well as I noticed in vroom if the input has same long, lat and job id, 95% of the times those jobs are assigned in the same trip next to each other.

[jcoupey]

It's possible to test this off the master branch using the new delivery and pickup keys for jobs. Check out the updated API docs, any feedback welcome!

EDIT: just to be clear, backward compatibility is provided for problems formatted with the deprecated amount key for jobs (an amount is just like a delivery with an empty pickup).