Vehicle arrives early at Shipment with DeliveryTimeWindow

[quiqua]

Issue

When creating a shipment with a delivery timewindow set to a specific time, the assigned vehicle will arrive early at the corresponding pickup and delivery activities:

/*
 * Licensed to GraphHopper GmbH under one or more contributor
 * license agreements. See the NOTICE file distributed with this work for
 * additional information regarding copyright ownership.
 *
 * GraphHopper GmbH licenses this file to you under the Apache License,
 * Version 2.0 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.graphhopper.jsprit.examples;

import com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm;
import com.graphhopper.jsprit.core.algorithm.box.Jsprit;
import com.graphhopper.jsprit.core.algorithm.state.StateManager;
import com.graphhopper.jsprit.core.problem.Location;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem.FleetSize;
import com.graphhopper.jsprit.core.problem.constraint.ConstraintManager;
import com.graphhopper.jsprit.core.problem.constraint.HardActivityConstraint;
import com.graphhopper.jsprit.core.problem.constraint.SoftActivityConstraint;
import com.graphhopper.jsprit.core.problem.cost.VehicleRoutingTransportCosts;
import com.graphhopper.jsprit.core.problem.job.Shipment;
import com.graphhopper.jsprit.core.problem.misc.JobInsertionContext;
import com.graphhopper.jsprit.core.problem.solution.SolutionCostCalculator;
import com.graphhopper.jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import com.graphhopper.jsprit.core.problem.solution.route.VehicleRoute;
import com.graphhopper.jsprit.core.problem.solution.route.activity.TimeWindow;
import com.graphhopper.jsprit.core.problem.solution.route.activity.TourActivity;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleImpl;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleType;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleTypeImpl;
import com.graphhopper.jsprit.core.reporting.SolutionPrinter;
import com.graphhopper.jsprit.core.util.Coordinate;
import com.graphhopper.jsprit.core.util.Solutions;
import com.graphhopper.jsprit.core.util.VehicleRoutingTransportCostsMatrix;
import com.graphhopper.jsprit.util.Examples;

import java.util.Collection;

public class ShipmentWithOpenPickupAndSetDeliveryTimeWindowExample {

    public static void main(String[] args) {
        /*
         * some preparation - create output folder
         */
        Examples.createOutputFolder();

        VehicleType type = VehicleTypeImpl.Builder.newInstance("type")
            .addCapacityDimension(0, 2)
            .setCostPerTransportTime(1)
            .build();
        VehicleImpl vehicle = VehicleImpl.Builder.newInstance("vehicle")
            .setStartLocation(Location.Builder.newInstance().setId("0").setCoordinate(Coordinate.newInstance(0,0)).build())
            .setEarliestStart(0)
            .setReturnToDepot(false)
            .setType(type)
            .build();
        Shipment s1 = Shipment.Builder.newInstance("shipment")
            .addSizeDimension(0, 1)
            .setPickupLocation(Location.Builder.newInstance().setId("1").setCoordinate(Coordinate.newInstance(10,10)).build())
            .setDeliveryLocation(Location.Builder.newInstance().setId("2").setCoordinate(Coordinate.newInstance(20,20)).build())
            .setDeliveryTimeWindow(TimeWindow.newInstance(40, 45))
            .setMaxTimeInVehicle(15)
            .build();

        //define a matrix-builder building a symmetric matrix
        VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
        costMatrixBuilder.addTransportTime("0", "0", 0.0);
        costMatrixBuilder.addTransportTime("0", "1", 10.0);
        costMatrixBuilder.addTransportTime("0", "2", 20.0);
        costMatrixBuilder.addTransportTime("1", "1", 0.0);
        costMatrixBuilder.addTransportTime("1", "2", 10.0);
        costMatrixBuilder.addTransportTime("2", "2", 0.0);

        VehicleRoutingTransportCosts costMatrix = costMatrixBuilder.build();

        VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
            .setFleetSize(FleetSize.INFINITE)
            .setRoutingCost(costMatrix)
            .addVehicle(vehicle).addJob(s1).build();

        SoftActivityConstraint lateArrivalsSoftConstraint = new SoftActivityConstraint() {
            @Override
            public double getCosts(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
                double transportTime = prevActDepTime + costMatrix.getTransportTime(prevAct.getLocation(), newAct.getLocation(), 0, null, null);
                double difference = newAct.getTheoreticalEarliestOperationStartTime() - transportTime;
                return Math.max(0, difference);
            }
        };

        HardActivityConstraint lateArrivalsHardConstraint = new HardActivityConstraint() {
            @Override
            public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
                double transportTime = prevActDepTime + costMatrix.getTransportTime(prevAct.getLocation(), newAct.getLocation(), 0, null, null);
                double difference = newAct.getTheoreticalEarliestOperationStartTime() - transportTime;
                if (difference <= 0) {
                    return ConstraintsStatus.FULFILLED;
                }
                return ConstraintsStatus.NOT_FULFILLED;
            }
        };

        SolutionCostCalculator objectiveFunction = new SolutionCostCalculator() {
            @Override
            public double getCosts(VehicleRoutingProblemSolution solution) {
                double costs = 0;
                for (VehicleRoute route : solution.getRoutes()) {
                    for (TourActivity activity : route.getActivities()) {
                        double difference = activity.getTheoreticalEarliestOperationStartTime() - activity.getArrTime();
                        costs += Math.max(0, difference);
                    }
                }
                return costs;
            }
        };

        StateManager stateManager = new StateManager(vrp);

        ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
        constraintManager.addTimeWindowConstraint();
//        constraintManager.addConstraint(lateArrivalsSoftConstraint);
//        constraintManager.addConstraint(lateArrivalsHardConstraint, ConstraintManager.Priority.CRITICAL);

        VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(vrp)
            .setStateAndConstraintManager(stateManager,constraintManager)
            .setObjectiveFunction(objectiveFunction)
            .buildAlgorithm();

        Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();

        SolutionPrinter.print(vrp, Solutions.bestOf(solutions), SolutionPrinter.Print.VERBOSE);
    }

}

+--------------------------+
| problem                  |
+---------------+----------+
| indicator     | value    |
+---------------+----------+
| noJobs        | 1        | 
| noServices    | 0        | 
| noShipments   | 1        | 
| noBreaks      | 0        | 
| fleetsize     | INFINITE | 
+--------------------------+
+----------------------------------------------------------+
| solution                                                 |
+---------------+------------------------------------------+
| indicator     | value                                    |
+---------------+------------------------------------------+
| costs         | 20.0                                     | 
| noVehicles    | 1                                        | 
| unassgndJobs  | 0                                        | 
+----------------------------------------------------------+
+--------------------------------------------------------------------------------------------------------------------------------+
| detailed solution                                                                                                              |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| route   | vehicle              | activity              | job             | arrTime         | endTime         | costs           |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| 1       | vehicle              | start                 | -               | undef           | 0               | 0               |
| 1       | vehicle              | pickupShipment        | shipment        | 10              | 10              | 10              |
| 1       | vehicle              | deliverShipment       | shipment        | 20              | 40              | 20              |
| 1       | vehicle              | end                   | -               | 40              | undef           | 20              |
+--------------------------------------------------------------------------------------------------------------------------------+

Expected behaviour:

The vehicle arrives at 40 for the delivery and figures out the latest time to achieve this.

---

If I set a corresponding pickup timewindow, I can force the desired behaviour, yet I'd like to not restrict this too much and let Jsprit figure out the optimal time.

My guess is that is a current limitation Jsprit calculating a solution from start to end and not vice versa as well, e.g. here:

jsprit/jsprit-core/src/main/java/com/graphhopper/jsprit/core/algorithm/recreate/ShipmentInsertionCalculator.java

Line 143 in 74c3c68

for(TimeWindow pickupTimeWindow : shipment.getPickupTimeWindows()) {

[rellmar]

Any sulotion to this problem?