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.

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

how to add capacity to vehicles? #54

Open
chkwon opened this issue Apr 25, 2022 · 16 comments
Open

how to add capacity to vehicles? #54

chkwon opened this issue Apr 25, 2022 · 16 comments

Comments

@chkwon
Copy link

chkwon commented Apr 25, 2022

Sorry for asking a question here. I couldn't find an appropriate forum. Please let me know if there is a better place for asking questions about pyvroom.

I'm trying to solve CVRP and couldn't figure out how to add the vehicle capacity.

import vroom
problem_instance = vroom.Input()

problem_instance.set_durations_matrix(
    profile="car",
    matrix_input=[[0, 2104, 197, 1299],
                  [2103, 0, 2255, 3152],
                  [197, 2256, 0, 1102],
                  [1299, 3153, 1102, 0]],
)

problem_instance.add_vehicle(
    vroom.Vehicle(0, start=0, end=0, capacity=[4])
)

This code generates the following error:

---------------------------------------------------------------------------
VroomInputException                       Traceback (most recent call last)
<ipython-input-10-9c3aa544d56c> in <module>
      9 )
     10 
---> 11 problem_instance.add_vehicle(
     12     vroom.Vehicle(0, start=0, end=0, capacity=[4])
     13 )

/usr/local/lib/python3.9/site-packages/vroom/input/input.py in add_vehicle(self, vehicle)
    135             vehicle = [vehicle]
    136         for vehicle_ in vehicle:
