Optimizing and Filtering List of Band Tour Stops with Predetermined Number of Stops.

Operations Research
Optimization
Traveling-Salesman
Author

Nathan Reese and Landon Jordan

Published

December 7, 2025

Twenty-One Pilots Optimized Tour Route

Table of Contents:

  1. Background and Motivation

  2. Methodology Behind the Model

  3. Constructing the Model

    1. Index Legend

    2. Parameters and Variables

    3. Objective Function

    4. Constraints

  4. Data

    1. Key Factors

  5. Interpreting the results

Background and Motivation

One of the main challenges faced by Industrial Engineers is transportation logistics. Many industries constantly research routes that are most optimal for their needs. To put a creative spin on this topic, This scenario focuses on a popular band and a new tour.

Twenty-One Pilots, where plans for a hypothetical tour is being researched in four distinct regions, with a list of 5 cities per region that fit one of two requirements.

  1. Must have a high concentration of listeners within a city’s metroplex.

    • Over half on the concentration scale.

  2. Must have a venue that can accommodate a reasonable sized concert.

    Maximum Venue Capacity ≥ 30,000 People.

Marketing analysts curated a list of 20 possible cities of interest, but with a caveat that the band’s scheduling only allows for 12 cities to be played in. If they were to charge $20 per ticket, and gas prices are assumed to be $6 per gallon, in a bus with 8 miles per gallon.

Methodology Behind the Model

The main network optimization strategy covered in this class is Dijkstra’s algorithm. The model we built is loosely based off this algorithm, with slight deviation from the standard set up. Use of sub-tours with implementation of a home node, where the band will start out in and return to, at the end complete the cycle. While Sub-tours are often considered a defect with a model, this model uses them as an advantage to improve efficiency.

Each sub-tour is confined to one of four predetermined regions and each sub-tour is calculated independently. There are other work around methods that could be used alternatively, each with their own pros and cons.

  1. Sub-tour method

    Pros:

    • Accounts for constraint that would restrict sub-tours.

    • The amount of feasible routes being calculated is significantly reduced from 125,970 to 10.

    Cons:

    • While the Sub-Tours alone can be considered optimal, however, the overarching tour is not optimal.

      • Since each regional sub-tour is independent, and the aforementioned home node is user selected, travel cost and optimality between regions is not factored within model.

      • The home node would have to be adapted to separate start and end nodes, with neighboring region nodes factored in.

    • Constraint needed to prevent the model from doubling back to the home node before completing a full cycle.

      • this constraint is model is fairly simple and works as intended in our mode. However, doesn’t entirely correct non-consecutive tour cycles issue when more nodes are factored in.

        subject to NoRepetition {j in CITIES1, i in CITIES1}:= y1[i,j] + y1[j,i] <= 1;

        # i.e. cannot take node path: home - 2 - home - 3.

  2. Greedy Heuristic

    Pros:

    • Can consider route involving all 20 cities.

      • Works through the 125,970 different combinations while working towards an estimated optimal value.

    • Considered closer to optimal due to lack of regional independence.

    Cons:

    • Takes a lot more time to run while not being the optimal solution and answer is dependent on amount of time allowed to run.

      • Since it’s running through all possible combinations, it’ll take some time to compute an answer. That being said, AMPL is able to calculate an estimate that the program believes it can reach. Depending on whenever the model stops, it’ll give you a ballpark percentage on how optimal the feasible solution is displayed.

    • Data frame for distance increases from 10 different distances to 190 different distances.

      • Thus subject to higher chance of data errors.

Weighing all our options, a decision was made to move forward with implementing regional sub-tours. For extending the model, all 20 cities were factored into one consecutive tour.

Constructing the Model

This model was coded using the language AMPL, a Python based language adapted to solve linear programming models. The code present is of only one region. The only difference between each region being variable numbers and the home node moving to cities within the feasible tour route.

Index Legend

Region & City

[i = j]

{i = leaving, j = entering}

 Region & City

