I’m using jsprit for routing trips for a bus. The use case is that there is a depot, and passengers take the bus to travel to and from the depot. For instance you can schedule a pickup at your home and to be dropped off at the depot, or you may be at the depot and want to be dropped off at home. Basically one side of the Shipment is always the depot. I’m having some trouble with the routes that it picks sometimes. I think I need to have it optimize for as little travel time per shipment as possible (or a balance of that and route time).
For example, please example the grid below. The X is the depot and there are 3 rides: A, B, and C. A and B start at X (they are at the depot) and end at their homes. C starts at their home and is dropped off at the depot.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2
3
4
5
6
7 C1 B2 X
8
9 A2
10
11
12
13
14
15
X = A1, B1
The route that i would expect (with the vehicle starting at the depot) would be:
pickup A (at depot),
pickup B (at depot),
deliver A (at home),
deliver B (at home),
pickup C (at home),
deliver C (at depot)
but instead what i’m seeing is:
pickup A (at depot),
pickup B (at depot),
deliver B (at home),
pickup C (at home), <- this is the weird step IMO
deliver A (at home),
deliver C (at depot)
I understand that this may be a more optimal route for picking up and dropping off packages, but for passengers it’s undesirable for A to have to sit in on the ride all the way to C before being brought home.
I hope that what i’m explaining is coming across correctly.
Here’s how i’m setting things up:
final VehicleTypeImpl vehicleType = VehicleTypeImpl.Builder.newInstance("standardVehicleType")
.addCapacityDimension(DIM_PASSENGER_COUNT, capacity)
.setMaxVelocity(11.176)
.build();
final VehicleImpl vehicle = VehicleImpl.Builder.newInstance("shuttle")
.setUserData(currentLocation)
.setType(vehicleType)
.setStartLocation(Location.newInstance(currentLocation.getLat(), currentLocation.getLon()))
.setEndLocation(Location.newInstance(finalLocation.getLat(), finalLocation.getLon()))
.setReturnToDepot(true)
.build();
... for each ride ...
Job job = ride.neesPickup() // (some passengers are already on the bus)
? Shipment.Builder.newInstance("shipment-" + ride.getId())
.setUserData(ride)
.setName(ride.getPassengerName() + " (" + ride.getId() + ")")
.addSizeDimension(DIM_PASSENGER_COUNT, ride.getPassengerCount()) // # of passengers
.setPickupLocation(Location.newInstance(
ride.getPickupLocation().getPoint().getLat(),
ride.getPickupLocation().getPoint().getLon()))
.setDeliveryLocation(Location.newInstance(
ride.getDropOffLocation().getPoint().getLat(),
ride.getDropOffLocation().getPoint().getLon()))
.build()
: Delivery.Builder.newInstance("delivery-" + ride.getId())
.setUserData(ride)
.setName(ride.getPassengerName() + " (" + ride.getId() + ")")
.addSizeDimension(DIM_PASSENGER_COUNT, ride.getPassengerCount()) // # of passengers
.setLocation(Location.newInstance(
ride.getDropOffLocation().getPoint().getLat(),
ride.getDropOffLocation().getPoint().getLon()))
.build());
final VehicleRoutingProblem problem = VehicleRoutingProblem.Builder.newInstance()
.addAllJobs(jobs)
.addVehicle(vehicle)
.setFleetSize(FleetSize.FINITE)
.build();
final StateManager stateManager = new StateManager(problem);
final ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);
final VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(problem)
.setStateAndConstraintManager(stateManager, constraintManager)
.buildAlgorithm();
final Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
final VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions)