More Like this

1. Resource Augmentation Analysis of the Greedy Algorithm for the Online Transportation Problem

   Stephen Arndt, Josh Ascher ( September 2023 , Latin and American Algorithms, Graphs and Optimization Symposium)

   We consider the online transportation problem set in a metric space containing parking garages of various capacities. Cars arrive over time, and must be assigned to an unfull parking garage upon their arrival. The objective is to minimize the aggregate distance that cars have to travel to their assigned parking garage. We show that the natural greedy algorithm, augmented with garages of k >= 3 times the capacity, is O(1)-competitive. 

   more » « less
2. Off-Street Parking for TNC Vehicles to Reduce Cruising Traffic

   https://doi.org/10.1109/CDC42340.2020.9304277  

   Li, Sen ; Qin, Junjie ; Yang, Hai ; Poolla, Kameshwar ; Varaiya, Pravin ( December 2020 , 2020 59th IEEE Conference on Decision and Control (CDC))

   null (Ed.)

   This paper considers off-street parking for the cruising vehicles of transportation network companies (TNCs) to reduce the traffic congestion. We propose a novel business that integrates the shared parking service into the TNC platform. In the proposed model, the platform (a) provides interfaces that connect passengers, drivers and garage operators (commercial or private garages); (b) determines the ride fare, driver payment, and parking rates; (c) matches passengers to TNC vehicles for ride-hailing services; and (d) matches vacant TNC vehicles to unoccupied parking garages to reduce the cruising cost. A queuing-theoretic model is proposed to capture the matching process of passengers, drivers, and parking garages. A market-equilibrium model is developed to capture the incentives of the passengers, drivers, and garage operators. An optimization-based model is formulated to capture the optimal pricing of the TNC platform. Through a realistic case study, we show that the proposed business model will offer a Pareto improvement that benefits all stakeholders, which leads to higher passenger surplus, higher drivers surplus, higher garage operator surplus, higher platform profit, and reduced traffic congestion. 

   more » « less
3. Competitive Spatial Pricing for Urban Parking Systems: Network Structures and Asymmetric Information

   https://doi.org/10.1080/24725854.2021.1937755  

   Wu, Yuguang ; He, Qiao-Chu ; Wang, Xin ( August 2021 , IISE Transactions)

   null (Ed.)

   Inspired by new technologies to monitor parking occupancy and process market signals, we aim to expand the application of demand-responsive pricing in the parking industry. Based on a graphical Hotelling model wherein each garage has information for its incoming parking demand, we consider a general competitive spatial pricing in parking systems under an asymmetric information structure. We focus on the impact of urban network structure on the incentive of information sharing. Our analyses suggest that the garages are always better off in a circular-networked city, while they could be worse off in the suburbs of a star-networked city. Nevertheless, the overall revenue for garages is improved and the aggregate congestion is reduced under information sharing. Our results also suggest that information sharing helps garages further exploit the customers who in turn become worse-off. Therefore, policy-makers should carefully evaluate their transportation data policy since impacts on the service-providers and the customers are typically conflicting. Using the SFpark data, we empirically confirmed the value of information sharing. In particular, garages with higher price-demand elasticity and lower demand variance tend to enjoy larger benefits via information sharing. These insights support the joint design of parking rates structure and information systems. 

   more » « less
4. A Generalization of Parking Functions Allowing Backward Movement

   https://doi.org/10.37236/8948  

   Christensen, Alex ; Harris, Pamela E. ; Jones, Zakiya ; Loving, Marissa ; Ramos Rodríguez, Andrés ; Rennie, Joseph ; Rojas Kirby, Gordon ( January 2020 , The Electronic Journal of Combinatorics)

   Classical parking functions are defined as the parking preferences for $n$ cars driving (from west to east) down a one-way street containing parking spaces labeled from $1$ to $n$ (from west to east). Cars drive down the street toward their preferred spot and park there if the spot is available. Otherwise, the car continues driving down the street and takes the first available parking space, if such a space exists. If all cars can park using this parking rule, we call the $n$-tuple containing the cars' parking preferences a parking function.   In this paper, we introduce a generalization of the parking rule allowing cars whose preferred space is taken to first proceed up to $k$ spaces west of their preferred spot to park before proceeding east if all of those $k$ spaces are occupied. We call parking preferences which allow all cars to park under this new parking rule $k$-Naples parking functions of length $n$. This generalization gives a natural interpolation between classical parking functions, the case when $k=0$, and all $n$-tuples of positive integers $1$ to $n$, the case when $k\geq n-1$. Our main result provides a recursive formula for counting $k$-Naples parking functions of length $n$. We also give a characterization for the $k=1$ case by introducing a new function that maps $1$-Naples parking functions to classical parking functions, i.e. $0$-Naples parking functions. Lastly, we present a bijection between $k$-Naples parking functions of length $n$ whose entries are in weakly decreasing order and a family of signature Dyck paths. 

   more » « less
5. Stretched exponential decay for subcritical parking times on

   https://doi.org/10.1002/rsa.21001  

   Damron, Michael ; Lyu, Hanbaek ; Sivakoff, David ( February 2021 , Random Structures & Algorithms)

   null (Ed.)

   In the parking model on ℤd, each vertex is initially occupied by a car (with probability p) or by a vacant parking spot (with probability 1−p). Cars perform independent random walks and when they enter a vacant spot, they park there, thereby rendering the spot occupied. Cars visiting occupied spots simply keep driving (continuing their random walk). It is known that p=1/2 is a critical value in the sense that the origin is a.s. visited by finitely many distinct cars when p<1/2, and by infinitely many distinct cars when p≥1/2. Furthermore, any given car a.s. eventually parks for p≤1/2 and with positive probability does not park for p>1/2. We study the subcritical phase and prove that the tail of the parking time τ of the car initially at the origin obeys the bounds exp(−C1tdd+2)≤ℙp(τ>t)≤exp(−c2tdd+2) for p>0 sufficiently small. For d=1, we prove these inequalities for all p∈[0,1/2). This result presents an asymmetry with the supercritical phase (p>1/2), where methods of Bramson--Lebowitz imply that for d=1 the corresponding tail of the parking time of the parking spot of the origin decays like e−ct√. Our exponent d/(d+2) also differs from those previously obtained in the case of moving obstacles. 

   more » « less