I’m new to jsprit and have been playing with it for a few days. Noticed there is a driver class (com.graphhopper.jsprit.core.problem.driver.Driver) which has seemingly useful properties like earlieststart, latestend, homelocation, etc.
However, I can’t seem to find how do the drivers relate to a Job or VehicleRoutingProblem…
There is no VehicleRoutingProblem.addDriver function, or anything obvious that makes it clear how to add driver information to a VRP as far as I can tell. Any examples?
Currently, Driver has no functionality. Everything which in the real
world belongs to drivers is currently modelled with vehicles. However, I
see it as placeholder for future developments. There might be good
reasons in future to separate drivers from vehicles.
Everything which in the real world belongs to drivers is currently modeled with vehicles.
I’m trying to model the following situation but can’t figure out how to do it:
Let’s say I have a heterogeneous fleet of 3 vehicles V1, V2, V3 with different capacities, c1, c2 and c3 respectively. Also let’s say I have
3 drivers D1, D2, D3 with different working times (earliest start, latest end) tw1, tw2, tw3. The drivers are not associated with any particular vehicle and can drive any of the three vehicles as needed.
UPDATE: I forgot to mention that the jobs (pickups, deliveries, services, etc) that this fleet will carry out also have Time windows
How can I model a VRP and solve it with jsprit considering this case?
I was thinking I could declare 3 vehicles for each real vehicle, each with one of the 3 different time windows of the drivers, for example for V1:
V1_1 (with c1, tw1)
V1_2 (with c1, tw2)
V1_3 (with c1, tw3)
However the problem obviously is that I end up with 9 vehicles, and in reality I only have 3. Is there a way to define that despite the fact that there are 9 vehicles the solver should only use 3? Or any other ideas how to model this case?
Hi @jmfairlie,
A simpler but less efficient way: add an outer loop for all possible matchings between vehicles and drivers (for 3 vehicles and 3 drivers, 6 matchings), and choose the solution with the best result.
A more complex but (possibly) more efficient way: add a hard constraint that only one of the 3 versions of each vehicle can be used. You will probably also need to add to the state manager to record the usage of the vehicles. I am not sure if this will work and how the result will be - I will look forward to seeing how it is.
Best regards,
He
Hi, Is there a special reason why you need to model this with drivers? If not, you can easily model this with vehicles only. Just define 3 vehicles with different earliest start and latest end. If you only have these 3 vehicles, add them to the problem and set fleet size to FINITE.
Well this is indeed the simplest and obvious solution but as you mention it is overwhelmingly inefficient since the # of combinations grows almost exponentially (N!) with the problem size. With 3 vehicles/drivers it is manageable, since the # of combinations amounts to 3! = 6 but once you get a slightly bigger more realistic problem with say 10 vehicles/drivers, suddenly the # of combinations grows to 10! = 3,628,800
This is more the kind of solution I was thinking of. Unfortunately I have no idea how to implement it. I was hoping someone that had already encountered this situation could give me some hints, otherwise I guess I’ll have to spend potentially ages scanning through the jsprit code to understand how things work under the hood.
UPDATE; I forgot to mention in my earlier description of the problem that the jobs (pickups, deliveries, services, etc) that this fleet will carry out also have Time windows. I guess without this clarification then you are right, I can just assign the drivers’ TWs arbitrarily to the vehicles.
Well. maybe I am misunderstanding the problem but as far as I understand, if I do what you mention then I wouldn’t necessarily get the optimal solution to the problem, since I would be assigning a single arbitrary TW (out of 3 possible TWs) to each given vehicle (remember that each vehicle has different characteristics. e.g Capacity). Intuitively, it seems to me that It’s totally possible that for some problems a different combination of Vehicles/TWs would result on a more optimal solution.
So in the problem I described:
Are you implying it doesn’t matter which of the 6 possible Vehicle/TW combinations I choose I will get an optimal solution, as good or better than what I would get with the other 5?
Hi Stefan,
Actually, I can see that this could be one of the situations you mentioned where you would want to decouple the driver from the vehicle. You have 3 vehicle types that could be driven 24/7, the limit is the person in the vehicle. You have 3 drivers, each with different shifts - whatever driver is picked for the vehicle then defines the working window for that vehicle. I believe your suggestion mandates that an arbitrary decision is made over which vehicle types can drive for which hours.
For example, I choose that type_1 gets driver 3, meaning that type_1 is now only available between 9 am and 4 pm. The problem is then solved. However, what if a better solution could have been achieved by having vehicle type_1 on the road for longer (I instead put driver 2 in this vehicle, and his shift is 9 am to 6 pm) and put driver 3 in a different vehicle. In each case, (n^2 - 1) possible solutions are never even tested; the blind spot scales fast!
I typed out a detailed reply to OP on how you might be able to do this using the same tricks I used in the huge thread on driver lunch breaks but then realise it fell down on the last hurdle. Whilst it will make all permutations available to the algorithm in a single run, I don’t think there’s anything stopping, for example, two vehicles escaping the warehouse that are both “driven” by the same driver with the longest working hours. I’ll provide it anyway in case it sparks a thought:
…
The idea here is that by creating the 6 jobs at the warehouse, your entire fleet (well, at least 6 vehicles just for the fake jobs) is mobilised to cover the fake jobs, which leaves them fair-game to start doing real jobs. This is not what you want because, once deployed, you lose the fixed cost parameter that would normally minimise the number of vehicles.
Instead, we cheat by massively inflating driving distance to/from warehouse (add 1000 km for each direction, even more if necessary to really make it truly disproportionate to your real problem scale) to simulate a fixed cost. So, even though all vehicles are deployed, it is not attractive to have more than the minimum number of vehicles to do anything other than sit at the warehouse because of the disproportionate fuel cost, even if for the longest shift he could have done 3 hours more work.
In each case, for a particular vehicle type, the one with the most appropriate working shift should be selected to escape the warehouse. If all 3 vehicles are not needed, there aren’t any fake jobs left so it should just never get deployed.
All well and good, in theory, BUT there are issues to think about:
Josh
Are you implying it doesn’t matter which of the 6 possible Vehicle/TW combinations I choose I will get an optimal solution, as good or better than what I would get with the other 5?
No, you absolutely could not give that guarantee but then it would also be worth looking at how much you actually save by investigating all possibilities; it would depend on how radically different the shift patterns are, (maybe?) the salaries and the vehicle running costs. Especially if the fleet isn’t pushed to the limit, it might be quite small.
I haven’t seen this raised before and it had never occurred to me. It’s a really interesting question because a solution to this could really have legs but for now thinking about how to approach this is quite overwhelming and brute-forcing it by testing all permutations definitely won’t scale; it’s probably a heuristic in itself, but I can’t think what you’d base it on.
Taking it further, if you considered a heterogeneous vehicle fleet as a totally pooled resource (ok, you probably won’t have HGV drivers with a motorbike licence… but you could), you could have non-standard shift patterns that ensure one vehicle is still in the field for an hour extra while the most sensible vehicle for the jobs on the next shift (and the next) was brought back to the warehouse. Shifts dictated by the vehicles and jobs, not the other way round. I imagine long-haul and Amazon et al. have some degree of this but it’s also possible they still insert human logic on what vehicle has to be at what depot at what time for the next driver shift.
Pulling back from Uber-type thinking, what is the scale of your real-world problem? If there aren’t many vehicles then you could either brute-force it or maybe we could try give some suggestions on short-cutting. Perhaps there’s a mixture of my base idea and some soft/hard constraints that can get something closer ( EDIT: perhaps a combination of fake skills to represent a shift pattern, and fake pickups to represent the vehicle type… I’d need to think more)
Hi Stefan, jmfairlie,
I think I’ve solved this using only existing hard constraints with reduced overhead compared to solving permutations individually. The key is to use two sets of services in sequence that act as teleporters. If a vehicle can’t use the teleporter, the travel time to all other locations is greater than the longest shift time… nothing that doesn’t pass through both filtering teleporters can do anything.
The first set of teleporters filters vehicles by their type. The second filters by available shifts. So, let’s change the problem setup to make it more complicated to demonstrate.
For brevity, we will assume that all vehicle types can be operated by all drivers.
At this point we have the filter for vehicle type. If a vehicle doesn’t do one of the pickups in point 6, it will never be able to get to any location. It’s impossible now for a non-real ratio of vehicles to be deployed out of all our permutations that are sitting at the warehouse.
Branching trees of teleporters could be made if certain vehicles could only be driven on a subset of all available shifts. It takes a bit of time to conceptualise it, but it’s simple enough to implement programmatically. Also, interestingly, the convergence time should decrease with every practical restriction you have in terms of driving ability because you introduce fewer permutations of vehicles.
I’d be really interested to see what you think and whether this actually converges on a solution in a reasonable time!
Josh
I would like to be able to solve VRPs with a heterogeneous fleet ideally with up to 20 vehicles , but at least up to 10.
So brute forcing all N! combinations as described above wouldn’t be reasonable.
Thank you very much for all the ideas! I will need some time to familiarize myself with JSprit, its code and examples a little better in order to be able to actually understand the concepts involved in your solution. I will get back to you.
Thank you very much for all the ideas! I will need some time to familiarize myself with JSprit, its code and examples a little better in order to be able to actually understand the concepts involved in your solution. I will get back to you.
You’re very welcome! You presented such an innocuous problem but I honestly don’t think this is really considered generally. Drivers != vehicles seems such a dumb revelation, but it has really re-framed my perspective.
In terms of my idea, I do have concerns with my proposed approach. Stefan is much better placed than me to say anything on this; I tried to keep the “gate-keeper” part as simplistic as possible - two stages and only one way to go through the portals - but it’s very possible that many iterations could be wasted on things not getting through both stages, making convergence near impossible. Or the optimisation part being focused on what got through the gatekeeper by random selection in the initial stage, and not allowing shifts to change.
I am not a competent Java programmer that can re-write the base code and so sometimes I’m forced to be creative to use the tools available. Jsprit is fantastic for this kind of thing because of the flexibility. A → B taking 10,000 years, but B → A taking seconds… it’s just numbers to be considered by the algorithm. You can distort reality to force things that are way beyond the already-huge range of tools it provides 
I would not be surprised if my approach becomes untenable, but I’d love to know the outcome either way. I think that, as long as it can converge, the worst case scenario is that you’re left with a solution that’s no different than arbitrarily assigning shifts to vehicles, but you do provide an opportunity to allocate shifts more intelligently if the algorithm doesn’t choke on the combinatorial problem at the start.
EDIT:
The high-level overview of the approach to help with understanding:
Loads of vehicles at the warehouse covering permutations. The only jobs that they can possibly do are the pickups in point 6; we’ve made everything else unreachable. Since these jobs have specific capacity requirements that are now analogous to vehicle types, only a real-fleet ratio of vehicles can be selected from our pool to do the pickups.
The vehicles that do the pickups have a random selection of skills, which are now analogous to shifts.
Again, these vehicles that did the pickups have nowhere to go other than the services we created that require specific skills that match up with the shift patterns of our drivers. It might be that they are have a skill (shift) that is not available in the next pool of jobs that are available. If they don’t, their solution is dead in the water and will be culled (or they will sit and do no other jobs if that vehicle isn’t needed in the real world problem). If they do, they perform one of the services available.
From the magical location (it’s in another dimension somewhere) that they perform the service, suddenly they find that all of the real-world locations are within reach, so they start doing real jobs.
It’s very abstract thinking. When I was working on lunch breaks, I initially had drivers taking them in another dimension. Philip Welch then had the fantastic idea that drivers should carry their lunch break as a delivery. Both worked but had their drawbacks. Somehow out of that madness, Stefan managed to create a viable feature in jsprit I’ve bundled all that learning into this approach, but the reality is that the combinatorial problem at the start might still be overwhelming in reaching a good solution; it probably requires a heuristic for smarter selection. You’d have to try it and see!
Best of luck!
Josh
@jmfairlie Thanks for working out a case where the differentiation between vehicles and drivers do make 100% sense. If you have a hetergogenous fleet and drivers with different shifts, you cannot use the current approach.
@roganjosh I love the way you find solutions for problems that seem to be unsolvable with jsprit 
. As far as I can judge it, it seems to be a reasonable approach. I am on travel the next two weeks, as soon as I find time after this, I try to setup my own examples with your approach. Probably, I need to get back to you to understand each and every piece of your suggestion. Thank you so much for your ideas.
Hi,
Enjoy your holiday, Stefan I had another idea driving home that could be much simpler. I might have been constrained by keeping my initial idea afloat.
Just have all vehicles start and finish at the same time covering big windows e.g. 1am to 11pm. Define a range of shipments that go from the warehouse to the warehouse to limit the shifts. E.g. if I want an 8 am to 6 pm shift, I create a pickup service time of 7 hours (1am to 8am) and a delivery service time of 5 hours (6pm to 11pm) at the warehouse. You can use capacity dimensions to limit shifts to particular vehicles and make sure they can only do one shipment each. Now you don’t have any permutations of vehicles.
You might still be stuck with a bit of reality-warping since again you deploy the whole fleet to do the fake shift-limiting-shipments. So again, you’d have to have these and the warehouse thousands of miles from the real jobs but zero distance to/from warehouse for the shipment locations such that vehicles just do those jobs and call it a day if it doesn’t make sense for them to do real jobs. If you don’t have shipments as part of your real service, great, penalise instances of shipments in unassigned to be extra sure
After that, I think I’m out of ideas, so it’s now a case of testing (I’d start with this one because it’s much simpler) and seeing what the difficulties are. I’m happy to clarify any points if they’re not clear.
Regards,
Josh
Hi @jmfairlie,
Can you test with the attached code and let me know how it works? I have tested on a very limited number of very small cases and it seems okay to me.
The only problem I have encountered in my limited tests is that, in the case that only one vehicle can be used and there must be unassigned jobs (in the code, for example, if you setTimeWindow for s1 as (15, 20) and remove v3), the result will be that s2 is assigned to v2 and all other 3 jobs are unassigned, rather than that s1 is unassigned and all other 3 jobs are assigned to v1.
Best regards,
He