The solution of the multidepot vehicle scheduling problem (MDVSP) can often be improved substantially by incorporating trip shifting (TS) as a model feature. By allowing departure times to deviate a few minutes from the original timetable, new combinations of trips may be carried out by the same vehicle, thus leading to more efficient scheduling. However, explicit modeling of each potential trip shift quickly causes the problem to get prohibitively large for current solvers such that researchers and practitioners are obligated to resort to heuristic methods to solve large instances. In this paper, we develop a dynamic discretization discovery algorithm that guarantees an optimal continuous-time solution to the MDVSP-TS without explicit consideration of all trip shifts. It does so by iteratively solving and refining the problem on a partially time-expanded network until the solution can be converted to a feasible vehicle schedule on the fully time-expanded network. Computational results demonstrate that this algorithm outperforms both the explicit modeling approach and a branch-and-price algorithm by a wide margin and is able to solve the MDVSP-TS for real-life instances with close to 4,000 trips even when many departure time deviations are considered. History: Accepted by Russel Bent, Area Editor for Network Optimization: Algorithms & Applications. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0698 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0698 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We study the periodic assignment problem, in which a set of periodically repeating tasks must be assigned to workers within a repeating schedule. The classical efficiency objective is to minimize the number of workers required to operate the schedule. We propose a (n log n) algorithm to solve this problem. Next, we formalize a notion of fairness among workers, and impose that each worker performs the same work over time. We analyze the resulting trade-off between efficiency and fairness, showing that the price of fairness is at most one extra worker, and that such a fair solution can always be found using the Nearest Neighbor heuristic. We characterize all instances that admit a solution that is both fair and efficient, and use this result to develop a (n log n) exact algorithm for the fair periodic assignment problem. Finally, we show that allowing aperiodic schedules never reduces the price of fairness.

We consider the following problem: given a set of lines in a public transportation network with their round trip times and frequencies, a maximum number of vehicles and a maximum number of lines that can be combined into a vehicle circulation, does there exist a set of vehicle circulations that covers all lines given the constraints. Solving this problem provides an estimate of the costs of operating a certain line plan, without having to compute a timetable first. We show that this problem is NP-hard for any restriction on the number of lines that can be combined into a circulation which is equal to or greater than three. We pay special attention to the case where at most two lines can be combined into a circulation, which is NP-hard if a single line can be covered by multiple circulations. If this is not allowed, a matching algorithm can be used to find the optimal solutions, which we show to be a 16/15-approximation for the case where it is allowed. We also provide an exact algorithm that is able to exploit low tree-width of the so-called circulation graph and small numbers of vehicles required to cover single circulations.