Author name cluster

Youngseo Kim

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

IJCAI Conference 2024 Conference Paper

Deploying Mobility-On-Demand for All by Optimizing Paratransit Services

Sophie Pavia
David Rogers
Amutheezan Sivagnanam
Michael Wilbur
Danushka Edirimanna
Youngseo Kim
Philip Pugliese
Samitha Samaranayake

While on-demand ride-sharing services have become popular in recent years, traditional on-demand transit services cannot be used by everyone, e. g. , people who use wheelchairs. Paratransit services, operated by public transit agencies, are a critical infrastructure that offers door-to-door transportation assistance for individuals who face challenges in using standard transit routes. However, with declining ridership and mounting financial pressure, public transit agencies in the USA struggle to operate existing services. We collaborate with a public transit agency from the southern USA, highlight the specific nuances of paratransit optimization, and present a vehicle routing problem formulation for optimizing paratransit. We validate our approach using real-world data from the transit agency, present results from an actual pilot deployment of the proposed approach in the city, and show how the proposed approach comprehensively outperforms existing approaches used by the transit agency. To the best of our knowledge, this work presents one of the first examples of using open-source algorithmic approaches for paratransit optimization.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

SmartTransit. AI: A Dynamic Paratransit and Microtransit Application

Sophie Pavia
David Rogers
Amutheezan Sivagnanam
Michael Wilbur
Danushka Edirimanna
Youngseo Kim
Ayan Mukhopadhyay
Philip Pugliese

New rideshare and shared mobility services have transformed urban mobility in recent years. Such services have the potential to improve efficiency and reduce costs by allowing users to share rides in high-capacity vehicles and vans. Most transit agencies already operate various ridepooling services, including microtransit and paratransit. However, the objectives and constraints for implementing these services vary greatly between agencies and can be challenging. First, off-the-shelf ridepooling formulations must be adapted for real-world conditions and constraints. Second, the lack of modular and reusable software makes it hard to implement and evaluate new ridepooling algorithms and approaches in real-world settings. We demonstrate a modular on-demand public transportation scheduling software for microtransit and paratransit services. The software is aimed at transit agencies looking to incorporate state-of-the-art rideshare and ridepooling algorithms in their everyday operations. We provide management software for dispatchers and mobile applications for drivers and users and conclude with results from the demonstration in Chattanooga, TN.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Rolling Horizon Based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows

Youngseo Kim
Danushka Edirimanna
Michael Wilbur
Philip Pugliese
Aron Laszka
Abhishek Dubey
Samitha Samaranayake

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 challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a large-scale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and high-quality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times.

PDF Details DOI