Search

Problem definition: We study an urban bike lane planning problem based on the fine-grained bike trajectory data, which are made available by smart city infrastructure, such as bike-sharing systems. The key decision is where to build bike lanes in the existing road network. Academic/practical relevance: As bike-sharing systems become widespread in the metropolitan areas over the world, bike lanes are being planned and constructed by many municipal governments to promote cycling and protect cyclists. Traditional bike lane planning approaches often rely on surveys and heuristics. We develop a general and novel optimization framework to guide the bike lane planning from bike trajectories. Methodology: We formalize the bike lane planning problem in view of the cyclists’ utility functions and derive an integer optimization model to maximize the utility. To capture cyclists’ route choices, we develop a bilevel program based on the Multinomial Logit model. Results: We derive structural properties about the base model and prove that the Lagrangian dual of the bike lane planning model is polynomial-time solvable. Furthermore, we reformulate the route-choice-based planning model as a mixed-integer linear program using a linear approximation scheme. We develop tractable formulations and efficient algorithms to solve the large-scale optimization problem. Managerial implications: Via a real-world case study with a city government, we demonstrate the efficiency of the proposed algorithms and quantify the trade-off between the coverage of bike trips and continuity of bike lanes. We show how the network topology evolves according to the utility functions and highlight the importance of understanding cyclists’ route choices. The proposed framework drives the data-driven urban-planning scheme in smart city operations management.

Problem definition: Shared micromobility vehicles provide an eco-friendly form of short-distance travel within an urban area. Because customers pick up and drop off vehicles in any service region at any time, such convenience often leads to a severe imbalance between vehicle supply and demand in different service regions. To overcome this, a micromobility operator can crowdsource individual riders with reward incentives in addition to engaging a third-party logistics provider (3PL) to relocate the vehicles. Methodology/results: We construct a time-space network with multiple service regions and formulate a two-stage stochastic mixed-integer program considering uncertain customer demands. In the first stage, the operator decides the initial vehicle allocation for the regions, whereas in the second stage, the operator determines subsequent vehicle relocation across the regions over an operational horizon. We develop an efficient solution approach that incorporates scenario-based and time-based decomposition techniques. Our approach outperforms a commercial solver in solution quality and computational time for solving large-scale problem instances based on real data. Managerial implications: The budgets for acquiring vehicles and for rider crowdsourcing significantly impact the vehicle initial allocation and subsequent relocation. Introducing rider crowdsourcing in addition to the 3PL can significantly increase profit, reduce demand loss, and improve the vehicle utilization rate of the system without affecting any existing commitment with the 3PL. The 3PL is more efficient for mass relocation than rider crowdsourcing, whereas the latter is more efficient in handling sporadic relocation needs. To serve a region, the 3PL often relocates vehicles in batches from faraway, low-demand regions around peak hours of a day, whereas rider crowdsourcing relocates a few vehicles each time from neighboring regions throughout the day. Furthermore, rider crowdsourcing relocates more vehicles under a unimodal customer arrival pattern than a bimodal pattern, whereas the reverse holds for the 3PL. Funding: This work was supported by the Research Grants Council of Hong Kong [Grants 15501319 and 15505318] and the National Natural Science Foundation of China [Grant 71931009]. Z. Jin was supported by the Hong Kong PhD Fellowship Scheme. Y. F. Lim was supported by the Lee Kong Chian School of Business, Singapore Management University [Maritime and Port Authority Research Fellowship]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/msom.2023.1199 .

Conditional quantile prediction involves estimating/predicting the quantile of a response random variable conditioned on observed covariates. The existing literature assumes the availability of independent and identically distributed (i.i.d.) samples of both the covariates and the response variable. However, such an assumption often becomes restrictive in many real-world applications. By contrast, we consider a fixed-design setting of the covariates, under which neither the response variable nor the covariates have i.i.d. samples. The present study provides a new data-driven distributionally robust framework under a fixed-design setting. We propose a regress-then-robustify method by constructing a surrogate empirical distribution of the noise. The solution of our framework coincides with a simple yet practical method that involves only regression and sorting, therefore providing an explanation for its empirical success. Measure concentration results are obtained for the surrogate empirical distribution, which further lead to finite-sample performance guarantees and asymptotic consistency. Numerical experiments are conducted to demonstrate the advantages of our approach. This paper was accepted by Hamid Nazerzadeh, Management Science Special Section on Data-Driven Prescriptive Analytics.

Content-sharing social network platforms rely heavily on user-generated content to attract users and advertisers, but they have limited authority over content provision. We develop an intervention that leverages social interactions between users to stimulate content production. We study social nudges, whereby users connected with a content provider on a platform encourage that provider to supply more content. We conducted a randomized field experiment (N [Formula: see text]) on a video-sharing social network platform where treatment providers could receive messages from other users encouraging them to produce more, but control providers could not. We find that social nudges not only immediately boosted video supply by 13.21% without changing video quality but also, increased the number of nudges providers sent to others by 15.57%. Such production-boosting and diffusion effects, although declining over time, lasted beyond the day of receiving nudges and were amplified when nudge senders and recipients had stronger ties. We replicate these results in a second experiment. To estimate the overall production boost over the entire network and guide platforms to utilize social nudges, we combine the experimental data with a social network model that captures the diffusion and over-time effects of social nudges. We showcase the importance of considering the network effects when estimating the impact of social nudges and optimizing platform operations regarding social nudges. Our research highlights the value of leveraging co-user influence for platforms and provides guidance for future research to incorporate the diffusion of an intervention into the estimation of its impacts within a social network. This paper was accepted by Victor Martínez-de-Albéniz, operations management. Funding: H. Dai thanks the University of California, Los Angeles (UCLA) [Hellman Fellowship and Faculty Development Award] for funding support. R. Zhang is grateful for financial support from the Hong Kong Research Grants Council [Grant 16505418]. Supplemental Material: The data files and online appendix are available at https://doi.org/10.1287/mnsc.2022.4622 .

Connected and automated vehicle (CAV) technology is providing urban transportation managers tremendous opportunities for better operation of urban mobility systems. However, there are significant challenges in real-time implementation as the computational time of the corresponding operations optimization model increases exponentially with increasing vehicle numbers. Following the companion paper (Chen et al. 2021), which proposes a novel automated traffic control scheme for isolated intersections, this study proposes a network-level, real-time traffic control framework for CAVs on grid networks. The proposed framework integrates a rhythmic control method with an online routing algorithm to realize collision-free control of all CAVs on a network and achieve superior performance in average vehicle delay, network traffic throughput, and computational scalability. Specifically, we construct a preset network rhythm that all CAVs can follow to move on the network and avoid collisions at all intersections. Based on the network rhythm, we then formulate online routing for the CAVs as a mixed integer linear program, which optimizes the entry times of CAVs at all entrances of the network and their time–space routings in real time. We provide a sufficient condition that the linear programming relaxation of the online routing model yields an optimal integer solution. Extensive numerical tests are conducted to show the performance of the proposed operations management framework under various scenarios. It is illustrated that the framework is capable of achieving negligible delays and increased network throughput. Furthermore, the computational time results are also promising. The CPU time for solving a collision-free control optimization problem with 2,000 vehicles is only 0.3 second on an ordinary personal computer.

We study how delivery data can be applied to improve the on-time performance of last-mile delivery services. Motivated by the delivery operations and data of a food delivery service provider, we discuss a framework that integrates travel-time predictors with order-assignment optimization. Such integration enables us to capture the driver’s routing behavior in practice as the driver’s decision-making process is often unobservable or intricate to model. Focusing on the order-assignment problem as an example, we discuss the classes of tractable predictors and prediction models that are highly compatible with the existing stochastic and robust optimization tools. We further provide reformulations of the integrated models, which can be efficiently solved with the proposed branch-and-price algorithm. Moreover, we propose two simple heuristics for the multiperiod order-assignment problem, and they are built upon single-period solutions. Using the delivery data, our numerical experiments on a real-world application not only demonstrate the superior performance of our proposed order-assignment models with travel-time predictors, but also highlight the importance of learning behavioral aspects from operational data. We find that a large sample size does not necessarily compensate for the misspecification of the driver’s routing behavior. This paper was accepted by Hamid Nazerzadeh, big data analytics.

Apiculture has gained worldwide interest because of its contributions to economic incomes and environmental conservation. In view of these, migratory beekeeping, as a high-yielding technique, is extensively adopted. However, because of the lack of an overall routing plan, beekeepers who follow the experiential migratory routes frequently encounter unexpected detours and suffer losses when faced with problems such as those related to nectar source capacities and the production of bee products. The migratory beekeeping routing problem (MBRP) is proposed based on the practical background of the commercial apiculture industry to optimize the global revenue for beekeepers by comprehensively considering nectar source allocation, migration, production and sales of bee products, and corresponding time decisions. The MBRP is a new variant of the vehicle routing problem but with significantly different production time decisions at the vertices (i.e., nectar sources). That is, only the overlaps between residence durations and flowering periods generate production benefits. Different sales visits cause different gains from the same products; in turn, these lead to different production time decisions at previously visited nectar source locations and even change the visits for production. To overcome the difficulty resulting from the complicated time decisions, we utilize the Dantzig–Wolfe decomposition method and propose a revised labeling algorithm for the pricing subproblems. The tests, performed on instances and a real-world case, demonstrate that the column generation method with the revised labeling algorithm is efficient for solving the MBRP. Compared with traditional routes, a more efficient overall routing schedule for migratory beekeepers is proposed. Summary of Contribution. Based on the practical background of commercial apiculture industry, this paper proposes a new type of routing problem named the migratory beekeeping routing problem (MBRP), which incorporates the selection of productive nodes and sales nodes as well as the production time decision at the productive nodes on a migratory beekeeping network. To overcome the difficulty resulting from the complicated time decisions, we utilize the Dantzig–Wolfe decomposition method and propose a revised labeling algorithm for the pricing subproblems. The tests, performed on instances and a real-world case, demonstrate that the column generation method with the revised labeling algorithm is efficient for solving the MBRP. Compared with traditional routes, a more efficient overall routing schedule for migratory beekeepers is proposed. Therefore, this paper is congruent with, and contributes to, the scope and mission of INFORMS Journal on Computing, especially the area of Network Optimization: Algorithms & Applications.

We propose a model for optimizing the last-mile delivery of n packages from a distribution center to their final recipients, using a strategy that combines the use of ride-sharing platforms (e.g., Uber or Lyft) with traditional in-house van delivery systems. The main objective is to compute the optimal reward offered to private drivers for each of the n packages such that the total expected cost of delivering all packages is minimized. Our technical approach is based on the formulation of a discrete sequential packing problem, in which bundles of packages are picked up from the warehouse at random times during the interval [Formula: see text]. Our theoretical results include both exact and asymptotic (as [Formula: see text]) expressions for the expected number of packages that are picked up by time T. They are closely related to the classical Rényi’s parking/packing problem. Our proposed framework is scalable with the number of packages.

Regulating on-demand ride-hailing services (e.g., Uber and DiDi) requires a balance of multiple competing objectives: encouraging innovative business models (e.g., DiDi), sustaining traditional industries (e.g., taxi), creating new jobs, and reducing traffic congestion. This study is motivated by a regulatory policy implemented by the Chinese government in 2017 and a similar policy approved by the New York City Council in 2018 that regulate the “maximum” number of registered Uber/DiDi drivers. We examine the impact of these policies on the welfare of different stakeholders (i.e., consumers, taxi drivers, on-demand ride service company, and independent drivers). By analyzing a two-period dynamic game that involves these stakeholders, we find that, without government intervention, the on-demand ride service platform can drive the traditional taxi industry out of the market under certain conditions. Relative to no regulations and a complete ban policy, a carefully designed regulatory policy can strike a better balance of multiple competing objectives. Finally, if a government can reform the taxi industry by adjusting the taxi fare, then lowering the taxi fare instead of imposing a strict policy toward on-demand ride services can improve the total social welfare. This paper was accepted by Serguei Netessine, operations management.