--> 137             self._add_vehicle(vehicle_)
    138 
    139     def set_durations_matrix(

VroomInputException: Inconsistent capacity length: 1 instead of 0.

What is the correct way? Thanks for help!

@jcoupey
Copy link
Contributor

jcoupey commented Apr 25, 2022

This inconsistency is because the initial problem is defined with no capacity (zero-length capacity array).

On the C++ side, we have a Input::set_amount_size function that is used to adjust this after creating the problem instance. I'm not sure this is accessible through the python bindings.

@jonathf will be able to comment further and it looks like he already fired a related PR (#55).

@jonathf
Copy link
Collaborator

jonathf commented Apr 25, 2022

The canonical way is to pre-define the capacity in the init with vroom.Input(amount_size=1), but I agree that is quite unintuitive. I''ve updated the code to allow for the format you are proposing.

I've pushed the changes to version 0.0.11. Let me know if that works for you.

@chkwon
Copy link
Author

chkwon commented Apr 25, 2022

Thanks for the quick help! Version 0.0.11 works fine for the above code.

After setting the vehicle capacity, how can I add the load size for jobs?

I tried:

problem_instance.add_job(
    vroom.Job(id=1414, location=1, delivery=[10])
)

But it says:

---------------------------------------------------------------------------
VroomInputException                       Traceback (most recent call last)
<ipython-input-7-075f1d1c79d0> in <module>
----> 1 problem_instance.add_job(
      2     vroom.Job(id=1414, location=1, delivery=[10])
      3 )

/usr/local/lib/python3.9/site-packages/vroom/input/input.py in add_job(self, job)
    119             job = [job]
    120         for job_ in job:
--> 121             self._add_job(job_)
    122 
    123     def add_shipment(

VroomInputException: Wrong job type.

@jonathf
Copy link
Collaborator

jonathf commented Apr 25, 2022

There is a difference between "jobs" and "shipments". Jobs assumes single jobs, and shipments assumes one pickup and one delivery. Pickups are signified by using the pickup= flag, and delivery with the delivery= flag. The single job is defined with not being either delivery or pickup. Jobs are added through add_jobs while shipments (as a pair) are added through add_shipment

This is a bit work in progress, and I am looking into improving this interface, if that makes sense.

@chkwon
Copy link
Author

chkwon commented Apr 25, 2022

@jonathf Thanks a lot for the kind explanation. It was very helpful to understand the concepts used in vroom.

This is what I ended up with:

import vroom

problem_instance = vroom.Input()

problem_instance.set_durations_matrix(
    profile="car",
    matrix_input=[[0, 2104, 197, 1299],
                  [2103, 0, 2255, 3152],
                  [197, 2256, 0, 1102],
                  [1299, 3153, 1102, 0]],
)

problem_instance.add_vehicle(
    vroom.Vehicle(0, start=0, end=0, capacity=[25])
)

problem_instance.add_shipment(
    vroom.JobPickup(id=101, location=0, amount=vroom.Amount([10])),
    vroom.JobDelivery(id=102, location=1, amount=vroom.Amount([10]))
)

problem_instance.add_shipment(
    vroom.JobPickup(id=201, location=0, amount=vroom.Amount([12])),
    vroom.JobDelivery(id=202, location=2, amount=vroom.Amount([12]))
)

problem_instance.add_shipment(
    vroom.JobPickup(id=301, location=0, amount=vroom.Amount([15])),
    vroom.JobDelivery(id=302, location=3, amount=vroom.Amount([15]))
)

solution = problem_instance.solve(exploration_level=5, nb_threads=4)
solution.routes

Just one more question about amount=vroom.Amount([15])). Is this correctly done? What was the reason to avoid a simple form like amount=15? I'm sure there are more complicated cases to handle, but just curious about it to understand vroom better.

@jcoupey
Copy link
Contributor

jcoupey commented Apr 25, 2022

What was the reason to avoid a simple form like amount=15?

This way you can input an arbitrary number of restrictions (e.g. weight, volume, number of boxes) and you get to choose which metrics are relevant for your use-case.

amount=vroom.Amount([15]))

Note that the amount key is deprecated for jobs and will default to a delivery at job level. You should rather use job.pickup or job.delivery keys explicitly, especially if you mix jobs with shipments.

A delivery amount is something that is loaded at vehicle startup and impacts load up to the delivery step (at job location), whereas a pickup amount is something that is brought back at the end of the route so it impacts load from the job location up to the end of the route. In real life, job objects can hold both pickup and delivery values. Typical academic benchmarks don't account for this difference expect partly in the VRPB (Backhaul) variant.

@chkwon
Copy link
Author

chkwon commented Apr 25, 2022

@jcoupey Thanks a lot!!

problem_instance.add_shipment(
    vroom.Job(id=101, location=0, pickup=vroom.Amount([10])),
    vroom.Job(id=102, location=1, delivery=vroom.Amount([10]))
)

Is this what you mean?

@jcoupey
Copy link
Contributor

jcoupey commented Apr 25, 2022

I'm not familiar with how the python bindings work but yes, that would be something along those lines.

Again it does not make a real difference if you're working with typical academic CVRP (single-depot-delivery-only) benchmarks but the bottom line is that you can define linehauls or backhauls this way.

@jonathf
Copy link
Collaborator

jonathf commented Apr 25, 2022

That is correct, though the Amount part is redundant in Python. E.g.:

problem_instance.add_shipment(
    vroom.Job(id=101, location=0, pickup=[10]),
    vroom.Job(id=102, location=1, delivery=[10])
)

@chkwon
Copy link
Author

chkwon commented Apr 25, 2022

Thanks a lot guys. Well, what about the multi-depot problem, when each shipment's pickup location can be any of the available depots? For example, if we have locations 0 and 1 as depots, then the pickup location can be either 0 or 1. In this case, I'd like to have something like

problem_instance.add_shipment(
    vroom.Job(id=101, location=0 or 1, pickup=[10]),
    vroom.Job(id=102, location=3, delivery=[10])
)

@jcoupey
Copy link
Contributor

jcoupey commented Apr 26, 2022

You only really want to use shipments in a "real" pickup-and-delivery setup (e.g. for PDPTW). It makes sense when pickup and delivery locations are scattered all over the place, but other situations can be modeled with jobs (single-location tasks).

what about the multi-depot problem

Simply describe the deliveries as job objects with a delivery key. Then use the depot locations as start/end for vehicles available at various depots.

@jonathf
Copy link
Collaborator

jonathf commented Apr 26, 2022

Good question. I'd like to know if that is possible too. Not my expertice, so I am limited to asking questions on this.

I'm not sure I understand your answer @jcoupey.

If you add a job with only delivery, won't that be rejected as input? add_job must have a single job, and add_shipment must have one pickup and one delivery, right?

Also, are you saying that the only way to achieve multi-depot, you need to force the vehicles to start and/or end at the various start depot locations?

@chkwon
Copy link
Author

chkwon commented Apr 26, 2022

@jcoupey I have this code:

import vroom

problem_instance = vroom.Input(amount_size=1)

problem_instance.set_durations_matrix(
    profile="car",
    matrix_input=[[0, 100, 100, 100],
                  [100, 0, 100, 1],
                  [100, 100, 0, 100],
                  [100, 1, 100, 0]],
)

problem_instance.add_vehicle(
    vroom.Vehicle(0, start=0, end=0, capacity=[200])
)

problem_instance.add_vehicle(
    vroom.Vehicle(1, start=1, end=1, capacity=[10])
)

problem_instance.add_job(
    vroom.Job(id=102, location=2, delivery=[10])
)

The last line generates this error:

---------------------------------------------------------------------------
VroomInputException                       Traceback (most recent call last)
~/Documents/GitHub/MDVRP/src/test.py in <module>
     21 )
     22 
