With the popularity of the Internet, traditional offline resource allocation has evolved into a new form, called online resource allocation. It features the online arrivals of agents in the system and the real-time decision-making requirement upon the arrival of each online agent. Both offline and online resource allocation have wide applications in various real-world matching markets ranging from ridesharing to crowdsourcing. There are some emerging applications such as rebalancing in bike sharing and trip-vehicle dispatching in ridesharing, which involve a two-stage resource allocation process. The process consists of an offline phase and another sequential online phase, and both phases compete for the same set of resources. In this paper, we propose a unified model which incorporates both offline and online resource allocation into a single framework. Our model assumes non-uniform and known arrival distributions for online agents in the second online phase, which can be learned from historical data. We propose a parameterized linear programming (LP)-based algorithm, which is shown to be at most a constant factor of 1/4 from the optimal. Experimental results on the real dataset show that our LP-based approaches outperform the LP-agnostic heuristics in terms of robustness and effectiveness.
- Award ID(s):
- 1922665
- NSF-PAR ID:
- 10377849
- Date Published:
- Journal Name:
- Transportation Science
- Volume:
- 56
- Issue:
- 2
- ISSN:
- 0041-1655
- Page Range / eLocation ID:
- 322 to 337
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
null (Ed.)more » « less
-
Jin, Sheng (Ed.)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. Permanent shifts away from transit and carpooling can add vehicles to congested road networks, increasing travel times. Growth in the number of workers who avoid commuting and work from home instead can offset travel time increases. To estimate these potential impacts, 6-9 years of American Community Survey commute data for 118 metropolitan statistical areas are investigated. For 74 of the metro areas, the average commute travel time is shown to be explainable using only the number of passenger vehicles used for commuting. A universal Bureau of Public Roads model characterizes the sensitivity of each metro area with respect to additional vehicles. The resulting models are then used to determine the change in average travel time for each metro area in scenarios when 25% or 50% of transit and carpool users switch to single occupancy vehicles. Under a 25% mode shift, areas such as San Francisco and New York that are already congested and have high transit ridership may experience round trip travel time increases of 12 minutes (New York) to 20 minutes (San Francisco), costing individual commuters $1065 and $1601 annually in lost time. The travel time increases and corresponding costs can be avoided with an increase in working from home. The main contribution of this work is to provide a model to quantify the potential increase in commute travel times under various behavior changes, that can aid policy making for more efficient commuting.more » « less
-
more » « less
A planned special event (PSE), such as a sports game or a concert, can greatly affect the normal operations of a transportation system. To facilitate traffic, the road network is usually reconfigured, which could include road closures, reversed lanes, and limited access to parking facilities. For recurring PSEs, event-goers are often provided with recommended routes to designated parking areas in advance. Such network reconfiguration and route and parking recommendations are, however, often ad hoc in practice. This paper focuses on the PSE traffic planning problem. We propose to simultaneously consider parking, ridesharing, and network configuration. The problem is formulated as an optimization problem with integer decision variables. We developed a flow-based traffic simulation tool that is able to incorporate parking and lane changing (which cannot be ignored around ridesharing drop-off locations) to evaluate the objective function. We also developed effective and efficient heuristic solution algorithms. The models and algorithms are tested using the real network and traffic data from Super Bowl XLIX in 2015. The results show that our methods and approaches are able to produce an effective comprehensive traffic plan with reasonable computation time. For the Super Bowl XLIX case study, the resulting optimal plan is able to save 39.6% of the total vehicle-hours associated with default network configurations. Sensitivity analysis has also been conducted with respect to the compliance rate of travelers following recommended routes. It is found that the resulting near-optimal PSE traffic plans are able to tolerate some uncertainty in the compliance rate.
-
Access control is often reported to be “profoundly broken” in real- world practices due to prevalent policy misconfigurations intro- duced by system administrators (sysadmins). Given the dynamics of resource and data sharing, access control policies need to be continuously updated. Unfortunately, to err is human—sysadmins often make mistakes such as over-granting privileges when chang- ing access control policies. With today’s limited tooling support for continuous validation, such mistakes can stay unnoticed for a long time until eventually being exploited by attackers, causing catastrophic security incidents. We present P-DIFF, a practical tool for monitoring access control behavior to help sysadmins early detect unintended access control policy changes and perform postmortem forensic analysis upon security attacks. P-DIFF continuously monitors access logs and infers access control policies from them. To handle the challenge of policy evolution, we devise a novel time-changing decision tree to effectively represent access control policy changes, coupled with a new learning algorithm to infer the tree from access logs. P-DIFF provides sysadmins with the inferred policies and detected changes to assist the following two tasks: (1) validating whether the access control changes are intended or not; (2) pinpointing the historical changes responsible for a given security attack. We evaluate P-DIFF with a variety of datasets collected from five real-world systems, including two from industrial companies. P- DIFF can detect 86%–100% of access control policy changes with an average precision of 89%. For forensic analysis, P-DIFF can pinpoint the root-cause change that permits the target access in 85%–98% of the evaluated cases.more » « less
-
The rise in deep learning models in recent years has led to various innovative solutions for intelligent transportation technologies. Use of personal and on-demand mobility services puts a strain on the existing road network in a city. To mitigate this problem, city planners need a simulation framework to evaluate the effect of any incentive policy in nudging commuters towards alternate modes of travel, such as bike and car-share options. In this paper, we leverage MATSim, an agent-based simulation framework, to integrate agent preference models that capture the altruistic behavior of an agent in addition to their disutility proportional to the travel time and cost. These models are learned in a data-driven approach and can be used to evaluate the sensitivity of an agent to system-level disutility and monetary incentives given, e.g., by the transportation authority. This framework provides a standardized environment to evaluate the effectiveness of any particular incentive policy of a city, in nudging its residents towards alternate modes of transportation. We show the effectiveness of the approach and provide analysis using a case study from the Metropolitan Nashville area.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1287/trsc.2021.1093
