Same-route precedence constraints

[nielsenko]

Would it be possible to assign a partial order to jobs, so that the sequences returned by vroom would respect this partial order?

Perhaps a rank could be assigned to jobs, and all jobs with lower rank must come before all jobs with higher rank. Jobs without rank should not be constrained by this.

This would disallow certain sequences, similar to how timeslots does today.

[jcoupey]

Could you expand a bit on the use-cases you have in mind? What kind of situation would this allow to handle?

[nielsenko]

Say you have a box of sorted letters. These are sorted in a static sequence, that you do not want to change, since it would require that you re-sort them. However, you also have a cage full of parcels that are unsorted, and that needs to be sorted anyhow. These you would like to mix with the letters on your route.

So the order of the letters is fixed (you can split the box between routes), but the order of the parcels is free.

Another use-case would be to ensure pickups happen before drop-offs. This would require something more flexible than the rank suggested above, ie. someway to specify that the pickup job x goes before drop-off job y (x < y).

I was challenged with these use-cases, by a representative from a postal service. I envision using a "respect partial order" feature to address such use-cases.

[braktar]

In an industrial context, we usually met three types of ordering relations between jobs.

• Same route : Jobs have to be visited within the same route without regardless to the order.
• Order : Jobs have to be visited within the same route in a particular order, letting other jobs to be inserted between.
• Sequence : Jobs have to be visited within the same route in a particular order, and no job can be inserted between.

[jcoupey]

A first step toward this could be to think about adding simple precedence constraints for jobs: i->j means that job i and j should belong to the same route in that order (with potentially other jobs in-between). This would cover the Order item above and would probably be enough to handle pick-up and delivery problems.

@nielsenko your situation would be modelled by a list of precedence constraints given by the pre-existing ordering, except you'd have to decide the box-splitting yourself in advance.

@braktar I'm curious about your Same route and Sequence categories, could you share real-life situations where those are required?

[braktar]

Same Route : One of the first met of this constraint was for a customer delivering fresh or frozen food. If I remember well some parcels were packed together and only split at deliveries.

Sequence : This constraint is often met with press delivery when some city districts are outsourced and contractually fixed.

The Order constraint is a good start for pick-up and delivery, but my thought is that it could be limited when both missions can't be inserted within the same route. For example, if the route is already fulfilled with some other Jobs, the pickup can be inserted, but inserting the delivery require to unassign another job.
In the pick-up and delivery case, both jobs are directly linked, In the general case Jobs are not directly dependant with an Order relation (Unassign one, doesn't mean you can't perform the other jobs)

[jcoupey]

Same Route

OK, this looks like a corner case to me. Also it could be handled using skills provided the common route is decided beforehand (less flexible but maybe doable in most situations).

Sequence

The sequence could then probably be seen as a single job, with to and from travel times based respectively on the first and last job and total service and time window adjusted accordingly. Again I don't think handling this is a priority right now.

On the other hand, the same-route precedence constraints would probably unlock more use-cases. I have no idea right now on how and when this could be implemented but I'll flag this issue to track the feature.

it could be limited when both missions can't be inserted within the same route

So far, I've only been talking from the API perspective: if the jobs are requested as related, then they should be in the right order in the same route, or all unassigned. That said, we'd have to handle the intermediate states you mention internally in term of solution validity.

[sinaabadi]

@jcoupey any news about adding this feature to vroom?

[jcoupey]

I have no idea right now on how and when this could be implemented

@sinaabadi to complement the above quote: no plan on my side for a short-term implementation, and no real visibility right now on how this will fit in my priority queue. But if anyone is willing to give it a try, I'd be happy to discuss implementation ideas.

The features that are currently planned for the next release are grouped in the v1.4 milestone.

[myleftshoe]

I have a similar use case: Let's say 50% of deliveries are standing orders and 50% are ad-hoc. The standing orders are always delivered by the same driver, let's call these their "usual runs". The ad-hoc deliveries are one off's and can be delivered by any driver. With three drivers would like split the ad-hoc deliveries and assign them to the the most appropriate driver, fitting them into their usual runs optimally.

