Publications (38)
Pruning Techniques for the Stochastic on-time Arrival Problem\texorpdfstring -- An Experimental Study
Moritz Kobitzsch, Samitha Samaranayake, Dennis Schieferdecker
Computing shortest paths is one of the most researched topics in algorithm engineering. Currently available algorithms compute shortest paths in mere fractions of a second on conti…
MoveOD: Synthesizing Origin-Destination Commute Distribution from U.S. Census Data
Rishav Sen, Jose Paolo Talusan, Abhishek Dubey +3
High-resolution origin-destination (OD) tables are essential for a wide spectrum of transportation applications, from modeling traffic and signal timing optimization to congestion…
Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests
Amutheezan Sivagnanam, Ayan Mukhopadhyay, Samitha Samaranayake +2
Transit agencies that operate on-demand transportation services have to respond to trip requests from passengers in real time, which involves solving dynamic vehicle routing proble…
Impacts of Covid-19 mode shift on road traffic
Yue Hu, William Barbour, Kun Qian +3
This work considers the sensitivity of commute travel times in US metro areas due to potential changes in commute patterns, for example caused by events such as pandemics. Permanen…
A Framework for the Joint Optimization of Assignment and Pricing in Mobility-on-Demand Systems with Shared Rides
Yang Liu, Qi Luo, Raga Gopalakrishnan +1
Mobility-on-Demand (MoD) systems have become a fixture in urban transportation networks, with the rapid growth of ride-hailing services such as Uber and Lyft. Ride-hailing is typic…
The Price of Fragmentation in Mobility-on-Demand Services
Thibault Séjourné, Samitha Samaranayake, Siddhartha Banerjee
Mobility-on-Demand platforms are a fast growing component of the urban transit ecosystem. Though a growing literature addresses the question of how to make individual MoD platforms…
Shareability Network Based Decomposition Approach for Solving Large-scale Single School Routing Problems
Xiaotong Guo, Samitha Samaranayake
We consider the Single School Routing Problem (SSRP) where students from a single school are picked up by a fleet of school buses, subject to a set of constraints. The constraints…
Vehicle Routing Problems in the Age of Semi-Autonomous Driving
Hins Hu, Samitha Samaranayake
We are in the midst of a semi-autonomous era in urban transportation in which varying forms of vehicle autonomy are gradually being introduced. This phase of partial autonomy is an…
Multimodal Mobility Systems: Joint Optimization of Transit Network Design and Pricing
Qi Luo, Samitha Samaranayake, Siddhartha Banerjee
The performance of multimodal mobility systems relies on the seamless integration of conventional mass transit services and the advent of Mobility-on-Demand (MoD) services. Prior w…
Stochastic on-time arrival problem in transit networks
Yang Liu, Sebastien Blandin, Samitha Samaranayake
This article considers the stochastic on-time arrival problem in transit networks where both the travel time and the waiting time for transit services are stochastic. A specific ch…
A Framework to Integrate Mode Choice in the Design of Mobility-on-Demand Systems
Yang Liu, Prateek Bansal, Ricardo Daziano +1
Mobility-on-Demand (MoD) systems are generally designed and analyzed for a fixed and exogenous demand, but such frameworks fail to answer questions about the impact of these servic…
Integrating On-demand Ride-sharing with Mass Transit at-Scale
Danushka Edirimanna, Hins Hu, Samitha Samaranayake
We are in the midst of a technology-driven transformation of the urban mobility landscape. However, unfortunately these new innovations are still dominated by car-centric personal…
From Accessibility to Allocation: An Integrated Workflow for Land-Use Assignment and FAR Estimation
Yue Sun, Ryan Weightman, Yang Yang +3
Urban land use and building intensity are often planned without a direct, auditable link to network accessibility, limiting ex-ante policy evaluation. This study asks whether multi…
Proactive rebalancing and speed-up techniques for on-demand high capacity ridesourcing services
Yang Liu, Samitha Samaranayake
We present a probabilistic proactive rebalancing method and speed-up techniques for improving the performance of a state-of-the-art real-time high-capacity fleet management framewo…
Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems
Hongyi Jiang, Samitha Samaranayake
Motivated by a transit line planning problem in transportation systems, we investigate the following capacitated assignment problem under a budget constraint. Our model involves $L…
Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics
Matthew Zalesak, Hins Hu, Samitha Samaranayake
On-demand ride-pooling has emerged as a popular urban transportation solution, addressing the efficiency limitations of traditional ride-hailing services by grouping multiple ridin…
A Review of Urban Resilience Frameworks: Transferring Knowledge to Enhance Pandemic Resilience
Yue Sun, Ryan Weightman, Anye Shi +2
Urbanization is rapidly increasing, with urban populations expected to grow significantly by 2050, particularly in developing regions. This expansion brings challenges related to c…
SEIR-Campus: Modeling Infectious Diseases on University Campuses
Matthew Zalesak, Samitha Samaranayake
We introduce a Python package for modeling and studying the spread of infectious diseases using an agent-based SEIR style epidemiological model with a focus on university campuses.…
On the Request-Trip-Vehicle Assignment Problem
J. Carlos MartÃnez Mori, Samitha Samaranayake
The request-trip-vehicle assignment problem is at the heart of a popular decomposition strategy for online vehicle routing. In this framework, assignments are done in batches in or…
Real-Time Approximate Routing for Smart Transit Systems
Siddhartha Banerjee, Chamsi Hssaine, Noémie Périvier +1
We study real-time routing policies in smart transit systems, where the platform has a combination of cars and high-capacity vehicles (e.g., buses or shuttles) and seeks to serve a…
A Combined Convex Model for Travel Demand Forecasting with Hierarchical Extended Logit Model
Youngseo Kim, Samitha Samaranayake, Damon Wischik
The travel demand forecasting model plays a crucial role in evaluating large-scale infrastructure projects, such as the construction of new roads or transit lines. While combined m…
Promoting Fair Online Resource Allocation with Indivisible Units
Igor Averbakh, Hongyi Jiang, Samitha Samaranayake +2
Allocating scarce, indivisible resources to diverse groups under uncertainty is a central challenge in operations research, where efficiency-focused methods often underserve margin…
Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows
Youngseo Kim, Danushka Edirimanna, Michael Wilbur +4
The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very cha…
Fleet management for ride-pooling with meeting points at scale: a case study in the five boroughs of New York City
Motahare Mounesan, Vindula Jayawardana, Yaocheng Wu +2
Introducing meeting points to ride-pooling (RP) services has been shown to increase the satisfaction level of both riders and service providers. Passengers may choose to walk to a…
Approximation Algorithms for Line Planning with Heterogeneous Fleets and Multiple Resource Constraints
Hongyi Jiang, Igor Averbakh, Samitha Samaranayake
This paper studies line planning for urban bus networks that face multiple resource limits such as budget, labor, and emission caps while using heterogeneous fleets. The objective…
Tractable Pathfinding for the Stochastic On-Time Arrival Problem
Mehrdad Niknami, Samitha Samaranayake
We present a new and more efficient technique for computing the route that maximizes the probability of on-time arrival in stochastic networks, also known as the path-based stochas…
Permutatorial Optimization via the Permutahedron
J. Carlos Martinez Mori, Samitha Samaranayake
A water company decides to expand its network with a set of water lines, but it cannot build them all at once. However, it starts reaping benefits from a partial expansion. In what…
Real Time Operation of High-Capacity Electric Vehicle Ridesharing Fleets
Matthew Zalesak, Samitha Samaranayake
We study the feasibility of using electric vehicles in online, high-capacity ridepooling systems. Prior work has shown that online algorithms perform well for centrally-controlled,…
Safe reopening of university campuses is possible with COVID-19 vaccination
Matthew Junge, Sheng Li, Samitha Samaranayake +1
We construct an agent-based SEIR model to simulate COVID-19 spread at a 16000-student mostly non-residential urban university during the Fall 2021 Semester. We find that mRNA vacci…
An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services
Michael Wilbur, Salah Uddin Kadir, Youngseo Kim +6
Many transit agencies operating paratransit and microtransit services have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequen…
The Batched Set Cover Problem
Juan C. MartÃnez Mori, Samitha Samaranayake
We introduce the batched set cover problem, which is a generalization of the online set cover problem. In this problem, the elements of the ground set that need to be covered arriv…
HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization
Hongzheng Chen, Yingheng Wang, Yaohui Cai +10
While Large Language Models (LLMs) have demonstrated significant advancements in reasoning and agent-based problem-solving, current evaluation methodologies fail to adequately asse…
Optimization of vaccination for COVID-19 in the midst of a pandemic
Qi Luo, Ryan Weightman, Sean T. McQuade +6
During the Covid-19 pandemic a key role is played by vaccination to combat the virus. There are many possible policies for prioritizing vaccines, and different criteria for optimiz…
Can Mobility-on-Demand services do better after discerning reliability preferences of riders?
Prateek Bansal, Yang Liu, Ricardo Daziano +1
We formalize one aspect of reliability in the context of Mobility-on-Demand (MoD) systems by acknowledging the uncertainty in the pick-up time of these services. This study answers…
Optimal Micro-Transit Zoning via Clique Generation and Integer Programming
Hins Hu, Rhea Goswami, Hongyi Jiang +1
Micro-transit services offer a promising solution to enhance urban mobility and access, particularly by complementing existing public transit. However, effectively designing these…
Designing Equitable Transit Networks
Sophie Pavia, J. Carlos Martinez Mori, Aryaman Sharma +4
Public transit is an essential infrastructure enabling access to employment, healthcare, education, and recreational facilities. While accessibility to transit is important in gene…
Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit
Amutheezan Sivagnanam, Salah Uddin Kadir, Ayan Mukhopadhyay +4
Vehicle routing problems (VRPs) can be divided into two major categories: offline VRPs, which consider a given set of trip requests to be served, and online VRPs, which consider re…
Column Generation for the Micro-Transit Zoning Problem
Hins Hu, Rishav Sen, Jose Paolo Talusan +3
Along with the rapid development of new urban mobility options like ride-sharing over the past decade, on-demand micro-transit services stand out as a middle ground, bridging the g…