GraphHopper.com | Forum | GitHub | Maps | Blog

Fuel delivery problem


#1

Originally i was asking how to make a shipment allow multiple possible pickup location.


Related shipments, but only one in solution
Explore fuel transportation solutions using jsprit
#2

By deeply exploring the mailing lists i now know this is not possible.
I’ll describe the full problem below, describe my theoretical solution and seek for suggestions.
(I’m considering to change the topic title in something more related to the actual problem)

Problem:
I have clients (gas stations) spread among a certain region.

1- Clients will place orders and order different quantity of 6 possible products p1,p2,p3,p4,p5,p6 ( p1,p2,p3,p4 being different diesel types, p5,p6 different gasoline types)

2- To fulfill the orders i have 4 depos (A,B,C,D) each with a number of vehicles, let’s say 3 vehicles for each depo.

3- Not all depos can serve all products. For example depo A can only serve p1,p2,p4.

4- Vehicles can load the products from any depo, but by the end of the day they must return to their own depo. They can do multiple trips.

5- Vehicles are all different and have the following types of constraints.
Some vehicles can’t load at some depo. Let’s say vehicle v1 can’t load at depo B, but can load at A,C,D.

6- (Important: The product compartmentation problem)
Vehicles have 2 or 3 tanks with their own capacity.For example v2 has three tanks witch has the following capacities tank1 : 2000 liters, tank2 : 1500 liters, tank3 : 4000 liters.
Tanks are not product specific. For example i can put p1 in tank1, p1 in tank2 and p5 in tank3, but i can put p5 in tank1, p1 in tank2 and p1 in tank3.
Not all vehicles can carry all products. Only some vehicles can carry the gasoline type products(p5,p6), but all vehicles can carry the diesl type products (p1,p2,p3,p4)
In addition if a vehicle can carry the gasoline type products, it can carry it on any of the tanks, but once carried a gasoline type product it cannot carry another gasoline type product, only diesel type products.
Basicly p5 and p6 can’t be in the same vehicle.
Obviously none of the products can be mixed.

Solution:
My proposed solutions are basically two:
a- Fork jsprit to allow more pickup locations for shipment.
Implement the product compartmentation somehow…

b- Consider all possible shipments and then put a constraint that only one will be considered.
Consider all possible compartmentations and add a vehicle for every compartmentation and then put a constraint that only one will be considered.

I’m not too confident to choose the first solution so i think i’ll pick the second one, having the downside of introducing some randomness (hoping not too much).

The following is a theoretical solutions to the above problem points
1- Split the orders into more orders, each one containing only one type of product.
So if a client placed an order containing 1000 of p1 and 2000 of p5, i’ll split this order in two orders, the first having 1000 of p1 and the second having 2000 of p5

2,3,5- Model orders as shipments having as pickup location any possible depo. In this phase i will filter out the depos that don’t serve a particular product by not creating that shipment. In the shipment i’ll put the required skill “depo_name”. This way if a vehicle can’t access the depo won’t have the “depo_name” skill.
If i consider having 100 orders (shipments) * 4 depos = 400 shipments

4- setReturnToDepot(true) should resolve this.

6- Calculate all the possible compartmentations a vehicle can have and add them as different vehicles. For example if a vehicle v3 has two tanks (with 1000 and 3000 liters of capacity) and can carry gasoline products i’ll create the following vehicles:
v3-1 with .addCapacityDimension(p1_index, 1000).addCapacityDimension(p1_index, 3000). This means that this vehicle can only carry p1 on both tanks
v3-2 with .addCapacityDimension(p1_index, 1000).addCapacityDimension(p2_index, 3000). This means that this vehicle can only carry p1 on the first tank and p2 on the second tank.

v3-n with .addCapacityDimension(pn_index, 1000).addCapacityDimension(pm_index, 3000). This means that this vehicle can only carry pn on the first tank and pm on the second tank.
This way i resolve the problem that a vehicle can’t carry gasoline products at all (because i’ll not generate that kind of vehicle) and the problem that if it can carry gasoline products it will not be able to carry two of them (because i’ll not generate that kind of vehicle).
If i consider the medium number of compartmentations for vehicle (some have more, some have less) around 25 and consider having 10 vehicles * 25 = 250 vehicles
I think this resolves the product compartmentation problem.

What do you think?
Is this the right way to proceed or am i missing something?


#3

Hi.

This is just my personal opinion but this post is too dense for me to get my head around properly. However, the problem you have listed seems legitimate as do your concerns. Is there any way at all that you can break this down into distinct problems and we (not just myself but others) can work through them sequentially? Often a misstep near the beginning is what is causes bloat in the whole approach. Particularly, 6-Important is causing me some issues in understanding.


#4

Thank you for the patience!

I’ll try to make a simple example:
I have 3 orders by 3 clients.
Order 1 : 2000 liters of product1 (p1) and 500 liters of product5 (p5)
Order 2 : 1000 liters of product2 (p2) and 1000 liters of product5 (p5)
Order 3 : 1000 liters of product1 (p1) and 500 liters of product5 (p5)
I have 2 depos (A,B) and 1 vehicle per depo. V1 in A and V2 in B

