The objective of the bar crawl optimization problem is to select a set of bars and determine an ordering to visit them so as to optimize the objective function subject to any constraints on the bar crawl. The objective function may include a single criterion or multiple criteria, and the constraints may include requirements to include one or more specific locations, limits on the cost of drinks, restrictions on operating hours, etc.
Problem Statement
According to Wikipedia, a bar crawl, or a pub crawl, is the act of one or more people drinking in multiple bars or pubs in a single night, normally walking or busing to each one between drinking. The Oxford English Dictionary reports that the term pub crawl and it variants have been in use since the late 19th century.
A bar crawl can be an informal outing for a group of friends or an organized event attracting thousands of people from around the country or the world. The Guinness World Record for the most people on a pub crawl involved 4885 people in Kansas City, Missouri in June 2013 to benefit cancer research. (See Crawl for Cancer.) Wisconsin is well-known for its many pub crawls. Oshkosh hosts pub crawls in the spring and in the fall. In the greater Milwaukee area, thousands of people have attended the Wolski’s Pub Crawl, the Bay View Pub Crawl, and the Zombie Pub Crawl. On a smaller scale, the concentration of bars in downtown Madison makes it a great place for college students to participate in their own bar crawls.
The rules governing a pub crawl vary from event to event, so there are different ways of formulating the pub crawl optimization problem. In the Kansas City Crawl for Cancer, each team of 10 people paid a fixed fee to receive a ticket for two pitchers of beer at each of the 10 participating bars. For teams seeking to minimize their walking distance, the optimal sequence of bars can be obtained by solving a traveling salesman problem (TSP).
In the TSP, every location needs to be visited, and consequently, there is no value associated with visiting a location. However, in an informal bar crawl event among friends, it is unlikely that every location needs to be visited, and the “benefit” associated with visiting a bar may vary. Feillet et al. (2005) define a class of problems, called traveling salesman problems with profits, that are generalizations of the TSP. In the TSP with profits, a profit is associated with each location and not every location must be visited. The overall goal is the simultaneous optimization of the collected profit and the travel costs. (Note that the problems are defined assuming that the tour starts and finishes at a defined location.) Within the class, they define three variations:
- profitable tour problems: the objective is to find a circuit that minimizes the travel costs minus the collected profit.
- orienteering problems: the objective is to find a circuit that maximizes the collected profit subject to the travel costs not exceeding a specified value.
- prize-collecting traveling salesman problems: the objective is to find a circuit that minimizes travel costs subject to the collected profits not being less than a specified value.
While one could reasonably cast the bar crawl optimization problem as any one of these problems, we consider a version of the bar crawl optimization problem that is similar to the profitable tour problem. There are two main differences. First, we do not specify in advance a starting/ending location. Second, most college students are budget-constrained, so we add a budget constraint to the problem. Given a set of nodes (bars), the pairwise distances between the nodes (bars), the benefit and the cost of visiting each node (i.e., the value of one drink and the cost of one drink at each bar), and a maximum available budget, the objective of the pub crawl optimization problem is to find a tour through a subset of the nodes so as to maximize the collected benefits minus the distance walked subject to a maximum available budget for drinks. Since the benefits and the distances are measured in different units, we include an objective weighting parameter alpha (\(\alpha\)).
Mathematical Formulation
Sets
\(V\) = set of nodes
\(A\) = \(\{(i,j): i \in V, j \in V, i \neq j\}\) = set of links
Parameters
\(\alpha\) = weighting value for objective function
\(d_{ij}\) = distance between nodes \(i\) and \(j\), \(\forall (i,j) \in A\)
\(b_j\) = “benefit” associated with a drink at node \(j\), \(\forall j \in V\)
\(c_j\) = cost of one drink at node \(j\), \(\forall j \in V\)
\(B\) = maximum available budget
Variables
\(x_{ij}\) = 1 if link \((i,j)\) is selected, 0 otherwise, \(\forall (i,j) \in A\)
\(y_j\) = 1 if node \(j\) is included in the tour, 0 otherwise, \(\forall j \in V\)
Bar Crawl Optimization Formulation
maximize \(\sum_{j \in V} b_j y_j – \alpha*\sum_{(i,j) \in A} d_{ij} x_{ij}\)
subject to exiting a node on the tour
\(\sum_{(i,j) \in A} x_{ij} – y_i = 0, \forall i \in V\)
subject to entering a node on the tour
\(\sum_{(i,j) \in A} x_{ij} – y_j = 0, \forall j \in V\)
subject to drink cost budget constraint
\(\sum_{j \in V} c_j y_j \leq B\)
subject to subtour elimination constraints
\(\sum_{i \in S} \sum_{j \in S} x_{ij} \leq |S| – 1, \forall S \subseteq V, 2 \leq |S| \leq |V|-1\)
To solve instances of this integer linear programming problem, we can use one of the NEOS solvers in the Mixed Integer Linear Programming category.
AMPL Model
Included below is an AMPL model for a small instance of the bar crawl optimization problem. Note that the model includes only a small set of the subtour elimination constraints, namely constraints to eliminate two-cycles and constraints to eliminate three-cycles (when necessary).
set V;
set LINKS := {i in V, j in V: i <> j};
param alpha >= 0;
param d{LINKS} >= 0;
param b{V} >= 0; #default benefit of visiting a bar
param c{V} >= 0; # default cost of one drink
param B default 30; # default maximum budget for drinks
var x{LINKS} binary;
var y{j in V} binary;
maximize benefit_minus_distance:
sum{j in V} b[j]*y[j] - alpha*sum{(i,j) in LINKS} d[i,j]*x[i,j];
subject to exit{i in V}:
sum{(i,j) in LINKS} x[i,j] - y[i] = 0;
subject to enter{j in V}:
sum{(i,j) in LINKS} x[i,j] - y[j] = 0;
subject to budget:
sum{j in V} c[j]*y[j] <= B;
subject to two_cycles{(i,j) in LINKS}:
x[i,j] + x[j,i] <= 1;
subject to three_cycles{(i,j) in LINKS, k in V: i <> k and j <> k}:
x[i,j] + x[j,k] + x[k,i] <= 2;
data;
set V := 1 2 3 4 5 6 7 8 9 10;
param alpha := 0.5;
param bonus := 1 550 2 600 3 450 4 650 5 700 6 800 7 1000 8 250 9 850 10 750;
param c := 1 4 2 4 3 4 4 5 5 5 6 4 7 6 8 4 9 5 10 5;
param d : 1 2 3 4 5 6 7 8 9 10 :=
1 . 4224 3168 1056 3696 427 5280 528 1056 2112
2 4224 . 1056 5280 6336 4224 1584 3696 4752 4224
3 3168 1056 . 4224 5808 3168 2112 2640 4224 3696
4 1056 5280 4224 . 2640 1584 6336 1584 141 1056
5 3696 6336 5808 2640 . 4224 7392 4224 2640 3696
6 427 4224 3168 1584 4224 . 5808 528 1584 1056
7 5280 1584 2112 6336 7392 5808 . 4752 6336 5808
8 528 3696 2640 1584 4224 528 4752 . 1584 1056
9 1056 4752 4224 141 2640 1584 6336 1584 . 1056
10 2112 4224 3696 1056 3696 1056 5808 1056 1056 .
;
If we submit the model to AMPL-Gurobi, we obtain the following output:
Gurobi 5.5.0: optimal solution; objective 1732
58 simplex iterations
x :=
1 6 1
4 9 1
6 10 1
9 1 1
10 4 1
;
The \(x_{ij}\) variables at value 1 in the solution indicate an ordering of the bars on the tour (loop) but not an origin. Starting at bar 1, the sequence would be 1-6-10-4-9-1 but any one of the bars is eligible to be the starting point. To compute the value of the objective function, we consider the total drink benefit (550+800+750+650+850 = 3600) minus alpha (0.5) times the total walking distance (427+1056+1056+141+1056 = 3736) to get 3600 – 0.5*3736 = 1732.
Solution Analysis
Let’s explore how the solution changes as alpha varies. We solved the AMPL model with five different values of alpha: 0, 0.25, 0.5, 0.75, 1, and 1.25. The corresponding solutions are shown in the table below.
| alpha | obj vaue | tour | benefit | distance |
|---|---|---|---|---|
| 0 | 4750 | 4-5-6-7-10-9-4 | 4750 | 19677 |
| 0.25 | 2784 | 1-6-8-10-9-4-1 | 3850 | 4264 |
| 0.5 | 1732 | 1-6-10-4-9-1 | 3600 | 3736 |
| 0.75 | 798 | 1-4-9-10-6-1 | 3600 | 3736 |
| 1 | 117 | 1-8-6-1 | 1600 | 1483 |
| 1.25 | 0 | none | 0 | 0 |
- When alpha is zero, the objective of the problem reduces to maximizing the total benefit, regardless of the distance walked. The problem is essentially a 0-1 knapsack problem: given a set of items (drinks), each with a weight (cost) and a value (benefit), determine which items to include so that the total weight (cost) is less than or equal to the given limit (budget) and the total value (benefit) is maximized.
- As alpha increases, the objective of the problem puts increasing emphasis on minimizing the distance walked. As one can see in the table, as the value of alpha increases from 0.25 to 0.5, the benefit of the tour decreases from 3850 to 3600 and the distance of the tour decreases from 4264 to 3736 as fewer stops are included.
- At some point, alpha increases to a large enough value such that the increased emphasis on minimizing the distance walked mathematically outweighs any benefit of a tour. The result is an optimal objective function value of 0, and no tour.
References
- Feillet, D., P. Dejax, and M. Gendreau. 2005. Traveling Salesman Problems with Profits. Transportation Science 39(2), 188-205.
- Martello, S. and P. Toth. 1990. Knapsack Problems: Algorithms and Computer Implementations. J. Wiley, Chichester.