GraphHopper.com | Forum | GitHub | Maps | Blog

Minimum load per vehicle


#1

I need to implement minimum load per vehicle. For example:

Vehicle 1
Capacity: 10
Min. Capacity: 7
Load at Beginning: 3
Load at End: 3

if Load at Beginning + Load at End < Min. Capacity then I must discard this route and set all activities as unasigned.

I don’t know where I can implement this logic and how to discard all activities so, I’m trying to increase costs with SoftContraint:

@Override
public double getCosts(VehicleRoutingProblemSolution solution) {
    double costs = 0.;

    for (VehicleRoute route : solution.getRoutes()) {

        //...

        Capacity loadAtDepot = stateManager.getRouteState(route, InternalStates.LOAD_AT_BEGINNING, Capacity.class);
        Capacity loadAtEnd = stateManager.getRouteState(route, InternalStates.LOAD_AT_END, Capacity.class);

        int total = loadAtDepot.get(0) + loadAtEnd.get(0);

        if (total < 4) {
            costs += Integer.MAX_VALUE;
        }
        
        //...
    }

But loadAtDepot is null. How can I archive this?


#2

just change

int total = loadAtDepot.get(0) + loadAtEnd.get(0);

to

int total = (loadAtDepot == null ? 0 : loadAtDepot.get(0)) + (loadAtEnd == null ? 0 : loadAtEnd.get(0));

btw, just curious, what is the use case of such constraint?


#3

@jie31best It worked, but the cost is not MAX_VALUE in this scenario:

VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("vehicleType").addCapacityDimension(0, 4);
VehicleType vehicleType = vehicleTypeBuilder.build();

VehicleImpl.Builder vehicleBuilder = VehicleImpl.Builder.newInstance("vehicle");
vehicleBuilder.setStartLocation(Location.newInstance(10, 10));
vehicleBuilder.setType(vehicleType);
VehicleImpl vehicle = vehicleBuilder.build();

Service service1 = Delivery.Builder.newInstance("1").addSizeDimension(0, 1).setLocation(Location.newInstance(5, 7)).build();
Service service2 = Delivery.Builder.newInstance("2").addSizeDimension(0, 1).setLocation(Location.newInstance(5, 13)).build();
Service service3 = Delivery.Builder.newInstance("3").addSizeDimension(0, 1).setLocation(Location.newInstance(15, 7)).build();

VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.addVehicle(vehicle);
vrpBuilder.setFleetSize(VehicleRoutingProblem.FleetSize.FINITE);
vrpBuilder.addJob(service1).addJob(service2).addJob(service3);
VehicleRoutingProblem problem = vrpBuilder.build();

Jsprit.Builder vraBuilder = Jsprit.Builder.newInstance(problem);
vraBuilder.setObjectiveFunction(new MinCost(problem, stateManager)); // My custom function
VehicleRoutingAlgorithm algorithm = vraBuilder.setStateAndConstraintManager(stateManager, constraintManager).buildAlgorithm();

VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);
new VrpXMLWriter(problem, solutions).write("output/problem-with-solution.xml");
SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();

±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | vehicle | start | - | 0 |
| 1 | vehicle | delivery | 2 | 6 |
| 1 | vehicle | delivery | 1 | 12 |
| 1 | vehicle | delivery | 3 | 22 |
| 1 | vehicle | end | - | 28 |
±-------------------------------------------------------------------------------------------------------------------------------+

It is for the situation where there are very few activities and it is cheaper to leave them unsigned. With the low demand, the cost of delivery increases because the routes need to consolidate deliveries between more distant regions


#4

hmm, but I got a solution with cost Integer.MAX_VALUE:

±-------------------------+
| problem |
±--------------±---------+
| indicator | value |
±--------------±---------+
| noJobs | 3 |
| noServices | 3 |
| noShipments | 0 |
| noBreaks | 0 |
| fleetsize | FINITE |
±-------------------------+
±---------------------------------------------------------+
| solution |
±--------------±-----------------------------------------+
| indicator | value |
±--------------±-----------------------------------------+
| costs | 2.147483647E9 |
| noVehicles | 1 |
| unassgndJobs | 0 |
±---------------------------------------------------------+
±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | vehicle | start | - | undef | 0 | 0 |
| 1 | vehicle | delivery | 3 | 6 | 6 | 6 |
| 1 | vehicle | delivery | 1 | 16 | 16 | 16 |
| 1 | vehicle | delivery | 2 | 22 | 22 | 22 |
| 1 | vehicle | end | - | 28 | undef | 28 |
±-------------------------------------------------------------------------------------------------------------------------------+

Anyway, if what you would like to achieve is to unassign all the jobs in a route under certain condition (e.g., with very few activities), you can use an InsertionEndsListener or an IterationEndsListener to conduct a post-processing after each iteration, and meanwhile, you can use a soft route constraint to encourage job insertion into routes with very few activities.

Best regards,
He