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

Pavlik, John

Permalink

https://hdl.handle.net/2142/113022 Copy

Description

Title

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

Author(s)

Pavlik, John

Issue Date

2021-07-12

Director of Research (if dissertation) or Advisor (if thesis)

Jacobson, Sheldon

Doctoral Committee Chair(s)

Jacobson, Sheldon

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2021-08

Type of Resource

Thesis

Permalink

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

Copyright and License Information

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

Owning Collections