GraphHopper.com | Forum | GitHub | Maps | Blog

Mix of Pickup and Service. What does Jsprit assume for Capacity


#1

If we use only Service class, then if we set vehicle capacity, suppose for dimIndex=0 and dimValue=100. then vehicle starts with loaded volume of 100 and then it goes to various service points to deliver.

If we use only Pickup class, then if we set vehicle capacity, suppose for dimIndex=0 and dimValue=100. then vehicle has no loaded volume but it can pick max 100.

What if we have Service and Pickup classes in VehicleRoutingProblem. Will vehicle start with empty box to fill it on pickup location or with loaded box to deliver it to service locations.


#2

Hello,

Currently, Service and Pickup works the same way, you need to use Delivery to deliver some points.

The actual load mechanism is as follow :
The vehicle will load the pickups until it is full. Then it will order the deliveries until the vehicle is empty, if need it will fill the vehicle at depot in the limit that the sum of pickups + load at start is less or equal to the vehicle capacity.


#3

So in the mix case, which is Pickup And Delivery (Not talking about Shipment). Vehicle will start with empty bag and then it will fill the bag at various pickup points and it will pickup until its box is full. Then it will go for delivery. It will deliver until it has no volume left. And this method will follow periodically.

I think the mechanism will then have problem. During pickups it may find a locality (delivery location) very close from vehicle current location, at which delivery can be done but due to the mechanism described it will not deliver and first go for more pickups. Had it delivered at that point, it would have been easy for vehicle to pick now more volume.


#4

Deliveries could happen before pickups, only the global route load matters. This way it can handle the case you expose, but it can’t handle it when the sum of all pickups is greater than the vehicle capacity.


#5

Hi @shivkrishnajaiswal,

For Pickup jobs, loading happens at the job location, and they are not dropped off during the route.

For Delivery jobs, they are already loaded at the very beginning of the route, and unloading happens at the job location.

Capacity constraint is that, at any point in the route, the load on the vehicle must not exceed its capacity.

Therefore, in the mix case, vehicle does not start with empty load. It loads the items of the Delivery jobs already (may or may not be all the Delivery jobs, depending on the capacity constraint).

If the vehicle is already full loaded at the beginning, then it cannot do any Pickup jobs before it drops off for some Delivery jobs.

At the end of the route, the vehicle will have dropped off for all the Delivery jobs that it loads at the beginning, and will have loaded for some Pickup jobs (again, may or may not be all the Pickup jobs, depending on the capacity constraint).

What happens during the route? Jspirt will try to optimize the route wrt the cost, meanwhile respecting the capacity constraint and other constraints. Thus, it may or may not do all the Pickup jobs first and do all the Delivery jobs later, or the opposite, or really mixed, depending on the locations of the jobs and the constraints (including capacity).

Hopefully it helps.

Best regards,
He


Negative values as capacities
#6

Does it also happen if we use Service jobObject instead of Delivery jobObject?

I found that Solutions differ in terms of total number vehicle used as well as value of cost returned at the end of the program for (Service + Pickup) and (Delivery + Pickup).


#7

As @braktar said, Service is effectively Pickup, so you can use Service to replace Pickup but not Delivery.


#8

All delivery volume should be picked up at depot itself.
Can we ensure that vehicle starts with 0 volume and delivery volume must comes from volume picked up up to that delivery point ?


#9

then you will need to model the jobs as shipments.


#10

But in that case, we already need to specify the pick up location as well as delivery location.
I was thinking whether we can produce the scenario in which volume that has to be delivered comes from volume that has been picked up.
For example:
Suppose we have,
Pickup A at (1,0) and pickedVol =10
Delivery B at (2,0) and deliveryVol =10
Pickup C at (3,0) and pickedVol =10

Depot location O is at (0,0) and vehicle capacity is 10.
path produced, is: O -> B -> C -> O
which is vehicle starts with vol 10 which is delivered at B and then biker picks vol at C.

VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();

	Job A = Pickup.Builder.newInstance("A")
			.addSizeDimension(0, 10)
			.setLocation(Location.newInstance(1, 0))
			.build();
	Job B = Delivery.Builder.newInstance("B")
			.addSizeDimension(0, 10)
			.setLocation(Location.newInstance(2, 0))
			.build();
	Job C = Pickup.Builder.newInstance("C")
			.addSizeDimension(0, 10)
			.setLocation(Location.newInstance(3, 0))
			.build();
	Vehicle V = VehicleImpl.Builder.newInstance("Vehicle")
			.setType(VehicleTypeImpl.Builder.newInstance("bike").addCapacityDimension(0, 10).build())
			.setStartLocation(Location.newInstance(0, 0))
			.build();

	vrpBuilder.addJob(A).addJob(B).addJob(C)
			.addVehicle(V)
			.setFleetSize(FleetSize.FINITE);

	VehicleRoutingProblem vrp = vrpBuilder.build();
	VehicleRoutingProblemSolution vrpSolution = Solutions.bestOf(Jsprit.createAlgorithm(vrp).searchSolutions());
	SolutionPrinter.print(vrp, vrpSolution, Print.VERBOSE);

I was thinking of scenario where biker starts with 0 vol. it goes to A picks 10 vol and then delivers 10 at B and then picks 10 at C. At each instant, maintaining that total volume that biker has is less than its capacity.
Expected path: O -> A -> B -> C -> O


#11

Okay, I think I see what you mean, but let us make sure we are on the same page first:

  1. let us assume there are m delivery jobs and n pickup jobs, and the volume of the m delivery jobs is termed as M, while that of the n pickup jobs is termed as N;

  2. in the case of M < N, all the volume of the m delivery jobs comes from the n pickup jobs, but you do not specify which pickup job corresponds to which delivery job(s), because it could be any; and all the remaining volume of pickups (i.e., N - M) goes back to the depot;

  3. the case of M > N follows the same logic.

Is the above correct?

Best regards,
He


#12

yes. But that could be very rough estimate.
The exact constraint would be, at each instant, algebraic sum of volume from pickup and delivery location that happened upto that instant must be greater than 0 and less than or equal to vehicle capacity.(Noting that vol from delivery object is negative and from pickup object it is positive.)


#13

Hi,

Did you find any solution to the problem?

Best regards,
Bálint