I can model the orders as shipments by adding:
For order 1 :
.addSizeDimension(1, 2000) //product1
.addSizeDimension(5, 500) //product5
For order 2:
.addSizeDimension(2, 1000) //product2
.addSizeDimension(5, 1000) //product5
For order 1 :
.addSizeDimension(1, 1000) //product1
.addSizeDimension(5, 1000) //product5

At this moment i need to know the .setPickupLocation(some_location), but i don’t, because either A, either B are valid pickup locations. And this is the first major problem.

Let’s say V1 has two tanks:
Tank 1 (t1) has a capacity of 3000 liters
Tank 2 (t2) has a capacity of 1500 liters

Let’s say V2 has three tanks:
Tank 1 (t1) has a capacity of 1000 liters
Tank 2 (t2) has a capacity of 2000 liters
Tank 3 (t3) has a capacity of 1500 liters

The tanks of V1 and V2 are not product specific, so they can carry any product.
So i can’t do the following on Truck 1 :
.addCapacityDimension(<id_of_product>, 1500)
.addCapacityDimension(<id_of_product>, 1000)
because the t1 and t2 can carry any product. And this is the second major problem.
I call this the “The product compartmentation problem”, and this is how it works in this example:
Vehicle 1:
Can carry Order1 and Order3 simultaneously because they in total are:
3000 liters of p1 and 1000 liters of p5 and the products can fit this way:
3000 liters of p1 in tank1 and 1000 liters of p5 in tank2 (i would have 500 liters of free space in tank2, but this is fine)
Can’t carry Order1 and Order2 simultaneously because they in total are:
2000 liters of p1, 1000 of p2 and 1500 liters of p5. V2 has only 2 tanks and those are 3 different products that can’t be mixed.

The combinations can be quite a few in an extended real-life problem.

Here’s a picture to illustrate what’s going on:


#5

Many thanks for your clarifications. This is an interesting problem; I will sleep on it and see if I have any suggestions in the coming days. I will get back to you.


#6

Hi @traveler.

  1. I think your proposed approach regarding multiple possible pickup locations for one job is the way to go.

For example, for job S, assume depot A, C and D are possible pickup locations, then you create three shipments S_a, S_c and S_d, and add a constraint that only one of the three can be served. I think it would be a hard route constraint such that, if the newAct job is one of the three, and if any of the other two are already served (you need a state updater to record this), the insertion is not allowed.

This seems to depend heavily on the order of insertion (in best insertion, half time it depends on job priority, and half time it is random; in regret insertion, it depends on regret score). It may or may not lead to sub-optimal result - I am not sure, and you might want to do some tests regarding this.

  1. The other important requirement is the tank constraint, and I don’t think it would be easy to fulfill in Jsprit.

There is a related post, which might be helpful to you: https://groups.google.com/forum/#!topic/jsprit-mailing-list/TEAyKlNzr_0

If you add vehicles in the way you proposed, the number of vehicles seems to grow exponentially with the number of tanks per vehicle.

Btw, .addCapacityDimension(p1_index, 1000).addCapacityDimension(p1_index, 3000) is not going to do what you expect. You should just .addCapacityDimension(p1_index, 1000 + 3000).

  1. Other requirements seem okay to me. For example, p5 and p6 can’t be in the same vehicle, which would need a hard route constraint; some vehicles can’t load at some depo, which I think the skill constraint, as you proposed, could solve.

  2. There might be other constraints you might want to consider. For example, you might want (or is it already implicitly included?) the multiple jobs for one client to be assigned to one vehicle and delivered at the same time (in direct sequence), which would need a hard activity constraint.

Best regards,
He


#7

Thanks for the response @jie31best

Regarding the compartmentation problem i am willing to do different versions of same vehicle and i’ll try keep the number of vehicles low.
So if i have a vehicle V1, i’ll make V1-a, V1-b and V1-c.
Is there a way to tell at a certain point if a vehicle has been used and deny the others?
For example if the algorithm uses V1-b, it shouldn’t be able to use V1-a or V1-c.

Regards!


#8

Hi @traveler,

I think this would be similar to the constraint that only one of multiple jobs can be served.

You will need a state updater to record what vehicles have been used. Then in the hard route constraint, assume the new vehicle is v1-i, if any of other v1-j has been used, and if the route vehicle is not v1-j (assuming vehicle switch is allowed), then the insertion should be disallowed.

Best regards,
He


#9

Hi all,
sorry to bump again this topic, but the problem persists.

I was able to solve the compartmentation problem (the setUserData in the latest jsprit release made it much simpler),
but the “multiple pickup locations” for single shipment still persists.
I was able to solve it by creating shipmet siblings, but as expected the results are more random than sub-optimals.

Any other suggestion on how to deal with this problem?

Thanks!


#10

Hey,

Your are so awesome, so nice of you.

Thanks for your comments on Explore fuel transportation solutions using jsprit, But I’m still confused a little.

How did you solve the compartmentation problem Fuel delivery problem and Can you please share your final solution/implementation with more details, if I may ask?

Regards!