search

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

Fixed jobs #345

Open balage1551 opened 7 years ago

balage1551 commented 7 years ago

Use case: There are some cases, when some jobs has to be done at a fix time with a well specified vehicle. They can't be moved or put onto an other vehicle, but interacts with the other jobs as any other activities. One reason is when some jobs is beyond the possibility to change, but other jobs could be "put around" it.

Proposal A new flag for jobs is defined marking them fixed. These jobs has to have no TW, but has a vehicle to be dedicated to, and has a start time/duration. The initial solution builder places these tasks into the route. The ruin strategies can't touch them.

Open questions: I don't know how the capacities could be handled. Also if the insertation follows a time sequencial strategy, it is hard to integrate it.

Compatibility impact It would add a new job type and can be implemented as a backward compatible feature.

lukes commented 7 years ago

We got around this issue by giving those jobs time windows of 1 minute around their fixed time, and assigning them a required skill of __vehicle_<id>__ (where <id> is the id of the vehicle it must be allocated to), and then give that vehicle the matching skill. That means that jsprit ought to allocate that job only to that vehicle, and within that specific window of time.