Theory and Algorithms Commons^™

Late-Night And Early-Morning Train Scheduling With Non-Traffic Hour Maintenance Window In Urban Rail Transit Systems, Yaochen Ma, Hai Yang, Hai Wang

Research Collection School Of Computing and Information Systems

Regular maintenance during non-traffic hours (NTH) is vital for the resilience of urban rail transit (URT) systems, yet an insufficient NTH maintenance window poses a challenge for URT systems in various cities. For instance, the Hong Kong MTR Corporation has noted that the required NTH maintenance time often exceeds the available window, prompting service adjustments such as earlier late-night closures and/or later early-morning starts. To address this challenge, this study develops an optimal scheduling framework that links late-night and early-morning URT services through the NTH maintenance window requirement to maximize public welfare. A Decoupled Optimization Model (DOM) first derives closed-form …

Extensive And Intensive Margin Labor Supply On Ride-Sourcing Platforms, Hao Sun, Hai Wang, Zhixi Wan

Research Collection School Of Computing and Information Systems

The rapid expansion of ride-sourcing platforms has enabled freelance drivers to flexibly determine both their participation and working hours. Understanding this flexible labor supply behavior is essential for managing platform capacity and evaluating the impacts of pricing and incentive policies on driver welfare. This study develops a labor supply model in which drivers optimally choose whether to participate (extensive margin) and how long to work (intensive margin) to maximize their utility from consumption and leisure. The model incorporates heterogeneity in drivers’ other income, idle time, and participation costs, allowing us to analytically characterize equilibrium labor supply decisions. The results show …

Largest 2-Regular Subgraphs In Complete S-Partite Graphs, Yiyang Jiang

McKelvey School of Engineering Graduate Student Theses & Dissertations

In this thesis, we focus on the class of complete $S$-partite graphs, for $S$ an undirected graph possibly with self-loops, and address the problem of finding largest $2$-regular subgraphs of these graphs, which can be formulated as an integer linear program. Roughly speaking, a complete $S$-partite graph is obtained by replacing every single node of $S$ with a number of nodes, preserving the edge/non-edge relations of $S$. Our motivation in studying largest $2$-regular subgraphs is rooted in the structural systems theory, particularly in the problem of finding largest subnetworks that can sustain controllability or asymptotic stability of the corresponding subsystems. …

A Knowledge Transfer-Based Membrane Evolutionary Algorithm For Solving Large-Scale Sorted Waste Collection Problem With Timeliness, Wenxue Zhang, Boquan Gao, Aldy Gunawan, Yunyun Niu, Jianhua Xiao

Research Collection School Of Computing and Information Systems

The sorted collection of municipal solid waste has emerged as an effective waste management strategy due to varying timeliness requirements across different waste types, giving rise to the critical research challenge of timeliness-based waste collection. While existing algorithms primarily focus on small-scale versions of this problem, solving large-scale timeliness-based waste collection problems remains particularly challenging. To tackle this issue, this paper proposes a knowledge transfer-based membrane evolutionary algorithm. Specifically, the original problem and simplified problem are constructed in different membranes respectively, and the knowledge transfer learning mechanism is incorporated into the membrane evolutionary algorithm, enabling effective information exchange between the …

Light Cone Cancellation For Variational Quantum Eigensolver In Solving Noisy Max-Cut, Xinwei Lee, Xinjian Yan, Ningyi Xie, Yoshiyuki Saito, Leo Kurosawa, Nobuyoshi Asai, Dongsheng Cai, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Variational Quantum Eigensolver (VQE) is a quantum-classical hybrid algorithm used to estimate the ground energy of a given Hamiltonian. It consists of a parameterized quantum circuit, which the parameters are optimized using a classical optimizer. With the increasing need in solving large-scale problems in real-world applications, solving those large problems with fewer qubits and fewer gates becomes essential, so that we reduce the simulation difficulty and mitigate the effect of noise in real quantum hardware. In this study, we applied the Light Cone Cancellation (LCC) method to reduce the number of qubits and gates required in a two-local ansatz. LCC …

