Using OptaPlanner to resolve multiple orders with pick-ups and deliveries

Question

Hello optaplanner community. Greetings and always grateful for your answers.

I have a VRP problem where I have a fleet of vehicles and the list of visits. Each visit has a delivery point (D delivering) and a picking point (P picking). The restriction is that each visit is attended by a single vehicle and the vehicle must first go to the pickup point to load what the visit demands and then go to deliver. If the demand of the delivery point is greater than the capacity, it must not be broken down into trips. If there is no other vehicle with a greater capacity capable of supporting this visit, it must ignore the visit in this planning. Above all because there are visits whose demand cannot be divided and therefore the vehicle must transport it in the same trip.

1- I would like to know if this problem I have can be modelled as VRPPD even though each vehicle must go only once to a delivery point? I understand that although each vehicle must go only once to a delivery point, there must be an order between visits and each pickup point must be made before the delivery point. I understand that each visit does not have multipicking, as the vehicle only goes once, but the entire route does have multiple pick-ups and deliveries.

2- I have made some assumptions to solve my problem. Do you have any suggestions that I can make to model it? Are my assumptions correct? I am a novice with Optaplanner and any suggestions would be very useful.

I've analyzed that maybe I can solve my VRPPPD by registering all the points as visits, where the delivery and pick-up point of a visit would be in the same location. Each visit would have a type to know which is Picking (P) and which is Delivering (D). It would have to manage a shadow variable to update the capacity of the vehicle, since in each P the capacity increases and in the D it decreases. And my hard restrictions would be one for the capacity, a restriction so that each P and D have the same vehicle, and another restriction so that each P is done before the D.

3- On the other hand, I thought to use the example "optaplanner-mixedvrp-experiment" by Geoffrey? I understand that this example is for multiple trips where the vehicle breaks up the trips to the customer into multiple trips, so I understand that the vehicle goes to the customer multiple times, so I understand that I must make some modifications.

What changes can I make in this example "optaplanner-mixedvrp-experiment" to mix pick-ups and deliveries, but never from the same customer. This is exactly my requirement.

Is it possible that 4 and 5 are solved by applying this example?

4- How can I manage that when there are visits with nearby collection points, I go perhaps first to several collection points and then to make the deliveries.

(P1 P2 D1 D2 P3 D3) where P1 and P2 are nearby, first pick up and then deliver

5- How can I manage that when there are visits with the same delivery point, the vehicle can load what is demanded by these visits at the same time, so that it does not have to return to the same point? Since I understand that the distances and time between visits should not be doubled, given that although they are different visits they have the same location.

(P1 D1 D2 P3 D3) where D1 and D2 have the same pickup point (P1) and the vehicle has sufficient capacity to load the demand of points D1 and D2 at P1.

6- How can I make the vehicle leave the depot with zero capacity and go directly to the 1st pickup point?

Answer 1

I am not familiar with Geoffrey's PDVRP experiment, but this is how I'd approach it (Note that I'll be using graph terminology):

• If you want only one vehicle to go to do a visit, you must have only one node (planning variable) present in your problem. Optaplanner will assign this node to a chain, more precisely to a previous node where the journey is planned to start from. If it has only one node it will essentially be a single visit.
• If you want Optaplanner to ignore a visit if its demand does not fit into a vehicle you must make it nullable (see this question). This means that Optaplanner does not assign it to a resource. Note that however Optaplanner doesn't support this on chain variables, but you can resolve that with a dummy vehicle.
• For your problem, you want to satisfy the pick-up and delivery constraint. You can either enforce this using custom moves (e.g. a chain move moves both the pick-up and delivery node and not a single one) or you can use constraints that penalize any violations of this constraint (i.e hard score of -1 for each violation). This is just a guess, but I would think that using custom moves is more efficient. Optaplanner is not configured out of the box to support this use-case and would spend more time exploring the infeasible solution space due to the nature of the built-in chain moves. Either way, you d have to know what object you are dealing with at any given time, so you an either create a class, e.g. Visit (or maybe Job), with subclasses PickupVisit and DeliveryVisit. Alternatively, you could store the type as a field, but that is design decision you need to consider. I would advise that whatever way you chose you can easily retrieve the sibling task, i.e. the corresponding pick-up or delivery task, as you'll need this in your computations.

How can I manage that when there are visits with the same delivery point, the vehicle can load what is demanded by these visits at the same time, so that it does not have to return to the same point?

There are a few options:

1. You can preprocess them into a single job
2. You can use an objective value to enforce this behaviour (e.g. an objective to minimize unique visits to a location). You have full flexibility where you put this.

How can I manage that when there are visits with the same delivery point, the vehicle can load what is demanded by these visits at the same time, so that it does not have to return to the same point? Since I understand that the distances and time between visits should not be doubled, given that although they are different visits they have the same location

By using the objectives. This sounds like it is desired behaviour, not required behaviour. So I'd put in a score that maximizes number of visits, or minimizes total distance. You'll have to play with it as there is no easy answer.

How can I make the vehicle leave the depot with zero capacity and go directly to the 1st pickup point? You need to implement a score calculator, so you'd do in there. E.g in a simple score calculator you just start accumulating from the first job onwards so you can start with 0. It gets a little more complicated for the other score calculators, but there are some good examples in the Optaplanner repo.

I hope this answers most of your questions.