The Traveling Baseball Fan Problem

Model formulation

$$ \begin{array}{rrcll} \text{minimize:} & \text{Total Time} \\ \text{subject to:} & \text{Balance} \\ & \text{Visit all stadiums once} \end{array} $$$$ \begin{array}{rlcll} \textrm{minimize:} & \sum_{(g_1, g_2) \in \text{ARCS}} c[g_1,g_2] \cdot u[g_1,g_2] \\ \textrm{subject to:} & \sum_{(g,g_2) \in \text{ARCS}} u[g,g_2] - \sum_{(g_1,g) \in \text{ARCS}} u[g_1,g] &= & \begin{cases} 1 & \text{if } g = \text{source,} \\ -1 & \text{if } g = \text{sink,} \\ 0 & \text{otherwise}\end{cases} & & \forall g \in \text{NODES} \\ & \sum_{(g1,g2) \in \text{ARCS}: g_2 \not = \text{sink and } l[g_2] = s} u[g_1, g_2] & = & 1 & & \forall s \in \text{STADIUMS} \end{array} $$

Solutions

In [1]:
# Import packages
import os
import pandas as pd
import folium

from bokeh.models.callbacks import CustomJS
from bokeh.io import output_notebook
from bokeh.layouts import column, row
from bokeh.models import HoverTool, ColumnDataSource, TapTool, Div
from bokeh.plotting import figure, show
from dateutil.parser import parse
from IPython.core.display import display, HTML
In [2]:
# Parse all solutions
solutions = []
for filename in sorted(os.listdir(os.getcwd() + '/results'), reverse=True):
    f = open('results/'+filename, 'r')
    rowx = {'ref': filename}
    for line in f:
        if 'schd' in line:
            rowx['schd'] = []
            for visit in f:
                if ']' not in visit:
                    items = visit.split(',')
                    items = [i.replace('\n','') for i in items]
                    rowx['schd'].append(items)
        elif ': ' in line:
            pl = line.split(': ')
            rowx[pl[0]] = pl[1].replace('\n','')
    rowx['df'] = pd.DataFrame(rowx['schd'], columns=['ID', 'Venue', 'Away', 'Home', 'City', 'Date', 'Lat', 'Long']).set_index(['ID'])
    rowx['df'] = rowx['df'].to_html(columns=['Away', 'Home', 'Venue', 'City', 'Date'])
    solutions.append(rowx)
    f.close()
In [3]:
# Generate source for plots and maps
solutions = sorted(solutions, key=lambda x: (round(float(x['mont'])), x['sdat'], x['objt']))
linef = '{:>2} {:>2} {:>11} {:>5} {:>4} {:>13} {:>12} {:>16} {:>12}'

df_source = []

for i, v in enumerate(solutions):
    period = v['sdat'][5:] + '/' + v['edat'][5:]
    df_source.append([
        i+1, v['ref'].split('.')[0], float(v['objt']), period, float(v['mont']), float(v['vars']), float(v['cons']),
        float(v['solv'].split()[0]), float(v['time'].split()[0]),
        float(v['dist'].split()[0]), float(v['cost'].split()[0]), v['df']
    ])

# Draw all maps
allhtml = []
for no, i in enumerate(solutions):
    mapname = 'maps/{}.html'.format(no+1)
    if not os.path.isfile(mapname):
        route = i['schd']
        tbfmap = folium.Map(location=[39.82, -98.58], zoom_start=4, tiles="OpenStreetMap")
        for node in route:
            popup_text = '''
            Game {}: {} @ {}<br>
            {}, {}<br>
            {}            
            '''.format(node[0], node[2], node[3], node[1], node[4],
                       parse(node[5]).strftime("%A, %B %d, %Y - %I:%M %p"))
            folium.Marker(location=[float(node[6]), float(node[7])],popup=popup_text,
                          #icon=folium.Icon(icon='adjust', prefix='fa')
                          icon=folium.DivIcon(html='<i class="fa fa-map-pin fa-stack-2x" style="font-size:28px"></i><strong style="text-align: center; color: white; font-family: Helvetica Neue, Helvetica, Arial; font-size:12px; width:16px;" class="fa-stack-1x">{}</strong>'.format(node[0]))
                          ).add_to(tbfmap)

        lines = folium.PolyLine(locations=[(float(i[6]), float(i[7])) for i in route])
        lines.add_to(tbfmap)
        tbfmap.save(mapname)
    allhtml.append('<iframe width="100%" height=500px src="{}"></iframe>'.format(mapname))

maps=ColumnDataSource(data=dict(map=allhtml))

Solution Table

In [4]:
# Prepare and print plot data

df = pd.DataFrame(
    df_source,
    columns=[
        'id', 'ref', 'objt', 'period', 'mont', 'vars', 'cons', 'solv',
        'time', 'dist', 'cost', 'html'
    ]).set_index(['id'])

axis_map = {
    "Tour Length": 'tour', "Tour Distance": 'dist', "Tour Cost": 'cost', "Period Length": 'mont'
}

