TSP optimization returns orders in the same way has they arrive

jsprit
1

Hi All,

So I have a weird issue where the results come back exactly the same as the original data set.

I have a function that creates services & shipments and build them as:

// Service
Service.Builder.newInstance(instanceName)
            .setName(details.get("invoice").toString())
            .setLocation(setLocation(instanceName, coords[0], coords[1]))
            .setServiceTime((Double) details.get("serviceTime")/60)
            .addRequiredSkill("TSP").setTimeWindow(TimeWindowSet).build()

// Shipment
Shipment.Builder.newInstance(instanceName)
            .setName(details.get("invoice").toString())
            .setPickupLocation(setLocation(instanceName, coords[0], coords[1]))
            .setDeliveryLocation(setLocation(instanceName2, coords2[0], coords2[1]))
            .setDeliveryTimeWindow(TimeWindowSet).addRequiredSkill("TSP")
            .setDeliveryServiceTime((Double) details.get("serviceTime")/60)
            .build();

I have tried using a large capacity for the vehicles when they are created and giving each job a weight of 0 - as suggested in the github docs for TSP.

When creating the problem, also in a function:

VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
            ArrayList<Service> SERVICES = new ArrayList<>();
            ArrayList<Shipment> SHIPMENTS = new ArrayList<>();
            for(Service service: List.of(services)) {
                SERVICES.add(service);
            }
            for(Shipment shipment: List.of(shipments)) {
                SHIPMENTS.add(shipment);
            }
            Collections.shuffle(SERVICES);
            Collections.shuffle(SHIPMENTS);
            if(trucks.length > 0) vrpBuilder.addAllVehicles(List.of(trucks));
            if(services.length > 0) vrpBuilder.addAllJobs(SERVICES);
            if(shipments.length > 0) vrpBuilder.addAllJobs(SHIPMENTS);
            vrpBuilder.setFleetSize(VehicleRoutingProblem.FleetSize.FINITE);
            vrpBuilder.setRoutingCost(createCostMatrix());
            VehicleRoutingProblem problem = vrpBuilder.build();
            return problem;

Note the Collections.shuffle() call was just to test the Algorithm to see if it was actually arranging them in a determined order after sending it to the algorithm

VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);
            Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
            return Solutions.bestOf(solutions);

Does anybody have any suggestions as to what could be the issue? Thanks for your help!

2

Can’t trial anything at moment but have you tried setting up your cost matrix to be asymmetric?

3

Hi @Gregws, Yeah I just tried that now. Still the same output. I have the console outputting the solution.

4

Hard to assess without seeing your matrix

5

The Matrix is built with a loop within a loop that has all the stops and truck location :

 // used true or false here
VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
    for (HashMap<String, double[]> LocID : AllLocationIdsAndGeos) {
       String fromID = LocID.keySet().toArray()[0].toString();
       double[] from = LocID.get(fromID);
       for (HashMap<String, double[]> LocID2 : AllLocationIdsAndGeos) {
          String toID = LocID2.keySet().toArray()[0].toString();
          double[] to = LocID2.get(toID);
          if(fromID != toID) {
             double distance = getDistance(from, to);
             costMatrixBuilder.addTransportDistance(fromID, toID, distance);
             costMatrixBuilder.addTransportTime(fromID, toID, distance/DEFAULT_SPEED);
         }
     }
}

so it would be something like

DE-976-300757 [x=51.082788][y=-114.142051]
DE-304548403 [x=51.161632][y=-114.115765]
DE-103558365 - return back to customer  [x=51.172573][y=-114.163388]
DE-304598796 [x=51.093477][y=-114.076844]
DE-976-048027 service call [x=51.130415][y=-114.140095]
DE-890666705 [x=51.141018][y=-114.225096]
DE-303468764 [x=51.129427][y=-114.074576]
DO-RA6545164RET [x=51.001742][y=-113.967472]
DE-303434042 [x=51.134045][y=-114.193636]
PU-RA6545164RET [x=51.15538][y=-114.084257]
DE-303659215 [x=51.19206][y=-114.496045]
DE-303623507 [x=51.160845][y=-114.155716]
DE-E200993 Basic Preassigned [x=51.082788][y=-114.109111]
DE-303188020 [x=51.145474][y=-114.123343]
WH-0 [x=51.001567][y=-113.967748]
DE-303516697 [x=51.161121][y=-114.149658]
DE-303105451 [x=51.114399][y=-114.144065]
DE-900-926565 [x=51.102789][y=-114.147732]
DE-205-730218 [x=51.075932][y=-114.072282]
DE-900-921080 [x=51.109018][y=-114.190143]

WH-0 is the vehicle location and the others are either deliveries, pickup and drop-offs

6

@Gregws I figured out why the results were coming back as the same. The time windows were so short that jsprit either returned as the same because switching stops wouldn’t make the route feasible. I removed the timewindows and the routes are now properly generated based on the distance. The alternative I guess, would be extending the time windows to enable stops to be re-ordered while abiding by time windows.

Thanks for your help!

Edit: it would also drop stops that couldn’t be completed within the time window if they were too far away.