‘Multiple time-windows’ has been the most requested feature. I recently implemented this. However, to verify whether the algorithm finds reasonable solutions I need your help (since official benchmarking problems are rare). Would you mind to solve some of your problems with multiple time-windows and give some feedback, e.g. whether the algorithm produces bad results or is too slow etc.?
You can find the latest implementation here. Here you can find two examples of how to setup and solve a problem with multiple time-windows:
Hi, I tested the multiple time windows feature on small set of services (10- 50). It works prefect and I did not get bad results. The results are reasonable compared to single time window. In some cases, there is some improvements in the solutions compared to single time window.
Regarding the performance, I didn’t notice big overhead. I compared the time required to generate the solutions with multiple time windows and without multiple time windows. Both are comparable. But, again I used only small number services as an initial test. I will use larger dataset, and see how it goes.
When adding a time window (timeWindow) and checking whether it overlaps with any existing time window (tw), besides checking whether timeWindow’s .getStart() or .getEnd() is inside any tw, I think it is also necessary to check whether any tw’s .getStart() or .getEnd() is inside timeWindow. Or is it done somewhere else?
Hello Karm,
Thanks a lot for your efforts and it sounds good that (up to now) everything works as intended . Looking forward to your analysis when it comes to larger problems.
Best, Stefan
@apoorv2203 Please use this branch for the latest developments. As the code you referred suggested, you probably used the old branch. In the new one, there is no such code anymore.
Hi @stefan Look at the sample data below. Ideally it should have followed the route 1,3,4,5,2. The actual result was 1,4,5,2. Unassigned 3. I modifed the TimeWindowTest
Service service1 = Service.Builder.newInstance(“1”)
.addTimeWindow(50,100)
.addTimeWindow(20,35)
.setServiceTime(10)
.addSizeDimension(WEIGHT_INDEX, 1).setLocation(Location.newInstance(10, 10)).build();
Service service2 = Service.Builder.newInstance("2")
.addSizeDimension(WEIGHT_INDEX, 1)
.setServiceTime(10)
.setLocation(Location.newInstance(20, 0)).setServiceTime(10).build();
Service service3 = Service.Builder.newInstance("3")
.addTimeWindow(5, 10)
.addTimeWindow(35, 50)
// .setServiceTime(1)
.addSizeDimension(WEIGHT_INDEX, 1).setLocation(Location.newInstance(30, 0)).build();
Service service4 = Service.Builder.newInstance("4")
If I am not mistaken, the earliest departure time from service1 will be 20 + 10 = 30, and if going to service3 right next, the earliest arrival time at service3 will be (assuming crowFly and speed is 1) 30 + sqrt(500) = 52.36, which is later than the latest allowed arrival time for service3 (50), thus, routing service3 right after service1 is not possible.
I want to share my experience with you and made some tests.
In this view the vehicles have multiple TW for 3 working days[480|1080, 1920| 2520, 3360|3960] and 4 vehicles
The locations and timewindows for the services were generatet randomy so these values can sometimes not make much sence, but I think this plot shows that the feature works good and i cant find very better solutions.
For your information:
702_540-900(30):
702 = id of the service
540 = earliest beginning
900 = latest beginning
(30) = servicetime
I hope this helps. if you want I can generate more examples.
And sorry for posing such a big text, cant find the function to make my text with an button hidable.
Total time: 11.075s
Finished at: Fri Jan 29 17:12:44 CET 2016
Final Memory: 5M/127M
------------------------------------------------------------------------
Hi ,
Did some of my own testing using the MultipleTimeWindowExample2. I made the following change as listed below. What I observed is that a) the job ends within the time window, but starts outside time window. b)the job begins within the time window, but ends outside time window. Is it possible to have a work completed within a time window
for(int i=0;i<40;i++){
double s1=0,s2=0,s3=0,l1=0,l2=0,l3=0;
s1=random.nextInt(50);
s2=220 + random.nextInt(50);
s3=400 + random.nextInt(50);
l1=75;
l2=300;
l3=500;
System.out.println((i+1)+" t1="+s1+","+l1+" t2="+s2+","+l2+" t3="+s3+"="+l3);
Service service = Service.Builder.newInstance("" + (i + 1))
.addTimeWindow(s1, l1)
.addTimeWindow(s2, l2)
.addTimeWindow(s3, l3)
. Looking forward to your analysis when it comes to larger problems.