[jcoupey]

@myleftshoe it does not sound like you need precedence constraints to model what you describe, but skills. You could use individual skills for each of your drivers and then a specific one to describe ad-hoc deliveries that can be assigned to any driver. The three drivers would for example have respective skills [0, 1], [0, 2] and [0, 3]. Ad-hoc deliveries would have a [0] skills array and standing orders could be directed to the relevant driver, e.g. using [2] for driver 2.

[myleftshoe]

@jcoupey. Thankyou! I'll give it a go today

[myleftshoe]

@jcoupey. Great! got it working. It's so simple. More of a comment than a feature request (possibly it's just demonstrating my limited understanding) :- it might be nice to be able to specify strings as the skills e.g. ['any', 'John']. Apologies for polluting the thread too.

[jcoupey]

@myleftshoe glad this worked out for you. The skills logic is flexible as is (with plain integers) and different use-cases can require different modelling, so I think it's better to keep it that way and let users decide on their own logic and properties.

[jsfurniss]

I have a suggestion to consider on how to "link" jobs together to support pickup and drop off scenarios: If the job object had an additional, optional field for "FollowsJobId", the id of the job it's linked to could be included. This would let the system know they are to be kept together and would also specify the sequence. This could support "trips" that have multiple stops. "Pick up Fred (Job 1), take Fred to store (Job 2, follows Job 1), take Fred back home (Job 3, follows Job 2)" The amount value (positive, zero or negative) would specify whether it's a pickup, stop or drop off respectively.

[jcoupey]

For generality's sake, follow-up jobs should ideally be modelled as a list instead of a single job id. Think about a situation where you pick a number of parcels along a route and have to deliver them each at a different location.

I guess we should go through a couple of papers on pickup and delivery problems to make sure this model is sufficient.

[jsfurniss]

For generality's sake, follow-up jobs should ideally be modelled as a list instead of a single job id. Think about a situation where you pick a number of parcels along a route and have to deliver them each at a different location.

What would be wrong with having more than one follow-up job with the same "parent" job id to support the above problem? 2 packages: 1 pickup location, 2 drop locations... Job 1 amount=2, Job 2 amount = -1 follows job 1, Job 3 amount = -1 also follows job 1. So we end up with two "trips" 1 to 2 and 1 to 3.

I'm proposing that rather than having a "list" of follow-up jobs attached to the primary job, we just have multiple follow-up jobs referencing the primary one. Both options arrive at the same goal and it ultimately comes down to how your logic is structured for which way would be easier to implement.

[ghost]

I have no idea right now on how and when this could be implemented

@sinaabadi to complement the above quote: no plan on my side for a short-term implementation, and no real visibility right now on how this will fit in my priority queue. But if anyone is willing to give it a try, I'd be happy to discuss implementation ideas.

I need this feature for my university project and I thought I'd give it a shot at implementing it. Note that Google Routing API implements similar feature as a simple restriction array data['pickups_deliveries'] = [ list of [pickup_id, delivery_id] pairs ], i.e.:
https://developers.google.com/optimization/routing/pickup_delivery#complete_programs

I thought maybe it might be a good idea to start with a quick POC implementation and have an array of [pickup_id, delivery_id] pair restrictions that would be iterated (and rejected if [pickup, delivery] pair is not in array) for each planned case; and then expand with a more generic precedence constraints. @jcoupey could you help me determine which parts need to be modified to do that? Thanks!

[jcoupey]

@johnvencky the tricky part is to be able to ensure solution validity (in a cheap way) throughout the whole solving process: i.e. for any precedence constraint, both pickup and delivery should be in the same route (or both unassigned) and in the right order.

High-level sketch of a possible approach:

1. Adjust the heuristics to always include both P&D whenever needed.
2. Adjust the existing local search operators to make sure we don't break P&D constraints.
3. Benchmark and test new "dedicated" local search operators that may be required (e.g. to move both P&D from one route to another).