Distilling The Complexity Of Agent-Based Simulations Into Textual Explanations Via Large Language Models, Noé Y. Flandre, Philippe J. Giabbanelli

VMASC Publications

Communicating the design and results of agent-based models (ABMs) to subject matter experts is challenging, which hinders participation and limits trust in simulation-based decision support. Large language models (LLMs) can communicate ABMs as textual summaries, thus complementing traditional disclosure through statistical and visualization techniques. While prior work translated the structure of conceptual models into narratives via LLMs, our extension covers the dynamics of simulation models via an automated simulation-to-text method that extracts contextual information from NetLogo ABMs, performs repeated simulations, and generates narrative descriptions (including the model’s purpose, parameters, and simulation dynamics) using mutimodal LLMs. Furthermore, four summarization algorithms spanning …

Optimizing Maintenance Routes For Highway Infrastructure Using Leader-Follower Autonomous Vehicles, Qing Tang, Chenxi Chen, Xianbiao Hu, Yuxin Ding, Tianjia Yang

Civil & Environmental Engineering Faculty Publications

The Autonomous Truck Mounted Attenuator (ATMA), a leader–follower style connected and automated vehicle system, enhances safety during transportation infrastructure maintenance in work zones. However, the significantly lower speed of ATMA, compared to regular vehicles, causes moving bottlenecks that reduce roadway capacity and prolong queuing, leading to further delays. Different ATMA routes lead to varying patterns of time-dependent capacity drop, affecting the user equilibrium traffic assignment and resulting in differing system costs. This study aims to optimize ATMA routing within a network to minimize the system cost associated with its slow-moving operation. To this end, a queuing-based traffic assignment approach is …

Advancing Real-World Implementation Of The Well Optimized Linear Finder (Wolf) High-Speed Atmospheric Turbulence Compensation Method, Timothy Evan Coon

Theses and Dissertations

This dissertation advances the real-world implementation of the Well Optimized Linear Finder (WOLF) method for high-speed Atmospheric Turbulence Compensation (ATC). Atmospheric turbulence introduces phase aberrations into optical wavefronts and degrades image quality in terrestrial imaging systems. Traditional phase diversity methods are computationally intensive and poorly suited to real-time operation. The WOLF method addresses these limitations through a novel, point-wise formulation of the optical transfer function (OTF) as a structured autocorrelation of the generalized pupil function (GPF). This formulation enables the estimation of phase aberrations at individual spatial coordinates with distributed computational complexity.

The research begins by developing a MATLAB-based simulation …

Graphtreemed: A Hybrid Graph-Tree Rag Architecture For Mission-Critical Medical Applications, Joshit Mohanty, Sandeep Kumar Nayak, Sumit Lahiri

Graduate Student Government Association Research Conference

Studies within engineering management indicate that decision-making is often based on the cognitive processing of grouped and pictographic information clusters entangled with high-level pattern recognition. Similarly, graph-based retrieval-augmented generation (RAG) architectures substantially improve diagnostic accuracy and interpretability, while tree-structured systems reduce critical misses through hierarchical reasoning. However, existing solutions often lack a unified framework that seamlessly integrates these two paradigms to address the multifaceted demands of mission-critical healthcare settings. This proposal introduces GraphTreeMed, a novel hybrid RAG architecture designed to harness the complementary strengths of graph-based and tree-based retrieval mechanisms, thereby advancing the safety and efficacy of clinical decision support …

Age Of Information-Based Optimal Scheduling With Energy Cost Trade-Off For Smart Warehouse: A Deep Reinforcement Learning-Based Approach, Sandip Roy, Abhishek Bisht, Ashok Kumar Das, Sachin Shetty

VMASC Publications

