Hi,
I’m curious if there’s a way to do the following:
Given a service with a time window between 5-6pm, there are two vehicles that are available. Vehicle 1 is 5 minutes away and Vehicle 2 is 10 minutes away.
If it is 4:45pm: neither vehicles get assigned to the service since both would arrive too soon.
If it is 4:50pm: still neither vehicles get assigned to the service. Vehicle 2 would not arrive too soon but Vehicle 1 is closer.
If it is 4:55pm: assign Vehicle 1 to the service.
It would seem that I’d need a HardActivityConstraint that, when evaluating if the service could be inserted in a route containing Vehicle 2, would be able to know that Vehicle 1 is closer and also that it can also be assigned to the service.
I’m pretty sure that I could use a problem state + state manager to keep track of the closest vehicle to every service, so that would solve the first part. But I’m not sure about the second part, leaving me with the following question:
Within a HardActivityConstraint, is there a way to query or track whether or not the service has had all of its constraints fulfilled by another vehicle?
If so, I’m thinking that I could then have this constraint be LOW priority and all of my other constraints be CRITICAL or HIGH.
This seems like a big ask and I definitely might be approaching this problem from the wrong angle. Any guidance at all would be really, really appreciated. Thanks in advance!
Hi,
I have to admit that I’m quite confused on what you are asking here. From your problem setup, it seems that you’re calling jsprit for a solution at set intervals? In which case, I have to ask why is the job going into your problem prematurely in the first place?
It would seem that I’d need a HardActivityConstraint that, when evaluating if the service could be inserted in a route containing Vehicle 2, would be able to know that Vehicle 1 is closer and also that it can also be assigned to the service.
If you’re calling the solution at regular intervals, and based on your criteria, then you should also be tracking the distance of all vehicles to all places. With 1000 orders and 100 vehicles… this still isn’t a mammoth task for graphhopper when you initialise the problem, and then there’s plenty of really simple rules to identify the pairs you might want to re-check before calling each new iteration of jsprit, leaving the rest unchecked (i.e. order A will never be suitable for vehicle B because it was 100km away initially).
Your criteria (and correct me if I’m wrong) appears to be: the item should be assigned to the closest vehicle that also would incur no waiting in accepting the job. The above approach would “solve” this… there is only ever one vehicle closest to the job at the time of calling for a solution and then you just check whether travel_time < (time_window_opening - current_time). Basically, just don’t inject it as a job into jsprit until your external check is passed. When you do inject it into the problem, give it a skill or capacity requirement that can only be accommodated by the vehicle you want it to go to.
But my concern here is that you’re turning this into a greedy type of problem. When you start forcing jobs to specific drivers on such short time scales, you completely override the power of Jsprit in finding a global optimum. How can you know, so arbitrarily, that assigning an order to the driver that could do the job immediately is the most appropriate choice in the overall problem? How do you know that some existing job isn’t converted to unassigned? Unless there is a very specific business requirement to do otherwise, just assign accurate values to .setCostPerDistance(), .setCostPerWaitingTime() and .setCostPerTransportTime().
I’ve just seen your post here: Resume previously planned solution? - #21 by roganjosh which frames this current question better for me.
…would be able to know that Vehicle 1 is closer and also that it can also be assigned to the service.
Bold highlight mine. It’s a combinatorial problem; you cannot know unless you try. What you’re trying here is a greedy approach - you can do that without Jsprit. I’m not sold on your approach. I’d be surprised if the other conversation goes into any further specifics, unfortunately; this would cost people their jobs because it’s mostly unsolved regardless of libraries and academia, but worth a lot to companies…
Yes, I am actually running jsprit continuously in a while(true) loop. There are a mix of services that need vehicles assigned to them including on demand (which can appear at any time) and scheduled services. The on demand services are the reason optimizations are run so frequently.
The nature of this continuous optimization is that its first step is to “recreate” the world in the state and then optimize whatever wasn’t added to an initial route. What jsprit is left to optimize is fairly limited right (to only scheduled services) now though the intention is to reduce the services that go into initial routes over time so that jsprit handles all service assignments.
The goal of the question was to see if vehicles can be proactively assigned to scheduled services. The answer is of course yes, though given how frequently we run optimizations the consequence in attempting proactive assignment is that a further vehicle will almost always get assigned to a scheduled service as opposed to waiting for time to pass so that the closer vehicle can be assigned to the scheduled service. In other words, distance/time is not being optimized in these cases.
Very distant scheduled services are filtered out of the problem though currently some are left in an attempt to proactive assign them. There seems to be a tradeoff here where the shorter the “proactive assignment window” that’s attempted the less likely jsprit is to find a vehicle to arrive right on time but the more likely the assignment is desirable.
For example, if the “proactive assignment window” were set to 5 minutes, it’s less likely that a vehicle is found that can arrive within 5 minutes than if the window were 30 minutes. If the window were 30 minutes however, it’s more likely that a vehicle could arrive within 30 minutes but it may end up being very far away despite other vehicles being much closer which leads to more distance traveled overall.
It sounds like this window will end up being a variable that I’ll have to tweak to find something that’s reasonable. I appreciate the thorough response and if my response here sparks any other ideas I’ll be sure to try them out!