jsprit Documentation

In jsprit 2.0, indices are no longer stored on Job and Vehicle objects. Instead, each VehicleRoutingProblem (VRP) manages its own indices internally.

Key changes:

• Object Reuse: You can safely reuse the same Job or Vehicle objects across multiple VehicleRoutingProblem instances without index conflicts.
• Automatic Assignment: Indices are assigned automatically (0 to n-1) when build() is called.
• Retrieving Indices: Use the VRP instance to retrieve the index for a specific object.

Note: Job.getIndex() and Vehicle.getIndex() are deprecated. They still work but return the index from the last VRP they were added to. Use the VRP methods instead.

// Define jobs once
Service job1 = Service.Builder.newInstance("job1").setLocation(loc1).build();
Service job2 = Service.Builder.newInstance("job2").setLocation(loc2).build();

// Create different problem variations reusing the same jobs
VehicleRoutingProblem vrp1 = VehicleRoutingProblem.Builder.newInstance()
    .addJob(job1).addJob(job2)
    .addVehicle(smallFleet)
    .build();

VehicleRoutingProblem vrp2 = VehicleRoutingProblem.Builder.newInstance()
    .addJob(job1).addJob(job2)
    .addVehicle(largeFleet)  // Different fleet
    .build();

// Solve both independently - no index conflicts

// Retrieving indices:
int jobIndex = vrp1.getJobIndex(job1);
int vehicleIndex = vrp1.getVehicleIndex(vehicle);

jsprit uses a meta-heuristic based on the ruin-and-recreate principle (a Large Neighborhood Search). This approach is designed for complex Vehicle Routing Problems (VRP) with many constraints and discontinuous solution spaces.

The algorithm follows an iterative process:

1. Ruin Step: The current solution is partially disintegrated. This results in a set of jobs that are no longer assigned to any vehicle and a partial solution containing the remaining jobs.
2. Recreation Step: The jobs removed during the ruin step are re-integrated into the partial solution to yield a new candidate solution.
3. Acceptance: If the new solution meets certain quality criteria (using elements of simulated annealing and threshold-accepting), it is accepted as the new best solution.
4. Iteration: This process repeats until a termination criterion is met, such as a maximum computation time or a specific number of iterations.

This structure allows for easy variation of search strategies (small vs. large moves) and simplifies constraint checking by clearly separating the removal and re-insertion phases.

The Traveling Salesman Problem (TSP) can be modeled in jsprit by defining a Vehicle Routing Problem (VRP) with specific constraints. You can achieve this using one of two approaches:

1. High Capacity Vehicle: Define a VehicleType with a capacity dimension set to a sufficiently high value (e.g., Integer.MAX_VALUE) to accommodate all services.
2. Zero Demand Services: Define services that have a capacity demand of 0 (which is the default behavior in the Service.Builder).

To implement the high-capacity approach, you must first build a VehicleTypeImpl with the required capacity, then associate it with a Vehicle via a VehicleBuilder.

/*
 * get a vehicle type-builder and build a type with the typeId "vehicleType" and a sufficently high capacity
 */
VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("vehicleType").addCapacityDimension(0,Integer.MAX_VALUE);
VehicleType vehicleType = vehicleTypeBuilder.build();

/*
 * get a vehicle-builder and build a vehicle located at (10,10) with type "vehicleType"
 */
VehicleBuilder vehicleBuilder = VehicleImpl.Builder.newInstance("vehicle");
vehicleBuilder.setStartLocation(Location.newInstance(10, 10));
vehicleBuilder.setType(vehicleType); 
Vehicle vehicle = vehicleBuilder.build();

/*
 * build services with id 1...4 at the required locations, each with a capacity-demand of 0 (which is the default).
 * Note, that the builder allows chaining which makes building quite handy
 */
Service service1 = Service.Builder.newInstance("1").setLocation(Location.newInstance(5, 7)).build();
Service service2 = Service.Builder.newInstance("2").setLocation(Location.newInstance(5, 13)).build();
Service service3 = Service.Builder.newInstance("3").setLocation(Location.newInstance(15, 7)).build();
Service service4 = Service.Builder.newInstance("4").setLocation(Location.newInstance(15, 13)).build();

To load a classical Vehicle Routing Problem (VRP) instance like the Solomon C101, use the SolomonReader. This reader populates a VehicleRoutingProblem.Builder instance.

Note: The SolomonReader assigns a fixed cost of 100 to each vehicle used, even if the original problem instance does not specify fixed costs. Consequently, total costs will be calculated as (number of vehicles * 100) + variable costs.

Ensure your instance file (e.g., C101_solomon.txt) is located in a directory named input relative to your project root.

/*
 * define problem-builder first
 */
VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();

/*
 * Read solomon instance with SolomonReader
 */
new SolomonReader(vrpBuilder).read("input/C101_solomon.txt");

/*
 * Build the problem. By default, transport costs are calculated as Euclidean distances.
 */
VehicleRoutingProblem vrp = vrpBuilder.build();