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.
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 ...
jsprit is fit for change due to comprehensive unit and integration tests.
jsprit is documented and additional code-examples illustrate its use.
jsprit allows you to define additional stateful and stateless constraints to account for the richness of your problem.
jsprit is benchmarked against classical VRP instances (e.g. Solomon instances).
jsprit is released under Apache License v2.
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();
// define an algorithm out of the box - this creates a large neighborhood search algorithm
VehicleRoutingAlgorithm algorithm = Jsprit.createAlgorithm(problem);
// search solutions
Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
// get best
VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);