[i = j]

{i = leaving, j = entering}
West Coast Region - First Tour Section Index Value Mid-West Region - Second Tour Section Index Value
Los Angeles, CA 1 Minneapolis, MN 1
Phoenix, AZ 2 St. Louis, MO 2
Salt Lake City, UT 3 Chicago, IL 3
Seattle, WA 4 Detroit, MI 4
Denver, CO 5 Columbus, OH 5
Southern Region - Third Tour Section Index Value Northeastern Region - Fourth Tour Section Index Value
Houston, TX 1 Washington, D.C. 1
Dallas, TX 2 Pittsburgh, PA 2
Fayetteville, AR 3 New York City, NY 3
Tampa, FL 4 Manchester, NH 4
Atlanta, GA 5 Boston, MA 5

Parameters and Variables

set CITIES1;

param D1 {CITIES1, CITIES1} >= 0;

param A1 {CITIES1} >= 0;

param Smax1 >= 1;

param lambda1 >= 0;

param home1 symbolic;

// visit or not

var x1 {i in CITIES1} binary;

// travel arc var Tour_Revenue_WestCoast; var TC1;

var y1 {i in CITIES1, j in CITIES1} binary;

Objective Function

Formatted in a way that Tour Revenue and Travel Costs can be viewed.

// Revenue made from shows.

subject to TourRev: sum{i in CITIES1} (A1[i] * x1[i]) * 20 = TR1

subject to TravelCost: ((sum{i in CITIES1, j in CITIES1} (D1[i,j] * y1[i,j])) / 8) * 6 = TC1;

// Objective Function

maximize Obj1: TR1 - lambda1 * TC1;

Constraints

Defines that each city where a showed is played in must be entered (excluding the return home)

// Each visited city except home must have in/out degree 1

subject to FlowOut {i in CITIES1 diff {home1}}:

sum {j in CITIES1 diff {i}} y1[i,j] = x1[i];

subject to FlowIn {i in CITIES1 diff {home1}}:

sum {j in CITIES1 diff {i}} y1[j,i] = x1[i];

Each city can be entered and exited once (excluding home)

// Home can have only 1 outgoing and 1 incoming

subject to HomeOut:

sum {j in CITIES1 diff {home1}} y1[home1,j] = 1;

subject to HomeIn:

sum {i in CITIES1 diff {home1}} y1[i,home1] = 1;

subject to NoRepetition {j in CITIES1, i in CITIES1}:

y1[i,j] + y1[j,i] <= 1;

Can’t exceed 3 shows, however, not restricted from further reduction if determined optimal.

// Maximum number of visited cities

subject to ShowLimit:

sum {i in CITIES1} x1[i] <= Smax1;

Data

Key Factors

Estimated Attendance

Distance from City i to City j

Los Angeles Phoenix Salt Lake City Seattle Denver
Los Angeles 0 378 703 968 1140
Phoenix 378 0 663 1327 1419
Salt Lake City 703 663 0 766 838
Seattle 968 1327 766 0 1316
Denver 1140 1419 838 1316 0
Houston Dallas Fayetteville Tampa Atlanta
Houston 0 266 597 533 992
Dallas 266 0 368 666 1124
Fayettevile 597 368 0 709 1177
Tampa 533 666 709 0 472
Atlanta 992 1124 1177 472 0
Minneapolis St. Louis Chicago Detroit Columbus
Minneapolis 0 433 449 525 789
St. Louis 433 0 560 411 699
Chicago 449 560 0 295 528
Detroit 525 411 295 0 284
Columbus 789 699 528 284 0
D.C. Pittsburgh NYC Boston Manchester
D.C. 0 248 375 226 476
Pittsburgh 248 0 361 243 346
NYC 375 372 0 243 251
Boston 226 372 243 0 251
Manchester 476 607 346 251 0

  1. Ticket Pricing

    $20 / each

  2. Travel Cost

    $6 / gallon, 8 miles per gallon

Interpreting the results