Traveling Baseball Players ? ? Problem In Korea
We study the so-called the traveling tourpage_seo_titlent problem (TTP), to find an optimal tourpage_seo_titlent schedule. Differently from the original TTP, in which the total travel distance of all the participants is the objective function to minimize, we instead seek to maximize the fairness of the round robin tourpage_seo_titlent schedule of the Korean Baseball League. The standard deviation of the travel distances of teams is defined as the energy function, and the Metropolis Monte-Carlo method combined with the simulated annealing technique is applied to find the ground state configuration. The resulting tourpage_seo_titlent schedule is found to satisfy all the constraint rules set by the Korean Baseball Organization, but with drastically increased fairness in traveling distances.
Monte-Carlo simulation, optimization, traveling salesman problem, traveling tourpage_seo_titlent problem, sports tourpage_seo_titlent, baseball league
pacs:
89.65.-s,89.75.Fb
The traveling salesman problem (TSP) is the one of the most important optimization problems in computational sciences Gutin and Punnen (2002). In TSP, for given number of places to visit, a traveling salesman hopes to minimize the total travel distance within the constraint that she is allowed to visit each place only once. Hinted by the similarity to the problem of finding the ground state of a system with a rugged energy landscape, TSP has also been broadly studied in physics community Kirkpatrick et al. 1983); Lee. Choi (1994). There are also biologically motivated interesting methods in the study of TSP, such as the genetic algorithm Brady (1985) and the ant colony optimization Dorigo and Stüzle (2004); Dorigo and Gambardella (1997). Although direct formulations based on TSP have broad range of applicability, we note that there are closely-related, but different, problems in reality. One among such problems is the scheduling of games in sports: In contrast to TSP, which is unilateral, i.e., the traveling salesman is not required to take into account existences of other salesmen, many sports games are bilateral, i.e., two teams or players should meet somewhere to play a game. Designing of a tourpage_seo_titlent schedule in sports league is notoriously difficult problem to solve, which has been studied mostly in the area of computational science Briskorn (2008); Kendall et al. (2010). Recently, there has been a significant development in the traveling tourpage_seo_titlent problem (TTP) Easton et al. (2001), in which the task is to construct the optimal timetable to minimize the total travel distance under the constraint of a given home-and-away pattern. Not surprisingly, the simulated-annealing method Anagnostopoulos et al. (2006), and the ant colony optimization method Chen et al. (2007) have been applied, as well as more conventional methods in computer science Trick (2001); *schaerf, to tackle TTP and similar problems.
In this work, we study the TTP, but with an important alteration: Instead of minimizing the total travel distance, we minimize the unfairness of the travel distance. This, we believe, is even more important than just minimizing the total travel distance summed over all the teams in the sports league. If one team should travel much longer distance than others, the team has less chance to win the tourpage_seo_titlent. Consequently, for the sake of fairness, the difference of the travel distance of each team must be made as small as possible, even though it might sacrifice the total sum of the travel distances of all the teams. In this respect, the present work is related with discussions of social justice in which equality of opportunity is the one of the key issues Rawls (1999); *dworkin; *skbaek. Specifically, this work is motivated by the common belief among baseball fans in Korea. One team (Lotte Giants) is located in the most southern part of Korean peninsula, and thus it is not fair for the team to compete with all others on the same ground. Interestingly, this claim, mostly by fans of Lotte Giants - they are also well known to be very enthusiastic by the way - has some truth in it, and the Korean Baseball Organization (KBO) set up a rule trying to reduce the travel distance of the Lotte Giants: KBO allows the team to have more away games in a row without returning to their home (see Sec. II).
The present paper is organized as follows: In Sec. II, we describe in detail the current scheduling scheme of KBO, which is followed by the formulation of the problem in terms of the Monte-Carlo method in statistical physics in Sec. III. The results are presented in Sec. IV, which are summarized in Sec. V with some discussion and proposal.
II Scheduling of Korean Baseball League
In Korean Baseball League (KBL), there are now eight teams as shown in Table 1. Two teams (5 and 6, Doosan Bears and LG Twins) based on Seoul, the capital of South Korea with over 10 million population, share the same stadium Jamsil. The locations of home stadiums are denoted in the form of (latitude, longitude) in Table 1. We also display the home positions of baseball teams on the map of South Korea in Fig. 1, which clearly shows that teams are not uniformly scattered across the country and that there are more teams around Seoul area. Since baseball teams usually travel by bus (in Monday afternoon and Thursday night), we measure the distance for a given pair of two teams by the output from the path finding service provided by a company in Internet. More specifically, we type in the location of the stadium of the team i??iitalic_i as the departure position, and then that of the team j??jitalic_j as the destination position. The Web service provided by the company Naver (http://www.naver.com) then returns us the distance dijsubscript??????d_ijitalic_d start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT and the estimated time tijsubscript?¡????t_ijitalic_t start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT for the travel path from i??iitalic_i to j??jitalic_j, as shown in Tables 2 and 3, respectively. It is to be noted that dij?djisubscript??????subscript??????d_ij\neq d_jiitalic_d start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT ?italic_d start_POSTSUBSCRIPT italic_j italic_i end_POSTSUBSCRIPT, and tij?tjisubscript?¡????subscript?¡????t_ij\neq t_jiitalic_t start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT ?italic_t start_POSTSUBSCRIPT italic_j italic_i end_POSTSUBSCRIPT, although the differences are not so substantial. Figure 2 displays (a) di¯?(1/16)?j=18(dij+dji)¯subscript????116superscriptsubscript??18subscript??????subscript??????\bard_i\equiv(1/16)\sum_j=1^8(d_ij+d_ji)over¯ start_ARG italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_ARG ? ( 1 / 16 ) ? start_POSTSUBSCRIPT italic_j = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 8 end_POSTSUPERSCRIPT ( italic_d start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT italic_j italic_i end_POSTSUBSCRIPT ) and (b) ti¯?(1/16)?j=18(tij+tji)¯subscript?¡??116superscriptsubscript??18subscript?¡????subscript?¡????\bart_i\equiv(1/16)\sum_j=1^8(t_ij+t_ji)over¯ start_ARG italic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_ARG ? ( 1 / 16 ) ? start_POSTSUBSCRIPT italic_j = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 8 end_POSTSUPERSCRIPT ( italic_t start_POSTSUBSCRIPT italic_i italic_j end_POSTSUBSCRIPT + italic_t start_POSTSUBSCRIPT italic_j italic_i end_POSTSUBSCRIPT ), respectively. We note that Lotte, Kia, and Samsung have larger average distances and times than other teams. The shorter average distances for Doosan, LG, SK, and Nexen are because of their locations near Seoul, and Hanwha has a short average distance because it is located in the middle of the country. From Fig. 2, we recognize that if the tourpage_seo_titlent scheduling is made without any consideration of the inequality of the average distances, some teams must travel longer distances spending longer times in traffic than other teams, and thus those teams might have less chance to win the games. The original formulation of TTP was made to minimize the total travel distances of all teams. However, in view of the unequal distance distribution in KBL (see Fig. 2), it is natural to shift the optimization focus toward the fairness of the tourpage_seo_titlent schedule, which will be the main research theme of the present work.
We next describe the tourpage_seo_titlent scheduling scheme of KBO in detail. At the time of writing of the present paper (year 2012), each team in one season plays 133 games, which corresponds to 19 (=133/7)absent1337(=133/7)( = 133 / 7 ) games for each pair of two teams, making the total number of games 532 (=133?8/2)absent?13382(=133\cdot 8/2)( = 133 ? 8 / 2 ). The scheduling constraints set by KBO are as follows:
1.
The number of home/away games are either 66/67 or 67/66 (with 66+67=133666713366+67=13366 + 67 = 133), respectively. If a team had 66 (67) home games in the last season, 67 (66) home games are assigned. In 2011, Kia, LG, Hanwha, and Nexen had 67 home games and Samsung, SK, Lotte, and Doosan had 66 home games. In 2012, therefore, the four former teams should have 66 home games and the latter 67 home games.
2.
There is no game on Monday. From Tuesday to Thursday two teams play three games in a row at the same stadium (home stadium of one of the two teams), and then move to other stadium to play three more games in a row from Friday to Sunday.
3.
The first week of the season is an exception: New season starts with an opening ceremony on Saturday. Each team plays two games on Saturday. Sunday without changing counterpart. The four stadiums of the first week are the homes of the top four teams of the season 2010 (SK, Samsung, Doosan, and Lotte). The final rank in 2010 determines the counterpart of each game [rank 1 (SK) plays with rank 5 (Kia), 2 (Samsung) with 6 (LG), 3 (Doosan) with 7 (Nexen), and 4 (Lotte) with 8 (Hanwha)].
4.
Among all 532 games, the game fixture for the first 500 games are fixed before the season starts (see Table 4). First week has 8 games, and from the second week 24 games are held every week. The third week of July (the 16th week of the season) is another exception. Regular season matches are held only for the first half of the week. On Saturday (July 21) there will be a special event so-called ”All Star Game”. Accordingly, after 22 weeks, all 500 [=8absent8=8= 8 (the 1st week) + 12121212 (the 3rd week of July) +24?20?242024\cdot 2024 ? 20 (regular weeks)] games are played, and remaining 32 games start from September 2. Fixture of those remaining 32 games will be determined during the season, reflecting the unavoidable changes made by e.g., canceled game due to heavy rain.
5.
Around the Children’s’ Day in Korea (May 5), the most popular day for kids to watch a baseball game in a stadium with family, four stadiums for three consecutive games are chosen as the homes of Samsung, SK, Kia, and LG. Every second year, the four teams alternate so that Doosan, Nexen, Lotte, and Hanwha will be the ones in the 2013 season.
6.
No team is allowed to play more than 6 home games consecutively.
7.
No team is allowed to play more than 6 away games consecutively, with one exception: KBO noticed the longer travel distance of Lotte, and allows the team to play 9 away games in a row, before the 500th game of the season (from June 15 to 24 in the 2012 season). In Table 4, we underline those 9 games in the 11th and 12th weeks of the schedule.
The above scheduling rules set by KBO show that the organization is trying to provide equal bases for all the teams. Especially, the rule 7 makes Lotte an exception to compensate the team’s longer distance as shown in Tables 2 and 3, and Fig. 2. We use the KBO schedule for the 2012 season in Table 4, to compute the total traveling distance and time of the season. For example, the team SK plays three home games at Munhak stadium in the 1st week (?d=0??0\sum d=0? italic_d = 0), and travels to Mokdong stadium to play three away games with NX (?d=d28??subscript??28\sum d=d_28? italic_d = italic_d start_POSTSUBSCRIPT 28 end_POSTSUBSCRIPT), and then back to Munhak stadium for three home games with HH (?d=d28+d82??subscript??28subscript??82\sum d=d_28+d_82? italic_d = italic_d start_POSTSUBSCRIPT 28 end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT 82 end_POSTSUBSCRIPT) in the 2nd week. SK keeps traveling following the schedule in Table 4 so that its total traveling distance is ?d=d28+d82+d23+d35+d52+?+d24??subscript??28subscript??82subscript??23subscript??35subscript??52?subscript??24\sum d=d_28+d_82+d_23+d_35+d_52+\cdots+d_24? italic_d = italic_d start_POSTSUBSCRIPT 28 end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT 82 end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT 23 end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT 35 end_POSTSUBSCRIPT + italic_d start_POSTSUBSCRIPT 52 end_POSTSUBSCRIPT + ? + italic_d start_POSTSUBSCRIPT 24 end_POSTSUBSCRIPT. When there are consecutive away games before and after Monday, we assume that the team travels directly from one place to other, without having a break on Monday at the team’s home. We also compute the total traveling time similarly to the total traveling distance, and list the both in Table 5. Clearly seen in Table 5 is that the above KBO rules do not successfully reduce the unequal distribution of traveling distances and times. For example, even though Lotte is given an exception (the rule 7) the team travels much longer distance (66%) than LG. Another interesting observation is that although Doosan and LG are located at the same home position, the travel distances are quite different: Doosan travels 23% longer distance compared to LG.
III Formulation
The total traveling distance of the team i??iitalic_i is given by
di=?(k,l)dkl,subscript????subscript????subscript??????d_i=\sum_(k,l)d_kl,italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = ? start_POSTSUBSCRIPT ( italic_k , italic_l ) end_POSTSUBSCRIPT italic_d start_POSTSUBSCRIPT italic_k italic_l end_POSTSUBSCRIPT , (1)
where the sum is over the traveling path for a given schedule, and dklsubscript??????d_klitalic_d start_POSTSUBSCRIPT italic_k italic_l end_POSTSUBSCRIPT is the distance from k??kitalic_k to l??litalic_l in Table 2. Differently from the usual TTP in which the objective function to minimize is ?idisubscript??subscript????\sum_id_i? start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT, we in this work propose to minimize the unfairness of the schedule, measured by the standard deviation of disubscript????d_iitalic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT. In analogy to the statistical physics problem finding the ground state of a system, we call it as “energy” E?¸Eitalic_E of the system, although the term does not mean much in the context of baseball game scheduling. Our objective function to minimize in the present work is given by
E=18?i=18(di-m)2=?di2?-?di?2??d,?¸18superscriptsubscript??18superscriptsubscript??????2delimited-??superscriptsubscript????2superscriptdelimited-??subscript????2subscript????E=\sqrt\frac18\sum_i=1^8(d_i-m)^2=\sqrt\langle d_i^2\rangle% -\langle d_i\rangle^2\equiv\sigma_d,italic_E = square-root start_ARG divide start_ARG 1 end_ARG start_ARG 8 end_ARG ? start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 8 end_POSTSUPERSCRIPT ( italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT - italic_m ) start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG = square-root start_ARG ? italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ? - ? italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ? start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG ? italic_? start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT , (2)
where the mean m??di??(1/8)?i=18di??delimited-??subscript????18superscriptsubscript??18subscript????m\equiv\langle d_i\rangle\equiv(1/8)\sum_i=1^8d_iitalic_m ? ? italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ? ? ( 1 / 8 ) ? start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 8 end_POSTSUPERSCRIPT italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT, and ?di2??(1/8)?i=18di2delimited-??superscriptsubscript????218superscriptsubscript??18superscriptsubscript????2\langle d_i^2\rangle\equiv(1/8)\sum_i=1^8d_i^2? italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ? ? ( 1 / 8 ) ? start_POSTSUBSCRIPT italic_i = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 8 end_POSTSUPERSCRIPT italic_d start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT. In contrast to the original TTP to minimize m??mitalic_m, our purpose here is to minimize E?¸Eitalic_E. In the ideal situation of E=0?¸0E=0italic_E = 0, all teams travel equal total distances, while the larger is E?¸Eitalic_E, the more unfair the schedule becomes. We also use the standard deviation ?tsubscript???¡\sigma_titalic_? start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT of the travel time ti??(k,l)tklsubscript?¡??subscript????subscript?¡????t_i\equiv\sum_(k,l)t_klitalic_t start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ? ? start_POSTSUBSCRIPT ( italic_k , italic_l ) end_POSTSUBSCRIPT italic_t start_POSTSUBSCRIPT italic_k italic_l end_POSTSUBSCRIPT with tklsubscript?¡????t_klitalic_t start_POSTSUBSCRIPT italic_k italic_l end_POSTSUBSCRIPT being the travel time from k??kitalic_k to l??litalic_l in Table 3, to define the energy function E?¸Eitalic_E.
In statistical physics, finding of the ground state configuration of a model system is the one of the most well-developed topics. The standard way to tackle the issue is to set up an energy function of the given model system and minimize the energy in a systematic way. In this regard, the most standard methodology is to use the Monte-Carlo (MC) simulation technique Newman and Barkema (1999). The standard Metropolis algorithm for local update is adopted: The local MC try with the energy difference ?E??¸\Delta Eroman_? italic_E is accepted if ?E?0??¸0\Delta E\leq 0roman_? italic_E ? 0. Otherwise (i.e., if ?E>0??¸0\Delta E>0roman_? italic_E >0), the MC try is accepted at the probability of e-?E/Tsuperscript????¸??e^-\Delta E/Titalic_e start_POSTSUPERSCRIPT - roman_? italic_E / italic_T end_POSTSUPERSCRIPT with the temperature T??Titalic_T. The Metropolis MC method is then combined with the simulated annealing technique. In more detail, we start from a high temperature, and decrease the temperature slowly until the zero temperature is reached. The similar MC method with the simulated annealing technique has been applied for the TSP Kirkpatrick et al. (1983). In Ref. Lee and Choi, 1994, a microcanonical MC method combined with an annealing technique called the entropic annealing method has also been applied for the TSP. In the present study, we do not aim at developing a more advanced methodology in finding the fairest tourpage_seo_titlent schedule, but we simply apply the well-known simulated annealing MC method to tackle the problem. Accordingly, we do not claim that we have found the fairest schedule of the KBL, but rather like to emphasize that a simple application of the well-known methodology in statistical physics can significantly increase the fairness of the schedule of the KBL.
The other important issue to discuss is what are the local update rules allowed in the MC simulation. In Ref. Anagnostopoulos et al., 2006, all five different ways of update are proposed: SwapHomes, SwapRounds, SwapTeams, PartialSwapRounds, and PartialSwapTeams. It has been shown that the first three swapping methods are not sufficiently efficient to explore the entire configuration space Anagnostopoulos et al. (2006); Chen et al. (2007). In this work, we only use SwapRounds and SwapHomes for updates due to their simplicity: In the former we pick two different rounds, e.g., Fri-Sun of the week 7 and Tue-Thu of the week 6, and swap the two entirely. In the SwapHomes update, we pick two pairs, e.g., NX/SK and SK/NX at two different rounds Tue-Thu of the week 2 and Fri-Sun of the week 6, and then swap the two. These two update methods (SwapRounds. SwapHomes) are the simplest ones among the five in Ref. Anagnostopoulos et al., 2006 and it is clear that the two update methods preserve the KBO rules explained in Sec.II if the schedule in Table 4 is used as an initial configuration of MC simulations.
IV Results
We start from a sufficiently high temperature T=100??100T=100italic_T = 100 with the KBO schedule in Table 4 as an initial condition and decrease T??Titalic_T slowly with the temperature step ?T=1.0???1.0\Delta T=1.0roman_? italic_T = 1.0 until T=0??0T=0italic_T = 0 is arrived. For 22 weeks of the season in Table 4, there are all 42 rounds, with two rounds per week except for the 1st and 16th weeks. At each temperature, we perform 10,000 MC steps, with one MC step composed of one SwapRounds update and one SwapHomes updates per round. Our update rules do not change the number of home games and away games for each team, and thus the rule 1 of KBO in Sec. II is automatically obeyed. The schedule of the first week is fixed (rule 3) in our simulation, and the “All Star Game” in the 16th week is also fixed (see rule 4). No teams are allowed to have more than six consecutive home games (rule 6), nor six consecutive away games (rule 7). The exception made for Lotte (rule 7 in Sec. II) is not necessary in our simulation. The rule 5 on the home stadiums around the Children’s Day is also obeyed during simulations. Consequently, all rules (except the unnecessary exception for Lotte in rule 7) are equally obeyed for all teams during our simulations at any temperature, and the ground state as an outcome of the simulated annealing MC simulations gives us the tourpage_seo_titlent schedule that is expected to be as fair as possible in terms of the travel distance (for E=?d?¸subscript????E=\sigma_ditalic_E = italic_? start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT) or the travel time (E=?t?¸subscript???¡E=\sigma_titalic_E = italic_? start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT). We repeat the same annealing procedure 10 times for the fairness of traveling distances (E=?d?¸subscript????E=\sigma_ditalic_E = italic_? start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT) and once for the fairness of traveling times (E=?t?¸subscript???¡E=\sigma_titalic_E = italic_? start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT). The results are almost the same for E=?d?¸subscript????E=\sigma_ditalic_E = italic_? start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT and E=?t?¸subscript???¡E=\sigma_titalic_E = italic_? start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT, and we below mostly present our results for the former.
In Fig. 3, we show the evolution of (a) ?dsubscript????\sigma_ditalic_? start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT and (b) m??mitalic_m in Eq. (2) during MC simulated annealing. As the temperature is lowered, it is shown that our simulation successfully lowers the energy, or increase fairness in the travel distance. Although our simulation tries to minimize ?dsubscript????\sigma_ditalic_? start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT, m??mitalic_m is also found to decrease as a byproduct of annealing as shown in Fig. 3(b). Ten independent simulated annealing with E=?d?¸subscript????E=\sigma_ditalic_E = italic_? start_POSTSUBSCRIPT italic_d end_POSTSUBSCRIPT give us ten ground state configurations, and the one with the lowest energy has the configuration tabulated in Table 6. We emphasize that our optimized baseball schedule keeps all the scheduling constraints by KBO, but with significantly enhanced fairness in travel distances.
In Table 7, we list the total traveling distances of teams for the ground state configuration in Table 6. In comparison to the corresponding values for the actual schedule run by KBO in Table 5, our optimized schedule clearly has more even distribution of travel distances. In Table 7, we also include the result from our MC simulated annealing with E=?t?¸subscript???¡E=\sigma_titalic_E = italic_? start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT, i.e., the fairness in traveling times as the objective function. The traveling time of each team has much smaller variance in comparison to the original schedule by KBO.
To summarize our main findings, we plot in Fig. 4 the traveling distances for (a) the KBO schedule in Tables 4 and 5 and (b) our optimized schedule in Tables 6 and 7. Clearly revealed is that our optimization scheme results in much better fairness in travel distances. The corresponding plot for the total traveling time looks very similar to Fig. 4 and thus not included in the present paper. Although the team Lotte still has the longest distance to travel, the difference to LG is now only about 6% (compared to 66% in original KBO schedule). Also, the difference between LG and Doosan shrinks to 2% (compared to 23% in KBO schedule). We also report somehow unexpected result of our scheme: Although not intended, the total sum of all the traveling distances of eight teams in our optimized schedule has smaller value than the one for the original KBO schedule. Accordingly, we conclude that we manage to find better schedule in terms of both fairness and effectiveness, in comparison to the KBO schedule.
V Summary and Discussion
We have studied numerically the traveling tourpage_seo_titlent problem in Korean Baseball League. Instead of using the total sum of traveling distances as the objective function to minimize, we focus on the fairness in the traveling distances of baseball teams. More specifically, we use the standard deviation of the traveling distance as the energy function in statistical mechanics, and apply the simulated annealing Monte-Carlo method to find the ground state configuration. The resulting timetable for the baseball games for year 2012 is shown to be better than the schedule posted by the Korean Baseball Organization, in terms of both the fairness, and the effectiveness. In other words, our optimized schedule yields more equal traveling distances across teams, and the total sum of total traveling distances is shorter than the corresponding value of the posted schedule by the organization.
We admit that there could be some other implicitly posed constraints not reflected in our simulations. However, if those constraints are explicitly revealed to public, our methodology can be applied with little changes in the MC program. We strongly believe that statistical physics approach like presented in this work has a broad applicability in a broad range of problems we encounter everyday, and hope to get encountered by more interesting problems in the real world of society.
Acknowledgements.
This work was done as a team project in the 9th KIAS-APCTP Winter School on Statistical Physics in Korea (2012). B.J.K. was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No. 2011-0015731).
Featured Products