Point 1 and 3 are difficult mostly because whenever a new job (say a pickup) is assigned to a route, there is a new range of choice for the linked job, and we can't really afford a huge increase of the algorithmic complexity. Point 2 is mostly about filtering out existing moves that would invalidate the solution.

[ghost]

Thanks for your guidance @jcoupey. I've taken a look at the code and can already appreciate the work and effort that you put into it! :)

What do you think about potentially simpler solution that would avoid the headache of trying to keep the jobs together in heuristics and local search stages.

The various time_window, amount, and skills restrictions are really invalid for pickup-delivery cases since they are inseparable -- so I thought why not just merge them together instead of trying to keep them together? Trying to keep them together seems fragile -- if delivery job breaks time_window, skills or other constraints then the whole (pickup, delivery) pair is invalid.

How about:

"jobs": [
    {
      "id": 1,
      "service": 300,
      "amount": [1],
      "location": [1.98935, 48.701],
      "skills": [1],
      "time_window": [32400, 36000],
      "delivery": [2.03655, 48.61128]
    },
    ...

In this case we could look at the whole job as atomic pickup-delivery pair, we would just need to make sure that "location" (lon,lan) is used for incoming edges, and "delivery" (lon,lan) used for outgoing edges. I think this would also address your concern about not increasing algorithmic complexity.

Thanks!

[jcoupey]

@johnvencky your description is indeed simpler and would fit the situation where the delivery is done right after the pickup. But this is too restrictive for a generic usage, in particular it would not allow to model some situations like:

• pickup and delivery with different time windows
• other pickups/deliveries/single jobs need to be inserted between P&D (think routes like Start -> P1 -> P2 -> other job -> D2 -> other job -> D1 -> end)
• multiple deliveries associated with one pickup
• multiple pickups associated with one delivery

If you need none of the above and grouping P&D in a single job is enough for your use-case, then it will indeed be simpler to give it a try. But if we are to merge a P&D implementation to master, I think it should address the above modelling needs.

[ghost]

I read your points and agree 100% that this is not suitable for master.

As our use case is very simple P&D between two groups, I actually came up with a much simpler solution that's already implemented in VROOM! I'll provide a custom Matrix (where each job is P&D pair), and set service time to distance(job_pickup, job_delivery) + service_pickup + service_delivery. That way I actually don't need to change any code.

Again, I think this should be implemented in master in the way you described, however I feel that I don't have enough knowledge and understanding to do it in a reasonable amount of time; and since our use-case is already covered by current implementation I'll leave it up to someone more suitable for this task.

Thanks again for your work and guidance @jcoupey, it is very much appreciated.

[mhosman]

Hey @jcoupey, Suppose I have 10 jobs. There are 4 jobs that must be done in a specific order but between those jobs I can complete another jobs (The other six jobs). There's a way to do this without specifying a time?

For example, in GraphHopper API (https://docs.graphhopper.com/#operation/solveVRP) you can set an array of relations with "in_sequence" option:

in_sequence: This relation type enforces n jobs to be in sequence. It can be specified as

 {
    "type": "in_sequence",
    "ids": ["serv_i_id","serv_j_id"]
 }

which means that service j need to be in the same route as service i AND it needs to occur somewhere after service i. As described above if a specific vehicle needs to conduct this, just add vehicle_id.

[jcoupey]

4 jobs that must be done in a specific order

@mhosman there is no way to do this right now, and this is exactly the kind of constraint this ticket is about. Like I said above, I think a minimum viable implementation should handle "one to one", "one to many" or "many to one" scenarios. But I'm curious about your example because it would imply a chain of "one to one" precedence constraints. Can you provide a bit of context on the underlying use-case?

[mhosman]

Hey, @jcoupey thank you very much for your response! It's like grouping jobs in a specific task that requires a sequence of jobs (let's say 4) to be done in a specific order, but with the availability to finish other jobs, from other "tasks" between this 4 jobs. The idea is to do this without setting the time_windows parameter (what matters is the sequence and not the time schedule).

[jcoupey]

Thanks @mhosman I get it from the modelling perspective. But would you have a real-life example where this kind of "chained ordering" constraints occur?

[mhosman]

Yes sure, for example, I have 5 jobs that must be done in sequence:

• Job 1: Destination A: Pick-up materials for dest. B & C.
• Job 2: Destination B: Deliver materials from dest. A and pick-up materials for dest C & A.
• Job 3: Destination C: Deliver materials from dest. A & B. and pick-up materials for dest. B & A.
• Job 4: Destination B: Deliver materials from dest. C.
• Job 5: Destination A: Deliver materials from dest. B & C.

Important!!! Between jobs 1-5 I can finish other jobs, not associated with these ones. (the important thing here is the sequence, not the order itself with the global amount of orders).

[mhosman]

Hey @jcoupey, is this example good enough? This situation is happening every day to me and today there is no way to achieve this (just with a time_window but is not an efficient way).

[jcoupey]

@mhosman yep, you've make it pretty clear. The difference with the "simple" usual P&D constraint is you'd need to be able to handle a chain of precedence constraints, not only pairs. At this point, I don't have a clear view on how much more complex this would be to implement.

[mhosman]

Thanks @jcoupey !. I think this is an important feature that opens up many new possibilities. Complex but necessary functionality.

@nielsenko @braktar @sinaabadi @myleftshoe It could be great to have more examples and ideas in order to implement this.

[tinchoel10]

Hi!! I'm trying VROOM for the very first time and I have the same problem! I need a sequence of jobs :)

[K-Leon]

We‘re also looking for a simple trick to maintain order. e.g. making sure the same shipment get’s picked up before delivery is planned. More or less a classical courier scenario.

[mhosman]

@K-Leon exactly!

[jcoupey]

In term of API, the difference with the current notion of job is that some info are shared between pickup and delivery, some are not. A way to deal with this would be to introduce a new job type that would have the common keys at higher level, then pickup and delivery objects for specific stuff.

{
  "amount": [14],
  "skills": [1],
  "priority": [0],
  "pickup": {
    "id": 0,
    "location": [4, 47],
    "service": 300,
    "time_windows": [[0, 28800]]
  },
  "delivery": {
    "id": 1,
    "location": [5, 48],
    "service": 240,
    "time_windows": [[36000, 43200]]
  }
}

This is both similar but different to the current job interface: pickup and delivery keys have different meaning here as they're not just plain amounts. So I think it would be wiser to separate such tasks in input, say in a shipments array.

Internally, we should probably stick to a job being a step in a route (be it a regular one-stop job, or a pickup or delivery).

[jcoupey]

Support for pickup and delivery scenario landed in master with #274. Feedback welcome, use new shipments array to add P&D with same-route precedence constraint.

[mhosman]

Great!!! We'll check the new functionality!!

[mhosman]

Hey @jcoupey, we tested v1.6 and we have some questions:

I don't know if this is an error or not but if I create two jobs with two vehicles I get one job per vehicle. If I create two shipments with two vehicles, both shipments are assigned to only one vehicle (2 pickups and 2 deliveries). This is okay?

If shipments are like jobs but the only difference is that the pickup must be done before a delivery, why not add the possibility to create shipments with only deliveries in order to delete jobs and unify the logic?

[jcoupey]

I don't know if this is an error or not but if I create two jobs with two vehicles I get one job per vehicle. If I create two shipments with two vehicles, both shipments are assigned to only one vehicle (2 pickups and 2 deliveries). This is okay?

The way jobs/shipments are grouped (or not) in routes is probably a result of the constraints you're setting so you're the one who can tell if it's ok. ;-)

why not add the possibility to create shipments with only deliveries in order to delete jobs and unify the logic

We can't really spare having two kind of objects here. Shipments describe the need to move something around from one place to another. Jobs describe actions that happens at some place: either a delivery from something loaded at the route start, or a pickup of something that will be brought back at the route end. Jobs are not a special case of shipment because both a delivery and a pickup can happen at the same location.