---> 23 problem_instance.add_job(
     24     vroom.Job(id=102, location=2, delivery=[10])
     25 )

/usr/local/lib/python3.9/site-packages/vroom/input/input.py in add_job(self, job)
    119             job = [job]
    120         for job_ in job:
--> 121             self._add_job(job_)
    122 
    123     def add_shipment(

VroomInputException: Wrong job type.

@jcoupey
Copy link
Contributor

jcoupey commented Apr 26, 2022

Maybe we have some mismatch between the initial C++ API and the current python binding, but I'm referring to the job and shipment objects as described in the API documentation.

If you add a job with only delivery, won't that be rejected as input? add_job must have a single job, and add_shipment must have one pickup and one delivery, right?

Probably there is a confusion here: a job object can hold a delivery key that is basically an amount and is built using Input::add_job. A shipment object has one pickup and one delivery, each of which are very similar to a job (they are tasks, not amounts). Those are passed to Input::add_shipment.

Also, are you saying that the only way to achieve multi-depot, you need to force the vehicles to start end at the various start depot locations?

Not the only way but the most efficient. If you define a pickup place at the depot location for each delivery, you're artificially doubling the size of the problem. Plus in that case you end up with the problem from previous comment were you need to pre-assign deliveries to depots. You don't have to do this if you define one job per delivery and a number of vehicles based at each depot.

@jcoupey I have this code:

Looks legit AFAICT but again I have no clear visibility on how the definitions work from the python bindings.

@jonathf
Copy link
Collaborator

jonathf commented Apr 26, 2022

You are right, I made a mistake when creating the bindings for shipment.

I'm putting fixing this on the top of my todo-list for pyvroom.

@jonathf
Copy link
Collaborator

jonathf commented May 2, 2022

I've made a new relase version 0.0.14 now.

There is a small descrepency between the C++ code and the API, and I've chosen to mimic the API for now. That means Job now are explusively used for single jobs, and is unchanged for the example above.
The shipment interface has changed a little. You now have to either do as the API:

shipment = vroom.Shipment(
  pickup=vroom.ShipmentStep(id=1, location=1),
  delivery=vroom.ShipmentStep(id=2, location=2),
)
problem_instance.add_job(shipment)

or for convinience, use add_shipment directly:

problem_instance.add_shipment(
  pickup=vroom.ShipmentStep(id=1, location=1),
  delivery=vroom.ShipmentStep(id=2, location=2),
)

Let me know if it works well.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants