Vehicle arrives early at Shipment with DeliveryTimeWindow
quiqua opened this issue · 1 comments
quiqua commented
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:
rellmar commented
Any sulotion to this problem?