graphhopper / jsprit

jsprit is a java based, open source toolkit for solving rich vehicle routing problems
https://www.graphhopper.com/open-source/
Apache License 2.0
1.64k stars 604 forks source link

how to handle intermediate status in pickup and deliver scenario #167

Closed PleaseWorld closed 9 years ago

PleaseWorld commented 9 years ago
  1. For pickup and delivery scenario, I want to evaluate the problem for multiple times during the delivery. So the evaluation may starts when the vehicle has already been delivering some cargo. When the problem is built, how to let jspirit know the vehicle already has some shipment on the way, which means it already gets some cargo from the pickup locations? This will have impact as the current capacity of the vehicle is not the capacity of the vehicle type set since it already has load, for example, the current load is 5 while the capacity is 7. It is not equal to be of capacity 2 as the capacity can grow to be greater then 2 after the cargo is delivered. In another word, the vehicles may already have some assignment of jobs before the evaluation, these assignment may have impact on the final solution.
  2. How to implement the soft time window? I cannot use hard time window constraints because for the intermediate status of delivery, the vehicle already pick ups cargo and it must deliver it. The hard time window will cause the shipment to be unassigned. I have found a post here in the forum but I cannot find any answer. Could you give more guide?
oblonski commented 9 years ago

@1 search for initial vehicle routes. jsprit allows you to specify initial loads

@2 soft time windows cannot be easily implemented yet. For such a job, you might widen the hard time window, or you omit it entirely and penalyze late arrivals by implementing a SoftActivityConstraint. Actually, I do not know whether this gives you reasonable results since if you deal with soft time windows you somehow need to evaluate arrival time shifts in the whole route rather than just in the neighborhood of your insertion. In research this is often estimated with a penalty function which is dependent on the local time shift. You need to try yourself.

PleaseWorld commented 9 years ago

@1 It seems to work, thanks! @2 I tried to use the logic in VehicleDependentTimeWindowConstraints to calculate the cost and it seems to work. Do you mean theoretically it may not be possible to achieve correct result in the current design? What do you mean the local time shift? Could you give more explanation?