search

reinterpretcat / vrp

A Vehicle Routing Problem solver
https://reinterpretcat.github.io/vrp/
Apache License 2.0
331 stars 68 forks source link

Violation on optional break window #129

Open ilibar-zpt opened 9 months ago

ilibar-zpt commented 9 months ago

Version: 1.22.1

problem.json

{"objectives": [[{"type": "minimize-unassigned","breaks": 999}],[{"type": "minimize-cost"}]],"plan": {"jobs": [{"id": "job1","pickups":[{"places": [{"location": {"lat": 52.5316,"lng": 13.3884},"duration": 100.0,"times": [["2019-07-04T10:00:00Z","2019-07-04T12:00:00Z"]]}],"demand": [1]}],"deliveries": [{"places": [{"location": {"lat": 52.52599,"lng": 13.45413},"duration": 300.0,"times": [["2019-07-04T11:00:00Z","2019-07-04T13:00:00Z"]]}],"demand": [1]}]},{"id": "job2","pickups":[{"places": [{"location": {"lat": 52.5316,"lng": 13.3884},"duration": 40.0,"times": [["2019-07-04T10:00:00Z","2019-07-04T12:00:00Z"]]}],"demand": [1]}],"deliveries": [{"places": [{"location": {"lat": 52.5225,"lng": 13.4095},"duration": 240.0,"times": [["2019-07-04T12:00:00Z","2019-07-04T14:00:00Z"]]}],"demand": [1]}]},{"id": "job3","pickups":[{"places": [{"location": {"lat": 52.5316,"lng": 13.3884},"duration": 100.0,"times": [["2019-07-04T10:00:00Z","2019-07-04T12:00:00Z"]]}],"demand": [1]}],"deliveries": [{"places": [{"location": {"lat": 52.5165,"lng": 13.3808},"duration": 300.0,"times": [["2019-07-04T13:00:00Z","2019-07-04T15:00:00Z"]]}],"demand": [1]}]}]},"fleet": {"vehicles": [{"typeId": "vehicle","vehicleIds": ["vehicle_1"],"profile": {"matrix": "normal_car"},"costs": {"fixed": 22.0,"distance": 0.0002,"time": 0.004806},"shifts": [{"start": {"earliest": "2019-07-04T09:00:00Z","location": {"lat": 52.5316,"lng": 13.3884}},"end": {"latest": "2019-07-04T18:00:00Z","location": {"lat": 52.5316,"lng": 13.3884}},"breaks": [{"time": [3600,4000],"places": [{"duration": 1800.0}]}]}],"capacity": [10]}],"profiles": [{"name": "normal_car"}]}}

Command: vrp-cli solve pragmatic problem.json --out-result result.json --log --max-time 15 --min-cv sample,10000,0.05,true --parallelism 1,1

result.json

{"statistic":{"cost":47.445932,"distance":11357,"duration":4822,"times":{"driving":1137,"serving":1080,"waiting":805,"break":1800,"commuting":0,"parking":0}},"tours":[{"vehicleId":"vehicle_1","typeId":"vehicle","shiftIndex":0,"stops":[{"location":{"lat":52.5316,"lng":13.3884},"time":{"arrival":"2019-07-04T09:00:00Z","departure":"2019-07-04T12:01:40Z"},"distance":0,"load":[3],"activities":[{"jobId":"departure","type":"departure","time":{"start":"2019-07-04T09:00:00Z","end":"2019-07-04T11:57:40Z"}},{"jobId":"job3","type":"pickup","location":{"lat":52.5316,"lng":13.3884},"time":{"start":"2019-07-04T11:57:40Z","end":"2019-07-04T11:59:20Z"}},{"jobId":"job2","type":"pickup","location":{"lat":52.5316,"lng":13.3884},"time":{"start":"2019-07-04T11:59:20Z","end":"2019-07-04T12:00:00Z"}},{"jobId":"job1","type":"pickup","location":{"lat":52.5316,"lng":13.3884},"time":{"start":"2019-07-04T12:00:00Z","end":"2019-07-04T12:01:40Z"}}]},{"location":{"lat":52.52599,"lng":13.45413},"time":{"arrival":"2019-07-04T12:09:10Z","departure":"2019-07-04T12:14:10Z"},"distance":4495,"load":[2],"activities":[{"jobId":"job1","type":"delivery"}]},{"location":{"lat":52.5225,"lng":13.4095},"time":{"arrival":"2019-07-04T12:19:15Z","departure":"2019-07-04T13:06:40Z"},"distance":7543,"load":[1],"activities":[{"jobId":"job2","type":"delivery","location":{"lat":52.5225,"lng":13.4095},"time":{"start":"2019-07-04T12:19:15Z","end":"2019-07-04T12:23:15Z"}},{"jobId":"break","type":"break","location":{"lat":52.5225,"lng":13.4095},"time":{"start":"2019-07-04T12:36:40Z","end":"2019-07-04T13:06:40Z"}}]},{"location":{"lat":52.5165,"lng":13.3808},"time":{"arrival":"2019-07-04T13:10:06Z","departure":"2019-07-04T13:15:06Z"},"distance":9599,"load":[0],"activities":[{"jobId":"job3","type":"delivery"}]},{"location":{"lat":52.5316,"lng":13.3884},"time":{"arrival":"2019-07-04T13:18:02Z","departure":"2019-07-04T13:18:02Z"},"distance":11357,"load":[0],"activities":[{"jobId":"arrival","type":"arrival"}]}],"statistic":{"cost":47.445932,"distance":11357,"duration":4822,"times":{"driving":1137,"serving":1080,"waiting":805,"break":1800,"commuting":0,"parking":0}}}]}

Expected: Break is scheduled between [3600,4000] seconds after departure.

Actual: Break is scheduled 2340 seconds after departure (2019-07-04T12:36:40Z - 2019-07-04T11:57:40Z)

reinterpretcat commented 9 months ago

Thanks! Seems related to usage of offset break and departure time optimization. I've changed validation rule to address this. Essentially, you need to disable departure time optimization for that vehicle by setting shift.start.latest = shift.start.earliest if time offset on break is used

ilibar-zpt commented 9 months ago

Thanks for quick responses! Is there a way to get breaks to work with time windows relative to departure and/or previous break end, and have it working with departure time optimization?

The reason for that is an irl regulation where drivers have to make a break after maximum 4hrs of driving for minimum 30mins, so next break depends on when last has ended

reinterpretcat commented 9 months ago

Hi, at the moment, there is no workaround as this is a limitation due to implementation.