Explore fuel transportation solutions using jsprit

jsprit
1

problem

  • assume many fuel-trucks load various fuel type from depot, and deliver them to many filling stations.
  • a fuel-truck have three tank, each tank only filling up one kind of fuel.
  • one filling stations need two - four type fuel every day.

failed with jsprit

first try

I’d like to use dimensions to represent for various fuel type, But turn out I’m wrong too much, dimensions constraint can’t apply to fuel type.

second try

I’d like to treat fuel type as Skill, But Skill have no capacity constraint at all. stuck again.

SO HOW TO SOLVE THIS PROBLEM USING JSPRIT, CAN JSPRIT SOLVE THIS KIND OF PROBLEM.

THANKS ADVANED!!

2

There’s very little detail in your question and it’s a little hard to understand the English. Please give an example problem and expected solution.

Skills can have a capacity restriction since you can effectively “lock” vehicles by using the skill parameter, and vehicles themselves have fixed capacities. But this is something along the lines of the non-conventional setups I used to use, and there’s nowhere near enough detail in your question to a) try set up some such system and b) determine if it’s even warranted rather than some other constraint.

3

Thanks for your replay.

I’d like to use jsprit to solve the problem like this:
Assume there is a fuel-transportation company own a fuel depot, the company have five trucks, and each truck have two or three containers, and each container can only fill one fuel type(e.g ESSENCE Sans plomb, GASOIL, GASOIL SANS SOUFRE).
One day the company received ten orders from ten gas station, each order have two or three item, each item represent for one kind of fuel and how much amount gas-station required.
After received orders, the company must decide how to schedule the routes of their five trucks and transport the fuel to gas station in time.

When I’m trying to solve this problem use jsprit, I found that if all orders only required one type of fuel, that will be very easy to solve it by using jsprit, But I faced a serious issue that there are three type of fuel, and different fuel type can’t put into a same container, one container can only contain one kind of fuel, So my questions Is there any solution/measure/sugguestion in jsprit can solve the issue I faced.

I hope I described the problem clearly.

Thanks advanced.

4

If I understand correctly, each tank can only ever hold 1 type of fuel, forever. So, if tank1 held unleaded petrol one month ago, it will only be able to hold unleaded petrol today? Or, is the fuel requirement only relevant on a day-to-day basis?

5

fuel requirement only relevant on a day-to-day basis, in another word, fuel type requirement only relevant on each jsprit calculation.
In each calculation, we would like to add ten vehicle, and ten orders as input parameters.

6

Thanks for the reply, but that ruins my initial idea :). I’ve got a lot on this week, will try formulate something when I get a chance, sorry. It looks like you’ll need to add in a few hard constraints. Hopefully can get back to you this week.

1 Like
7

I was asking some time ago, a very similar question here https://discuss.graphhopper.com/t/fuel-delivery-problem/1660 (the product compartmentation problem)
I’ve managed to solve this using capacities.
Basically you make shipments with capacities this way:
Let’s assume you got order O with three products. P1 (3000 liters), P2 (5000 liters), P3 (7000 liters)
Now you add capacities this way

shipmentBuilder.addSizeDimension(1, 3000) 
shipmentBuilder.addSizeDimension(2, 5000) 
shipmentBuilder.addSizeDimension(3, 7000) 
//using dimension 0 for the total amount
shipmentBuilder.addSizeDimension(0, 15000)

Now, if you don’t have any truck that can carry 3 products, this order can’t be served.
Let’s assume you do have a 3 tank (compartment) truck.
Let’s assume that the truck tanks have the capacities as follows:
T1(4000 liters),T2(8000) and T3(10000)
Same as for shipments:

vehicleTypeBuilder.addCapacityDimension(1,10000)
vehicleTypeBuilder.addCapacityDimension(2,10000)
vehicleTypeBuilder.addCapacityDimension(3,10000)
vehicleTypeBuilder.addCapacityDimension(0,22000)
//this basically is saying that the truck can carry 10000 liters of product 1,2 or 3 (because it has a tank able to), but max 25000 liters.

Till now we have solved the capacity problems, but it’s not 100% accurate.
We can see that truck can carry the order, but if we slighly modify the order to have 7000 liters of P1 instead of 3000 it would work for Jsprit because we set that the truck can carry for each tank 10000 and the sum is smaller than the max capacity of the truck (23000liters).
But this wouldn’t work in reality because we can fit P3 in T3, P2 in T2 but, P1 that now have 7000liters couldn’t fit in T1.

Here comes the second implementation to solve the problem.

//passing the information about tanks as user data truck_tanks = [4000,8000,10000]
vehicleTypeBuilder.setUserData(truck_tanks)

add

    StateManager stateManager = new StateManager(vrp)
    ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager)
    HardActivityConstraint compartmentationConstraint = new CompartmentationConstraint(stateManager)
    constraintManager.addConstraint(compartmentationConstraint, ConstraintManager.Priority.CRITICAL)

Now we have to implement the CompartmentationConstraint class this way :

CompartmentationConstraint(RouteAndActivityStateGetter stateManager) {
        super()
        this.stateManager = stateManager
        defaultValue = Capacity.Builder.newInstance().build()
    }

/**
 * Checks whether there is enough capacity to insert newAct between prevAct and nextAct.
 */
@Override
HardActivityConstraint.ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
    if (!(newAct instanceof PickupShipment) && !(newAct instanceof DeliverShipment)) {
        return HardActivityConstraint.ConstraintsStatus.FULFILLED
    }
    Capacity loadAtPrevAct
    if (prevAct instanceof Start) {
        loadAtPrevAct = stateManager.getRouteState(iFacts.getRoute(), InternalStates.LOAD_AT_BEGINNING, Capacity.class)
        if (loadAtPrevAct == null) {
            loadAtPrevAct = defaultValue
        }
    }
    else {
        loadAtPrevAct = stateManager.getActivityState(prevAct, InternalStates.LOAD, Capacity.class)
        if (loadAtPrevAct == null) {
            loadAtPrevAct = defaultValue
        }
    }
    //here we add upp the products the orders
    Capacity capacity
    VehicleType vehicleType = iFacts.getNewVehicle().getType()
    if (newAct instanceof PickupShipment) {
        capacity = Capacity.addup(loadAtPrevAct, newAct.getSize())
        if (!capacity.isLessOrEqual(vehicleType.getCapacityDimensions())) {
            return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED
        }
    }
    if (newAct instanceof DeliverShipment) {
        capacity = Capacity.addup(loadAtPrevAct, Capacity.invert(newAct.getSize()))
        if (!capacity.isLessOrEqual(vehicleType.getCapacityDimensions())) {
            return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED_BREAK
        }
    }
    //we need to implement this method
    if (!productsFitOnTruck(capacity, (List) vehicleType.getUserData())) {
        return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED_BREAK
    }

    return HardActivityConstraint.ConstraintsStatus.FULFILLED
}

The last thing is to implement a FAST working method

private Boolean productsFitOnTruck(capacity, (List) vehicleType.getUserData()) {…}

i’m not going to write the implementation code here, because it’s not Jsprit related, but the general idea here is:
You have some products in

capacity

and you have some tanks in

(List) vehicleType.getUserData()

and have to write an algorithm that determines if the products will fit in the truck tanks or not.
Like in your case where you have a limited amount of tanks (max 3) and a limited amount of products (max 4)
i would write an algorithm that fits the first product on the empty tanks, then the next product on empty and non empty tanks (because there is product 1 in one ore more of them) and then the last product.
If you can fit (in some way) all of the products you return true else false.

Hope this helps.

2 Likes
8

thanks very much
I will try this