Low priority score in mixed setup with jobs and shipments

[jayroos]

I am trying to build routes that make sure each location is visited at least once and generally only on one route.

The background is we have 37 locations with 3 routes and a central depot. Every location receives a delivery (job) from the depot. We also have shipments taking place between locations where items are picked up at one location and delivered to another.

Ideally, once all locations are visited the vans will return to the depot where undelivered items are unloaded, sorted and loaded into vans for the next day.

If I only have deliveries (jobs) in the input file, every location gets just one visit. However, to ensure that we don't exceed vehicle capacity, I need to also consider the shipments between locations. When I add shipments between the non-depot locations, then stops get dropped.

I have attempted to fix this by giving deliveries from the depot priority 100 and shipments between stops priority 1, but it did not resolve the issue.

I have perused past issues and the documentation, but have not figured out how to resolve this. Any help is appreciated.

[jcoupey]

When I add shipments between the non-depot locations, then stops get dropped.

You mean you get unassigned tasks? That's a normal consequence when you have too many tasks along with constraints: capacity, time windows etc.

I'm not sure I totally get what exactly you think is wrong. Could you share a standalone problem instance along with the solution we provide and point out what you'd expect instead (or what is the problem in the existing solution)?

[jayroos]

Yes, unassigned tasks. I need the delivery jobs to all get assigned. I'm fine with having pickup and delivery shipments get dropped. I tried to use priorities to ensure the delivery visits would still all be performed, but it didn't seem to have much effect. All locations are visited when it's a delivery from the depot only. When I add in the pickup and drop off shipments then delivery jobs stop getting assigned.

I am attaching two standalone instances (delivery only and delivery and pickup). Both of them have our required time constraint which is more than sufficient for the deliveries alone. I also have a capacity restraint, but I've raised it high enough that it wouldn't ever be reached. I tried removing it, but it seems I have to remove it from all of the jobs/shipments or it won't parse.

route-matrix.zip

[jcoupey]

You don't have a capacity problem but a timing one. The vehicle working hours are enough for all the deliveries indeed, but as soon as you add (a lot of) shipments, handling everything would require more route legs. The 3 provided vehicles simply don't have enough time to handle everything with their current time_window. To be more precise:

• vehicles still have some available time at the end of the routes for the job-only instance while routes provided with added shipments are tightly packed in term of timing;
• if for example you double the size of the vehicle time window (from [0, 26400] to [0, 52800]), then the number of unassigned tasks drops dramatically.

[jayroos]

I understand that and I wouldn't expect all of the shipments to be made. I'm just not understanding why, even with the high priorities, jobs are going unassigned. Shouldn't they be prioritized to be completed with the lower priority shipments going unassigned? If not, what are the priorities for?

It's completely OK to have shipments go back to the depot, in fact it's expected. I only include them for 2 reasons:

1. Optimize any on-route shipments to have less going back to the depot and quicker delivery.
2. Make sure that no van gets overloaded beyond it's capacity.

[jcoupey]

Right, I overlooked the priority question and now I see your point. The solution with all jobs assigned is valid and would have a total priority score of 3600, while we provide a solution with priority 2900.

This is very similar to #319. The work to fix that was ticketed in #324 and a fix has been released since. The problem is that this has been designed with jobs in mind and should be extended in some way for situations including shipments.

In short: we have ways to make sure low-priority jobs will get unassigned to favor high-priority jobs, but we're unable to discard a low-priority shipment to make room for a higher priority job.

[jayroos]

Would switching the delivery jobs to shipments with high priority make more sense or do I just induce other problems with that approach?

[jcoupey]

I don't expect switching jobs to shipments would do any good, and it would artificially increase the size of the problem.

You'd rather need to do it the other way around: turning shipments into jobs. This is not generally possible, except that in your case you can do it for all shipments that have a location_index of 0 which coincide with the vehicles end. Those can be modeled as jobs with a pickup key. Not a generic fix of course, but may do the trick in your example.

[jcoupey]

For the record: I think the suboptimal example we have in this ticket would be solved by #988.

[jcoupey]

I think the suboptimal example we have in this ticket would be solved by #988.

The solution is now much better using v1.14.0-rc.3 compared to v1.13.0: priority score is now 3400 (was 2900), unassigned tasks is 1074 (was 1077) and cost is 60960 (was 63259).

We're still not reaching the optimal priority score of 3600 though.