javanetwork-programmingoptimizationroutesjsprit

Not able to get the correct optimised route by providing the time windows to services using Jsprit


I am trying to get the optimized route by using Jsprit.I have three jobs each has its own time window.Now it's like this

            VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder
                .newInstance("smallVehicle")
                .addCapacityDimension(0, 4);

        VehicleType vehicleType = vehicleTypeBuilder
                .build();

        /**
         * Create vehicle.
         */
        Builder vehicleBuilder = VehicleImpl.Builder
                .newInstance("audi");
        vehicleBuilder.setStartLocation(Location.Builder
                .newInstance()
                .setCoordinate(new Coordinate(4, 4))
                .setIndex(0).build());
        vehicleBuilder.setType(vehicleType);
        // Start time and end time of the resource in seconds from 10AM to 8PM.
        vehicleBuilder.setEarliestStart(36000);
        vehicleBuilder.setLatestArrival(72000);
        VehicleImpl vehicle = vehicleBuilder.build();

        /**
         * Create the services those should be accomplished by vehicle.
         */

        Service service1 = Service.Builder
                .newInstance("1(11am-1pm)1hr")
                .addSizeDimension(0, 1)
                .setLocation(
                        Location.Builder
                                .newInstance()
                                .setCoordinate(
                                        new Coordinate(4, 5))
                                .setIndex(1).build())
                // Job should be started at 10AM and ends at 8PM.
                .addTimeWindow(39600,46800)
                // Time required to do job is 4 hours
                .setServiceTime(3600).build();

        Service service2 = Service.Builder
                .newInstance("2(2pm-5pm)1hr")
                .addSizeDimension(0, 1)
                .setLocation(
                        Location.Builder
                                .newInstance()
                                .setCoordinate(
                                        new Coordinate(5, 4))
                                .setIndex(1).build())
                // Time required to complete job is 3 hours.
                .setServiceTime(3600)
                // Job should be started at 2PM and ends at 8PM.
                .addTimeWindow(50400, 61200).build();

        Service service3 = Service.Builder
                .newInstance("3(6pm-8pm)1hr")
                .addSizeDimension(0, 1)
                .setLocation(
                        Location.Builder
                                .newInstance()
                                .setCoordinate(
                                        new Coordinate(5, 8))
                                .setIndex(3).build())
                // Service takes 1 hour to complete.
                .setServiceTime(3600)
                // From 12-1
                .addTimeWindow(64800, 72000).build();

        VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder
                .newInstance();
        vrpBuilder.addVehicle(vehicle);
        vrpBuilder.addJob(service1).addJob(service2)
                .addJob(service3);
        vrpBuilder
                .setFleetSize(VehicleRoutingProblem.FleetSize.INFINITE);

        VehicleRoutingProblem vrp = vrpBuilder.build();

        /**
         * Create the algorithm based on the VRP you have created.
         */
        VehicleRoutingAlgorithm algorithm = Jsprit
                .createAlgorithm(vrp);
Collection<VehicleRoutingProblemSolution> solutions = algorithm
                .searchSolutions();

        /**
         * Get the best route among given sollutions.
         */
        VehicleRoutingProblemSolution bestOne = Solutions
                .bestOf(solutions);

Now vehicle has to finish all three jobs within 10 AM - 8PM. I have created the problem for this and got the results also but I am not understanding on what basis it's giving two routes even though the capacity dimension of the vehicle is more than the capacity required to complete the jobs.

The result is like this enter image description here


Solution

  • Because using two vehicles returns smaller total cost (10.28538328578604) than using one vehicle (10.537319187990756) in your case.

    If you would like to force it to use only one vehicle, you can either set fleet size to FINITE or set a fixed cost to the vehicle type.