情報学を使って日本プロ野球の日程を現状よりもっと効率的にします
Applying informatics to optimize scheduling for Nippon Pro Baseball
星野 リチャード

河原林 健一Richard HOSHINO

Ken-ichi KAWARABAYASHI

研究動機

Main Result

2009年，鳩山首相（当時）は，今後10年間で二酸化炭素排出量を２５％削減する長期目標を発表した．本研
究では，情報学および離散数学における「グラフ理論」的手法をスケジューリングに応用し，エコにやさしい各種スケジュールの作成を目指す．特に日本プロ野球のスケジューリングの大幅な改良に取り組む。

グラフ理論的手法を用いて日本プロ野球のセ・パ両リーグのスケジュールの改良に取り組み、昨年度のスケジュールと比較して69,186キロの総移動距離の削減，さらに旅行回数の24.3%の削減に成功した。今後MLB(メジャーリーグ)，NBA(バスケットボール)などのスケジュール作成への応用が期待される。

理論的背景
巡回トーナメント問題 (TTP)とは，Jリーグのように、与えられたｎチームそれぞれが、他のｎ－１チームと本拠地(ホーム）とアウェイで1試合ずつ対戦するスケジュールを，ホーム＆アウェイゲームのバランスと，ある「公平性」のもとで，総移動距離最短のものを作成することである。
TTPは有名な巡回セールスマン問題と類似である。
本研究では，TTPを応用して，グラフ上の最短距離パスを利用し，セ・パ両リーグのスケジュールを提案した（Figure 2）。この提案手法は，現行のスケジュールに比べて，総移動距離２５％の改良になっている。
また，セパ交流戦のスケジュール改良にも取り組んだ(Figure 3)。

グラフ理論の日本プロ野球（NPB)スケジューリングへの応用
TeamName

最適なスケジュール(パリーグ)
１カード3試合; 主催試合(ホームゲーム)は赤2010 日程(km)最適(km)削減比千葉(C)SHTFO TFOSH TFOSH OSHTF HOFST FSTHO TSHOF HOFTS

23,266

16,606

28.6%

東北 (T)HFCOS COSHF CHSFO SFOCH SHOFC OFCSH CHOFS OFSCH

23,71017,97524.2%

北海道(H)

TCOSF OSFTC STFOC FOCST CTSOF SOFCT FTCSO CSOFT

28,59920,23429.2%

オリックス(O)FSHTC HTCFS FSCHT CHTFS FCTHS THSFC SFTCH TCHSF

24,12818,713

22.4%

福岡(F)

OTSCH SCHOT OCHTS HTSOC OSCTH CTHOS HOSTC STCHO

33,352

21,143

36.6%

埼玉(S)

COFHT FHTCO HOTCF TCFHO TFHCO HCOTF OCFHT FHTOC

20,885

19,498

6.6%

2010 日程（旅行回数)

最適削減比（旅行回数)

Figure 1

Figure 2

総試合数

2010日程
(km)

削減
(km)

削減比

パ・リーグ日程

6 x 120

153,940

114,169

25.8%

208

169

18.8%

セ・リーグ日程

6 x 120

79,067

57,836

26.8%199

170

14.6%

交流戦

12 x 24

51,13442,95016.0%108101

6.5%

合計

1728

284,141

214,955

24.3%

515

440

14.6%

Figure 3

This research will be presented at three conferences this summer:
R. Hoshino and K. Kawarabayashi, The Inter-League Extension of the Traveling Tournament Problem and its Application to Sports
Scheduling, 25th AAAI Conference on Artificial Intelligence (AAAI). San Francisco, USA, August 2011.
R. Hoshino and K. Kawarabayashi, The Multi-Round Balanced Traveling Tournament Problem, 21st International Conference onAutomated Planning and Scheduling (ICAPS). Freiburg, Germany, June 2011.
R. Hoshino and K. Kawarabayashi, The Distance-Optimal Inter-League Schedule for Japanese Pro Baseball, ICAPS Workshop on
Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS). Freiburg, Germany, June 2011.

連絡先 (Contact): 河原林 健一 (Ken-ichi KAWARABAYASHI), 情報学プリンシプル研究系 (Principles of Informatics Research Division)
TEL : 03-4212-2555

FAX : 03-4212-2555

Email : {rhoshino, k_keniti}@nii.ac.jp

情報学を使って日本プロ野球の日程を,現状よりもっと効率的にします
Applying informatics to optimize scheduling for Nippon Pro Baseball
星野 リチャード

河原林 健一Richard HOSHINO

Ken-ichi KAWARABAYASHI

MotivationContribution

The Government of Japan has promised to reducegreenhouse gas emissions by 25% from 1990 levels
by 2020. Informatics can help achieve this ambitious
target, where combinatorial and graph-theoretic
techniques are applied to scheduling optimization,
leading to economic and environmental benefits.

We have developed the distance-optimal schedule
for the Nippon Professional Baseball (NPB) league,eliminating 69,186 kilometres of total team travel, a
24.3% reduction compared to last year’s schedule.
Our work represents significant potential savings interms of time, money, and greenhouse gas emissions.

Theoretical Contributions
In the Traveling Tournament Problem (TTP), the output is a double round-robin schedule that minimizes the sum total of distances
traveled by all teams as they move from city to city, subject to several natural constraints to ensure balance and fairness. The TTP isa mix of integer programming and constraint programming, and is similar to the Traveling Salesman Problem only much harder!
To optimize the NPB intra-league schedule, we develop a multi-round generalization of the TTP and present an algorithm thatconverts the problem to finding the shortest path in a directed graph (see Figure 2).
To optimize the NPB inter-league schedule, we develop a bipartite generalization of the TTP, and apply a clever heuristic based onminimum-weight 4-cycle-covers (see Figure 3).

Application to the NPB
Team

Optimal Intra-League Schedule (Pacific League)
Each slot consists of three games; home games are marked in red

2010 NPB(km)

Optimal(km)PotentialReduction

Chiba (C)SHTFO TFOSH TFOSH OSHTF HOFST FSTHO TSHOF HOFTS

23,266

16,606

28.6%

Tohoku (T)HFCOS COSHF CHSFO SFOCH SHOFC OFCSH CHOFS OFSCH

23,71017,975

24.2%

Hokkaido (H)TCOSF OSFTC STFOC FOCST CTSOF SOFCT FTCSO CSOFT

28,59920,23429.2%

Orix (O)FSHTC HTCFS FSCHT CHTFS FCTHS THSFC SFTCH TCHSF

24,12818,713

22.4%

Fukuoka (F)OTSCH SCHOT OCHTS HTSOC OSCTH CTHOS HOSTC STCHO

33,352

21,143

36.6%

Saitama (S)COFHT FHTCO HOTCF TCFHO TFHCO HCOTF OCFHT FHTOC

20,885

19,498

6.6%

Figure 1

Figure 2

NPB Schedule
Components

Total
Games

2010 NPB(km)

Optimal(km)PotentialReduction2010 NPB(# Trips)

Optimal(# Trips)

PotentialReduction

Intra-League (PL)6 x 120

153,940

114,169

25.8%

208

169

18.8%

Intra-League (CL)

6 x 120

79,067

57,836

26.8%

199

170

14.6%

Inter-League (PL vs. CL)

12 x 24

51,13442,950

16.0%

108

101

6.5%

TOTAL

1728

284,141

214,955

24.3%

515

440

14.6%

Figure 3

This work will be presented at three conferences this summer:
R. Hoshino and K. Kawarabayashi, The Inter-League Extension of the Traveling Tournament Problem and its Application to Sports Scheduling,
to appear in the Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI). San Francisco, USA, August 2011.
R. Hoshino and K. Kawarabayashi, The Multi-Round Balanced Traveling Tournament Problem, to appear in the Proceedings of the 21stInternational Conference on Automated Planning and Scheduling (ICAPS). Freiburg, Germany, June 2011.
R. Hoshino and K. Kawarabayashi, The Distance-Optimal Inter-League Schedule for Japanese Pro Baseball, to appear in the Proceedings ofthe ICAPS Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS). Freiburg, Germany, June 2011.

連絡先 (Contact): 河原林 健一 (Ken-ichi KAWARABAYASHI), 情報学プリンシプル研究系 (Principles of Informatics Research Division)
TEL : 03-4212-2555

FAX : 03-4212-2150 (?)

Email : {rhoshino, k_keniti}@nii.ac.jp