Need help to verify multiple time window feature

Hello community,

‘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:

Example1

Example2

Looking forward to read from you. Thanks a lot.
Stefan

1 Like

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.

Thanks,
Karm

Hi Stefan,

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?

Best regards,
He

Hello Karm,
Thanks a lot for your efforts and it sounds good that (up to now) everything works as intended :smile:. Looking forward to your analysis when it comes to larger problems.
Best, Stefan

Hi He,
This makes perfekt sense. Thanks a lot. I will be implementing this.
Best, Stefan

Hello He,
integrated:
tests
impl
Thanks again,
Stefan

Hi Stefan,
else if(actArrTime < tw.getStart()){
return tw;
}
Whats the reasoning behind this. This does not fit in the time window.

Also this will pick the first timewindow that is before the actArrival time and not the one which is closest to the actArrivalTime

Can you please send me the link to the code snippet you refered to?

Am 19/12/15 um 11:53 schrieb Apoorv Jain:

@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.

sorry for the late reply. Sure I will check the branch

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")

// .addTimeWindow(5,10)
.addTimeWindow(20, 40)
.addTimeWindow(45, 80)
.setServiceTime(15)
.addSizeDimension(WEIGHT_INDEX, 1).setLocation(Location.newInstance(40, 15)).build();

    Service service5 = Service.Builder.newInstance("5")
        .addTimeWindow(5,10)
        .addTimeWindow(20, 40)
        .addTimeWindow(60,150)
        .addSizeDimension(WEIGHT_INDEX, 1).setLocation(Location.newInstance(20, 50)).build();

Hi @apoorv2203,

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.

Best regards,
He

1 Like

I aggree with He. Thanks, He.

Hi He,
Agree with you.

Hello!

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.

