# Copyright 2010-2025 Google LLC # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. """This model implements a bus driver scheduling problem. Constraints: - max driving time per driver <= 9h - max working time per driver <= 12h - min working time per driver >= 6.5h (soft) - 30 min break after each 4h of driving time per driver - 10 min preparation time before the first shift - 15 min cleaning time after the last shift - 2 min waiting time after each shift for passenger boarding and alighting """ import argparse import collections import math from ortools.sat.python import cp_model PARSER = argparse.ArgumentParser() PARSER.add_argument("--instance", default=1, type=int, help="Instance number (1..3).") PARSER.add_argument( "--output_proto_file", default="", help="Output file to write the cp_model" "proto to.", ) PARSER.add_argument("--params", default="", help="Sat solver parameters.") SAMPLE_SHIFTS_SMALL = [ # # column description: # - shift id # - shift start time as hh:mm string (for logging and readability purposes) # - shift end time as hh:mm string (for logging and readability purposes) # - shift start minute # - shift end minute # - shift duration in minutes # [0, "05:18", "06:00", 318, 360, 42], [1, "05:26", "06:08", 326, 368, 42], [2, "05:40", "05:56", 340, 356, 16], [3, "06:06", "06:51", 366, 411, 45], [4, "06:40", "07:52", 400, 472, 72], [5, "06:42", "07:13", 402, 433, 31], [6, "06:48", "08:15", 408, 495, 87], [7, "06:59", "08:07", 419, 487, 68], [8, "07:20", "07:36", 440, 456, 16], [9, "07:35", "08:22", 455, 502, 47], [10, "07:50", "08:55", 470, 535, 65], [11, "08:00", "09:05", 480, 545, 65], [12, "08:00", "08:35", 480, 515, 35], [13, "08:11", "09:41", 491, 581, 90], [14, "08:28", "08:50", 508, 530, 22], [15, "08:35", "08:45", 515, 525, 10], [16, "08:40", "08:50", 520, 530, 10], [17, "09:03", "10:28", 543, 628, 85], [18, "09:23", "09:49", 563, 589, 26], [19, "09:30", "09:40", 570, 580, 10], [20, "09:57", "10:20", 597, 620, 23], [21, "10:09", "11:03", 609, 663, 54], [22, "10:20", "10:30", 620, 630, 10], [23, "11:00", "11:10", 660, 670, 10], [24, "11:45", "12:24", 705, 744, 39], [25, "12:18", "13:00", 738, 780, 42], [26, "13:18", "14:44", 798, 884, 86], [27, "13:53", "14:49", 833, 889, 56], [28, "14:03", "14:50", 843, 890, 47], [29, "14:28", "15:15", 868, 915, 47], [30, "14:30", "15:41", 870, 941, 71], [31, "14:48", "15:35", 888, 935, 47], [32, "15:03", "15:50", 903, 950, 47], [33, "15:28", "16:54", 928, 1014, 86], [34, "15:38", "16:25", 938, 985, 47], [35, "15:40", "15:56", 940, 956, 16], [36, "15:58", "16:45", 958, 1005, 47], [37, "16:04", "17:30", 964, 1050, 86], [38, "16:28", "17:15", 988, 1035, 47], [39, "16:36", "17:21", 996, 1041, 45], [40, "16:50", "17:00", 1010, 1020, 10], [41, "16:54", "18:20", 1014, 1100, 86], [42, "17:01", "17:13", 1021, 1033, 12], [43, "17:19", "18:31", 1039, 1111, 72], [44, "17:23", "18:10", 1043, 1090, 47], [45, "17:34", "18:15", 1054, 1095, 41], [46, "18:04", "19:29", 1084, 1169, 85], [47, "18:34", "19:58", 1114, 1198, 84], [48, "19:56", "20:34", 1196, 1234, 38], [49, "20:05", "20:48", 1205, 1248, 43], ] # yapf:disable SAMPLE_SHIFTS_MEDIUM = [ [0, "04:30", "04:53", 270, 293, 23], [1, "04:46", "04:56", 286, 296, 10], [2, "04:52", "05:56", 292, 356, 64], [3, "04:53", "05:23", 293, 323, 30], [4, "05:07", "05:44", 307, 344, 37], [5, "05:10", "06:06", 310, 366, 56], [6, "05:18", "06:03", 318, 363, 45], [7, "05:30", "05:40", 330, 340, 10], [8, "05:30", "05:40", 330, 340, 10], [9, "05:33", "06:15", 333, 375, 42], [10, "05:40", "05:50", 340, 350, 10], [11, "05:43", "06:08", 343, 368, 25], [12, "05:54", "07:20", 354, 440, 86], [13, "06:04", "06:37", 364, 397, 33], [14, "06:13", "06:58", 373, 418, 45], [15, "06:14", "07:40", 374, 460, 86], [16, "06:15", "07:15", 375, 435, 60], [17, "06:16", "06:26", 376, 386, 10], [18, "06:17", "06:34", 377, 394, 17], [19, "06:20", "06:36", 380, 396, 16], [20, "06:22", "07:06", 382, 426, 44], [21, "06:24", "07:50", 384, 470, 86], [22, "06:27", "06:44", 387, 404, 17], [23, "06:30", "06:40", 390, 400, 10], [24, "06:31", "06:43", 391, 403, 12], [25, "06:33", "07:53", 393, 473, 80], [26, "06:34", "07:09", 394, 429, 35], [27, "06:40", "06:56", 400, 416, 16], [28, "06:44", "07:17", 404, 437, 33], [29, "06:46", "06:58", 406, 418, 12], [30, "06:49", "07:43", 409, 463, 54], [31, "06:50", "07:05", 410, 425, 15], [32, "06:52", "07:36", 412, 456, 44], [33, "06:54", "07:27", 414, 447, 33], [34, "06:56", "08:23", 416, 503, 87], [35, "07:04", "07:44", 424, 464, 40], [36, "07:11", "08:36", 431, 516, 85], [37, "07:17", "07:35", 437, 455, 18], [38, "07:22", "08:06", 442, 486, 44], [39, "07:27", "08:15", 447, 495, 48], [40, "07:35", "07:45", 455, 465, 10], [41, "07:43", "08:08", 463, 488, 25], [42, "07:50", "08:37", 470, 517, 47], [43, "07:58", "08:45", 478, 525, 47], [44, "08:00", "08:35", 480, 515, 35], [45, "08:06", "08:51", 486, 531, 45], [46, "08:10", "08:45", 490, 525, 35], [47, "08:15", "08:30", 495, 510, 15], [48, "08:16", "09:00", 496, 540, 44], [49, "08:18", "09:16", 498, 556, 58], [50, "08:20", "08:36", 500, 516, 16], [51, "08:27", "09:07", 507, 547, 40], [52, "08:30", "08:45", 510, 525, 15], [53, "08:35", "09:15", 515, 555, 40], [54, "08:46", "09:30", 526, 570, 44], [55, "08:51", "09:17", 531, 557, 26], [56, "08:55", "09:15", 535, 555, 20], [57, "08:58", "09:38", 538, 578, 40], [58, "09:00", "09:35", 540, 575, 35], [59, "09:00", "09:16", 540, 556, 16], [60, "09:20", "09:36", 560, 576, 16], [61, "09:31", "09:43", 571, 583, 12], [62, "09:33", "10:15", 573, 615, 42], [63, "09:54", "10:05", 594, 605, 11], [64, "10:11", "10:38", 611, 638, 27], [65, "10:18", "11:00", 618, 660, 42], [66, "10:21", "10:47", 621, 647, 26], [67, "10:25", "11:04", 625, 664, 39], [68, "10:26", "11:08", 626, 668, 42], [69, "10:44", "12:11", 644, 731, 87], [70, "11:00", "11:16", 660, 676, 16], [71, "11:15", "11:54", 675, 714, 39], [72, "11:16", "11:28", 676, 688, 12], [73, "11:20", "11:30", 680, 690, 10], [74, "11:21", "11:47", 681, 707, 26], [75, "11:25", "12:04", 685, 724, 39], [76, "11:34", "11:45", 694, 705, 11], [77, "11:35", "12:14", 695, 734, 39], [78, "11:41", "12:23", 701, 743, 42], [79, "11:44", "12:35", 704, 755, 51], [80, "11:46", "11:58", 706, 718, 12], [81, "12:00", "12:10", 720, 730, 10], [82, "12:04", "12:15", 724, 735, 11], [83, "12:04", "13:04", 724, 784, 60], [84, "12:11", "12:38", 731, 758, 27], [85, "12:15", "12:54", 735, 774, 39], [86, "12:25", "13:10", 745, 790, 45], [87, "12:30", "12:40", 750, 760, 10], [88, "12:34", "13:58", 754, 838, 84], [89, "12:38", "13:25", 758, 805, 47], [90, "12:48", "13:35", 768, 815, 47], [91, "13:00", "13:16", 780, 796, 16], [92, "13:05", "13:44", 785, 824, 39], [93, "13:08", "13:55", 788, 835, 47], [94, "13:14", "14:38", 794, 878, 84], [95, "13:23", "13:49", 803, 829, 26], [96, "13:25", "14:04", 805, 844, 39], [97, "13:28", "14:54", 808, 894, 86], [98, "13:31", "13:43", 811, 823, 12], [99, "13:34", "14:58", 814, 898, 84], [100, "13:38", "14:25", 818, 865, 47], [101, "13:38", "15:04", 818, 904, 86], [102, "13:39", "14:33", 819, 873, 54], [103, "13:40", "13:50", 820, 830, 10], [104, "13:43", "14:10", 823, 850, 27], [105, "13:48", "14:35", 828, 875, 47], [106, "13:48", "14:35", 828, 875, 47], [107, "13:53", "14:40", 833, 880, 47], [108, "13:58", "15:24", 838, 924, 86], [109, "13:58", "14:25", 838, 865, 27], [110, "14:00", "14:16", 840, 856, 16], [111, "14:13", "15:00", 853, 900, 47], [112, "14:20", "15:31", 860, 931, 71], [113, "14:25", "15:02", 865, 902, 37], [114, "14:34", "14:45", 874, 885, 11], [115, "14:40", "15:51", 880, 951, 71], [116, "14:40", "14:56", 880, 896, 16], [117, "14:46", "14:58", 886, 898, 12], [118, "14:49", "15:43", 889, 943, 54], [119, "14:52", "15:21", 892, 921, 29], [120, "14:58", "16:24", 898, 984, 86], [121, "14:59", "15:53", 899, 953, 54], [122, "15:00", "15:10", 900, 910, 10], [123, "15:00", "15:35", 900, 935, 35], [124, "15:08", "15:45", 908, 945, 37], [125, "15:12", "15:36", 912, 936, 24], [126, "15:18", "16:05", 918, 965, 47], [127, "15:24", "16:05", 924, 965, 41], [128, "15:31", "15:43", 931, 943, 12], [129, "15:35", "15:54", 935, 954, 19], [130, "15:36", "16:21", 936, 981, 45], [131, "15:39", "16:33", 939, 993, 54], [132, "15:48", "16:35", 948, 995, 47], [133, "15:50", "17:01", 950, 1021, 71], [134, "16:03", "16:50", 963, 1010, 47], [135, "16:18", "17:44", 978, 1064, 86], [136, "16:24", "17:05", 984, 1025, 41], [137, "16:28", "17:15", 988, 1035, 47], [138, "16:34", "17:15", 994, 1035, 41], [139, "16:38", "17:25", 998, 1045, 47], [140, "16:40", "16:56", 1000, 1016, 16], [141, "16:45", "17:04", 1005, 1024, 19], [142, "16:52", "17:36", 1012, 1056, 44], [143, "16:58", "17:45", 1018, 1065, 47], [144, "17:04", "18:30", 1024, 1110, 86], [145, "17:04", "17:45", 1024, 1065, 41], [146, "17:09", "18:03", 1029, 1083, 54], [147, "17:18", "18:44", 1038, 1124, 86], [148, "17:28", "18:15", 1048, 1095, 47], [149, "17:29", "18:41", 1049, 1121, 72], [150, "17:36", "18:21", 1056, 1101, 45], [151, "17:38", "18:25", 1058, 1105, 47], [152, "17:40", "17:56", 1060, 1076, 16], [153, "17:45", "18:04", 1065, 1084, 19], [154, "17:46", "17:58", 1066, 1078, 12], [155, "17:48", "18:35", 1068, 1115, 47], [156, "17:49", "18:43", 1069, 1123, 54], [157, "17:55", "18:14", 1075, 1094, 19], [158, "17:58", "18:45", 1078, 1125, 47], [159, "18:00", "19:11", 1080, 1151, 71], [160, "18:04", "18:45", 1084, 1125, 41], [161, "18:09", "19:03", 1089, 1143, 54], [162, "18:13", "19:00", 1093, 1140, 47], [163, "18:13", "18:40", 1093, 1120, 27], [164, "18:19", "19:13", 1099, 1153, 54], [165, "18:28", "19:25", 1108, 1165, 57], [166, "18:48", "19:28", 1128, 1168, 40], [167, "19:03", "19:45", 1143, 1185, 42], [168, "19:20", "19:36", 1160, 1176, 16], [169, "19:21", "19:31", 1161, 1171, 10], [170, "19:25", "20:04", 1165, 1204, 39], [171, "19:26", "20:08", 1166, 1208, 42], [172, "19:30", "19:40", 1170, 1180, 10], [173, "19:44", "20:33", 1184, 1233, 49], [174, "19:48", "21:09", 1188, 1269, 81], [175, "19:53", "21:02", 1193, 1262, 69], [176, "20:04", "20:29", 1204, 1229, 25], [177, "20:17", "21:03", 1217, 1263, 46], [178, "20:20", "20:57", 1220, 1257, 37], [179, "20:29", "21:18", 1229, 1278, 49], [180, "20:35", "21:54", 1235, 1314, 79], [181, "20:40", "20:50", 1240, 1250, 10], [182, "20:47", "21:42", 1247, 1302, 55], [183, "21:00", "21:10", 1260, 1270, 10], [184, "21:07", "21:44", 1267, 1304, 37], [185, "21:14", "22:03", 1274, 1323, 49], [186, "21:39", "21:55", 1299, 1315, 16], [187, "21:40", "22:17", 1300, 1337, 37], [188, "21:40", "21:50", 1300, 1310, 10], [189, "21:48", "22:03", 1308, 1323, 15], [190, "22:17", "23:03", 1337, 1383, 46], [191, "22:43", "23:08", 1363, 1388, 25], [192, "23:35", "01:05", 1415, 1505, 90], [193, "23:46", "00:01", 1426, 1441, 15], [194, "23:47", "00:33", 1427, 1473, 46], [195, "23:52", "00:24", 1432, 1464, 32], [196, "23:58", "00:38", 1438, 1478, 40], [197, "00:02", "00:12", 1442, 1452, 10], [198, "00:07", "00:39", 1447, 1479, 32], [199, "00:25", "01:12", 1465, 1512, 47], ] # yapf:disable SAMPLE_SHIFTS_LARGE = [ [0, "04:18", "05:00", 258, 300, 42], [1, "04:27", "05:08", 267, 308, 41], [2, "04:29", "05:26", 269, 326, 57], [3, "04:29", "04:55", 269, 295, 26], [4, "04:30", "04:53", 270, 293, 23], [5, "04:30", "04:51", 270, 291, 21], [6, "04:31", "04:53", 271, 293, 22], [7, "04:33", "05:15", 273, 315, 42], [8, "04:34", "04:44", 274, 284, 10], [9, "04:34", "05:03", 274, 303, 29], [10, "04:35", "04:50", 275, 290, 15], [11, "04:36", "04:46", 276, 286, 10], [12, "04:37", "05:18", 277, 318, 41], [13, "04:41", "05:13", 281, 313, 32], [14, "04:42", "05:23", 282, 323, 41], [15, "04:43", "04:53", 283, 293, 10], [16, "04:44", "05:45", 284, 345, 61], [17, "04:45", "05:11", 285, 311, 26], [18, "04:46", "05:01", 286, 301, 15], [19, "04:46", "04:56", 286, 296, 10], [20, "04:47", "05:14", 287, 314, 27], [21, "04:48", "05:30", 288, 330, 42], [22, "04:49", "05:41", 289, 341, 52], [23, "04:49", "05:18", 289, 318, 29], [24, "04:50", "05:33", 290, 333, 43], [25, "04:52", "05:56", 292, 356, 64], [26, "04:52", "05:07", 292, 307, 15], [27, "04:53", "05:19", 293, 319, 26], [28, "04:53", "05:23", 293, 323, 30], [29, "04:55", "05:27", 295, 327, 32], [30, "04:57", "05:38", 297, 338, 41], [31, "05:00", "06:00", 300, 360, 60], [32, "05:00", "05:54", 300, 354, 54], [33, "05:01", "05:33", 301, 333, 32], [34, "05:01", "05:26", 301, 326, 25], [35, "05:02", "05:29", 302, 329, 27], [36, "05:02", "05:12", 302, 312, 10], [37, "05:03", "05:45", 303, 345, 42], [38, "05:03", "05:18", 303, 318, 15], [39, "05:03", "06:28", 303, 388, 85], [40, "05:03", "05:13", 303, 313, 10], [41, "05:04", "06:24", 304, 384, 80], [42, "05:07", "05:44", 307, 344, 37], [43, "05:08", "05:48", 308, 348, 40], [44, "05:10", "06:06", 310, 366, 56], [45, "05:11", "05:37", 311, 337, 26], [46, "05:11", "05:53", 311, 353, 42], [47, "05:13", "06:15", 313, 375, 62], [48, "05:13", "05:38", 313, 338, 25], [49, "05:16", "05:44", 316, 344, 28], [50, "05:17", "05:27", 317, 327, 10], [51, "05:18", "06:40", 318, 400, 82], [52, "05:18", "06:03", 318, 363, 45], [53, "05:18", "06:11", 318, 371, 53], [54, "05:18", "06:00", 318, 360, 42], [55, "05:19", "06:34", 319, 394, 75], [56, "05:20", "06:17", 320, 377, 57], [57, "05:22", "05:59", 322, 359, 37], [58, "05:24", "05:48", 324, 348, 24], [59, "05:25", "05:40", 325, 340, 15], [60, "05:26", "06:08", 326, 368, 42], [61, "05:27", "06:30", 327, 390, 63], [62, "05:27", "05:54", 327, 354, 27], [63, "05:28", "05:53", 328, 353, 25], [64, "05:29", "05:44", 329, 344, 15], [65, "05:30", "05:40", 330, 340, 10], [66, "05:30", "05:40", 330, 340, 10], [67, "05:30", "05:40", 330, 340, 10], [68, "05:32", "06:53", 332, 413, 81], [69, "05:33", "07:00", 333, 420, 87], [70, "05:33", "06:15", 333, 375, 42], [71, "05:33", "05:47", 333, 347, 14], [72, "05:37", "06:13", 337, 373, 36], [73, "05:37", "06:05", 337, 365, 28], [74, "05:38", "06:33", 338, 393, 55], [75, "05:38", "06:04", 338, 364, 26], [76, "05:38", "06:18", 338, 378, 40], [77, "05:39", "05:54", 339, 354, 15], [78, "05:40", "05:56", 340, 356, 16], [79, "05:40", "06:41", 340, 401, 61], [80, "05:40", "05:50", 340, 350, 10], [81, "05:41", "06:23", 341, 383, 42], [82, "05:41", "06:01", 341, 361, 20], [83, "05:43", "06:08", 343, 368, 25], [84, "05:44", "07:10", 344, 430, 86], [85, "05:44", "05:55", 344, 355, 11], [86, "05:45", "06:44", 345, 404, 59], [87, "05:47", "06:17", 347, 377, 30], [88, "05:48", "07:08", 348, 428, 80], [89, "05:48", "06:30", 348, 390, 42], [90, "05:50", "06:50", 350, 410, 60], [91, "05:50", "06:00", 350, 360, 10], [92, "05:50", "06:00", 350, 360, 10], [93, "05:50", "06:51", 350, 411, 61], [94, "05:52", "06:33", 352, 393, 41], [95, "05:52", "06:36", 352, 396, 44], [96, "05:52", "06:23", 352, 383, 31], [97, "05:54", "06:14", 354, 374, 20], [98, "05:54", "07:20", 354, 440, 86], [99, "05:55", "06:40", 355, 400, 45], [100, "05:55", "06:27", 355, 387, 32], [101, "05:56", "06:35", 356, 395, 39], [102, "05:56", "06:06", 356, 366, 10], [103, "05:57", "06:21", 357, 381, 24], [104, "05:58", "07:23", 358, 443, 85], [105, "05:58", "06:23", 358, 383, 25], [106, "05:58", "06:08", 358, 368, 10], [107, "05:58", "06:43", 358, 403, 45], [108, "06:00", "06:10", 360, 370, 10], [109, "06:00", "06:16", 360, 376, 16], [110, "06:00", "07:01", 360, 421, 61], [111, "06:01", "07:00", 361, 420, 59], [112, "06:01", "06:13", 361, 373, 12], [113, "06:01", "06:45", 361, 405, 44], [114, "06:03", "06:50", 363, 410, 47], [115, "06:04", "06:37", 364, 397, 33], [116, "06:04", "07:30", 364, 450, 86], [117, "06:05", "06:24", 365, 384, 19], [118, "06:06", "06:51", 366, 411, 45], [119, "06:07", "06:43", 367, 403, 36], [120, "06:08", "07:30", 368, 450, 82], [121, "06:10", "06:20", 370, 380, 10], [122, "06:10", "07:17", 370, 437, 67], [123, "06:11", "06:54", 371, 414, 43], [124, "06:11", "06:21", 371, 381, 10], [125, "06:13", "06:38", 373, 398, 25], [126, "06:13", "06:58", 373, 418, 45], [127, "06:13", "06:53", 373, 413, 40], [128, "06:14", "07:03", 374, 423, 49], [129, "06:14", "06:47", 374, 407, 33], [130, "06:14", "07:40", 374, 460, 86], [131, "06:15", "07:15", 375, 435, 60], [132, "06:16", "06:28", 376, 388, 12], [133, "06:16", "06:26", 376, 386, 10], [134, "06:17", "06:34", 377, 394, 17], [135, "06:18", "07:06", 378, 426, 48], [136, "06:18", "07:38", 378, 458, 80], [137, "06:18", "07:02", 378, 422, 44], [138, "06:19", "06:53", 379, 413, 34], [139, "06:20", "07:25", 380, 445, 65], [140, "06:20", "06:36", 380, 396, 16], [141, "06:20", "06:30", 380, 390, 10], [142, "06:20", "06:30", 380, 390, 10], [143, "06:21", "06:49", 381, 409, 28], [144, "06:22", "07:06", 382, 426, 44], [145, "06:24", "07:50", 384, 470, 86], [146, "06:24", "06:57", 384, 417, 33], [147, "06:26", "07:45", 386, 465, 79], [148, "06:26", "07:10", 386, 430, 44], [149, "06:27", "06:44", 387, 404, 17], [150, "06:28", "06:53", 388, 413, 25], [151, "06:28", "07:14", 388, 434, 46], [152, "06:29", "07:03", 389, 423, 34], [153, "06:30", "06:40", 390, 400, 10], [154, "06:30", "07:37", 390, 457, 67], [155, "06:31", "06:43", 391, 403, 12], [156, "06:33", "07:14", 393, 434, 41], [157, "06:33", "07:53", 393, 473, 80], [158, "06:34", "08:16", 394, 496, 102], [159, "06:34", "07:09", 394, 429, 35], [160, "06:34", "07:07", 394, 427, 33], [161, "06:36", "07:21", 396, 441, 45], [162, "06:37", "07:22", 397, 442, 45], [163, "06:37", "06:54", 397, 414, 17], [164, "06:38", "07:30", 398, 450, 52], [165, "06:38", "07:18", 398, 438, 40], [166, "06:39", "07:33", 399, 453, 54], [167, "06:40", "07:52", 400, 472, 72], [168, "06:40", "06:50", 400, 410, 10], [169, "06:40", "07:22", 400, 442, 42], [170, "06:40", "06:56", 400, 416, 16], [171, "06:41", "08:00", 401, 480, 79], [172, "06:42", "07:26", 402, 446, 44], [173, "06:42", "07:13", 402, 433, 31], [174, "06:43", "07:08", 403, 428, 25], [175, "06:43", "07:30", 403, 450, 47], [176, "06:43", "07:23", 403, 443, 40], [177, "06:44", "07:17", 404, 437, 33], [178, "06:44", "08:13", 404, 493, 89], [179, "06:46", "07:01", 406, 421, 15], [180, "06:46", "06:58", 406, 418, 12], [181, "06:47", "07:04", 407, 424, 17], [182, "06:48", "08:15", 408, 495, 87], [183, "06:48", "07:34", 408, 454, 46], [184, "06:48", "07:37", 408, 457, 49], [185, "06:49", "07:43", 409, 463, 54], [186, "06:50", "08:00", 410, 480, 70], [187, "06:50", "07:00", 410, 420, 10], [188, "06:50", "07:05", 410, 425, 15], [189, "06:51", "07:18", 411, 438, 27], [190, "06:52", "07:36", 412, 456, 44], [191, "06:53", "07:37", 413, 457, 44], [192, "06:54", "08:20", 414, 500, 86], [193, "06:54", "07:27", 414, 447, 33], [194, "06:54", "07:20", 414, 440, 26], [195, "06:56", "08:23", 416, 503, 87], [196, "06:57", "07:12", 417, 432, 15], [197, "06:57", "07:58", 417, 478, 61], [198, "06:57", "07:45", 417, 465, 48], [199, "06:57", "07:40", 417, 460, 43], [200, "06:58", "07:23", 418, 443, 25], [201, "06:59", "07:53", 419, 473, 54], [202, "06:59", "08:07", 419, 487, 68], [203, "07:00", "07:10", 420, 430, 10], [204, "07:00", "07:16", 420, 436, 16], [205, "07:01", "08:30", 421, 510, 89], [206, "07:01", "07:13", 421, 433, 12], [207, "07:01", "07:43", 421, 463, 42], [208, "07:03", "08:30", 423, 510, 87], [209, "07:04", "07:37", 424, 457, 33], [210, "07:04", "07:44", 424, 464, 40], [211, "07:05", "07:52", 425, 472, 47], [212, "07:05", "08:05", 425, 485, 60], [213, "07:05", "07:46", 425, 466, 41], [214, "07:06", "07:51", 426, 471, 45], [215, "07:07", "08:08", 427, 488, 61], [216, "07:07", "07:52", 427, 472, 45], [217, "07:07", "08:16", 427, 496, 69], [218, "07:07", "07:27", 427, 447, 20], [219, "07:09", "07:50", 429, 470, 41], [220, "07:09", "08:40", 429, 520, 91], [221, "07:09", "08:03", 429, 483, 54], [222, "07:10", "07:20", 430, 440, 10], [223, "07:11", "08:36", 431, 516, 85], [224, "07:12", "08:00", 432, 480, 48], [225, "07:12", "07:47", 432, 467, 35], [226, "07:13", "07:54", 433, 474, 41], [227, "07:13", "07:38", 433, 458, 25], [228, "07:14", "07:59", 434, 479, 45], [229, "07:16", "08:50", 436, 530, 94], [230, "07:16", "07:28", 436, 448, 12], [231, "07:17", "07:35", 437, 455, 18], [232, "07:17", "07:58", 437, 478, 41], [233, "07:18", "08:06", 438, 486, 48], [234, "07:18", "08:44", 438, 524, 86], [235, "07:19", "08:13", 439, 493, 54], [236, "07:20", "08:02", 440, 482, 42], [237, "07:20", "08:07", 440, 487, 47], [238, "07:20", "07:30", 440, 450, 10], [239, "07:20", "07:57", 440, 477, 37], [240, "07:20", "07:36", 440, 456, 16], [241, "07:21", "07:48", 441, 468, 27], [242, "07:22", "08:06", 442, 486, 44], [243, "07:22", "08:25", 442, 505, 63], [244, "07:24", "08:27", 444, 507, 63], [245, "07:24", "08:05", 444, 485, 41], [246, "07:26", "08:23", 446, 503, 57], [247, "07:26", "08:52", 446, 532, 86], [248, "07:27", "08:07", 447, 487, 40], [249, "07:27", "07:42", 447, 462, 15], [250, "07:27", "08:15", 447, 495, 48], [251, "07:28", "07:53", 448, 473, 25], [252, "07:28", "08:09", 448, 489, 41], [253, "07:28", "07:38", 448, 458, 10], [254, "07:30", "08:35", 450, 515, 65], [255, "07:31", "07:43", 451, 463, 12], [256, "07:32", "08:13", 452, 493, 41], [257, "07:34", "09:00", 454, 540, 86], [258, "07:34", "08:33", 454, 513, 59], [259, "07:34", "09:04", 454, 544, 90], [260, "07:35", "08:22", 455, 502, 47], [261, "07:35", "07:45", 455, 465, 10], [262, "07:35", "08:16", 455, 496, 41], [263, "07:36", "08:17", 456, 497, 41], [264, "07:36", "08:36", 456, 516, 60], [265, "07:37", "07:50", 457, 470, 13], [266, "07:40", "07:56", 460, 476, 16], [267, "07:40", "08:20", 460, 500, 40], [268, "07:40", "08:45", 460, 525, 65], [269, "07:41", "08:39", 461, 519, 58], [270, "07:41", "07:51", 461, 471, 10], [271, "07:42", "08:30", 462, 510, 48], [272, "07:42", "08:21", 462, 501, 39], [273, "07:43", "08:08", 463, 488, 25], [274, "07:43", "08:24", 463, 504, 41], [275, "07:44", "09:10", 464, 550, 86], [276, "07:44", "08:43", 464, 523, 59], [277, "07:46", "08:28", 466, 508, 42], [278, "07:46", "07:58", 466, 478, 12], [279, "07:47", "08:00", 467, 480, 13], [280, "07:48", "09:14", 468, 554, 86], [281, "07:49", "08:32", 469, 512, 43], [282, "07:50", "08:55", 470, 535, 65], [283, "07:50", "08:00", 470, 480, 10], [284, "07:50", "08:37", 470, 517, 47], [285, "07:50", "08:26", 470, 506, 36], [286, "07:51", "08:18", 471, 498, 27], [287, "07:52", "08:21", 472, 501, 29], [288, "07:53", "08:35", 473, 515, 42], [289, "07:54", "09:19", 474, 559, 85], [290, "07:55", "08:53", 475, 533, 58], [291, "07:56", "08:54", 476, 534, 58], [292, "07:57", "08:39", 477, 519, 42], [293, "07:57", "08:10", 477, 490, 13], [294, "07:58", "08:45", 478, 525, 47], [295, "07:58", "08:23", 478, 503, 25], [296, "08:00", "08:10", 480, 490, 10], [297, "08:00", "09:05", 480, 545, 65], [298, "08:00", "08:16", 480, 496, 16], [299, "08:00", "08:35", 480, 515, 35], [300, "08:01", "08:13", 481, 493, 12], [301, "08:01", "08:43", 481, 523, 42], [302, "08:03", "09:26", 483, 566, 83], [303, "08:04", "09:29", 484, 569, 85], [304, "08:05", "08:21", 485, 501, 16], [305, "08:05", "08:47", 485, 527, 42], [306, "08:06", "08:51", 486, 531, 45], [307, "08:06", "09:03", 486, 543, 57], [308, "08:07", "08:20", 487, 500, 13], [309, "08:08", "08:55", 488, 535, 47], [310, "08:08", "08:50", 488, 530, 42], [311, "08:10", "08:45", 490, 525, 35], [312, "08:10", "09:15", 490, 555, 65], [313, "08:10", "08:20", 490, 500, 10], [314, "08:11", "09:41", 491, 581, 90], [315, "08:12", "08:55", 492, 535, 43], [316, "08:13", "08:38", 493, 518, 25], [317, "08:14", "09:38", 494, 578, 84], [318, "08:15", "08:30", 495, 510, 15], [319, "08:16", "08:30", 496, 510, 14], [320, "08:16", "08:28", 496, 508, 12], [321, "08:16", "09:00", 496, 540, 44], [322, "08:17", "09:13", 497, 553, 56], [323, "08:18", "09:16", 498, 556, 58], [324, "08:18", "09:05", 498, 545, 47], [325, "08:20", "08:36", 500, 516, 16], [326, "08:20", "08:55", 500, 535, 35], [327, "08:20", "09:05", 500, 545, 45], [328, "08:20", "08:30", 500, 510, 10], [329, "08:20", "09:25", 500, 565, 65], [330, "08:21", "08:38", 501, 518, 17], [331, "08:21", "08:47", 501, 527, 26], [332, "08:22", "08:45", 502, 525, 23], [333, "08:23", "09:10", 503, 550, 47], [334, "08:24", "09:48", 504, 588, 84], [335, "08:26", "08:46", 506, 526, 20], [336, "08:27", "09:07", 507, 547, 40], [337, "08:28", "08:50", 508, 530, 22], [338, "08:28", "09:56", 508, 596, 88], [339, "08:28", "09:23", 508, 563, 55], [340, "08:29", "09:20", 509, 560, 51], [341, "08:30", "09:05", 510, 545, 35], [342, "08:30", "08:45", 510, 525, 15], [343, "08:30", "08:40", 510, 520, 10], [344, "08:30", "09:35", 510, 575, 65], [345, "08:31", "08:43", 511, 523, 12], [346, "08:31", "09:13", 511, 553, 42], [347, "08:34", "09:58", 514, 598, 84], [348, "08:35", "08:55", 515, 535, 20], [349, "08:35", "09:15", 515, 555, 40], [350, "08:35", "08:45", 515, 525, 10], [351, "08:36", "08:46", 516, 526, 10], [352, "08:36", "09:00", 516, 540, 24], [353, "08:38", "09:20", 518, 560, 42], [354, "08:38", "09:35", 518, 575, 57], [355, "08:38", "09:14", 518, 554, 36], [356, "08:39", "09:33", 519, 573, 54], [357, "08:40", "09:45", 520, 585, 65], [358, "08:40", "08:50", 520, 530, 10], [359, "08:40", "08:56", 520, 536, 16], [360, "08:42", "09:25", 522, 565, 43], [361, "08:43", "09:08", 523, 548, 25], [362, "08:44", "09:35", 524, 575, 51], [363, "08:45", "09:00", 525, 540, 15], [364, "08:45", "09:05", 525, 545, 20], [365, "08:46", "09:24", 526, 564, 38], [366, "08:46", "08:58", 526, 538, 12], [367, "08:46", "09:30", 526, 570, 44], [368, "08:48", "10:11", 528, 611, 83], [369, "08:48", "10:13", 528, 613, 85], [370, "08:49", "09:43", 529, 583, 54], [371, "08:50", "09:30", 530, 570, 40], [372, "08:50", "10:00", 530, 600, 70], [373, "08:50", "09:00", 530, 540, 10], [374, "08:51", "09:17", 531, 557, 26], [375, "08:53", "09:20", 533, 560, 27], [376, "08:53", "09:35", 533, 575, 42], [377, "08:55", "09:34", 535, 574, 39], [378, "08:55", "09:15", 535, 555, 20], [379, "08:58", "09:38", 538, 578, 40], [380, "08:58", "10:26", 538, 626, 88], [381, "08:59", "09:53", 539, 593, 54], [382, "08:59", "09:50", 539, 590, 51], [383, "09:00", "09:35", 540, 575, 35], [384, "09:00", "09:16", 540, 556, 16], [385, "09:00", "09:10", 540, 550, 10], [386, "09:00", "09:16", 540, 556, 16], [387, "09:01", "09:13", 541, 553, 12], [388, "09:03", "09:45", 543, 585, 42], [389, "09:03", "10:28", 543, 628, 85], [390, "09:05", "09:44", 545, 584, 39], [391, "09:05", "09:25", 545, 565, 20], [392, "09:08", "09:53", 548, 593, 45], [393, "09:08", "10:04", 548, 604, 56], [394, "09:09", "10:03", 549, 603, 54], [395, "09:10", "10:15", 550, 615, 65], [396, "09:10", "09:20", 550, 560, 10], [397, "09:11", "09:38", 551, 578, 27], [398, "09:13", "10:00", 553, 600, 47], [399, "09:14", "09:39", 554, 579, 25], [400, "09:14", "10:05", 554, 605, 51], [401, "09:15", "09:54", 555, 594, 39], [402, "09:16", "09:28", 556, 568, 12], [403, "09:18", "10:43", 558, 643, 85], [404, "09:18", "10:41", 558, 641, 83], [405, "09:18", "09:58", 558, 598, 40], [406, "09:19", "10:13", 559, 613, 54], [407, "09:20", "09:30", 560, 570, 10], [408, "09:20", "09:36", 560, 576, 16], [409, "09:21", "09:47", 561, 587, 26], [410, "09:23", "10:30", 563, 630, 67], [411, "09:23", "10:05", 563, 605, 42], [412, "09:23", "09:49", 563, 589, 26], [413, "09:24", "09:35", 564, 575, 11], [414, "09:25", "09:35", 565, 575, 10], [415, "09:25", "10:04", 565, 604, 39], [416, "09:28", "10:08", 568, 608, 40], [417, "09:29", "09:45", 569, 585, 16], [418, "09:29", "10:20", 569, 620, 51], [419, "09:29", "10:56", 569, 656, 87], [420, "09:29", "10:23", 569, 623, 54], [421, "09:30", "09:40", 570, 580, 10], [422, "09:31", "09:43", 571, 583, 12], [423, "09:33", "10:58", 573, 658, 85], [424, "09:33", "10:15", 573, 615, 42], [425, "09:34", "09:45", 574, 585, 11], [426, "09:35", "10:14", 575, 614, 39], [427, "09:38", "10:45", 578, 645, 67], [428, "09:39", "10:33", 579, 633, 54], [429, "09:40", "09:56", 580, 596, 16], [430, "09:40", "09:50", 580, 590, 10], [431, "09:41", "10:08", 581, 608, 27], [432, "09:41", "10:23", 581, 623, 42], [433, "09:44", "10:35", 584, 635, 51], [434, "09:44", "11:11", 584, 671, 87], [435, "09:44", "09:55", 584, 595, 11], [436, "09:45", "10:24", 585, 624, 39], [437, "09:46", "09:58", 586, 598, 12], [438, "09:48", "10:30", 588, 630, 42], [439, "09:48", "11:13", 588, 673, 85], [440, "09:48", "10:04", 588, 604, 16], [441, "09:49", "10:43", 589, 643, 54], [442, "09:50", "10:00", 590, 600, 10], [443, "09:51", "10:17", 591, 617, 26], [444, "09:53", "10:49", 593, 649, 56], [445, "09:53", "11:00", 593, 660, 67], [446, "09:54", "10:05", 594, 605, 11], [447, "09:55", "10:34", 595, 634, 39], [448, "09:56", "10:38", 596, 638, 42], [449, "09:57", "10:20", 597, 620, 23], [450, "09:59", "11:26", 599, 686, 87], [451, "09:59", "10:50", 599, 650, 51], [452, "09:59", "10:53", 599, 653, 54], [453, "10:00", "10:16", 600, 616, 16], [454, "10:00", "10:10", 600, 610, 10], [455, "10:01", "10:13", 601, 613, 12], [456, "10:03", "11:28", 603, 688, 85], [457, "10:03", "10:45", 603, 645, 42], [458, "10:04", "10:15", 604, 615, 11], [459, "10:05", "10:44", 605, 644, 39], [460, "10:08", "11:15", 608, 675, 67], [461, "10:09", "11:03", 609, 663, 54], [462, "10:10", "10:20", 610, 620, 10], [463, "10:11", "10:38", 611, 638, 27], [464, "10:11", "10:53", 611, 653, 42], [465, "10:14", "11:05", 614, 665, 51], [466, "10:14", "11:41", 614, 701, 87], [467, "10:14", "10:25", 614, 625, 11], [468, "10:15", "10:54", 615, 654, 39], [469, "10:16", "10:28", 616, 628, 12], [470, "10:18", "11:43", 618, 703, 85], [471, "10:18", "11:00", 618, 660, 42], [472, "10:19", "11:13", 619, 673, 54], [473, "10:20", "10:30", 620, 630, 10], [474, "10:20", "10:36", 620, 636, 16], [475, "10:21", "10:47", 621, 647, 26], [476, "10:23", "11:30", 623, 690, 67], [477, "10:23", "10:45", 623, 645, 22], [478, "10:24", "10:35", 624, 635, 11], [479, "10:25", "11:04", 625, 664, 39], [480, "10:26", "11:08", 626, 668, 42], [481, "10:29", "11:20", 629, 680, 51], [482, "10:29", "11:23", 629, 683, 54], [483, "10:29", "11:56", 629, 716, 87], [484, "10:30", "10:40", 630, 640, 10], [485, "10:31", "10:43", 631, 643, 12], [486, "10:33", "11:15", 633, 675, 42], [487, "10:33", "11:58", 633, 718, 85], [488, "10:34", "10:45", 634, 645, 11], [489, "10:35", "11:14", 635, 674, 39], [490, "10:38", "11:45", 638, 705, 67], [491, "10:39", "11:33", 639, 693, 54], [492, "10:40", "10:50", 640, 650, 10], [493, "10:40", "10:56", 640, 656, 16], [494, "10:41", "11:23", 641, 683, 42], [495, "10:41", "11:08", 641, 668, 27], [496, "10:44", "12:11", 644, 731, 87], [497, "10:44", "11:35", 644, 695, 51], [498, "10:44", "10:55", 644, 655, 11], [499, "10:45", "11:24", 645, 684, 39], [500, "10:46", "10:58", 646, 658, 12], [501, "10:48", "12:13", 648, 733, 85], [502, "10:48", "11:30", 648, 690, 42], [503, "10:49", "11:43", 649, 703, 54], [504, "10:50", "11:00", 650, 660, 10], [505, "10:51", "11:17", 651, 677, 26], [506, "10:53", "12:00", 653, 720, 67], [507, "10:53", "11:20", 653, 680, 27], [508, "10:54", "11:05", 654, 665, 11], [509, "10:55", "11:34", 655, 694, 39], [510, "10:56", "11:38", 656, 698, 42], [511, "10:59", "11:14", 659, 674, 15], [512, "10:59", "12:26", 659, 746, 87], [513, "10:59", "11:53", 659, 713, 54], [514, "10:59", "11:50", 659, 710, 51], [515, "11:00", "11:16", 660, 676, 16], [516, "11:00", "11:10", 660, 670, 10], [517, "11:01", "11:13", 661, 673, 12], [518, "11:03", "11:45", 663, 705, 42], [519, "11:03", "12:28", 663, 748, 85], [520, "11:04", "11:15", 664, 675, 11], [521, "11:05", "11:44", 665, 704, 39], [522, "11:08", "12:15", 668, 735, 67], [523, "11:09", "12:03", 669, 723, 54], [524, "11:10", "11:20", 670, 680, 10], [525, "11:11", "11:38", 671, 698, 27], [526, "11:11", "11:53", 671, 713, 42], [527, "11:14", "11:25", 674, 685, 11], [528, "11:14", "12:05", 674, 725, 51], [529, "11:14", "12:38", 674, 758, 84], [530, "11:14", "12:41", 674, 761, 87], [531, "11:15", "11:54", 675, 714, 39], [532, "11:16", "11:28", 676, 688, 12], [533, "11:18", "12:00", 678, 720, 42], [534, "11:19", "12:13", 679, 733, 54], [535, "11:20", "11:30", 680, 690, 10], [536, "11:20", "11:36", 680, 696, 16], [537, "11:21", "11:47", 681, 707, 26], [538, "11:23", "12:30", 683, 750, 67], [539, "11:23", "11:49", 683, 709, 26], [540, "11:24", "12:48", 684, 768, 84], [541, "11:24", "11:35", 684, 695, 11], [542, "11:25", "12:04", 685, 724, 39], [543, "11:26", "12:08", 686, 728, 42], [544, "11:29", "11:44", 689, 704, 15], [545, "11:29", "12:23", 689, 743, 54], [546, "11:29", "12:20", 689, 740, 51], [547, "11:29", "12:54", 689, 774, 85], [548, "11:30", "11:40", 690, 700, 10], [549, "11:31", "11:43", 691, 703, 12], [550, "11:33", "12:15", 693, 735, 42], [551, "11:34", "12:58", 694, 778, 84], [552, "11:34", "11:45", 694, 705, 11], [553, "11:35", "12:14", 695, 734, 39], [554, "11:38", "12:45", 698, 765, 67], [555, "11:39", "12:33", 699, 753, 54], [556, "11:40", "11:56", 700, 716, 16], [557, "11:40", "11:50", 700, 710, 10], [558, "11:41", "12:08", 701, 728, 27], [559, "11:41", "12:23", 701, 743, 42], [560, "11:44", "11:55", 704, 715, 11], [561, "11:44", "13:14", 704, 794, 90], [562, "11:44", "13:08", 704, 788, 84], [563, "11:44", "12:35", 704, 755, 51], [564, "11:45", "12:24", 705, 744, 39], [565, "11:46", "11:58", 706, 718, 12], [566, "11:48", "12:30", 708, 750, 42], [567, "11:49", "12:43", 709, 763, 54], [568, "11:50", "12:00", 710, 720, 10], [569, "11:51", "12:17", 711, 737, 26], [570, "11:53", "12:49", 713, 769, 56], [571, "11:53", "13:00", 713, 780, 67], [572, "11:54", "13:18", 714, 798, 84], [573, "11:54", "12:05", 714, 725, 11], [574, "11:55", "12:40", 715, 760, 45], [575, "11:55", "12:34", 715, 754, 39], [576, "11:56", "12:35", 716, 755, 39], [577, "11:57", "12:20", 717, 740, 23], [578, "11:58", "12:29", 718, 749, 31], [579, "11:59", "12:50", 719, 770, 51], [580, "11:59", "12:53", 719, 773, 54], [581, "11:59", "13:24", 719, 804, 85], [582, "11:59", "12:14", 719, 734, 15], [583, "12:00", "12:16", 720, 736, 16], [584, "12:00", "12:10", 720, 730, 10], [585, "12:01", "12:45", 721, 765, 44], [586, "12:01", "12:13", 721, 733, 12], [587, "12:03", "12:50", 723, 770, 47], [588, "12:04", "12:15", 724, 735, 11], [589, "12:04", "13:04", 724, 784, 60], [590, "12:04", "13:28", 724, 808, 84], [591, "12:05", "12:44", 725, 764, 39], [592, "12:08", "13:11", 728, 791, 63], [593, "12:08", "12:39", 728, 759, 31], [594, "12:09", "13:03", 729, 783, 54], [595, "12:10", "12:20", 730, 740, 10], [596, "12:11", "12:55", 731, 775, 44], [597, "12:11", "12:38", 731, 758, 27], [598, "12:14", "13:05", 734, 785, 51], [599, "12:14", "12:25", 734, 745, 11], [600, "12:14", "13:44", 734, 824, 90], [601, "12:14", "13:38", 734, 818, 84], [602, "12:15", "12:54", 735, 774, 39], [603, "12:16", "12:28", 736, 748, 12], [604, "12:18", "13:00", 738, 780, 42], [605, "12:19", "13:13", 739, 793, 54], [606, "12:20", "12:30", 740, 750, 10], [607, "12:20", "13:31", 740, 811, 71], [608, "12:20", "12:30", 740, 750, 10], [609, "12:20", "12:36", 740, 756, 16], [610, "12:21", "12:47", 741, 767, 26], [611, "12:23", "12:45", 743, 765, 22], [612, "12:24", "12:35", 744, 755, 11], [613, "12:24", "13:48", 744, 828, 84], [614, "12:25", "13:10", 745, 790, 45], [615, "12:25", "13:04", 745, 784, 39], [616, "12:26", "13:05", 746, 785, 39], [617, "12:28", "13:54", 748, 834, 86], [618, "12:28", "12:38", 748, 758, 10], [619, "12:28", "13:15", 748, 795, 47], [620, "12:29", "13:23", 749, 803, 54], [621, "12:30", "13:41", 750, 821, 71], [622, "12:30", "12:40", 750, 760, 10], [623, "12:31", "13:15", 751, 795, 44], [624, "12:31", "12:43", 751, 763, 12], [625, "12:33", "12:48", 753, 768, 15], [626, "12:33", "13:20", 753, 800, 47], [627, "12:34", "13:58", 754, 838, 84], [628, "12:34", "13:34", 754, 814, 60], [629, "12:34", "12:45", 754, 765, 11], [630, "12:35", "13:14", 755, 794, 39], [631, "12:38", "13:25", 758, 805, 47], [632, "12:38", "13:25", 758, 805, 47], [633, "12:38", "14:04", 758, 844, 86], [634, "12:39", "13:33", 759, 813, 54], [635, "12:40", "13:51", 760, 831, 71], [636, "12:40", "12:50", 760, 770, 10], [637, "12:40", "12:56", 760, 776, 16], [638, "12:41", "13:08", 761, 788, 27], [639, "12:43", "13:30", 763, 810, 47], [640, "12:44", "12:55", 764, 775, 11], [641, "12:44", "14:08", 764, 848, 84], [642, "12:45", "13:24", 765, 804, 39], [643, "12:46", "12:58", 766, 778, 12], [644, "12:46", "13:21", 766, 801, 35], [645, "12:48", "14:14", 768, 854, 86], [646, "12:48", "13:35", 768, 815, 47], [647, "12:48", "12:58", 768, 778, 10], [648, "12:48", "13:35", 768, 815, 47], [649, "12:49", "13:43", 769, 823, 54], [650, "12:50", "14:01", 770, 841, 71], [651, "12:50", "13:00", 770, 780, 10], [652, "12:50", "13:00", 770, 780, 10], [653, "12:51", "13:17", 771, 797, 26], [654, "12:53", "13:20", 773, 800, 27], [655, "12:53", "13:24", 773, 804, 31], [656, "12:53", "13:40", 773, 820, 47], [657, "12:54", "14:18", 774, 858, 84], [658, "12:54", "13:05", 774, 785, 11], [659, "12:55", "13:34", 775, 814, 39], [660, "12:58", "14:24", 778, 864, 86], [661, "12:58", "13:25", 778, 805, 27], [662, "12:58", "13:45", 778, 825, 47], [663, "12:58", "13:45", 778, 825, 47], [664, "12:59", "13:53", 779, 833, 54], [665, "13:00", "13:10", 780, 790, 10], [666, "13:00", "13:16", 780, 796, 16], [667, "13:00", "14:11", 780, 851, 71], [668, "13:01", "13:13", 781, 793, 12], [669, "13:03", "13:34", 783, 814, 31], [670, "13:03", "13:50", 783, 830, 47], [671, "13:04", "13:15", 784, 795, 11], [672, "13:04", "14:28", 784, 868, 84], [673, "13:05", "13:44", 785, 824, 39], [674, "13:08", "13:55", 788, 835, 47], [675, "13:08", "14:34", 788, 874, 86], [676, "13:08", "13:55", 788, 835, 47], [677, "13:09", "14:03", 789, 843, 54], [678, "13:10", "13:20", 790, 800, 10], [679, "13:10", "14:21", 790, 861, 71], [680, "13:13", "14:00", 793, 840, 47], [681, "13:13", "13:40", 793, 820, 27], [682, "13:14", "14:38", 794, 878, 84], [683, "13:14", "13:25", 794, 805, 11], [684, "13:15", "13:54", 795, 834, 39], [685, "13:16", "13:28", 796, 808, 12], [686, "13:18", "14:05", 798, 845, 47], [687, "13:18", "14:44", 798, 884, 86], [688, "13:18", "14:05", 798, 845, 47], [689, "13:19", "14:13", 799, 853, 54], [690, "13:20", "13:36", 800, 816, 16], [691, "13:20", "14:31", 800, 871, 71], [692, "13:20", "13:30", 800, 810, 10], [693, "13:21", "13:47", 801, 827, 26], [694, "13:23", "14:10", 803, 850, 47], [695, "13:23", "13:49", 803, 829, 26], [696, "13:24", "14:48", 804, 888, 84], [697, "13:24", "13:35", 804, 815, 11], [698, "13:25", "14:04", 805, 844, 39], [699, "13:28", "14:15", 808, 855, 47], [700, "13:28", "14:54", 808, 894, 86], [701, "13:28", "13:55", 808, 835, 27], [702, "13:28", "14:15", 808, 855, 47], [703, "13:29", "14:23", 809, 863, 54], [704, "13:30", "13:40", 810, 820, 10], [705, "13:30", "14:41", 810, 881, 71], [706, "13:31", "13:43", 811, 823, 12], [707, "13:33", "14:20", 813, 860, 47], [708, "13:34", "14:58", 814, 898, 84], [709, "13:34", "13:45", 814, 825, 11], [710, "13:35", "14:14", 815, 854, 39], [711, "13:38", "14:25", 818, 865, 47], [712, "13:38", "14:25", 818, 865, 47], [713, "13:38", "15:04", 818, 904, 86], [714, "13:39", "14:33", 819, 873, 54], [715, "13:40", "13:50", 820, 830, 10], [716, "13:40", "13:56", 820, 836, 16], [717, "13:40", "14:51", 820, 891, 71], [718, "13:43", "14:30", 823, 870, 47], [719, "13:43", "14:10", 823, 850, 27], [720, "13:44", "15:09", 824, 909, 85], [721, "13:44", "13:55", 824, 835, 11], [722, "13:45", "14:24", 825, 864, 39], [723, "13:46", "13:58", 826, 838, 12], [724, "13:48", "14:35", 828, 875, 47], [725, "13:48", "15:14", 828, 914, 86], [726, "13:48", "14:35", 828, 875, 47], [727, "13:49", "14:43", 829, 883, 54], [728, "13:50", "14:00", 830, 840, 10], [729, "13:50", "15:01", 830, 901, 71], [730, "13:51", "14:17", 831, 857, 26], [731, "13:53", "14:40", 833, 880, 47], [732, "13:53", "14:49", 833, 889, 56], [733, "13:54", "14:05", 834, 845, 11], [734, "13:54", "15:19", 834, 919, 85], [735, "13:55", "14:34", 835, 874, 39], [736, "13:57", "14:20", 837, 860, 23], [737, "13:58", "15:24", 838, 924, 86], [738, "13:58", "14:45", 838, 885, 47], [739, "13:58", "14:45", 838, 885, 47], [740, "13:58", "14:25", 838, 865, 27], [741, "13:59", "14:53", 839, 893, 54], [742, "14:00", "14:16", 840, 856, 16], [743, "14:00", "14:10", 840, 850, 10], [744, "14:00", "15:11", 840, 911, 71], [745, "14:01", "14:13", 841, 853, 12], [746, "14:03", "14:50", 843, 890, 47], [747, "14:04", "14:15", 844, 855, 11], [748, "14:04", "15:29", 844, 929, 85], [749, "14:05", "14:44", 845, 884, 39], [750, "14:08", "14:55", 848, 895, 47], [751, "14:08", "14:55", 848, 895, 47], [752, "14:08", "15:34", 848, 934, 86], [753, "14:09", "15:03", 849, 903, 54], [754, "14:10", "15:21", 850, 921, 71], [755, "14:10", "14:20", 850, 860, 10], [756, "14:13", "15:00", 853, 900, 47], [757, "14:13", "14:40", 853, 880, 27], [758, "14:14", "15:40", 854, 940, 86], [759, "14:14", "14:25", 854, 865, 11], [760, "14:15", "14:54", 855, 894, 39], [761, "14:16", "14:28", 856, 868, 12], [762, "14:18", "15:05", 858, 905, 47], [763, "14:18", "15:44", 858, 944, 86], [764, "14:18", "15:05", 858, 905, 47], [765, "14:19", "15:13", 859, 913, 54], [766, "14:20", "15:31", 860, 931, 71], [767, "14:20", "14:30", 860, 870, 10], [768, "14:20", "14:36", 860, 876, 16], [769, "14:21", "14:47", 861, 887, 26], [770, "14:23", "15:10", 863, 910, 47], [771, "14:23", "14:45", 863, 885, 22], [772, "14:24", "15:50", 864, 950, 86], [773, "14:24", "14:35", 864, 875, 11], [774, "14:25", "15:02", 865, 902, 37], [775, "14:26", "14:52", 866, 892, 26], [776, "14:28", "15:15", 868, 915, 47], [777, "14:28", "14:55", 868, 895, 27], [778, "14:28", "15:54", 868, 954, 86], [779, "14:28", "15:15", 868, 915, 47], [780, "14:29", "15:23", 869, 923, 54], [781, "14:30", "15:41", 870, 941, 71], [782, "14:30", "14:40", 870, 880, 10], [783, "14:31", "14:43", 871, 883, 12], [784, "14:33", "15:20", 873, 920, 47], [785, "14:34", "16:00", 874, 960, 86], [786, "14:34", "14:45", 874, 885, 11], [787, "14:35", "15:11", 875, 911, 36], [788, "14:38", "15:25", 878, 925, 47], [789, "14:38", "15:25", 878, 925, 47], [790, "14:38", "16:04", 878, 964, 86], [791, "14:39", "15:33", 879, 933, 54], [792, "14:40", "14:50", 880, 890, 10], [793, "14:40", "15:51", 880, 951, 71], [794, "14:40", "14:56", 880, 896, 16], [795, "14:43", "15:30", 883, 930, 47], [796, "14:43", "15:10", 883, 910, 27], [797, "14:44", "15:00", 884, 900, 16], [798, "14:44", "16:10", 884, 970, 86], [799, "14:45", "15:19", 885, 919, 34], [800, "14:46", "14:58", 886, 898, 12], [801, "14:48", "15:35", 888, 935, 47], [802, "14:48", "15:35", 888, 935, 47], [803, "14:48", "17:04", 888, 1024, 136], [804, "14:49", "15:43", 889, 943, 54], [805, "14:50", "16:01", 890, 961, 71], [806, "14:50", "15:00", 890, 900, 10], [807, "14:51", "15:17", 891, 917, 26], [808, "14:52", "15:27", 892, 927, 35], [809, "14:52", "15:21", 892, 921, 29], [810, "14:53", "15:40", 893, 940, 47], [811, "14:54", "15:08", 894, 908, 14], [812, "14:54", "16:20", 894, 980, 86], [813, "14:58", "16:24", 898, 984, 86], [814, "14:58", "15:45", 898, 945, 47], [815, "14:58", "15:25", 898, 925, 27], [816, "14:58", "15:45", 898, 945, 47], [817, "14:59", "15:53", 899, 953, 54], [818, "15:00", "15:10", 900, 910, 10], [819, "15:00", "15:35", 900, 935, 35], [820, "15:00", "16:11", 900, 971, 71], [821, "15:00", "15:16", 900, 916, 16], [822, "15:01", "15:13", 901, 913, 12], [823, "15:02", "15:16", 902, 916, 14], [824, "15:03", "15:50", 903, 950, 47], [825, "15:04", "16:30", 904, 990, 86], [826, "15:08", "16:34", 908, 994, 86], [827, "15:08", "15:55", 908, 955, 47], [828, "15:08", "15:55", 908, 955, 47], [829, "15:08", "15:45", 908, 945, 37], [830, "15:09", "16:14", 909, 974, 65], [831, "15:09", "16:03", 909, 963, 54], [832, "15:10", "16:21", 910, 981, 71], [833, "15:10", "15:20", 910, 920, 10], [834, "15:11", "15:24", 911, 924, 13], [835, "15:12", "15:36", 912, 936, 24], [836, "15:13", "16:00", 913, 960, 47], [837, "15:13", "15:40", 913, 940, 27], [838, "15:14", "16:40", 914, 1000, 86], [839, "15:16", "15:28", 916, 928, 12], [840, "15:16", "15:55", 916, 955, 39], [841, "15:18", "16:05", 918, 965, 47], [842, "15:18", "16:44", 918, 1004, 86], [843, "15:18", "16:05", 918, 965, 47], [844, "15:19", "16:13", 919, 973, 54], [845, "15:19", "15:34", 919, 934, 15], [846, "15:20", "15:30", 920, 930, 10], [847, "15:20", "16:31", 920, 991, 71], [848, "15:20", "15:36", 920, 936, 16], [849, "15:21", "15:47", 921, 947, 26], [850, "15:21", "16:06", 921, 966, 45], [851, "15:23", "16:10", 923, 970, 47], [852, "15:24", "16:50", 924, 1010, 86], [853, "15:24", "16:05", 924, 965, 41], [854, "15:27", "15:51", 927, 951, 24], [855, "15:27", "15:44", 927, 944, 17], [856, "15:28", "16:15", 928, 975, 47], [857, "15:28", "16:54", 928, 1014, 86], [858, "15:28", "16:15", 928, 975, 47], [859, "15:28", "15:55", 928, 955, 27], [860, "15:29", "16:23", 929, 983, 54], [861, "15:30", "16:41", 930, 1001, 71], [862, "15:30", "15:40", 930, 940, 10], [863, "15:31", "15:43", 931, 943, 12], [864, "15:33", "16:20", 933, 980, 47], [865, "15:34", "17:00", 934, 1020, 86], [866, "15:34", "16:15", 934, 975, 41], [867, "15:35", "15:54", 935, 954, 19], [868, "15:36", "16:21", 936, 981, 45], [869, "15:38", "16:25", 938, 985, 47], [870, "15:38", "16:25", 938, 985, 47], [871, "15:38", "16:39", 938, 999, 61], [872, "15:39", "16:33", 939, 993, 54], [873, "15:40", "15:50", 940, 950, 10], [874, "15:40", "16:51", 940, 1011, 71], [875, "15:40", "15:56", 940, 956, 16], [876, "15:43", "16:10", 943, 970, 27], [877, "15:43", "16:30", 943, 990, 47], [878, "15:44", "17:10", 944, 1030, 86], [879, "15:44", "16:25", 944, 985, 41], [880, "15:45", "16:04", 945, 964, 19], [881, "15:46", "15:58", 946, 958, 12], [882, "15:48", "16:35", 948, 995, 47], [883, "15:48", "16:35", 948, 995, 47], [884, "15:48", "17:14", 948, 1034, 86], [885, "15:49", "16:43", 949, 1003, 54], [886, "15:50", "16:00", 950, 960, 10], [887, "15:50", "17:01", 950, 1021, 71], [888, "15:51", "16:18", 951, 978, 27], [889, "15:52", "16:36", 952, 996, 44], [890, "15:53", "16:40", 953, 1000, 47], [891, "15:54", "17:20", 954, 1040, 86], [892, "15:54", "16:35", 954, 995, 41], [893, "15:55", "16:14", 955, 974, 19], [894, "15:58", "16:25", 958, 985, 27], [895, "15:58", "16:45", 958, 1005, 47], [896, "15:58", "16:45", 958, 1005, 47], [897, "15:58", "17:24", 958, 1044, 86], [898, "15:59", "17:11", 959, 1031, 72], [899, "15:59", "16:53", 959, 1013, 54], [900, "16:00", "16:10", 960, 970, 10], [901, "16:00", "16:16", 960, 976, 16], [902, "16:01", "16:13", 961, 973, 12], [903, "16:03", "16:50", 963, 1010, 47], [904, "16:04", "17:30", 964, 1050, 86], [905, "16:04", "16:45", 964, 1005, 41], [906, "16:05", "16:24", 965, 984, 19], [907, "16:06", "16:51", 966, 1011, 45], [908, "16:08", "16:55", 968, 1015, 47], [909, "16:08", "17:34", 968, 1054, 86], [910, "16:08", "16:55", 968, 1015, 47], [911, "16:09", "17:03", 969, 1023, 54], [912, "16:09", "17:21", 969, 1041, 72], [913, "16:10", "16:20", 970, 980, 10], [914, "16:13", "16:40", 973, 1000, 27], [915, "16:13", "17:00", 973, 1020, 47], [916, "16:14", "16:55", 974, 1015, 41], [917, "16:14", "17:40", 974, 1060, 86], [918, "16:15", "16:34", 975, 994, 19], [919, "16:16", "16:28", 976, 988, 12], [920, "16:18", "17:05", 978, 1025, 47], [921, "16:18", "17:05", 978, 1025, 47], [922, "16:18", "17:44", 978, 1064, 86], [923, "16:19", "17:31", 979, 1051, 72], [924, "16:19", "17:13", 979, 1033, 54], [925, "16:20", "16:30", 980, 990, 10], [926, "16:20", "16:36", 980, 996, 16], [927, "16:21", "16:48", 981, 1008, 27], [928, "16:22", "17:06", 982, 1026, 44], [929, "16:23", "17:10", 983, 1030, 47], [930, "16:24", "17:05", 984, 1025, 41], [931, "16:24", "17:50", 984, 1070, 86], [932, "16:25", "16:44", 985, 1004, 19], [933, "16:28", "17:15", 988, 1035, 47], [934, "16:28", "17:15", 988, 1035, 47], [935, "16:28", "16:55", 988, 1015, 27], [936, "16:28", "17:54", 988, 1074, 86], [937, "16:29", "17:23", 989, 1043, 54], [938, "16:29", "17:41", 989, 1061, 72], [939, "16:30", "16:40", 990, 1000, 10], [940, "16:31", "16:43", 991, 1003, 12], [941, "16:33", "17:20", 993, 1040, 47], [942, "16:34", "17:15", 994, 1035, 41], [943, "16:34", "18:00", 994, 1080, 86], [944, "16:35", "16:54", 995, 1014, 19], [945, "16:36", "17:21", 996, 1041, 45], [946, "16:38", "17:25", 998, 1045, 47], [947, "16:38", "17:25", 998, 1045, 47], [948, "16:38", "18:04", 998, 1084, 86], [949, "16:39", "17:33", 999, 1053, 54], [950, "16:39", "17:51", 999, 1071, 72], [951, "16:40", "16:56", 1000, 1016, 16], [952, "16:40", "16:50", 1000, 1010, 10], [953, "16:43", "17:10", 1003, 1030, 27], [954, "16:43", "17:30", 1003, 1050, 47], [955, "16:44", "17:25", 1004, 1045, 41], [956, "16:44", "18:10", 1004, 1090, 86], [957, "16:45", "17:04", 1005, 1024, 19], [958, "16:46", "16:58", 1006, 1018, 12], [959, "16:48", "18:14", 1008, 1094, 86], [960, "16:48", "17:35", 1008, 1055, 47], [961, "16:48", "17:35", 1008, 1055, 47], [962, "16:49", "18:01", 1009, 1081, 72], [963, "16:49", "17:43", 1009, 1063, 54], [964, "16:50", "17:00", 1010, 1020, 10], [965, "16:51", "17:18", 1011, 1038, 27], [966, "16:52", "17:36", 1012, 1056, 44], [967, "16:53", "17:40", 1013, 1060, 47], [968, "16:54", "18:20", 1014, 1100, 86], [969, "16:54", "17:35", 1014, 1055, 41], [970, "16:55", "17:14", 1015, 1034, 19], [971, "16:58", "17:25", 1018, 1045, 27], [972, "16:58", "17:45", 1018, 1065, 47], [973, "16:58", "17:45", 1018, 1065, 47], [974, "16:58", "18:24", 1018, 1104, 86], [975, "16:59", "18:11", 1019, 1091, 72], [976, "16:59", "17:53", 1019, 1073, 54], [977, "17:00", "17:16", 1020, 1036, 16], [978, "17:00", "17:10", 1020, 1030, 10], [979, "17:01", "17:13", 1021, 1033, 12], [980, "17:03", "17:50", 1023, 1070, 47], [981, "17:04", "18:30", 1024, 1110, 86], [982, "17:04", "17:45", 1024, 1065, 41], [983, "17:05", "17:24", 1025, 1044, 19], [984, "17:06", "17:51", 1026, 1071, 45], [985, "17:08", "17:55", 1028, 1075, 47], [986, "17:08", "17:55", 1028, 1075, 47], [987, "17:08", "18:34", 1028, 1114, 86], [988, "17:09", "18:03", 1029, 1083, 54], [989, "17:09", "18:21", 1029, 1101, 72], [990, "17:10", "17:20", 1030, 1040, 10], [991, "17:13", "17:40", 1033, 1060, 27], [992, "17:13", "18:00", 1033, 1080, 47], [993, "17:14", "17:55", 1034, 1075, 41], [994, "17:14", "18:40", 1034, 1120, 86], [995, "17:15", "17:34", 1035, 1054, 19], [996, "17:16", "17:28", 1036, 1048, 12], [997, "17:18", "18:05", 1038, 1085, 47], [998, "17:18", "18:05", 1038, 1085, 47], [999, "17:18", "18:44", 1038, 1124, 86], [1000, "17:19", "18:31", 1039, 1111, 72], [1001, "17:19", "18:13", 1039, 1093, 54], [1002, "17:20", "17:36", 1040, 1056, 16], [1003, "17:20", "17:30", 1040, 1050, 10], [1004, "17:21", "17:47", 1041, 1067, 26], [1005, "17:22", "18:06", 1042, 1086, 44], [1006, "17:23", "18:10", 1043, 1090, 47], [1007, "17:24", "18:50", 1044, 1130, 86], [1008, "17:24", "18:05", 1044, 1085, 41], [1009, "17:25", "17:44", 1045, 1064, 19], [1010, "17:28", "17:55", 1048, 1075, 27], [1011, "17:28", "18:15", 1048, 1095, 47], [1012, "17:28", "18:15", 1048, 1095, 47], [1013, "17:28", "18:54", 1048, 1134, 86], [1014, "17:29", "18:41", 1049, 1121, 72], [1015, "17:29", "18:23", 1049, 1103, 54], [1016, "17:30", "17:40", 1050, 1060, 10], [1017, "17:31", "17:43", 1051, 1063, 12], [1018, "17:33", "18:20", 1053, 1100, 47], [1019, "17:34", "18:15", 1054, 1095, 41], [1020, "17:34", "19:00", 1054, 1140, 86], [1021, "17:35", "17:54", 1055, 1074, 19], [1022, "17:36", "18:21", 1056, 1101, 45], [1023, "17:38", "18:25", 1058, 1105, 47], [1024, "17:38", "19:04", 1058, 1144, 86], [1025, "17:38", "18:25", 1058, 1105, 47], [1026, "17:39", "18:51", 1059, 1131, 72], [1027, "17:39", "18:33", 1059, 1113, 54], [1028, "17:40", "17:56", 1060, 1076, 16], [1029, "17:40", "17:50", 1060, 1070, 10], [1030, "17:43", "18:10", 1063, 1090, 27], [1031, "17:43", "18:30", 1063, 1110, 47], [1032, "17:44", "18:25", 1064, 1105, 41], [1033, "17:44", "19:14", 1064, 1154, 90], [1034, "17:45", "18:04", 1065, 1084, 19], [1035, "17:46", "17:58", 1066, 1078, 12], [1036, "17:48", "18:35", 1068, 1115, 47], [1037, "17:48", "18:35", 1068, 1115, 47], [1038, "17:48", "19:14", 1068, 1154, 86], [1039, "17:49", "19:01", 1069, 1141, 72], [1040, "17:49", "18:43", 1069, 1123, 54], [1041, "17:50", "18:00", 1070, 1080, 10], [1042, "17:51", "18:17", 1071, 1097, 26], [1043, "17:52", "18:36", 1072, 1116, 44], [1044, "17:53", "18:40", 1073, 1120, 47], [1045, "17:54", "18:35", 1074, 1115, 41], [1046, "17:54", "18:57", 1074, 1137, 63], [1047, "17:55", "18:14", 1075, 1094, 19], [1048, "17:58", "18:45", 1078, 1125, 47], [1049, "17:58", "18:45", 1078, 1125, 47], [1050, "17:58", "18:25", 1078, 1105, 27], [1051, "17:58", "19:26", 1078, 1166, 88], [1052, "17:59", "18:53", 1079, 1133, 54], [1053, "18:00", "19:11", 1080, 1151, 71], [1054, "18:00", "18:10", 1080, 1090, 10], [1055, "18:00", "18:16", 1080, 1096, 16], [1056, "18:01", "18:13", 1081, 1093, 12], [1057, "18:03", "18:50", 1083, 1130, 47], [1058, "18:04", "18:45", 1084, 1125, 41], [1059, "18:04", "19:29", 1084, 1169, 85], [1060, "18:05", "18:24", 1085, 1104, 19], [1061, "18:06", "18:51", 1086, 1131, 45], [1062, "18:08", "18:55", 1088, 1135, 47], [1063, "18:08", "19:06", 1088, 1146, 58], [1064, "18:08", "18:55", 1088, 1135, 47], [1065, "18:09", "19:03", 1089, 1143, 54], [1066, "18:10", "18:20", 1090, 1100, 10], [1067, "18:10", "19:21", 1090, 1161, 71], [1068, "18:13", "19:00", 1093, 1140, 47], [1069, "18:13", "18:40", 1093, 1120, 27], [1070, "18:14", "19:43", 1094, 1183, 89], [1071, "18:14", "18:55", 1094, 1135, 41], [1072, "18:15", "18:34", 1095, 1114, 19], [1073, "18:16", "18:28", 1096, 1108, 12], [1074, "18:17", "18:27", 1097, 1107, 10], [1075, "18:18", "19:41", 1098, 1181, 83], [1076, "18:18", "18:58", 1098, 1138, 40], [1077, "18:18", "19:05", 1098, 1145, 47], [1078, "18:19", "19:13", 1099, 1153, 54], [1079, "18:20", "19:31", 1100, 1171, 71], [1080, "18:20", "18:36", 1100, 1116, 16], [1081, "18:20", "18:30", 1100, 1110, 10], [1082, "18:22", "19:05", 1102, 1145, 43], [1083, "18:23", "19:05", 1103, 1145, 42], [1084, "18:24", "19:27", 1104, 1167, 63], [1085, "18:24", "19:05", 1104, 1145, 41], [1086, "18:25", "18:44", 1105, 1124, 19], [1087, "18:28", "19:25", 1108, 1165, 57], [1088, "18:28", "18:55", 1108, 1135, 27], [1089, "18:28", "19:08", 1108, 1148, 40], [1090, "18:28", "19:15", 1108, 1155, 47], [1091, "18:29", "19:23", 1109, 1163, 54], [1092, "18:30", "19:05", 1110, 1145, 35], [1093, "18:30", "18:40", 1110, 1120, 10], [1094, "18:31", "18:43", 1111, 1123, 12], [1095, "18:33", "19:15", 1113, 1155, 42], [1096, "18:34", "19:58", 1114, 1198, 84], [1097, "18:34", "19:14", 1114, 1154, 40], [1098, "18:35", "18:55", 1115, 1135, 20], [1099, "18:36", "19:20", 1116, 1160, 44], [1100, "18:38", "19:25", 1118, 1165, 47], [1101, "18:38", "19:23", 1118, 1163, 45], [1102, "18:38", "19:56", 1118, 1196, 78], [1103, "18:39", "19:33", 1119, 1173, 54], [1104, "18:40", "18:50", 1120, 1130, 10], [1105, "18:40", "19:45", 1120, 1185, 65], [1106, "18:40", "18:56", 1120, 1136, 16], [1107, "18:43", "19:10", 1123, 1150, 27], [1108, "18:43", "19:30", 1123, 1170, 47], [1109, "18:44", "19:24", 1124, 1164, 40], [1110, "18:45", "19:05", 1125, 1145, 20], [1111, "18:46", "18:58", 1126, 1138, 12], [1112, "18:48", "19:35", 1128, 1175, 47], [1113, "18:48", "20:12", 1128, 1212, 84], [1114, "18:48", "20:11", 1128, 1211, 83], [1115, "18:48", "19:28", 1128, 1168, 40], [1116, "18:49", "19:43", 1129, 1183, 54], [1117, "18:50", "19:00", 1130, 1140, 10], [1118, "18:51", "19:01", 1131, 1141, 10], [1119, "18:53", "19:35", 1133, 1175, 42], [1120, "18:53", "19:15", 1133, 1155, 22], [1121, "18:53", "20:00", 1133, 1200, 67], [1122, "18:55", "19:15", 1135, 1155, 20], [1123, "18:55", "19:34", 1135, 1174, 39], [1124, "18:58", "19:38", 1138, 1178, 40], [1125, "18:59", "19:53", 1139, 1193, 54], [1126, "18:59", "19:50", 1139, 1190, 51], [1127, "18:59", "19:53", 1139, 1193, 54], [1128, "19:00", "19:16", 1140, 1156, 16], [1129, "19:00", "19:10", 1140, 1150, 10], [1130, "19:00", "19:16", 1140, 1156, 16], [1131, "19:01", "19:13", 1141, 1153, 12], [1132, "19:03", "20:26", 1143, 1226, 83], [1133, "19:03", "19:45", 1143, 1185, 42], [1134, "19:05", "19:44", 1145, 1184, 39], [1135, "19:05", "19:25", 1145, 1165, 20], [1136, "19:08", "20:15", 1148, 1215, 67], [1137, "19:08", "19:35", 1148, 1175, 27], [1138, "19:09", "19:49", 1149, 1189, 40], [1139, "19:09", "20:03", 1149, 1203, 54], [1140, "19:10", "19:20", 1150, 1160, 10], [1141, "19:10", "19:20", 1150, 1160, 10], [1142, "19:11", "19:53", 1151, 1193, 42], [1143, "19:14", "20:26", 1154, 1226, 72], [1144, "19:14", "19:35", 1154, 1175, 21], [1145, "19:14", "19:24", 1154, 1164, 10], [1146, "19:14", "20:05", 1154, 1205, 51], [1147, "19:15", "19:30", 1155, 1170, 15], [1148, "19:15", "19:54", 1155, 1194, 39], [1149, "19:18", "20:39", 1158, 1239, 81], [1150, "19:18", "20:00", 1158, 1200, 42], [1151, "19:19", "20:14", 1159, 1214, 55], [1152, "19:20", "19:30", 1160, 1170, 10], [1153, "19:20", "19:36", 1160, 1176, 16], [1154, "19:21", "19:31", 1161, 1171, 10], [1155, "19:23", "20:30", 1163, 1230, 67], [1156, "19:23", "19:35", 1163, 1175, 12], [1157, "19:24", "19:45", 1164, 1185, 21], [1158, "19:24", "19:45", 1164, 1185, 21], [1159, "19:25", "20:04", 1165, 1204, 39], [1160, "19:26", "20:08", 1166, 1208, 42], [1161, "19:29", "20:02", 1169, 1202, 33], [1162, "19:29", "20:18", 1169, 1218, 49], [1163, "19:29", "20:41", 1169, 1241, 72], [1164, "19:30", "19:40", 1170, 1180, 10], [1165, "19:33", "20:54", 1173, 1254, 81], [1166, "19:33", "20:17", 1173, 1217, 44], [1167, "19:34", "19:55", 1174, 1195, 21], [1168, "19:35", "20:14", 1175, 1214, 39], [1169, "19:38", "20:05", 1178, 1205, 27], [1170, "19:38", "20:45", 1178, 1245, 67], [1171, "19:39", "20:12", 1179, 1212, 33], [1172, "19:40", "19:50", 1180, 1190, 10], [1173, "19:40", "19:56", 1180, 1196, 16], [1174, "19:41", "20:27", 1181, 1227, 46], [1175, "19:43", "19:55", 1183, 1195, 12], [1176, "19:44", "20:05", 1184, 1205, 21], [1177, "19:44", "20:33", 1184, 1233, 49], [1178, "19:44", "21:00", 1184, 1260, 76], [1179, "19:45", "20:24", 1185, 1224, 39], [1180, "19:48", "20:37", 1188, 1237, 49], [1181, "19:48", "21:09", 1188, 1269, 81], [1182, "19:50", "20:00", 1190, 1200, 10], [1183, "19:52", "20:29", 1192, 1229, 37], [1184, "19:53", "20:08", 1193, 1208, 15], [1185, "19:53", "21:02", 1193, 1262, 69], [1186, "19:53", "20:20", 1193, 1220, 27], [1187, "19:54", "20:19", 1194, 1219, 25], [1188, "19:55", "20:34", 1195, 1234, 39], [1189, "19:56", "20:34", 1196, 1234, 38], [1190, "19:59", "20:48", 1199, 1248, 49], [1191, "19:59", "21:20", 1199, 1280, 81], [1192, "20:00", "20:16", 1200, 1216, 16], [1193, "20:00", "20:10", 1200, 1210, 10], [1194, "20:03", "20:42", 1203, 1242, 39], [1195, "20:03", "21:24", 1203, 1284, 81], [1196, "20:04", "20:29", 1204, 1229, 25], [1197, "20:05", "20:48", 1205, 1248, 43], [1198, "20:07", "20:44", 1207, 1244, 37], [1199, "20:08", "20:40", 1208, 1240, 32], [1200, "20:08", "20:35", 1208, 1235, 27], [1201, "20:10", "20:20", 1210, 1220, 10], [1202, "20:10", "20:22", 1210, 1222, 12], [1203, "20:11", "20:47", 1211, 1247, 36], [1204, "20:14", "21:04", 1214, 1264, 50], [1205, "20:14", "21:03", 1214, 1263, 49], [1206, "20:17", "21:03", 1217, 1263, 46], [1207, "20:18", "21:39", 1218, 1299, 81], [1208, "20:20", "20:30", 1220, 1230, 10], [1209, "20:20", "20:57", 1220, 1257, 37], [1210, "20:20", "20:36", 1220, 1236, 16], [1211, "20:22", "20:59", 1222, 1259, 37], [1212, "20:22", "20:42", 1222, 1242, 20], [1213, "20:24", "20:49", 1224, 1249, 25], [1214, "20:27", "21:22", 1227, 1282, 55], [1215, "20:29", "21:18", 1229, 1278, 49], [1216, "20:30", "21:07", 1230, 1267, 37], [1217, "20:30", "20:40", 1230, 1240, 10], [1218, "20:30", "20:40", 1230, 1240, 10], [1219, "20:30", "21:40", 1230, 1300, 70], [1220, "20:32", "21:18", 1232, 1278, 46], [1221, "20:35", "21:54", 1235, 1314, 79], [1222, "20:37", "21:14", 1237, 1274, 37], [1223, "20:38", "21:08", 1238, 1268, 30], [1224, "20:40", "20:50", 1240, 1250, 10], [1225, "20:40", "21:17", 1240, 1277, 37], [1226, "20:40", "20:56", 1240, 1256, 16], [1227, "20:44", "21:33", 1244, 1293, 49], [1228, "20:47", "21:33", 1247, 1293, 46], [1229, "20:47", "21:42", 1247, 1302, 55], [1230, "20:50", "21:00", 1250, 1260, 10], [1231, "20:50", "22:00", 1250, 1320, 70], [1232, "20:50", "22:09", 1250, 1329, 79], [1233, "20:50", "21:27", 1250, 1287, 37], [1234, "20:52", "21:29", 1252, 1289, 37], [1235, "20:53", "21:20", 1253, 1280, 27], [1236, "20:56", "21:11", 1256, 1271, 15], [1237, "20:59", "21:48", 1259, 1308, 49], [1238, "21:00", "21:10", 1260, 1270, 10], [1239, "21:00", "21:37", 1260, 1297, 37], [1240, "21:02", "21:48", 1262, 1308, 46], [1241, "21:05", "22:24", 1265, 1344, 79], [1242, "21:07", "21:44", 1267, 1304, 37], [1243, "21:07", "22:02", 1267, 1322, 55], [1244, "21:08", "21:38", 1268, 1298, 30], [1245, "21:10", "22:25", 1270, 1345, 75], [1246, "21:10", "21:20", 1270, 1280, 10], [1247, "21:10", "21:47", 1270, 1307, 37], [1248, "21:14", "22:03", 1274, 1323, 49], [1249, "21:17", "22:03", 1277, 1323, 46], [1250, "21:20", "22:18", 1280, 1338, 58], [1251, "21:20", "21:57", 1280, 1317, 37], [1252, "21:20", "21:30", 1280, 1290, 10], [1253, "21:22", "21:59", 1282, 1319, 37], [1254, "21:24", "21:49", 1284, 1309, 25], [1255, "21:27", "22:21", 1287, 1341, 54], [1256, "21:30", "22:07", 1290, 1327, 37], [1257, "21:30", "22:20", 1290, 1340, 50], [1258, "21:30", "21:40", 1290, 1300, 10], [1259, "21:32", "22:18", 1292, 1338, 46], [1260, "21:32", "22:01", 1292, 1321, 29], [1261, "21:35", "22:54", 1295, 1374, 79], [1262, "21:37", "22:14", 1297, 1334, 37], [1263, "21:39", "21:55", 1299, 1315, 16], [1264, "21:40", "22:17", 1300, 1337, 37], [1265, "21:40", "21:50", 1300, 1310, 10], [1266, "21:41", "22:08", 1301, 1328, 27], [1267, "21:47", "22:16", 1307, 1336, 29], [1268, "21:47", "22:51", 1307, 1371, 64], [1269, "21:47", "22:33", 1307, 1353, 46], [1270, "21:48", "22:03", 1308, 1323, 15], [1271, "21:50", "22:55", 1310, 1375, 65], [1272, "21:50", "22:27", 1310, 1347, 37], [1273, "21:50", "22:00", 1310, 1320, 10], [1274, "21:52", "22:29", 1312, 1349, 37], [1275, "21:53", "22:19", 1313, 1339, 26], [1276, "22:00", "22:38", 1320, 1358, 38], [1277, "22:00", "22:10", 1320, 1330, 10], [1278, "22:02", "22:12", 1322, 1332, 10], [1279, "22:02", "22:48", 1322, 1368, 46], [1280, "22:04", "22:31", 1324, 1351, 27], [1281, "22:05", "23:24", 1325, 1404, 79], [1282, "22:07", "22:44", 1327, 1364, 37], [1283, "22:07", "22:39", 1327, 1359, 32], [1284, "22:09", "22:25", 1329, 1345, 16], [1285, "22:10", "23:25", 1330, 1405, 75], [1286, "22:13", "22:38", 1333, 1358, 25], [1287, "22:13", "22:53", 1333, 1373, 40], [1288, "22:17", "22:27", 1337, 1347, 10], [1289, "22:17", "23:03", 1337, 1383, 46], [1290, "22:19", "22:46", 1339, 1366, 27], [1291, "22:22", "22:59", 1342, 1379, 37], [1292, "22:24", "22:48", 1344, 1368, 24], [1293, "22:27", "22:52", 1347, 1372, 25], [1294, "22:27", "23:21", 1347, 1401, 54], [1295, "22:28", "23:08", 1348, 1388, 40], [1296, "22:30", "23:17", 1350, 1397, 47], [1297, "22:32", "22:42", 1352, 1362, 10], [1298, "22:32", "23:11", 1352, 1391, 39], [1299, "22:34", "23:01", 1354, 1381, 27], [1300, "22:35", "23:54", 1355, 1434, 79], [1301, "22:37", "23:14", 1357, 1394, 37], [1302, "22:43", "23:23", 1363, 1403, 40], [1303, "22:43", "23:08", 1363, 1388, 25], [1304, "22:47", "23:33", 1367, 1413, 46], [1305, "22:47", "22:57", 1367, 1377, 10], [1306, "22:49", "23:16", 1369, 1396, 27], [1307, "22:52", "23:29", 1372, 1409, 37], [1308, "22:53", "23:15", 1373, 1395, 22], [1309, "22:55", "23:55", 1375, 1435, 60], [1310, "22:57", "23:51", 1377, 1431, 54], [1311, "22:58", "23:38", 1378, 1418, 40], [1312, "23:02", "23:41", 1382, 1421, 39], [1313, "23:02", "23:12", 1382, 1392, 10], [1314, "23:04", "23:31", 1384, 1411, 27], [1315, "23:05", "00:24", 1385, 1464, 79], [1316, "23:07", "23:44", 1387, 1424, 37], [1317, "23:13", "23:53", 1393, 1433, 40], [1318, "23:13", "23:38", 1393, 1418, 25], [1319, "23:17", "00:03", 1397, 1443, 46], [1320, "23:17", "23:27", 1397, 1407, 10], [1321, "23:19", "23:46", 1399, 1426, 27], [1322, "23:22", "23:59", 1402, 1439, 37], [1323, "23:25", "00:25", 1405, 1465, 60], [1324, "23:27", "00:21", 1407, 1461, 54], [1325, "23:28", "00:08", 1408, 1448, 40], [1326, "23:32", "23:42", 1412, 1422, 10], [1327, "23:34", "00:01", 1414, 1441, 27], [1328, "23:35", "01:05", 1415, 1505, 90], [1329, "23:37", "00:09", 1417, 1449, 32], [1330, "23:43", "00:23", 1423, 1463, 40], [1331, "23:43", "00:08", 1423, 1448, 25], [1332, "23:46", "00:01", 1426, 1441, 15], [1333, "23:47", "23:57", 1427, 1437, 10], [1334, "23:47", "00:33", 1427, 1473, 46], [1335, "23:52", "00:24", 1432, 1464, 32], [1336, "23:55", "00:49", 1435, 1489, 54], [1337, "23:57", "00:57", 1437, 1497, 60], [1338, "23:58", "00:38", 1438, 1478, 40], [1339, "00:02", "00:12", 1442, 1452, 10], [1340, "00:07", "00:39", 1447, 1479, 32], [1341, "00:13", "00:38", 1453, 1478, 25], [1342, "00:13", "00:51", 1453, 1491, 38], [1343, "00:15", "01:14", 1455, 1514, 59], [1344, "00:17", "01:23", 1457, 1523, 66], [1345, "00:23", "00:33", 1463, 1473, 10], [1346, "00:24", "00:40", 1464, 1480, 16], [1347, "00:25", "01:12", 1465, 1512, 47], [1348, "00:28", "01:07", 1468, 1507, 39], [1349, "00:33", "01:05", 1473, 1505, 32], [1350, "00:43", "01:21", 1483, 1521, 38], [1351, "00:44", "00:54", 1484, 1494, 10], [1352, "00:47", "01:09", 1487, 1509, 22], [1353, "00:47", "01:26", 1487, 1526, 39], [1354, "00:54", "01:04", 1494, 1504, 10], [1355, "00:57", "01:07", 1497, 1507, 10], ] # yapf:disable def find_minimum_number_of_drivers(shifts, params): """Minimize the number of needed drivers.""" num_shifts = len(shifts) # All durations are in minutes. max_driving_time = 540 # 8 hours. max_driving_time_without_pauses = 240 # 4 hours min_pause_after_4h = 30 min_delay_between_shifts = 2 max_working_time = 720 min_working_time = 390 # 6.5 hours extra_time = 10 + 25 max_break = 180 # Computed data. total_driving_time = sum(shift[5] for shift in shifts) min_num_drivers = int(math.ceil(total_driving_time * 1.0 / max_driving_time)) min_start_time = min(shift[3] for shift in shifts) max_end_time = max(shift[4] for shift in shifts) print("Bus driver scheduling") print(" num shifts =", num_shifts) print(" total driving time =", total_driving_time, "minutes") print(" min num drivers =", min_num_drivers) print(" min start time =", min_start_time) print(" max end time =", max_end_time) # We are going to build a flow from a the start of the day to the end # of the day. # # Along the path, we will accumulate driving time, accrued time since the # last break, and total working time. model = cp_model.CpModel() # Per node info driving_time = {} working_time = {} no_break_driving_time = {} incoming_literals = collections.defaultdict(list) outgoing_literals = collections.defaultdict(list) outgoing_source_literals = [] incoming_sink_literals = [] all_literals = [] # Create all the shift variables before iterating on the transitions # between these shifts. for shift in range(num_shifts): driving_time[shift] = model.NewIntVar(0, max_driving_time, "dt_%i" % shift) no_break_driving_time[shift] = model.NewIntVar( 0, max_driving_time_without_pauses, "nbdt_%i" % shift ) working_time[shift] = model.NewIntVar(0, max_working_time, "wt_%i" % shift) for shift in range(num_shifts): duration = shifts[shift][5] # Arc from source to shift. # - set the working time of the driver # - increase driving time and driving time since the last break source_lit = model.NewBoolVar("from source to %i" % shift) all_literals.append(source_lit) outgoing_source_literals.append(source_lit) incoming_literals[shift].append(source_lit) model.Add(driving_time[shift] == duration).OnlyEnforceIf(source_lit) model.Add(no_break_driving_time[shift] == duration).OnlyEnforceIf(source_lit) model.Add(working_time[shift] == duration + extra_time).OnlyEnforceIf( source_lit ) # Arc from shift to sink # - checks that working time is greater than min_working_time sink_lit = model.NewBoolVar("from %i to sink" % shift) all_literals.append(sink_lit) outgoing_literals[shift].append(sink_lit) incoming_sink_literals.append(sink_lit) model.Add(working_time[shift] >= min_working_time).OnlyEnforceIf(sink_lit) for other in range(num_shifts): delay = shifts[other][3] - shifts[shift][4] if delay < min_delay_between_shifts: continue if delay > max_break: break # Assumes start times are sorted. other_duration = shifts[other][5] lit = model.NewBoolVar("from %i to %i" % (shift, other)) all_literals.append(lit) # Increase driving time model.Add( driving_time[other] == driving_time[shift] + other_duration ).OnlyEnforceIf(lit) # Increase no_break_driving or reset it to 0 depending on the delay if delay >= min_pause_after_4h: model.Add(no_break_driving_time[other] == other_duration).OnlyEnforceIf( lit ) else: model.Add( no_break_driving_time[other] == no_break_driving_time[shift] + other_duration ).OnlyEnforceIf(lit) # Increase working time model.Add( working_time[other] == working_time[shift] + delay + other_duration ).OnlyEnforceIf(lit) # Add arc outgoing_literals[shift].append(lit) incoming_literals[other].append(lit) # Create dag constraint. for shift in range(num_shifts): model.Add(sum(outgoing_literals[shift]) == 1) model.Add(sum(incoming_literals[shift]) == 1) # Num drivers num_drivers = model.NewIntVar(min_num_drivers, min_num_drivers * 3, "num_drivers") model.Add(sum(incoming_sink_literals) == num_drivers) model.Add(sum(outgoing_source_literals) == num_drivers) model.Minimize(num_drivers) # Solve model. solver = cp_model.CpSolver() solver.parameters.log_search_progress = True # solver.parameters.num_search_workers = 16 # solver.parameters.boolean_encoding_level = 0 # solver.parameters.lns_focus_on_decision_variables = True status = solver.Solve(model) if status != cp_model.OPTIMAL and status != cp_model.FEASIBLE: return -1 # Display solution optimal_num_drivers = int(solver.ObjectiveValue()) print("minimal number of drivers =", optimal_num_drivers) return optimal_num_drivers def main(args): """Optimize the bus driver allocation in two passes.""" print("----------- first pass: minimize the number of drivers") shifts = [] if args.instance == 1: shifts = SAMPLE_SHIFTS_SMALL elif args.instance == 2: shifts = SAMPLE_SHIFTS_MEDIUM elif args.instance == 3: shifts = SAMPLE_SHIFTS_LARGE num_drivers = find_minimum_number_of_drivers(shifts, args.params) print("----------- second pass: minimize the sum of working times") # bus_driver_scheduling(False, num_drivers) if __name__ == "__main__": main(PARSER.parse_args())