GraphHopper.com | Forum | GitHub | Maps | Blog

Route Time Exceeds Upper Limits


#1

I am trying to create a pickup/delivery route for 14 shipments using one driver. I have specified time limits using setEarliestStart (vehicle), setLatestArrival (vehicle), setPickupTimeWindow (shipment), and setDeliveryTimeWindow (shipment) to test my program under strict time constraints. My expectation is that the vehicle routing solution would contain as many activities as possible without exceeding any of the specified time limits – i.e. at the very least, the route would not start before 51000 or end after 61200 (see details below). I am noticing, however, that jsprit is returning “best solutions” with routes that end beyond these time limits. Please see below for more details:

Vehicle Builder:

VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder
.newInstance(“Vehicle1”)
.addCapacityDimension(0,2)
.addCapacityDimension(1,2)
.addCapacityDimension(2,2);
VehicleType vehicleType = vehicleTypeBuilder.build();

VehicleImpl.Builder vehicleBuilder = VehicleImpl.Builder.newInstance(“Vehicle1”);
vehicleBuilder.setStartLocation(depot_location);
vehicleBuilder.setEarliestStart(51000);
vehicleBuilder.setLatestArrival(61200);
vehicleBuilder.setType();

VehicleImpl vehicle_ = vehicleBuilder.build();
vrpBuilder.addVehicle(vehicle_);

Shipment Builder (for each of the 14 shipments):

Shipment shipment = Shipment.Builder.newInstance(shipmentId)
.setName(shipmentName)
.addSizeDimension(0,1)
.addSizeDimension(1,0)
.addSizeDimension(2,0)
.setPickupLocation(depot_location)
.setDeliveryLocation(destination)
.setPickupTimeWindow(new TimeWindow(39600,61200))
.setDeliveryTimeWindow(new TimeWindow(39600,61200))
.setDeliveryServiceTime(900.)
.setPickupServiceTime(300.)
.setPriority(3) .build();
vrpBuilder.addJob(shipment);

Outputs:

| problem |
±--------------±---------+
| indicator | value |
±--------------±---------+
| noJobs | 14 |
| noServices | 0 |
| noShipments | 14 |
| noBreaks | 0 |
| fleetsize | FINITE |
±-------------------------+
±---------------------------------------------------------+
| solution |
±--------------±-----------------------------------------+
| indicator | value |
±--------------±-----------------------------------------+
| costs | 2.79577332E8 |
| noVehicles | 1 |
| unassgndJobs | 9 |
±---------------------------------------------------------+
±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | Vehicle1 | start | - | undef | 51000 | 0 |
| 1 | Vehicle1 | pickupShipment | shipment3 | 51000 | 51300 | 300 |
| 1 | Vehicle1 | deliverShipment | shipment3 | 52724 | 53624 | 2624 |
| 1 | Vehicle1 | pickupShipment | shipment7 | 55133 | 55433 | 4433 |
| 1 | Vehicle1 | pickupShipment | shipment11 | 55433 | 55733 | 4733 |
| 1 | Vehicle1 | deliverShipment | shipment11 | 56127 | 57027 | 6027 |
| 1 | Vehicle1 | pickupShipment | shipment10 | 57413 | 57713 | 6713 |
| 1 | Vehicle1 | deliverShipment | shipment7 | 58190 | 59090 | 8090 |
| 1 | Vehicle1 | pickupShipment | shipment9 | 59499 | 59799 | 8799 |
| 1 | Vehicle1 | deliverShipment | shipment9 | 61143 | 62043 | 11043 |
| 1 | Vehicle1 | deliverShipment | shipment10 | 63069 | 63969 | 12969 |
| 1 | Vehicle1 | end | - | 65204 | undef | 14204 |
±-------------------------------------------------------------------------------------------------------------------------------+
±---------------+
| unassignedJobs |
±---------------+
| shipment2 |
| shipment1 |
| shipment5 |
| shipment4 |
| shipment14 |
| shipment12 |
| shipment8 |
| shipment6 |
| shipment13 |
±---------------+

Interestingly, this issue does not occur if I instead use: vehicleBuilder.setLatestArrival(55000) – i.e. no shipments occur after 55000 (solution below). Therefore, this appears to be a non-deterministic error!

±-------------------------+
| problem |
±--------------±---------+
| indicator | value |
±--------------±---------+
| noJobs | 14 |
| noServices | 0 |
| noShipments | 14 |
| noBreaks | 0 |
| fleetsize | FINITE |
±-------------------------+
±---------------------------------------------------------+
| solution |
±--------------±-----------------------------------------+
| indicator | value |
±--------------±-----------------------------------------+
| costs | 2.034887589E9 |
| noVehicles | 1 |
| unassgndJobs | 12 |
±---------------------------------------------------------+
±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | Vehicle1 | start | - | undef | 51000 | 0 |
| 1 | Vehicle1 | pickupShipment | shipment7 | 51000 | 51300 | 300 |
| 1 | Vehicle1 | pickupShipment | shipment11 | 51300 | 51600 | 600 |
| 1 | Vehicle1 | deliverShipment | shipment11 | 51994 | 52894 | 1894 |
| 1 | Vehicle1 | deliverShipment | shipment7 | 53520 | 54420 | 3420 |
| 1 | Vehicle1 | end | - | 54829 | undef | 3829 |
±-------------------------------------------------------------------------------------------------------------------------------+
±---------------+
| unassignedJobs |
±---------------+
| shipment12 |
| shipment8 |
| shipment6 |
| shipment5 |
| shipment4 |
| shipment3 |
| shipment2 |
| shipment1 |
| shipment13 |
| shipment14 |
| shipment10 |
| shipment9 |
±---------------+