We study the energy consumption minimization problems of natural gas transmission in gunbarrel structured networks. In particular, we consider the transient-state dynamics of natural gas and the compressor’s nonlinear working domain and min-up-and-down constraints. We formulate the problem as a two-level dynamic program (DP), where the upper-level DP problem models each compressor station as a decision stage and each station’s optimization problem is further formulated as a lower-level DP by setting each time period as a stage. The upper-level DP faces the curse of high dimensionality. We propose an approximate dynamic programming (ADP) approach for the upper-level DP using appropriate basis functions and an exact approach for the lower-level DP by exploiting the structure of the problem. We validate the superior performance of the proposed ADP approach on both synthetic and real networks compared with the benchmark simulated annealing (SA) heuristic and the commonly used myopic policy and steady-state policy. On the synthetic networks (SNs), the ADP reduces the energy consumption by 5.8%–6.7% from the SA and 12% from the myopic policy. On the test gunbarrel network with 21 compressor stations and 28 pipes calibrated from China National Petroleum Corporation, the ADP saves 4.8%–5.1% (with an average of 5.0%) energy consumption compared with the SA and the currently deployed steady-state policy, which translates to cost savings of millions of dollars a year. Moreover, the proposed ADP algorithm requires 18.4%–61.0% less computation time than the SA. The advantages in both solution quality and computation time strongly support the proposed ADP algorithm in practice.

We discuss some recent developments in smart city initiatives across the world to motivate the opportunities and challenges that such initiatives pose, and we categorize them into three themes: data access and collection, end-user utility, and economic viability of different solutions. We recognize that the academic literature that can help in addressing some of these challenges is at its nascent state and provide guidelines on how manufacturing and service operations management scholars can contribute to the global smart city movement.

China National Petroleum Corporation collaborated with researchers from the University of California and Tsinghua University to develop software for planning its natural gas pipelines. The work resulted in increased profits of $530 million between 2015 and 2017 and a budget reduction of more than $20 billion in construction costs for the subsequent five years.

The β-robust machine scheduling has attracted increasing attention as an effective method to hedge against uncertainty. However, existing β-robust scheduling models rely on the normality assumption of uncertain parameters, and existing solution methods are based on branch and bound, which cannot solve problems of 45 jobs within 3,600 seconds. This paper proposes distributionally β-robust scheduling (DRS) models to handle uncertain processing times. The DRS models only require the lower bound, mean, and covariance information of processing times, and have the capability of handling both single and parallel machine problems. Another key contribution of this paper is to devise efficient parametric search (PS) methods for the DRS models. Specifically, we show that there exists a parameterized assignment problem (PAP), such that its optimal solutions are also optimal for the original problem. The proposed methods only need to perform a one-dimensional PS and solve a series of PAPs. We further propose a bidirectional PS to reduce the number of PAPs needed to be solved, and we design a speedup shortest augmentation path algorithm for these PAPs. Experimental results on both single and identical parallel machine problems show that the improved PS method outperforms existing algorithms by more than three orders of magnitude improvement in computation time for problems of 45 jobs, and it is able to solve problems of 500 jobs within 0.5 seconds.

Problem definition: In this paper, we study a reliable hub location model, the objective of which is to minimize the associated costs plus the penalty for unserved demands. The model assigns to eac...

Most consumers in rural areas of many developing countries cannot afford to purchase certain livelihood improvement products such as home appliances. To improve consumer welfare and manufacturer profit, many governments launch different types of subsidy programs that offer subsidies to consumers, manufacturers, or both. Motivated by a subsidy program developed by the Chinese government in 2007, we present a parsimonious model to determine the optimal subsidy program in different settings so as to gain a better understanding about the conditions under which it is optimal for the government to subsidize consumers only, manufacturers only, or both. Our analysis reveals that the structure of the optimal subsidy program (i.e., subsidize consumers only, manufacturers only, or both) depends on: (a) whether there is a well-established market selling price for the products; and (b) the relative emphasis that the government places on consumer welfare versus manufacturer profit. Also, we find that government can improve consumer welfare by developing subsidy programs that involve multiple (competing) manufacturers with different market sizes. Moreover, when using an earmarked budget to develop a subsidy program that is intended to improve social welfare (manufacturer profit and consumer welfare), we find that it is more effective for the government to subsidize consumers only. Our findings provide insights for developing effective subsidy programs in developing countries.

We develop a framework for continuous search for information on a choice set of multiple alternatives and apply it to consumer search in a product market. When a consumer considers purchasing a product in a product category, the consumer can gather information sequentially on several products. At each moment, the consumer can choose which product to gather more information on and whether to stop gathering information and purchase one of the products or to exit the market with no purchase. Given costly information gathering, consumers end up not gathering complete information on all the products and need to make decisions under imperfect information. Under the assumption of constant informativeness of search, we solve for the optimal search, switch, and purchase or exit behavior in such a setting, which is characterized by an optimal consideration set and a purchase threshold structure. This paper shows that a product is only considered for search or purchase if it has a sufficiently high expected utility. Given multiple products in the consumer's consideration set, the consumer only stops searching for information and purchases a product if the difference between the expected utilities of the top two products is greater than some threshold. Comparative statics show that negative information correlation among products widens the purchase threshold, and so does an increase in the number of the choices. Under our rational consumer model, we show that choice overload can occur when consumers search or evaluate multiple alternatives before making a purchase decision. We also find that it is optimal for a monopolistic seller of multiple products to facilitate information search for low-valuation consumers and obfuscate information for those with high valuations. Keywords: information; search theory; consideration set; Brownian motions; choice overload

