Initial solution or initialRoute. Both Not Useful

Hi,
I was trying to understand the use of addinitialRoute and addinitialSolution. I hoped that giving the additional information, solution of the problem will be obtained in comparatively less time.
Here is my problem:
I created a Vehicle Routing Problem with two services and one vehicle and I got right solution.

Now I created new Vehicle Routing Problem which has all jobs as earlier problem and one additional job.
I used addInitialVehicleRoutes. Produced answer was not correct.
I used addInitialSolution in algorithm, which was even worse.
I used both, answer was same as using addInitialSolution.
I removed both. I got right answer.
Here goes the code: uncomment to add the feature of using addInitialVehicleRoute or addInitialSolution.

  Location O = Location.Builder.newInstance().setId("O").build();
  Location A = Location.Builder.newInstance().setId("A").build();
  Location B = Location.Builder.newInstance().setId("B").build();
  Location C = Location.Builder.newInstance().setId("C").build();
  VehicleRoutingTransportCostsMatrix.Builder builder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
  builder.addTransportDistance("O", "A", 1);
  builder.addTransportDistance("O", "C", 0.5);
  builder.addTransportDistance("O", "B", 1.25);
  builder.addTransportDistance("A", "B", 0.5);
  builder.addTransportDistance("A", "C", 100);
  builder.addTransportDistance("B", "C", 1);
  VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();

  VehicleTypeImpl impl = VehicleTypeImpl.Builder.newInstance("VehicleType").setCostPerDistance(1).addCapacityDimension(0, 1000).build();
  VehicleImpl vehicle = VehicleImpl.Builder.newInstance("V").setType(impl).setReturnToDepot(false).setStartLocation(O).build();

  Service a = Service.Builder.newInstance("a").addSizeDimension(0, 1).setLocation(A).build();
  Service b = Service.Builder.newInstance("b").addSizeDimension(0, 1).setLocation(B).build();
  vrpBuilder.setRoutingCost(builder.build());
  vrpBuilder.addVehicle(vehicle);
  vrpBuilder.addJob(a);
  vrpBuilder.addJob(b);
  vrpBuilder.setFleetSize(FleetSize.FINITE);

  VehicleRoutingProblem problem = vrpBuilder.build();
  Collection<VehicleRoutingProblemSolution> allSolutions = Jsprit.createAlgorithm(problem).searchSolutions();
  VehicleRoutingProblemSolution solution = Solutions.bestOf(allSolutions);
  SolutionPrinter.print(problem, solution, Print.VERBOSE);
  Service c = Service.Builder.newInstance("c").addSizeDimension(0, 1).setLocation(C).build();

  VehicleRoutingProblem.Builder tspBuilder = VehicleRoutingProblem.Builder.newInstance();
  tspBuilder.addAllVehicles(problem.getVehicles());
  tspBuilder.addAllJobs(vrpBuilder.getAddedJobs());
  tspBuilder.addJob(c);
  tspBuilder.setFleetSize(FleetSize.FINITE);
  tspBuilder.setRoutingCost(problem.getTransportCosts());
  // tspBuilder.addInitialVehicleRoutes(solution.getRoutes());

  VehicleRoutingProblem tsp = tspBuilder.build();

  VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(tsp).buildAlgorithm();
  algorithm.setMaxIterations(20000);
  // algorithm.addInitialSolution(solution);

  VehicleRoutingProblemSolution tspSolution = Solutions.bestOf(algorithm.searchSolutions());SolutionPrinter.print(tsp, tspSolution, Print.VERBOSE);

Hi @shivkrishnajaiswal,

Regarding initial route, you need to note that the jobs in the initial routes will not be ruined at all in the optimization process. Therefore, not only the job-vehicle assignment (in a multi-vehicle context) will not change, the sequence of them within the route will also not change. The new job(s) can still be inserted before/between/after them, though. Therefore, when you use .addInitialVehicleRoutes(), you will get a solution as a-b-c, because in your initial route (i.e., solution.getRoutes()), you have the sequence a-b.

