jsprit is a java based, open source toolkit for solving rich traveling salesman (TSP) and vehicle routing problems (VRP). It is lightweight, flexible and easy-to-use.

Learn More

Features

jsprit can solve problems with pickups and deliveries, back hauls, heterogeneous fleets, finite and infinite fleets, multiple depots, time windows, open routes, different start and end locations, multiple capacity dimensions, initial loads, skills ...

Tested

jsprit is fit for change due to comprehensive unit and integration tests.

Documented

jsprit is documented and additional code-examples illustrate its use.

Constraints

jsprit allows you to define additional stateful and stateless constraints to account for the richness of your problem.

Benchmarked

jsprit is benchmarked against classical VRP instances (e.g. Solomon instances).

Open Source

jsprit is released under LGPL (v3).


Quickstart - Problem, Algorithm and Solution

Problem

Specify your jobs - jsprit allows you to define services (one stop) and shipments (two stops) with multiple capacity dimensions. Additionally, you can set time windows and required skills.

// specify service - which involves one stop 
Service service =  Service.Builder.newInstance("serviceId")
          .setName("myService")
          .setLocation(Location.newInstance(5,7))
          .addSizeDimension(0,5).addSizeDimension(1,20)
          .addRequiredSkill("electric drill")
          .setTimeWindow(TimeWindow.newInstance(20,35))
          .build();
// specify shipment - which involves two stops
Shipment shipment = Shipment.Builder.newInstance("shipmentId")
          .setName("myShipment")
          .setPickupLocation(Location.newInstance(2,7)).setDeliveryLocation(Location.newInstance(10,2))
          .addSizeDimension(0,9).addSizeDimension(1,50)
          .addRequiredSkill("loading bridge").addRequiredSkill("electric drill")
          .build();

Specify your fleet - jsprit allows you to add multiple depots by just adding vehicles/drivers with different start locations. You can specify start and end locations explicitly. You can also instruct your drivers to return to their depots again as well as to stay at the last customer site. Additionally, you can define a heterogeneous fleet by assigning different vehicle types (with different capacities and transportation costs), skills and operation times to your vehicles.

// specify type of both vehicles
VehicleTypeImpl vehicleType = VehicleTypeImpl.Builder.newInstance("vehicleType")
          .addCapacityDimension(0,30).addCapacityDimension(1,100)
          .build();

// specify vehicle1 with different start and end locations
VehicleImpl vehicle1 = VehicleImpl.Builder.newInstance("vehicle1Id")
          .setType(vehicleType)
          .setStartLocation(Location.newInstance(0,0)).setEndLocation(Location.newInstance(20,20))
          .addSkill("loading bridge").addSkill("electric drill")
          .build();

// specify vehicle2 with open end, i.e. end is determined by the algorithm
VehicleImpl vehicle2 = VehicleImpl.Builder.newInstance("vehicle2Id")
          .setType(vehicleType)
          .setStartLocation(Location.newInstance(5,0))
          .setReturnToDepot(false)
          .addSkill("loading bridge")
          .build();

Put it all together to define the problem, set the routing costs (by default Euclidean distance is used) and specify whether you have a finite or infinite fleet. Latter might be important at tactical level when designing your fleet.

VehicleRoutingProblem.Builder vrpBuilder =  VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.addJob(service).addJob(shipment).addVehicle(vehicle1).addVehicle(vehicle2));
vrpBuilder.setFleetSize(FleetSize.FINITE);
VehicleRoutingProblem problem =  vrpBuilder.build();

Algorithm

// define an algorithm out of the box - this creates a large neighborhood search algorithm 
VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);

Solution

// search solutions
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
// get best
VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);