Regions with abundant wind resources usually have no ready access to the existing electric grid. However, building transmission lines that instantaneously deliver all geographically distributed wind energy can be costly. Energy storage (ES) systems can help reduce the cost of bridging wind farms and grids and mitigate the intermittency of wind outputs. In this paper, we propose models of transmission network planning with colocation of ES systems. Our models determine the sizes and sites of ES systems as well as the associated topology and capacity of the transmission network under the feed-in-tariff policy instrument. We first formulate a location model as a mixed-integer second-order-conic program to solve for the ES-transmission network design with uncapacitated storage. Then we propose a method to choose ES sizes by deriving a closed-form upper bound. The major insight is that, in most cases, using even small-sized ES systems can significantly reduce the total expected cost, but their marginal values diminish faster than those of the transmission lines as their capacities expand. Despite uncertainties in climate, technologies, and construction costs, the cost-efficient infrastructure layout is remarkably robust. We also identify the major bottleneck cost factors for different forms of ES technologies.

Most previous studies on reliable facility location design assume that disruptions at different locations are independent. In this paper, we present a model that allows disruptions to be correlated with an uncertain joint distribution, and we apply distributionally robust optimization to minimize the expected cost under the worst-case distribution with given marginal disruption probabilities. The worst-case distribution has a practical interpretation with disruption propagation, and its sparse structure allows solving the problem efficiently. Our numerical results show that ignoring disruption correlation could lead to significant loss that increases dramatically in key factors such as source disaster probability, disruption propagation effect, and service interruption penalty. On the other hand, the robust model results in very low regret, even when disruptions are independent, and starts to outperform the model assuming independence when disruptions are mildly correlated. Most of the benefit of the robust model can be captured with a very low additional cost, which makes it easy to implement. Given these advantages, we believe that the robust model can serve as a promising alternative approach for solving reliable facility location problems.

We study an inventory system wherein a customer may leave the seller's market after experiencing an inventory stockout. Traditionally, researchers and practitioners assume a single penalty cost to model this customer behavior of stockout aversion. Recently, a stream of researchers explicitly model this customer behavior and support the traditional penalty cost approach. We enrich this literature by studying the statistical learning of service-dependent demand. We build and solve four models: a baseline model, where the seller can observe the demand distribution; a second model, where the seller cannot observe the demand distribution but statistically learns the demand distribution; a third model, where the seller can learn or pay to obtain the exact information of the demand distribution; and a fourth model, where demand in excess of available inventory is lost and unobserved. Interestingly, we find that all four models support the traditional penalty cost approach. This result confirms the use of a state-independent stockout penalty cost in the presence of demand learning. More strikingly, the first three models imply the same stockout penalty cost, which is larger than the stockout penalty cost implied by the last model.

The benefits of inventory risk pooling are well known and documented. It has been proven in the literature that the expected costs of a centralized system are increasing in the degree of (positive) dependence of demand in an idealized newsvendor setting. Using the supermodular stochastic order to characterize dependence, we study a general two-tiered supply chain structure, in which both demand and supply yields are random, and prove that the expected costs are increasing in the degrees of positive dependence between demand and supply yield loss factors. Furthermore, using a distributionally robust optimization framework, we prove an analogous result for the case where demand and yield distributions are not precisely known.

We consider reliable facility location models in which facilities are subject to unexpected failures, and customers may be reassigned to facilities other than their regular facilities. The objective is to minimize the total expected costs in normal and failure scenarios. We allow facilities to have different failure rates and do not limit the number of facilities that might be assigned to a customer. Lower bounds for reliable uncapacitated fixed-charge location problem (RUFLP) are derived and used to introduce a class of efficient algorithms for solving the RUFLP problem.