Regarding initial solution, you need to add the new job(s) to it as a collection of unassigned job(s), and also need to add an associated cost, like the following:

   VehicleRoutingProblemSolution initialSolution =
            new VehicleRoutingProblemSolution(
                    solution.getRoutes(),
                    Collections.singleton(c),
                    solution.getCost() * (1 + 1 * 2)
            );
    algorithm.addInitialSolution(initialSolution);

Otherwise, if you call .addInitialSolution(solution) directly, you will probably not be able to improve from there.

Hopefully this helps.

@stefan, when verifying the initial solution, maybe the number of jobs in the initial solution should also count the jobs in the unassigned jobs list? Otherwise in the above case, it will always throw the warning.

Best regards,
He

Thanks jie31best. :slight_smile:

I have noticed a problem that if I use Shipment instead of service then I am getting:
“number of jobs in initial solution (5) is not equal nuJobs in vehicle routing problem (6)
this might yield unintended effects, e.g. initial solution cannot be improved anymore.”

Let me explain the actual problem that I am trying to solve.

We are solving a Vehicle Routing Problem which has it inputs as various Shipments and the VehicleRoutingTransportCostsMatrix.

I got the solution.

If a new Shipment comes then instead of solving complete new Vehicle Routing Problem containing all older Shipments and the new Shipment ( of course, new CostsMatrix is given), I am solving route wise Vehicle Route Problem which is, I try to check if new Shipment can be included in one of the older Vehicle Routes (which can be said to be “Route Wise Vehicle Routing Problem”), if yes then what is the new Vehicle Route.

Though this will not be optimal solution, it will be good solution which is time efficient.

