skip to main content
Explore Scholarly Publications and Datasets in the NSF-PAR

Title: Optimal Operations Management of Mobility-on-Demand Systems
The emergence of the sharing economy in urban transportation networks has enabled new fast, convenient and accessible mobility services referred to as Mobilty-on-Demand systems (e.g., Uber, Lyft, DiDi). These platforms have flourished in the last decade around the globe and face many operational challenges in order to be competitive and provide good quality of service. A crucial step in the effective operation of these systems is to reduce customers' waiting time while properly selecting the optimal fleet size and pricing policy. In this paper, we jointly tackle three operational decisions: (i) fleet size, (ii) pricing, and (iii) rebalancing, in order to maximize the platform's profit or its customers' welfare. To accomplish this, we first devise an optimization framework which gives rise to a static policy. Then, we elaborate and propose dynamic policies that are more responsive to perturbations such as unexpected increases in demand. We test this framework in a simulation environment using three case studies and leveraging traffic flow and taxi data from Eastern Massachusetts, New York City, and Chicago. Our results show that solving the problem jointly could increase profits between 1% and up to 50%, depending on the benchmark. Moreover, we observe that the proposed fleet size more » yield utilization of the vehicles in the fleet is around 75% compared to private vehicle utilization of 5%. « less
Authors:
; ;
Award ID(s):
1931600
Publication Date:
NSF-PAR ID:
10288848
Journal Name:
Frontiers in Sustainable Cities
Volume:
3
ISSN:
2624-9634
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ( , Management Science)
    The prevalence of e-commerce has made customers’ detailed personal information readily accessible to retailers, and this information has been widely used in pricing decisions. When using personalized information, the question of how to protect the privacy of such information becomes a critical issue in practice. In this paper, we consider a dynamic pricing problem over T time periods with an unknown demand function of posted price and personalized information. At each time t, the retailer observes an arriving customer’s personal information and offers a price. The customer then makes the purchase decision, which will be utilized by the retailer to learn the underlying demand function. There is potentially a serious privacy concern during this process: a third-party agent might infer the personalized information and purchase decisions from price changes in the pricing system. Using the fundamental framework of differential privacy from computer science, we develop a privacy-preserving dynamic pricing policy, which tries to maximize the retailer revenue while avoiding information leakage of individual customer’s information and purchasing decisions. To this end, we first introduce a notion of anticipating [Formula: see text]-differential privacy that is tailored to the dynamic pricing problem. Our policy achieves both the privacy guarantee and the performancemore »guarantee in terms of regret. Roughly speaking, for d-dimensional personalized information, our algorithm achieves the expected regret at the order of [Formula: see text] when the customers’ information is adversarially chosen. For stochastic personalized information, the regret bound can be further improved to [Formula: see text]. This paper was accepted by J. George Shanthikumar, big data analytics.« less
  2. ; ; ; ( , Manufacturing & service operations management)
    Problem definition: Inspired by new developments in dynamic spectrum access, we study the dynamic pricing of wireless Internet access when demand and capacity (bandwidth) are stochastic. Academic/practical relevance: The demand for wireless Internet access has increased enormously. However, the spectrum available to wireless service providers is limited. The industry has, thus, altered conventional license-based spectrum access policies through unlicensed spectrum operations. The additional spectrum obtained through these operations has stochastic capacity. Thus, the pricing of this service by the service provider has novel challenges. The problem considered in this paper is, therefore, of high practical relevance and new to the academic literature. Methodology: We study this pricing problem using a Markov decision process model in which customers are posted dynamic prices based on their bandwidth requirement and the available capacity. Results: We characterize the structure of the optimal pricing policy as a function of the system state and of the input parameters. Because it is impossible to solve this problem for practically large state spaces, we propose a heuristic dynamic pricing policy that performs very well, particularly when the ratio of capacity to demand rate is low. Managerial implications: We demonstrate the value of using a dynamic heuristic pricing policymore »compared with the myopic and optimal static policies. The previous literature has studied similar systems with fixed capacity and has characterized conditions under which myopic policies perform well. In contrast, our setting has dynamic (stochastic) capacity, and we find that identifying good state-dependent heuristic pricing policies is of greater importance. Our heuristic policy is computationally more tractable and easier to implement than the optimal dynamic and static pricing policies. It also provides a significant performance improvement relative to the myopic and optimal static policies when capacity is scarce, a condition that holds for the practical setting that motivated this research.« less
  3. ; ; ( , IISE Transactions)
    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.
  4. ; ; ( , INFORMS Journal on Computing)
    We consider a variant of the vehicle routing problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation-based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the “pricing problem,” which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50–957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2%more »optimality gaps for most VRP benchmark instances and less than 1% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the run time. Summary of Contribution: The vehicle routing problem (VRP) is a fundamental combinatorial problem, and its variants have been studied extensively in the literature of operations research and computer science. In this paper, we consider general-purpose algorithms for solving VRPs, including the column-generation approach for the linear programming relaxations of the integer programs of VRPs and the column-enumeration approach for seeking improved integer solutions. We revise the pulse algorithm and also propose a random-coloring algorithm that can be used for solving the elementary shortest path problem that formulates the pricing problem in the column-generation approach. We show that the parallel implementation of both algorithms can significantly improve the performance of column generation and the random coloring algorithm can improve the solution time and quality of the VRP integer solutions produced by the column-enumeration approach. We focus on algorithmic design for VRPs and conduct extensive computational tests to demonstrate the performance of various approaches.« less
  5. ; ( , IEEE Transactions on Smart Grid)
    We consider the setting in which an electric power utility seeks to curtail its peak electricity demand by offering a fixed group of customers a uniform price for reductions in consumption relative to their predetermined baselines. The underlying demand curve, which describes the aggregate reduction in consumption in response to the offered price, is assumed to be affine and subject to unobservable random shocks. Assuming that both the parameters of the demand curve and the distribution of the random shocks are initially unknown to the utility, we investigate the extent to which the utility might dynamically adjust its offered prices to maximize its cumulative risk-sensitive payoff over a finite number of T days. In order to do so effectively, the utility must design its pricing policy to balance the tradeoff between the need to learn the unknown demand model (exploration) and maximize its payoff (exploitation) over time. In this paper, we propose such a pricing policy, which is shown to exhibit an expected payoff loss over T days that is at most O( p T), relative to an oracle pricing policy that knows the underlying demand model. Moreover, the proposed pricing policy is shown to yield a sequence of pricesmore »that converge to the oracle optimal prices in the mean square sense.« less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email