Recent advances in the integration of high-speed mobile networks and real-time IoT devices have facilitated in building of smart warehouses, where a set of beacons and Internet of Things (IoT) devices (or source nodes) can monitor the status of various physical processes in a time-critical way. In real-time status monitoring systems, like smart warehouses, quantifying the freshness of the Internet of Things (IoT) data based on the age of information (AoI) metrics becomes quite crucial. As source nodes are battery-constrained, a balanced trade-off between AoI minimization and preservation of source node battery energy is essential. In this paper, in a …

Physics-Informed Deep Learning With Kalman Filter Mixture For Traffic State Prediction, Niharika Deshpande, Hyoshin (John) Park

Engineering Management & Systems Engineering Faculty Publications

Accurate traffic forecasting is crucial for understanding and managing congestion for efficient transportation planning. However, conventional approaches often neglect epistemic uncertainty, which arises from incomplete knowledge across different spatiotemporal scales. This study addresses this challenge by introducing a novel methodology to establish dynamic spatiotemporal correlations that captures the unobserved heterogeneity in travel time through distinct peaks in probability density functions, guided by physics-based principles. We propose an innovative approach to modifying both prediction and correction steps of the Kalman Filter (KF) algorithm by leveraging established spatiotemporal correlations. Central to our approach is the development of a novel deep learning model …

Quantifying The Transfer Effectiveness Of An Artificial Intelligence-Based Simulator Pre-Training Program For Student Pilots, Ryan Guthridge

Journal of Aviation/Aerospace Education & Research

Since the airline pilot shortage was initially studied in 2016, the pilot hiring model has been significantly impacted, with airlines hiring qualified pilots at unprecedented rates. The COVID-19 pandemic has slowed this hiring rate, however it is expected that airline hiring will soon increase to a rate higher than initially expected (Bureau of Transportation Statistics, 2022). With this dynamic, certified flight instructors are often the most qualified recruits for airlines, due to the number of hours and experience they have gained in the flight training organization. In turn, certified flight instructors are in short supply for flight training organizations worldwide. …

Sampling Balanced High-Quality Data To Train An Automatic Mesh Generator, Jie Pan, Jingwei Huang, Gengdong Cheng, Yong Zeng

Engineering Management & Systems Engineering Faculty Publications

In real-world scenarios, high-quality data are often scarce and imbalanced, yet it is essential for the optimal performance of data-driven algorithmic models. Data synthesis methods are commonly used to address this issue; however, they typically rely heavily on the original dataset, which limits their ability to significantly improve performance. This article presents a quality function-based method for directly generating high-quality data and applies it to a mesh generation algorithm to demonstrate its efficiency and effectiveness. The proposed approach samples input-output pairs of the algorithm based on their feature spaces, selects high-quality samples using a defined quality function that evaluates the …

Irl For Restless Multi-Armed Bandits With Applications In Maternal And Child Health, Gauri Jain, Pradeep Varakantham, Haifeng Xu, Aparna Taneja, Prashant Doshi, Milind Tambe

Research Collection School Of Computing and Information Systems

Public health practitioners often have the goal of monitoring patients and maximizing patients’ time spent in “favorable” or healthy states while being constrained to using limited resources. Restless multi-armed bandits (RMAB) are an effective model to solve this problem as they are helpful to allocate limited resources among many agents under resource constraints, where patients behave differently depending on whether they are intervened on or not. However, RMABs assume the reward function is known. This is unrealistic in many public health settings because patients face unique challenges and it is impossible for a human to know who is most deserving …

Constrained Assortment Optimization Under The Cross-Nested Logit Model, Cuong Le, Tien Mai

Research Collection School Of Computing and Information Systems

We study the assortment optimization problem under general linear constraints, where the customer choice behavior is captured by the cross-nested logit model. In this problem, there is a set of products organized into multiple subsets (or nests), where each product can belong to more than one nest. The aim is to find an assortment to offer to customers so that the expected revenue is maximized. We show that, under the cross-nested logit model, the unconstrained assortment problem is NP-hard even when there are only two nests, and the problem is generally NP-hard to approximate to any constant factors. To tackle …

