Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Support for mixing independent pickups and deliveries #241

Closed
vaibhavmehrotra94 opened this issue Jun 14, 2019 · 6 comments
Closed

Support for mixing independent pickups and deliveries #241

vaibhavmehrotra94 opened this issue Jun 14, 2019 · 6 comments
Assignees
@jcoupey
Labels
feature request
Milestone
v1.5.0

Comments

@vaibhavmehrotra94
Copy link

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
Copy link

See #189

@jcoupey
Copy link
Collaborator

jcoupey commented Jun 15, 2019

@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
Copy link
Author

@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
Copy link
Collaborator

jcoupey commented Jun 17, 2019

@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.

@jcoupey jcoupey changed the title Support for pickup and delivery Support for mixing independent pickups and deliveries Jun 17, 2019
@jcoupey jcoupey added this to the v1.5.0 milestone Jun 17, 2019
@vaibhavmehrotra94
Copy link
Author

@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 jcoupey mentioned this issue Jun 27, 2019
Closed
@jcoupey jcoupey self-assigned this Jun 27, 2019
@jcoupey jcoupey mentioned this issue Aug 8, 2019
Merged
18 tasks
@jcoupey
Copy link
Collaborator

jcoupey commented Sep 17, 2019 •
edited

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).

@jcoupey jcoupey closed this as completed Sep 17, 2019
@jcoupey jcoupey mentioned this issue Oct 7, 2019
Merged
15 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@jcoupey jcoupey

Labels
feature request
Projects
None yet
Milestone
v1.5.0
Development

No branches or pull requests
3 participants
@jcoupey @nielsenko @vaibhavmehrotra94