Taxi / Bus use case not using optimal route

[briandilley]

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)

[JO-WTF]

You concern is understandable but you must define the priority of delivery and pickup by yourself.

In the case you introduced, it is indeed better to deliver A and B first before picking up C. However, that may result in a higher cost. So how would you leverage between the road cost and the cost of customer waiting in the cab for delivery?

What I mean here is you need to add some cost to customers who have already got on the taxi waiting to be delivered. In that case, picking up C before delivering A will make that waiting-in-cab cost much higher compared with the increased transportation cost increased when delivering A first.

[briandilley]

So then I should add some cost for how long each passenger is waiting in the vehicle then? Would I use a VehicleRoutingActivityCosts for that?

[briandilley]

Using the MaxTimeInVehcileConstraint as a reference I was able to create a SoftActivityConstraint for determining the time on the vehicle. Now i guess I just need to figure out the math for generating a cost based on the time:

		constraintManager.addConstraint(new SoftActivityConstraint() {

			private final TransportTime transportTime = problem.getTransportCosts();

			@Override
			public double getCosts(
					JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {

				if (newAct instanceof DeliveryActivity) {

					double newActArrival = prevActDepTime + transportTime.getTransportTime(
							prevAct.getLocation(),
							newAct.getLocation(),
							prevActDepTime,
							iFacts.getNewDriver(),
							iFacts.getNewVehicle());

					double newActStart = Math.max(newActArrival, newAct.getTheoreticalEarliestOperationStartTime());

					double pickupEnd = (iFacts.getAssociatedActivities().size() == 1)
						? iFacts.getNewDepTime()
						: iFacts.getRelatedActivityContext().getEndTime();

					double timeInVehicle = newActStart - pickupEnd;

					return timeInVehicle;
				}

				return 0;
			}
		});

[briandilley]

I figured this out with the above