Comparison Of Evolutionary Algorithms: A Case Study On The Multi-Objective Carbon-Aware Mine Planning, Nurul Asyikeen Binte Azhar, Aldy Gunawan, Shih-Fen Cheng, Erwin Leonardi

Research Collection School Of Computing and Information Systems

The NP-hard precedence-constrained production scheduling problem (PCPSP) for mine planning chooses the ordered removal of materials from the mine pit and the next processing steps based on resource, geological, and geometrical constraints. Traditionally, it prioritizes the net present value (NPV) of profits across the lifespan of the mine. Yet, the growing shift in environmental concerns also requires shifts to more carbon-aware practices. In this paper, we use the enhanced multi-objective version of the generic PCPSP formulation by adding the NPV of carbon costs as another objective. We then compare how the Non-dominated Sorting Genetic Algorithm II (NSGA-II) and the Pareto …

Path-Choice-Constrained Bus Bridging Design Under Urban Rail Transit Disruptions, Yiyang Zhu, Jian Gang Jin, Hai Wang

Research Collection School Of Computing and Information Systems

Although urban rail transit systems play a crucial role in urban mobility, they frequently suffer from unexpected disruptions due to power loss, severe weather, equipment failure, and other factors that cause significant disruptions in passenger travel and, in turn, socioeconomic losses. To alleviate the inconvenience of affected passengers, bus bridging services are often provided when rail service has been suspended. Prior research has yielded various methodologies for effective bus bridging services; however, they are mainly based on the strong assumption that passengers must follow predetermined bus bridging routes. Less attention is paid to passengers’ path choice behaviors, which could affect …

Segac: Sample Efficient Generalized Actor Critic For The Stochastic On-Time Arrival Problem, Honglian Guo, Zhi He, Wenda Sheng, Zhiguang Cao, Yingjie Zhou, Weinan Gao

Research Collection School Of Computing and Information Systems

This paper studies the problem in transportation networks and introduces a novel reinforcement learning-based algorithm, namely. Different from almost all canonical sota solutions, which are usually computationally expensive and lack generalizability to unforeseen destination nodes, segac offers the following appealing characteristics. segac updates the ego vehicle’s navigation policy in a sample efficient manner, reduces the variance of both value network and policy network during training, and is automatically adaptive to new destinations. Furthermore, the pre-trained segac policy network enables its real-time decision-making ability within seconds, outperforming state-of-the-art sota algorithms in simulations across various transportation networks. We also successfully deploy segac …

A Feasibility-Preserved Quantum Approximate Solver For The Capacitated Vehicle Routing Problem, Ningyi Xie, Xinwei Lee, Dongsheng Cai, Yoshiyuki Saito, Nobuyoshi Asai, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. The CVRP extends from the Vehicle Routing Problem (VRP), aiming to determine the most efficient plan for a fleet of vehicles to deliver goods to a set of customers, subject to the limited carrying capacity of each vehicle. As the number of possible solutions increases exponentially with the number of customers, finding high-quality solutions remains a significant challenge. Recently, the Quantum Approximate Optimization Algorithm (QAOA), a quantum–classical hybrid algorithm, has exhibited enhanced performance in certain combinatorial optimization problems, such as …

Fine-Grained Passenger Load Prediction Inside Metro Network Via Smart Card Data, Xiancai Tian, Chen Zhang, Baihua Zheng

Research Collection School Of Computing and Information Systems

Metro system serves as the backbone for urban public transportation. Accurate passenger load prediction for the metro system plays a crucial role in metro service quality improvement, such as helping operators schedule train timetables and passengers plan their trips. However, existing works can only predict low-grained passenger flows of origin-destination (O-D) paths or inflows/outflows of each station but cannot predict passenger load distribution over the whole metro network. To this end, this paper proposes an end-to-end inference framework, PIPE, for passenger load prediction of every metro segment between two adjacent stations, by only utilizing smart card data. In particular, PIPE …

