Two graph problems: bidirectional heuristic search and the airplane seating assignment problem

This dissertation covers two different types of graph problems, bidirectional heuristic search and airplane seating assignment. Bidirectional heuristic search is used to solve for the shortest path between two given vertices in a graph. The airplane seating assignment problem (ASAP) is to find an optimal airplane passenger seating configuration to minimize their disease transmission risks. ASAP is solved by modeling the airplane seats as graph vertices and the disease transmission risks as graph edges then optimizing a mixed-integer linear model. This dissertation introduces three new algorithms to solve bidirectional heuristic search, Iterative Deepening DIBBS (IDD), Consistent-heuristic Bucket-based Bidirectional Search (CBBS), and Front-to-Front GPU Bidirectional Search (FFGBS). IDD applies the technique of iterative deepening and a new technique named h-middle filtering to solve bidirectional search problems using less memory than previous algorithms. CBBS compares buckets of nodes between the forward and backward search in order to eliminate nodes and select buckets more likely to terminate the search faster. FFGBS implements a front-to-front heuristic using the GPU to reduce the number of node expansions required while minimizing running time by exploiting the parallel nature of the GPU. Computational experiments are performed for IDD on the pancake problem, the sliding tile puzzle, and the Rubik's cube. Experiments for CBBS are performed on the pancake problem. Finally, experiments for FFGBS are performed on the pancake problem and DIMACS road networks. This dissertation introduces ASAP, two mixed integer linear models for solving ASAP, and four risk models for constructing ASAP graph instances. The two mixed integer linear models are Vertex Packing Risk minimization (VPR) and Risk-Constrained Vertex packing (RCV), both based on generalizing vertex packing. The four risk models are two influenza-based models for coughing and non-coughing symptoms (both without masks) and two SARS-CoV-2 models for masked and unmasked passengers. ASAP experiments are performed using CPLEX to solve the VPR and RCV models, demonstrating different seating arrangements on a variety of aircraft. Recommendations are made about which risk model is appropriate for different situations and how they can be translated into guidelines for aircraft seating.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Pavlik, John

Contributors dc:contributor

• Jacobson, Sheldon
• Hauser, Kris
• Smaragdis, Paris
• Sewell, Edward

• discrete algorithm
• heuristic search
• bidirectional search
• consistent heuristic
• pancake
• road
• Rubik's cube
• bidirectional heuristic search
• air travel
• covid-19
• discrete optimization
• public health

Statement dc:rights

• This material is declared a work of the U.S. Government and is not subject to copyright protection in the United States.

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/113022

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/113022