University of Illinois Urbana-Champaign

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

Pavlik, John

Content Files
PAVLIK-DISSERTATION-2021.pdf

Permalink

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

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
Date of Ingest
2022-01-12T21:45:39Z
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

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science