GraphHopper.com | Forum | GitHub | Maps | Blog

Max departures per time


#1

Hello. First, thank for this fantastic library: it’s great.

I’m trying to implement a constraint to limit the number of routes that start in a particular time window (e.g. limiting the number of departures per day). My thinking was to add a StateUpdater to increment the number of routes that start within a particular time window and a HardRouteConstraint to inspect the state and return whether or not the maxDepartures limit is satisfied.

My code is as follows:

public class DeparturesPerDay implements HardRouteConstraint {
    private StateManager stateManager;
    private StateId stateId;
    private int maxDeparturesPerDay;


    public DeparturesPerDay(StateManager stateManager, StateId stateID, int maxDeparturesPerDay) {
        this.stateManager = stateManager;
        this.stateId = stateID;
        this.maxDeparturesPerDay = maxDeparturesPerDay;
    }

    private int getMax(HashMap<Integer, HashMap<VehicleRoute, Integer>> map) {

        Map.Entry<Integer, Integer> maxEntry = null;
        if (map == null || map.isEmpty()) {
            return 0;
        } else {
            int max = 0;
            for(Map<VehicleRoute, Integer> val: map.values())
            {
                int sum_of_all_departing = 0;
                for(Integer i: val.values())
                {
                    sum_of_all_departing+=i;
                }
                max = sum_of_all_departing > max ? sum_of_all_departing: max;
            }
            return max;
        }
    }

    public boolean fulfilled(JobInsertionContext iFacts) {
        // get the maximum number of departures per day in the problem state
        HashMap<Integer, HashMap<VehicleRoute, Integer>> maxDepaturesState = stateManager.getProblemState(stateId, HashMap.class);
        Integer maxDeparturesInADay = getMax(maxDepaturesState);
        System.out.println(maxDeparturesInADay);
        return (maxDeparturesInADay <= maxDeparturesPerDay);

    }

}

public class UpdateDeparturesPerDay implements StateUpdater, ActivityVisitor, IterationEndsListener {

    private StateManager stateManager;
    private StateId maxBoatStateId;
    private HashMap<Integer, HashMap<VehicleRoute, Integer>> departuresPerDay = new HashMap<>();
    private VehicleRoute route;


    UpdateDeparturesPerDay(StateManager stateManager, StateId maxBoatStateID) {
        this.stateManager = stateManager;
        this.maxBoatStateId = maxBoatStateID;
    }

    @Override
    public void informIterationEnds(int iteration, VehicleRoutingProblem vrp, Collection<VehicleRoutingProblemSolution> soln) {
        this.departuresPerDay.clear();
    }

    @Override
    public void begin(VehicleRoute route) {
        this.route = route;
        double departureTime = route.getStart().getEndTime();
        int departureDay = (int) Math.ceil(departureTime / (24.0 * 60.0));
        HashMap<VehicleRoute, Integer> routeDepartures = departuresPerDay.get(departureDay);
        if (routeDepartures == null) {
            // there have been no route keys inserted on the day
            routeDepartures = new HashMap<>();
        }
        routeDepartures.put(this.route, 1);
        departuresPerDay.put(departureDay, routeDepartures);
        stateManager.putProblemState(maxBoatStateId, HashMap.class, departuresPerDay);
    }

    @Override
    public void visit(TourActivity activity) {
    }

    @Override
    public void finish() {

    }


}
   StateManager stateManager = new StateManager(this.problem);
        stateManager.addStateUpdater(new UpdateDeparturesPerDay(
                stateManager,
                stateManager.createStateId("max_departures_per_day")));

        //create relevant constraints
        DeparturesPerDay departuresPerDayConstraint = new DeparturesPerDay(
                stateManager,
                stateManager.createStateId("max_departures_per_day"),
                appConfig.max_boats_per_day_from_port
        );

        ConstraintManager constraintManager = new ConstraintManager(this.problem, stateManager);
        constraintManager.addConstraint(departuresPerDayConstraint);
        }

But the constraint is not being enforced. Obviously I’m misunderstanding how to do this, so any steering help would be appreciated.


#2

So after some research I realized that jsprit doesn’t actually change the Start as part of the ruin and recreate strategy, so there’s no way to dynamically enforce a constraint on sequential Starts (i.e. you could set the theoretical earliest departure time for each vehicle - but I wanted to limit the number of vehicles that can depart in a time window). So…in a bit of a hack, I created a StateUpdater that listens for the ruin step - and just arbitrarily forces some Routes to start later (according to a max departures per day rule that I set up). It seems to work - but if anyone has better ideas of how to do this, I’d appreciate the input.

And…if I get really crazy, maybe I can contribute in some way to this repo - it’s really clever.

public class UpdateDeparturesPerDay implements StateUpdater, RuinListener {

    private StateManager stateManager;
    private StateId maxDeparturesPerDayStateId;
    private SortedMap<Integer, Set<VehicleRoute>> departuresPerDay = new TreeMap<>();
    private int maxDepartures;

    UpdateDeparturesPerDay(StateManager stateManager, StateId maxDeparturesPerDayStateId, int maxDeparturesPerDay) {
        this.stateManager = stateManager;
        this.maxDeparturesPerDayStateId = maxDeparturesPerDayStateId;
        this.maxDepartures = maxDeparturesPerDay;
    }

    @Override
    public void ruinStarts(Collection<VehicleRoute> routes) {
        /*
        naive implementation - just sequentially go through the routes and make sure they depart on the
        firstAvailableDay. A more robust implementation might randomly cycle through the routes to make sure
        the solution is being explored more fully.
         */
        departuresPerDay.clear();
        for (VehicleRoute r : routes) {
            int firstAvailableDay = MapUtil.getFirstAvailableDay(MapUtil.aggMap(departuresPerDay), maxDepartures);
            r.getStart().setEndTime(6D * 60D + firstAvailableDay * 24D * 60D);
            Set<VehicleRoute> existingRoutes = departuresPerDay.get(firstAvailableDay);
            if (existingRoutes == null) {
                existingRoutes = new HashSet<>();
            }
            existingRoutes.add(r);
            departuresPerDay.put(firstAvailableDay, existingRoutes);
        }
    }

    @Override
    public void ruinEnds(Collection<VehicleRoute> routes, Collection<Job> unassignedJobs) {

    }

    @Override
    public void removed(Job job, VehicleRoute route) {

    }