±-------------------------+
| problem |
±--------------±---------+
| indicator | value |
±--------------±---------+
| noJobs | 60 |
| noServices | 60 |
| noShipments | 0 |
| fleetsize | FINITE |
±-------------------------+
±---------------------------------------------------------+
| solution |
±--------------±-----------------------------------------+
| indicator | value |
±--------------±-----------------------------------------+
| costs | 30940.785873648183 |
| noVehicles | 4 |
| unassgndJobs | 19 |
±---------------------------------------------------------+
±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | v3 | start | - | undef | 480 | 0 |
| 1 | v3 | service | 702_540-900(30) | 524 | 570 | 44 |
| 1 | v3 | service | 761_660-960(30) | 640 | 690 | 114 |
| 1 | v3 | service | 768_660-960(90) | 763 | 853 | 187 |
| 1 | v3 | service | 920_840-900(30) | 887 | 917 | 221 |
| 1 | v3 | service | 725_480-960(60) | 1042 | 1980 | 346 |
| 1 | v3 | service | 229_840-900(60) | 2057 | 2340 | 424 |
| 1 | v3 | service | 630_900-960(30) | 2375 | 2405 | 459 |
| 1 | v3 | service | 538_480-960(30) | 2481 | 3390 | 535 |
| 1 | v3 | service | 489_660-720(60) | 3480 | 3600 | 626 |
| 1 | v3 | service | 764_780-900(90) | 3649 | 3750 | 675 |
| 1 | v3 | service | 852_900-960(60) | 3838 | 3898 | 764 |
| 1 | v3 | end | - | 4046 | undef | 911 |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 2 | v1 | start | - | undef | 480 | 0 |
| 2 | v1 | service | 775_600-780(90) | 598 | 690 | 118 |
| 2 | v1 | service | 369_840-900(30) | 777 | 870 | 205 |
| 2 | v1 | service | 345_540-600(90) | 925 | 2070 | 260 |
| 2 | v1 | service | 27_660-900(30) | 2171 | 2201 | 361 |
| 2 | v1 | service | 285_780-840(60) | 2260 | 2320 | 420 |
| 2 | v1 | service | 664_780-960(60) | 2351 | 2411 | 452 |
| 2 | v1 | service | 806_540-840(30) | 2470 | 3450 | 510 |
| 2 | v1 | service | 284_600-960(60) | 3534 | 3594 | 594 |
| 2 | v1 | service | 517_840-900(30) | 3709 | 3750 | 709 |
| 2 | v1 | service | 166_900-960(90) | 3826 | 3916 | 784 |
| 2 | v1 | end | - | 4161 | undef | 1029 |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 3 | v2 | start | - | undef | 480 | 0 |
| 3 | v2 | service | 453_480-900(90) | 550 | 640 | 70 |
| 3 | v2 | service | 488_780-960(60) | 740 | 840 | 170 |
| 3 | v2 | service | 425_600-900(90) | 872 | 962 | 202 |
| 3 | v2 | service | 474_480-540(90) | 1169 | 2010 | 409 |
| 3 | v2 | service | 108_480-780(30) | 2126 | 2156 | 525 |
| 3 | v2 | service | 312_720-780(30) | 2204 | 2234 | 573 |
| 3 | v2 | service | 741_540-900(30) | 2330 | 2360 | 669 |
| 3 | v2 | service | 215_720-960(30) | 2373 | 2403 | 682 |
| 3 | v2 | service | 523_480-660(90) | 2618 | 3450 | 897 |
| 3 | v2 | service | 690_660-720(90) | 3545 | 3635 | 992 |
| 3 | v2 | service | 474_780-840(30) | 3673 | 3703 | 1030 |
| 3 | v2 | end | - | 3806 | undef | 1133 |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 4 | v4 | start | - | undef | 480 | 0 |
| 4 | v4 | service | 931_660-720(90) | 560 | 750 | 80 |
| 4 | v4 | service | 99_720-840(30) | 804 | 834 | 133 |
| 4 | v4 | service | 768_600-960(90) | 913 | 1003 | 212 |
| 4 | v4 | service | 976_600-780(90) | 1201 | 2130 | 410 |
| 4 | v4 | service | 345_780-840(60) | 2244 | 2304 | 524 |
| 4 | v4 | service | 671_900-960(90) | 2347 | 2437 | 568 |
| 4 | v4 | service | 551_660-720(60) | 2536 | 3600 | 666 |
| 4 | v4 | service | 745_780-840(60) | 3666 | 3726 | 732 |
| 4 | v4 | service | 923_780-960(90) | 3815 | 3905 | 821 |
| 4 | v4 | end | - | 4092 | undef | 1008 |
±-------------------------------------------------------------------------------------------------------------------------------+
±---------------+
| unassignedJobs |
±---------------+
| 217_840-960(90) |
| 491_780-840(60) |
| 651_840-900(60) |
| 976_720-780(90) |
| 304_780-900(60) |
| 854_900-960(90) |
| 870_660-780(60) |
| 233_900-960(60) |
| 770_480-540(60) |
| 431_780-900(60) |
| 920_840-900(60) |
| 180_840-960(60) |
| 274_780-840(90) |
| 190_780-960(30) |
| 517_780-840(90) |
| 253_720-780(90) |
| 613_780-840(30) |
| 712_780-840(60) |
| 399_900-960(30) |
±---------------+
2016-01-29 17:12:42,814 [main] INFO jsprit.analysis.toolbox.Plotter - plot to output/plot.png

BUILD SUCCESS

Total time: 11.075s
Finished at: Fri Jan 29 17:12:44 CET 2016
Final Memory: 5M/127M
------------------------------------------------------------------------

1 Like

Thanks, Patrick for your help. Great! Good to know that you did not find any inconsistencies :).

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)

// .addSizeDimension(0, 1)
.setServiceTime(25)
.setLocation(Location.newInstance(random.nextInt(50), random.nextInt(50))).build();
vrpBuilder.addJob(service);
}

@stefan can you please give me some pointers on how to achieve this. I want the task to begin and complete both within the time window.

Powered by Discourse