Numerous urban planners advocate for differentiated transit pricing to improve both ridership and service equity. Several metropolitan cities are considering switching to a more "fair fare system," where passengers pay according to the distance travelled, rather than a flat fare or zone boundary scheme that discriminates against various marginalized groups. In this paper, we present a two-part optimal pricing formula for switching to distance-based transit fares: the first formula maximizes forecasted revenue given a target ridership, and the second formula maximizes forecasted ridership given a target revenue. Both formulas hold for all price elasticities. Our theory has been successfully tested on the SkyTrain mass transit network in Metro Vancouver, British Columbia, with over 400,000 daily passengers. This research has served Metro Vancouver's transportation authority as they consider changing their fare structure for the first time in over 30 years.

Employee scheduling is one of the most difficult challenges facing any small business owner. The problem becomes more complex when employees with different levels of seniority indicate preferences for specific roles in certain shifts and request flexible work hours outside of the standard eight-hour block. Many business owners and managers, who cannot afford (or choose not to use) commercially-available timetabling apps, spend numerous hours creating sub-optimal schedules by hand, leading to low staff morale. In this paper, we explain how two undergraduate students generalized the Nurse Scheduling Problem to take into account multiple roles and flexible work hours, and implemented a user-friendly automated timetabler based on a four-dimensional integer linear program. This system has been successfully deployed at two businesses in our community, each with 20+ employees: a coffee shop and a health clinic.

In this paper, we construct a Balanced Weekend Tournament, motivated by the real-life problem of scheduling an n-team double round-robin season schedule for a Canadian university soccer league. In this 6-team league, games are only played on Saturdays and Sundays, with the condition that no team has two road games on any weekend. The implemented regular-season schedule for n = 6 was best-possible, but failed to meet an important "compactness" criterion, as the 10-game tournament required more than five weekends to complete. The motivation for this paper was to determine whether an optimal season schedule, satisfying all of the league's constraints on compact balanced play, could be constructed for sports leagues with n > 6 teams. We present a simple recursive algorithm to answer this question for all even n > 6. As a corollary, our construction gives us an explicit solution to a challenging and well-known graph theory question, namely the problem of decomposing the complete directed graph K* 2 m into 2 m –1 directed Hamiltonian cycles of length 2 m .

The Traveling Tournament Problem (TTP) is a complex problem in sports scheduling whose solution is a schedule of home and away games meeting specific feasibility requirements, while minimizing the total distance traveled by all the teams. A recently-developed "hybrid" algorithm, combining local search and integer programming, has resulted in best-known solutions for many TTP instances. In this paper, we tackle the TTP from a graph-theoretic perspective, by generating a new "canonical" schedule in which each team's three-game road trips match up with the underlying graph's minimum-weight P_3-packing. By using this new schedule as the initial input for the hybrid algorithm, we develop tournament schedules for five benchmark TTP instances that beat all previously-known solutions.

The Traveling Tournament Problem (TTP) is a well-known NP-complete problem in sports scheduling that was inspired by the application of optimizing schedules for Major League Baseball to reduce total team travel. The techniques and heuristics from the n-team TTP can be extended to optimize the scheduling of other sports leagues, such as the Nippon Professional Baseball (NPB) league in Japan. In this paper, we describe the additional scheduling constraints required by the NPB league, such as the requirement that each team play the same number of weekend home games, weekday home games, weekend road games, and weekday road games. We fully solve this TTP-variant for the case n=6, and conclude the paper by presenting the official 2013 NPB Central League Schedule, where we helped this Japanese baseball league reduce total team travel by over six thousand kilometres.

We introduce a linear distance relaxation of the n-team Traveling Tournament Problem (TTP), a simple yet powerful heuristic that temporarily "assumes"' the n teams are located on a straight line, thereby reducing the n ( n –1)/2 pairwise distance parameters to just n –1 variables. The modified problem then becomes easier to analyze, from which we determine an approximate solution for the actual instance on n teams. We present combinatorial techniques to solve the Linear Distance TTP (LD-TTP) for n = 4 and n = 6, without any use of computing, generating the complete set of optimal distances regardless of where the n teams are located. We show that there are only 295 non-isomorphic schedules that can be a solution to the 6-team LD-TTP, and demonstrate that in all previously-solved benchmark TTP instances on 6 teams, the distance-optimal schedule appears in this list of 295, even when the six teams are arranged in a circle or located in three-dimensional space. We then extend the LD-TTP to multiple rounds, and apply our theory to produce a nearly-optimal regular-season schedule for the Nippon Pro Baseball league in Japan. We conclude the paper by generalizing our theory to the n -team LD-TTP, producing a feasible schedule whose total distance is guaranteed to be no worse than 4/3 times the optimal solution.

With the recent inclusion of inter-league games to professional sports leagues, a natural question is to determine the "best possible" inter-league schedule that retains all of the league's scheduling constraints to ensure competitive balance and fairness, while minimizing the total travel distance for both economic and environmental efficiency. To answer that question, this paper introduces the Bipartite Traveling Tournament Problem (BTTP) , the inter-league extension of the well-studied Traveling Tournament Problem. We prove that the 2n -team BTTP is NP-complete, but for small values of n , a distance-optimal inter-league schedule can be generated from an algorithm based on minimum-weight 4-cycle-covers. We apply our algorithm to the 12-team Nippon Professional Baseball (NPB) league in Japan, creating an inter-league tournament that reduces total team travel by 16% compared to the actual schedule played by these teams during the 2010 NPB season. We also analyze the problem of inter-league scheduling for the 30-team National Basketball Association (NBA), and develop a tournament schedule whose total inter-league travel distance is just 3.8% higher than the trivial theoretical lower bound.  

Given an n -team sports league, the Traveling Tournament Problem (TTP) seeks to determine an optimal double round-robin schedule minimizing the sum total of distances traveled by the n teams as they move from city to city. In the TTP, the number of "rounds" is fixed at r = 2. In this paper, we propose the Multi-Round Balanced Traveling Tournament Problem (mb-TTP), inspired by the actual league structure of Japanese professional baseball, where n = 6 teams play 120 intra-league games over r = 8 rounds, subject to various constraints that ensure competitive balance. These additional balancing constraints enable us to reformulate the 2 k -round mb-TTP as a shortest path problem on a directed graph, for all k >= 1. We apply our theoretical algorithm to the 6-team Nippon (Japanese) Professional Baseball Central League, creating a distance-optimal schedule with 57836 kilometres of total travel, a 26.8% reduction compared to the 79067 kilometres traveled by these six teams during the 2010 regular season.