caa a22 4500 445838671 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s10951-011-0234-0 doi (NATIONALLICENCE)springer-10.1007/s10951-011-0234-0 Fügenschuh Armin Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), Takustr. 7, 14195, Berlin, Germany aut A set partitioning reformulation of a school bus scheduling problem [Elektronische Daten] [Armin Fügenschuh] We present an integer programming model for the integrated optimization of bus schedules and school starting times, which is a single-depot vehicle scheduling problem with additional coupling constraints among the time windows. For instances with wide time windows the linear relaxation is weak and feasible solutions found by an ILP solver are of poor quality. We apply a set partitioning relaxation to compute better lower bounds and, in combination with a primal construction heuristic, also better primal feasible solutions. Integer programs with at most two non-zero coefficient per constraint play a prominent role in our approach. Computational results for several random and a real-world instance are given and compared with results from a standard branch-and-cut approach. Springer Science+Business Media, LLC, 2011 Integer linear programming nationallicence Single-depot vehicle scheduling with time windows nationallicence IP2 nationallicence Set partitioning nationallicence Cutting planes nationallicence Journal of Scheduling Springer US; http://www.springer-ny.com 14/4(2011-08-01), 307-318 1094-6136 14:4<307 2011 14 10951 https://doi.org/10.1007/s10951-011-0234-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-011-0234-0 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Fügenschuh Armin Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), Takustr. 7, 14195, Berlin, Germany aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/4(2011-08-01), 307-318 1094-6136 14:4<307 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer