Computational Experiments for the MIP Models
In this section we begin by introducing a set of real-world instances from different German bus companies in Section 6.1; this is followed by a description of the solutions achieved with different solvers, namely the Gurobi Optimizer (see Gurobi Optimizat
- PDF / 285,676 Bytes
- 10 Pages / 419.528 x 595.276 pts Page_size
- 65 Downloads / 220 Views
1. Properties of the Real-World Data Instances We test our solution approaches on 16 real-world instances for which the number of duties varies between 1,013 and 19,486. The number of drivers in the instances varies between 48 and 629. The names of the instances include the number of drivers (NCCR) / groups of drivers (CCR), the number of planning days, and the number of included shift types. Instance
Duties
Standbys
Days off
φAlt.
Act.arcs(fixed)
Com.arcs
48-75-6 52-73-6 52-75-6 9-238-11* 393-45-37 392-45-37 397-40-37 96-70-8 87-70-8 89-70-8 214-45-34 211-45-34 221-45-30 629-46-26 606-70-26 607-70-26
1,313 1,288 1,321 1,013 5,420 5,815 4,917 3,200 3,273 3,260 3,966 4,003 4,214 11,073 18,739 19,486
454 664 488 303 2,619 2,342 2,717 876 796 671 1,472 1,447 1,646 4,292 4,977 4,549
1,472 1,487 1,509 483 8,030 8,364 7,438 1,936 1,708 1,758 3,240 3,029 3,222 9,246 13,612 13,364
2.2 2.2 2.2 4.7 1.5 1.3 1.4 5 4.5 4.8 6.6 7 6.7 5 5.3 5.1
10,516 (12.7%) 11,367 (12.2%) 11,072 (15.5%) 6,672 (12.4%) 45,035 (23.8%) 43,367 (26.2%) 38,277 (26.3%) 38,413 (6.3%) 38,944 (4.1%) 40,392 (4.8%) 55,366 (8.7%) 55,376 (8.9%) 64,576 (7.6%) 150,616 (11.8%) 255,657 (7.5%) 258,075 (7.3%)
34,584 37,907 36,113 30,457 145,491 134,974 115,236 287,490 301,374 326,505 472,958 490,521 624,520 1,212,486 2,158,525 2,205,303
Table 6.1. Characteristics of the test set instances. The star (*) indicates the instance for the CCR problem. L. Xie, Decision Support for Crew Rostering in Public Transit, DOI 10.1007/978-3-658-08167-6_6, © Springer Fachmedien Wiesbaden 2015
58
6. Computational Experiments for the MIP Models
In Table 6.1, the important properties of the instances are shown, including the number of activities, i.e. duties, standbys, and days off, the average alternatives (φAlt.), the number of activity arcs (Act.arcs), the percentage of fixed activity arcs in parentheses, and the number of compatibility arcs (Com.arcs). These are some of the factors causing difficulties in solving the instances. As we consider more activities (duties, standbys, days off) and drivers, more activity and compatibility arcs are generated in our network. If more alternatives for desired activities of drivers are provided, that also causes more activity and compatibility arcs. However, if we consider more fixed activity arcs, then this problem is easier to solve (such as the instances 96-70-8 vs. 89-70-8). The instances are sorted according to the gap to optimum after 24 hours for solving the integrated problem. Besides those factors shown in Table 6.1, another important factor is how many quality rules are considered in those instances. Most of the instances in Table 6.1 consider all quality rules in Section 2.2.1, but the instances 392-45-37, 393-45-37 and 397-40-37 only consider the objectives (5.15), (5.22), (5.23), and (5.24) and their corresponding soft constraints. This is one of the reasons why these instances can be solved more easily compared with, for example, 221-45-30. The instance 9-238-11 is used to solve the CCR problem. It includes nine groups of
Data Loading...