df2=df.rename(columns = {'ref': 'Reference', 'objt':'Obj. Type', 'period': 'Period', 'mont': 'P.Length', 'vars': '# Variables', 'cons': '# Constraints',
                        'solv': 'Solve Time (secs)', 'time': 'Tour Time (days)', 'dist': 'Tour Distance (miles)', 'cost': 'Tour Cost ($)'})
display(HTML(df2.to_html(columns=['Period', '# Variables', '# Constraints', 'Solve Time (secs)', 'Tour Time (days)', 'Tour Distance (miles)', 'Tour Cost ($)'],index_names=False)))
Period # Variables # Constraints Solve Time (secs) Tour Time (days) Tour Distance (miles) Tour Cost ($)
1 03-28/06-01 24301.0 868.0 98.118 24.794 20007.125 8224.969
2 03-28/06-01 24301.0 868.0 646.210 25.872 12700.912 6538.527
3 06-01/08-01 22019.0 802.0 51.119 24.271 18065.080 7671.478
4 06-01/08-01 22019.0 802.0 539.105 28.292 13167.397 6969.766
5 08-01/10-01 22981.0 834.0 81.058 24.993 21884.875 8720.316
6 08-01/10-01 22981.0 834.0 554.763 29.000 11629.848 6677.462
7 03-28/07-01 36742.0 1276.0 129.182 24.271 18623.640 7811.118
8 03-28/07-01 36742.0 1276.0 1182.587 25.872 12700.912 6538.527
9 07-01/10-30 34389.0 1202.0 139.693 24.125 18912.350 7864.338
10 07-01/10-30 34389.0 1202.0 1112.149 26.333 12829.267 6630.650
11 03-28/10-30 72953.0 2446.0 471.340 24.125 18763.451 7827.113
12 03-28/10-30 72953.0 2446.0 7439.571 25.872 12700.912 6538.527
In [5]:
# Generate plots and set callbacks
callback = CustomJS(code="""
console.log('Tap event occured at x-position: ' + cb_obj.x + ',' + cb_obj.y)
""")

output_notebook()
    
def add_plots(dfv=11):
    source=ColumnDataSource(df)
    divtext = '<h2>Solution: {}</h2>Length: '.format(dfv) + str(df.iloc[dfv-1, 7]) + ' days, Distance: '\
              + str(df.iloc[dfv-1, 8]) + ' miles, Cost: ' + str(df.iloc[dfv-1,9]) + ' USD ' + allhtml[dfv-1]
    divtext += '<center>' + df.iloc[dfv-1, 10] +'</center>'
    div = Div(width=900, height=1600,
              text=divtext)

    hover = HoverTool(tooltips=[
        ("ID", "@id"),
        ("Tour Time", "@time days"),
        ("Tour Distance", "@dist miles"),
        ("Tour Cost", "@cost USD"),
        ("Obj. Type", "@objt"),
        ("Period", "@mont months"),
        ("Num of Variables", "@vars"),
        ("Num of Constraints", "@cons"),
        ("Solve Time", "@solv secs"),
    ])

    plots = [None]*4
    plot_pairs = [
        ('dist', 'time'),
        ('dist', 'cost'),
        ('solv', 'vars'),
        ('solv', 'time')    
    ]
    plot_labels = [
        ('Tour Distance (miles)', 'Tour Time (days)'),
        ('Tour Distance (miles)', 'Tour Cost (USD)'),
        ('Solve Time (secs)', 'Number of Variables'),
        ('Solve Time (secs)', 'Tour Time (days)')
    ]
    
    for i, pp in enumerate(plot_pairs):
        
        hover = HoverTool(tooltips=[
            ("ID", "@id"),
            (plot_labels[i][0], "@{}{{0.0}}".format(pp[0])),
            (plot_labels[i][1], "@{}{{0.0}}".format(pp[1]))
        ])
        
        plots[i] = figure(plot_width=450, plot_height=300,
                          tools=[hover, 'save', 'pan', 'tap', 'box_zoom', 'reset']
                         )
        c = plots[i].circle(
                     x=pp[0], y=pp[1], 
                     source=source, size=15,
                     hover_fill_color="pink",
                     selection_fill_color="green",
        )
        plots[i].xaxis.axis_label = plot_labels[i][0]
        plots[i].yaxis.axis_label = plot_labels[i][1]
        taptool = plots[i].select(type=TapTool)
        code = '''
        var s = source.selected['1d'].indices[0];
        div.text = '<h2>Solution: ' + (s+1) + '</h2>Length: ' +
                    source.data.time[s] + ' days, Distance: ' + 
                    source.data.dist[s] + ' miles, Cost: ' + 
                    source.data.cost[s] + ' USD ' + maps.data.map[s] +
                    '<center>' + source.data.html[s] + '</center>';
        '''
        taptool.callback = CustomJS(args=dict(source=source, maps=maps,
                                              div=div
                                             ), code=code)

    display(HTML('<h1 id="plots">Plots</h1><strong>Click on the solution you would like to display</strong>'))
    show(column(row(plots[0], plots[1]),row(plots[2], plots[3]), row(div)))

add_plots(9)
Loading BokehJS ...

Plots

Click on the solution you would like to display