GraphHopper.com | Forum | GitHub | Maps | Blog

Modelling quantized loads and vehicle compartments


#1

Hello,

First, kudos for the great work on developing graphhopper and jsprit. It is amazing how refined and well thought both tools are.

I have a VRP that involves hazardous liquid materials and, for safety reasons, a vehicle compartment carrying such materials must either be empty of completely full. So, if I have a 28 m3 load and a 6-compartments 30 m3 truck, for instance, I am not able to use such a truck for this cargo as the last compartment would only have 3 m3 (60% of its capacity), or would load only 25 m3 and have a 3 m3 pending deliver.

I though about modeling this using a hard constraint that would check if there are no partially filled compartments in the given vehicle and though of a couple of ways for storing the compartments descriptions of a vehicle:

  • Using a “dummy” capacity position to store the number of compartments in the vehicle (disadvantage of not being able to model vehicles with asymmetrical compartment sizes)
  • Piggybacking the compartments description in some String variable (like the vehicle id or vehicle type id)

I am not really sure if those are good alternatives or if there is a better way to do those and I am open to suggestions. Thanks in advance for any help on the matter.

Best regards


#2

if this is the case, then you can use a hard constraint or simply the skills feature in jsprit to disallow the vehicle to serve the job.

this looks more tricky and you will have to split the job before you define it - this looks like another layer of loop or optimization outside the vrp.


#3

Hi @jie31best,

Thank you for taking the time to help.

Could you elaborate on this? The way I got it, the skills feature works as a boolean flag: if a job requires a skill and the vehicle has it, no problem, if it doesn’t then it cannot take the job.[quote=“jie31best, post:2, topic:2422”]
this looks more tricky and you will have to split the job before you define it - this looks like another layer of loop or optimization outside the vrp.
[/quote]

Sounds fair.

Best regards


#4

Hi @jie31best, how are you doing?

I still haven’t found a good solution for my issues regarding the load allocation in the compartments, and I have two additional constraints regarding how it should be done and no idea on how to handle those additional constraints combined:

  • 1st, a truck often has asymmetrical compartments: meaning a 30m3 truck can have 6 x 5m3 compartments or 1 x 10m3 + 4 x 5m3 compartments, for instance or any other asymmetrical compartment layout.

  • 2nd, the truck compartments must be filled in the order they will be delivered, from the trucks end towards the driver cabin, for security reasons. That wouldn`t be a problem if the truck compartments for a single truck were all equal, but since they often aren’t, it poses a problem on job allocation, since placing a new job in a route can potentially void the fully loaded compartments and compartments filled in delivery order constraints in a truck with asymmetrical compartments.

    Let me give and example on how these constraints combined are tricky to fulfill. Ex: A truck with the following compartments 5/5/10/10 currently has a route containing 2 customers with sizes 10 and 10 (ok since they would fill the 1st and 2nd compartment for the last customer to visit and the 3rd compartment for the 1st one), if the job insertion tries to insert a new customer with size 5 in the last trip of the route, it would void the previous allocation and violate the safety rules, since the new customer would fill the 1st compartment and the 2nd customer to visit would have his order of 10 split between the 2nd compartment (ok, completely filled) and 3rd compartment (not ok, as only 5 of it’s capacity of 10 would be in use, and each compartment must be completely used by the same delivery, for safety reasons).

    Would you have any insight that could aid me on finding a good solution for these issues? Thanks for the help.

Best regards