An Adaptive Large Neighborhood Search For The Multi-Vehicle Profitable Tour Problem With Flexible Compartments And Mandatory Customers, Vincent F. Yu, Nabila Yuraisyah Salsabila, Aldy Gunawan, Anggun Nurfitriani Handoko

Research Collection School Of Computing and Information Systems

The home-refill delivery system is a business model that addresses the concerns of plastic waste and its impact on the environment. It allows customers to pick up their household goods at their doorsteps and refill them into their own containers. However, the difficulty in accessing customers’ locations and product consolidations are undeniable challenges. To overcome these issues, we introduce a new variant of the Profitable Tour Problem, named the multi-vehicle profitable tour problem with flexible compartments and mandatory customers (MVPTPFC-MC). The objective is to maximize the difference between the total collected profit and the traveling cost. We model the proposed …

Dl-Drl: A Double-Level Deep Reinforcement Learning Approach For Large-Scale Task Scheduling Of Multi-Uav, Xiao Mao, Guohua Wu, Mingfeng Fan, Zhiguang Cao, Witold Pedrycz

Research Collection School Of Computing and Information Systems

Exploiting unmanned aerial vehicles (UAVs) to execute tasks is gaining growing popularity recently. To address the underlying task scheduling problem, conventional exact and heuristic algorithms encounter challenges such as rapidly increasing computation time and heavy reliance on domain knowledge, particularly when dealing with large-scale problems. The deep reinforcement learning (DRL) based methods that learn useful patterns from massive data demonstrate notable advantages. However, their decision space will become prohibitively huge as the problem scales up, thus deteriorating the computation efficiency. To alleviate this issue, we propose a double-level deep reinforcement learning (DL-DRL) approach based on a divide and conquer framework …

An Algorithm Based On Priority Rules For Solving A Multi-Drone Routing Problem In Hazardous Waste Collection, Youssef Harrath Dr., Jihene Kaabi Dr.

Research & Publications

This research investigates the problem of assigning pre-scheduled trips to multiple drones to collect hazardous waste from different sites in the minimum time. Each drone is subject to essential restrictions: maximum flying capacity and recharge operation. The goal is to assign the trips to the drones so that the waste is collected in the minimum time. This is done if the total flying time is equally distributed among the drones. An algorithm was developed to solve the problem. The algorithm is based on two main ideas: sort the trips according to a given priority rule and assign the current trip …

Integrative Machine Learning Approaches For Enhanced Classification Of Genomic Sequences: A Next-Generation Sequencing Perspective, Sujatha Alla, Nagesh Bheesetty, Sai Gireesh Komaragiri, Prasanthi Chidipudi, Joshit Mohanty, Sathish Kumar Chintala, Jubin Thomas, Jayapal Vummadi, Hemanth Volikatla, Navin Kamuni

Engineering Management & Systems Engineering Faculty Publications

The advent of Next-Generation Sequencing (NGS) techniques has revolutionized genomic research by enabling the rapid sequencing of DNA and RNA. This data can be used for various applications, including genome sequencing, transcriptome profiling, metagenomics, and epigenetics studies. For this study, DNA classifier dataset was extracted from UCI repository of machine learning databases. This vast amount of genomic data necessitates the development of sophisticated machine learning (ML) models for effective classification and analysis. This study presents a comprehensive comparison of various ML models, including Support Vector Machines (SVM), Random Forests (RF), and Neural Networks (NNs), approaches, in classifying genomic data. We …

Abmscore: A Heuristic Algorithm For Forming Strategic Coalitions In Agent-Based Simulation, Andrew J. Collins, Gayane Grigoryan

Engineering Management & Systems Engineering Faculty Publications

Integrating human behavior into agent-based models has been challenging due to its diversity. An example is strategic coalition formation, which occurs when an individual decides to collaborate with others because it strategically benefits them, thereby increasing the expected utility of the situation. An algorithm called ABMSCORE was developed to help model strategic coalition formation in agent-based models. The ABMSCORE algorithm employs hedonic games from cooperative game theory and has been applied to various situations, including refugee egress and smallholder farming cooperatives. This paper discusses ABMSCORE, including its mechanism, requirements, limitations, and application. To demonstrate the potential of ABMSCORE, a new …

Neural Airport Ground Handling, Yaoxin Wu, Jianan Zhou, Yunwen Xia, Xianli Zhang, Zhiguang Cao, Jie Zhang

Research Collection School Of Computing and Information Systems

Airport ground handling (AGH) offers necessary operations to flights during their turnarounds and is of great importance to the efficiency of airport management and the economics of aviation. Such a problem involves the interplay among the operations that leads to NP-hard problems with complex constraints. Hence, existing methods for AGH are usually designed with massive domain knowledge but still fail to yield high-quality solutions efficiently. In this paper, we aim to enhance the solution quality and computation efficiency for solving AGH. Particularly, we first model AGH as a multiple-fleet vehicle routing problem (VRP) with miscellaneous constraints including precedence, time windows, …

Joint Location And Cost Planning In Maximum Capture Facility Location Under Random Utilities, Ngan H. Duong, Tien Thanh Dam, Thuy Anh Ta, Tien Mai

Research Collection School Of Computing and Information Systems

We study a joint facility location and cost planning problem in a competitive market under random utility maximization (RUM) models. The objective is to locate new facilities and make decisions on the costs (or budgets) to spend on the new facilities, aiming to maximize an expected captured customer demand, assuming that customers choose a facility among all available facilities according to a RUM model. We examine two RUM frameworks in the discrete choice literature, namely, the additive and multiplicative RUM. While the former has been widely used in facility location problems, we are the first to explore the latter in …

Robust Maximum Capture Facility Location Under Random Utility Maximization Models, Tien Thanh Dam, Thuy Anh Ta, Tien Mai

Research Collection School Of Computing and Information Systems

We study a robust version of the maximum capture facility location problem in a competitive market, assuming that each customer chooses among all available facilities according to a random utility maximization (RUM) model. We employ the generalized extreme value (GEV) family of models and assume that the parameters of the RUM model are not given exactly but lie in convex uncertainty sets. The problem is to locate new facilities to maximize the worst-case captured user demand. We show that, interestingly, our robust model preserves the monotonicity and submodularity from its deterministic counterpart, implying that a simple greedy heuristic can guarantee …

Grasp Solution Approach For The E-Waste Collection Problem, Aldy Gunawan, Dang Viet Anh Nguyen, Pham Kien Minh Nguyen, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

The digital economy has brought significant advancements in electronic devices, increasing convenience and comfort in people’s lives. However, this progress has also led to a shorter life cycle for these devices due to rapid advancements in hardware and software technology. As a result, e-waste collection and recycling have become vital for protecting the environment and people’s health. From the operations research perspective, the e-waste collection problem can be modeled as the Heterogeneous Vehicle Routing Problem with Multiple Time Windows (HVRP-MTW). This study proposes a metaheuristic based on the Greedy Randomized Adaptive Search Procedure complemented by Path Relinking (GRASP-PR) to solve …

Learning To Send Reinforcements: Coordinating Multi-Agent Dynamic Police Patrol Dispatching And Rescheduling Via Reinforcement Learning, Waldy Joe, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We address the problem of coordinating multiple agents in a dynamic police patrol scheduling via a Reinforcement Learning (RL) approach. Our approach utilizes Multi-Agent Value Function Approximation (MAVFA) with a rescheduling heuristic to learn dispatching and rescheduling policies jointly. Often, police operations are divided into multiple sectors for more effective and efficient operations. In a dynamic setting, incidents occur throughout the day across different sectors, disrupting initially-planned patrol schedules. To maximize policing effectiveness, police agents from different sectors cooperate by sending reinforcements to support one another in their incident response and even routine patrol. This poses an interesting research challenge …