for (VehicleRoute route : oldSolution.getRoutes()) {
…

VehicleRoutingProblemSolution initialSolution =new VehicleRoutingProblemSolution(Collections.singleton(route), unassignedJobs, Double.MAX_VALUE);

where unassignedJobs are the new Shipments that have come.

This is exactly what I put in the last paragraph of my earlier reply.

number of jobs in initial solution (5) does not count the new Shipment in unassignedJobs, and thus is not equal to nuJobs in vehicle routing problem (6).

Does this prevent you from getting a good solution?

Yes.
Later on I created a VehicleRoute.Builder which contains all the initial job in the older route and the new Shipment. And then feed this route in the :
new VehicleRoutingProblemSolution(Collections.singleton(routeBuilder.build()), unassignedJobs,Double.Max);

but the problem is not solved.

What I mean is that you just ignore the warning for now if your initial solution contains unassigned jobs, because the verify() method never counts unassigned jobs in the number of jobs in initial solution and you will always see the warning.

I am getting error. The error is produced when I use .searchSolutions() method through algorithm object.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 24
    at jsprit.core.algorithm.state.StateManager.putInternalTypedActivityState(StateManager.java:424)
    at jsprit.core.algorithm.state.UpdateVehicleDependentPracticalTimeWindows.visit(UpdateVehicleDependentPracticalTimeWindows.java:104)
    at jsprit.core.algorithm.state.UpdateVehicleDependentPracticalTimeWindows.visit(UpdateVehicleDependentPracticalTimeWindows.java:38)
    at jsprit.core.algorithm.state.StateManager.informInsertionStarts(StateManager.java:571)
    at jsprit.core.algorithm.recreate.listener.InsertionListeners.informInsertionStarts(InsertionListeners.java:63)
    at jsprit.core.algorithm.recreate.AbstractInsertionStrategy.insertJobs(AbstractInsertionStrategy.java:88)
    at jsprit.core.algorithm.module.RuinAndRecreateModule.runAndGetSolution(RuinAndRecreateModule.java:54)
    at jsprit.core.algorithm.SearchStrategy.run(SearchStrategy.java:146)
    at jsprit.core.algorithm.VehicleRoutingAlgorithm.searchSolutions(VehicleRoutingAlgorithm.java:205)

Hi @shivkrishnajaiswal,

Sorry but it is difficult for me to judge what goes wrong here (I am not Stefan after all, LOL). Could you send me the code that you construct your problem and algorithm so that I might be able to help? Thanks.

Best regards,
He

  // ----------------------Main Code Starts-------------------------------------------------------
  Demo.GetCompleteSet completeSet = Demo.getProblemSet();
  /*
   * Demo.getProblemSet() generates the object of GetCompleteSet which consists of the following Parameters:
   * 1) VehicleRoutingTransportCostsMatrix costsMatrix;
   * 2) VehicleRoutingProblem vrp;
   * 3) VehicleRoutingAlgorithm vrpAlgorithm;
   * 4) VehicleRoutingProblemSolution vrpSolution;
   */

  final VehicleRoutingProblemSolution oldSolution = completeSet.vrpSolution;

  Set<Shipment> newShipment = null;

  int oldRouteSize = 0;
  int newRouteSize = 0;
  // oldRouteSize is number of the Job in oldRoute.
  double a = 0 , b = 0;
  // a is the total distance of oldRoute and b is the total distance of newRoute

  for (VehicleRoute route : oldSolution.getRoutes()) {

     Solution checkSolution = new Solution();
     /*
      * Solution class consists of :
      * 1) VehicleRoute newRoute , oldRoute;
      * 2) double cost;// = b;
      * 3) boolean shouldAdd = true;
      * 4) boolean hasOldJobRemoved = false;
      * 5) double addDistance = 0;// = b-a;
      */
     checkSolution.oldRoute = route;
     a = getCost(route);//  getCost returns total distance of route.

     oldRouteSize = route.getTourActivities().getJobs().size();

     VehicleRoutingProblem.Builder tspBuilder = VehicleRoutingProblem.Builder.newInstance();

     newShipment = AddingToVRPBuilder.addShipment("files/newServices", tspBuilder);

     tspBuilder.addAllJobs(route.getTourActivities().getJobs());

     Shipment shipment = newShipment.iterator().next();// For test case I am taking only one job

     tspBuilder.addVehicle((AbstractVehicle) route.getVehicle());
     tspBuilder.setFleetSize(FleetSize.FINITE);
     tspBuilder.setRoutingCost(costMatrix);

     VehicleRoutingProblem tsp = tspBuilder.build();

     VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(tsp);

     VehicleRoutingProblemSolution initialSolution =
           new VehicleRoutingProblemSolution(Collections.singleton(route), Collections.singleton(shipment), Double.MAX_VALUE);

     algorithm.addInitialSolution(initialSolution);
     VehicleRoutingProblemSolution problemSolution = Solutions.bestOf(algorithm.searchSolutions());// This the place problem occurred
     // -------------------------------Main code ends----------------------------------------------------------------------------

Will tspBuilder.addJob(shipment); solve the problem?

Actually this function: AddingToVRPBuilder.addShipment(“files/newServices”, tspBuilder);
adds shipments to tspBuilder.

does that function add all the shipments to tspBuilder or only the one you add to the initial solution?

New shipments are not added to the “initial solution”. Initial solution is only the old route.

does that function add 1) all the shipments or 2) only the following one, which you add to the initial solution, to tspBuilder?

Only the new Shipments are added by method ddingToVRPBuilder.addShipment(“files/newServices”, tspBuilder);
Old jobs are added by the feeding VehicleRoute.getActivities.getJobs() to tspBuilder.

Assuming newShipment contains 100 shipments, do you add all of them to tspBuilder?

Yes, Then I will be using collection of new Shipments and then add this into tspBuilder and into unassignedJobs in initialSolution.

Currently, I am adding only one Shipment.

I am solving route-wise VehicleRoutingProblem so tspBuilder is first fed with route.getTourActivities().getJobs() and then it is added with new Shipments.
Then in initialSolution, the route and newShipments and cost are added.

Have you tried adding only the first one shipment to tspBuilder so that the jobs in tsp will be the same as those in the initial solution (or the other way around, i.e., adding all 100 shipments to the initial solution as unassigned jobs)?