Tag Archives: optimization

Recent research

Information design

Leave a comment

I have been collaborating with my PhD student, Qianni Wang, on information design for over a year. This paper—currently under review at Transportation Science—is the first fruit of our dedicated effort, and I am confident it will not be the last.

At its core, the idea behind information design is both simple and fascinating. If you are not yet familiar with it, I encourage you to explore Bayesian Persuasion, one of the earliest and most influential works published on the subject.

Information asymmetry—where one party holds information unavailable to others — lies at the heart of many important problems in economic and sociotechnical systems . In principal-agent problem (or the incentive problem), for example, the interests of the principal and agents diverge because the principal cannot perfectly monitor agents’ hidden actions or intentions. In the selection problem, one party in a transaction has private information that can lead to mismatches or undesirable outcomes. The beauty contest (or social learning) problem—which causes socially harmful herd behaviors—arise from individuals’ imperfect information, both of the system state and of what others know. The adverse effects of information asymmetry may be mitigated by aligning incentives, increasing transparency and inducing truthful behavior, often achieved through mechanism design.

Information design is motivated by information asymmetry that strongly favors the principal over the agents in a principal-agent game. In the context of transportation management, the principal is the manager and the agents are the users. Here, the users’ payoff depends on certain information observable only to the manager. As a result, the manager can exploit the information asymmetry to better align the interests of the two parties through persuasion . A unique feature of information design is that the manager is committed to an information structure ex-ante, which provides transparency and ensures incentive compatibility of the users.

This paper applies the concept of information design to a particular transportation application: resolving chaos in EV charging.  You can find an abstract below, and download a preprint here.

Charging remains an obstacle to the mass adoption of electric vehicles (EVs), especially for long-distance travel. If many EV drivers take to the road roughly at the same time, their “range anxiety” may create a self-fulfilling prophecy. As the drivers anticipate uncertainty and congestion at charging stations, they tend to make overly conservative decisions about when and where to charge. Yet, these decisions could worsen the very problem they try to prevent, collectively leading to chaos and inefficiency. Here, we show that information design can be used to persuade the drivers to adopt decisions that are better for the system while being consistent with their self-interest as defined by Bayesian Nash equilibrium. Our stylized model incorporates the congestion effect into the drivers‘ payoffs. It also assumes that the information designer has private knowledge about the state of charging and the driver type, defined by vehicle range. We consider both public and private information designs. The former does not depend on the driver type while the latter does. For the private design problem, we propose a novel cutoff structure that enables us to reformulate an infinite-dimensional problem as a finite one. When the random charging state can only take two discrete values, we prove that the optimal public design equals full information revelation. The optimal private design, however, promises significantly better results, potentially delivering the system optimal outcome under favorable conditions — e.g. when the charging state is highly uncertain and the marginal cost is similar regardless of the charging decision. We also show that the value of information increases with the level of uncertainty and the extra cost imposed by charging.

housekeeping, Recent research

Integrated bus-bike system

Leave a comment

After much delay, the last paper Sida and I wrote together came out last week in Transportation Research Part C.   Growing out of the last chapter of Sida’s PhD dissertation, the first draft of the paper was completed before he went back to China in the summer of 2020, at the height of COVID19 pandemic.   In part, the long delay was due to Sida’s transition to his new job at Beijing Jiaotong University.   I am glad he pressed on despite the early setbacks and eventually published the paper  in a descent journal.  Here is the abstract for those who wonder what is an integrated bus-bike system.

Abstract: This paper examines the design of a transit system that integrates a fixed-route bus service and a bike-sharing service. Bike availability – the average probability that a traveller can find a bike at a dock – is modelled as an analytical function of bike utilization rate, which depends on travel demand, bike usage and bike fleet size. The proposed system also recognizes the greater flexibility provided by biking. Specifically, a traveller can choose between the closest bus stop and a more distant stop for access, egress or both. Whether the closest stop is a better choice depends on the relative position of the traveller’s origin and destination, as well as system design parameters. This interdependence complicates the estimation of average system cost, which is conditional on route choice. Using a stylized analysis approach, we construct the optimal design problem as a mixed integer program with a small number of decision variables. Results from our numerical experiments show the integrated bus-bike system promises a modest but consistent improvement over several benchmark systems, especially in poorer cities with lower demand density. We find a large share of travellers, more than 20% in nearly all cases tested, opt not to use the nearest bus stop in an optimally designed system. The system also tends to maintain a high level of bike availability: the probability of finding a bike rarely drops below 90% except in very poor cities.

Recent research

Ethics-Aware Transit Design

Leave a comment

In this paper we proposed a corridor transit design model that places accessibility and equity at the center of the trade-off. By guiding transit design with ethical theories, it promises to improve vertical equity. We reviewed and examined four different ethical principle but were focused on the utilitarian principle (the status quo) and John Rawls’ difference principle (a form of egalitarianism). The main findings from our analysis of the design models are summarized as follows.

  • When the transit service is homogeneous in space, the utilitarian design model and the egalitarian design model are mathematically equivalent. Thus, they always produce identical designs for all forms of the opportunity distribution.
  • With supply heterogeneity, the egalitarian design has a prominent equity-enhancing effect, whereas the utilitarian design tends to exacerbate inequity, especially in presence of large innate inequality.
  • Correcting innate inequality by applying the egalitarian principle often entails interventions that appear more “discriminatory” than the status quo. Whether such distributive measures are justified, the appearance of unfairness can be met with skepticism, if not outright opposition, from the general public.
  •  Our ability to promote equity is restricted not only by the resources available but also by the structure of the problem at hand. The difference principle is useful because it defines the upper limit of equity that we may strive to reach but should not exceed.

It is worth recalling the egalitarian design based on the difference principle tends to reduce the total accessibility of all residents, compared to the incumbent design regime of utilitarianism. When innate inequality is large, the loss of accessibility can be substantial, up to 40\% according to our experiments. This, of course, is hardly a surprise, given the primary concern of the difference principle is the distributive justice, not the total utility. One thing is clear though: the benefits to the most disadvantaged could come at a hefty price to society writ large. Steven Dubner, the host of the popular podcast Freakonomics, likes to quip,

Economists know the price of everything but the value of nothing.

No doubt the same can be said about many if not most engineers. In some sense, our study constitutes an attempt to price social values in engineering practice. To be sure, these values are priceless to many an advocate, who would be quick to point out that the obsession with pricing everything is precisely what got us here in the first place. However, understanding the consequence of imposing certain values in engineering systems is still a crucial task, if only because we always need to secure public support or determine affordability.

The work is partially funded by Northwestern University’s Catalyst fund and NSF’s Smart and Connected Community (S&CC) Planning
Grant.  A prerprint of the paper may be downloaded here.

Recent research

Allocation problem for the platform of platforms

1 Comment

Another joint work with Ruijie Li, built on our previous research of ridesharing, including A-PASS and Pricing carpool.

In this study, we consider a general problem called the Allocation Problem for the Platform of Platforms – dubbed AP3.  Such a problem might arise  in a two-sided service market, where a third-party integrator tries to allocate customers to workers separately controlled by a set of online platforms in a manner that satisfies all stakeholders.   The integrator, as a leader, influences the outcome of the game by pricing the service, whereas the platforms (followers) are given the freedom to accept or reject customers to maximize their own profit, given the prices set by the integrator (see the plot below for an illustration).  A set of nonlinear constraints are imposed on the leader’s problem to eliminate artificial scarcity, orignated from the integrator’s monopoly power.  We formulate AP3 as a Stackelberg bipartite matching problem, which is known to be NP-hard in general.  Our main result concerns the proof that AP3 can be reduced to a polynomially solvable problem by taking advantage of, somewhat paradoxically, the hard requirement of ruling out artificial scarcity.

A preprint can be downloaded here.

Abstract: We study the Allocation Problem for the Platform of Platforms (abbreviated as AP3) in a two-sided service market, where a third-party integrator tries to allocate customers to workers separately controlled by a set of online platforms in a manner that satisfies all stakeholders. AP3 is a natural Stackelberg game. The integrator, as a leader, influences the outcome of the game by pricing the service, whereas the platforms (followers) are given the freedom to accept or reject customers to maximize their own profit, given the prices set by the integrator. A set of nonlinear constraints are imposed on the leader’s problem to eliminate artificial scarcity, derived from the integrator’s monopoly power. We formulate AP3 as a Stackelberg bipartite matching problem, which is known to be NP-hard in general. Our main result concerns the proof that AP3 can be reduced to a polynomially solvable problem by taking advantage of, somewhat paradoxically, the “hard” requirement of ruling out artificial scarcity. Numerical experiments are conducted using the ride-hail service market as a case study. We find artificial scarcity negatively affects the number of customers served, although the magnitude of the effect varies with market conditions. In most cases, the integrator takes the lion’s share of the profit, but the need to eliminate artificial scarcity sometimes forces them to concede the benefits of collaboration to the platforms. The tighter the supply relative to the demand, the more the platforms benefit from removing artificial scarcity. In an over-supplied market, however, the integrator has a consistent and overwhelming advantage bestowed by its monopoly position.

Recent research

Differentiable bilevel programming

Leave a comment

A Stackelberg congestion game (SCG) is a bilevel program in which a leader aims to maximize their own gain by anticipating and manipulating the equilibrium state at which followers settle by playing a congestion game. Large-scale SCGs are well known for their intractability and complexity.   In this study,  we attempt to marry the latest developments in machine learning with traditional methodologies — notably bilevel optimization and game theory — to forge an integrative approach based on differentiable programming.  Among other advantages,  the approach enables us to treat the equilibration of a congestion game as a deep neural network (see below), so that a suite of computational tools, notably automatic differentiation, can be easily applied.  You may download a preprint here.

Abstract: A Stackelberg congestion game (SCG) is a bilevel program in which a leader aims to maximize their own gain by anticipating and manipulating the equilibrium state at which followers settle by playing a congestion game. Large-scale SCGs are well known for their intractability and complexity. This study approaches SCGs through differentiable programming, which marries the latest developments in machine learning with conventional methodologies. The core idea centers on representing the lower-level equilibrium problem using an evolution path formed by the imitative logit dynamics. It enables the use of automatic differentiation over the evolution path towards equilibrium, leading to a double-loop gradient descent algorithm. We further show the fixation on the lower-level equilibrium may be a self-imposed computational obstacle. Instead, the leader may only look ahead along the followers’ evolution path for a few steps, while updating their decisions in sync with the followers through a co-evolution process. The revelation gives rise to a single-loop algorithm that is more efficient in terms of both memory consumption and computation time. Through numerical experiments that cover a wide range of benchmark problems, we find the single-loop algorithm consistently strikes a good balance between solution quality and efficiency, outperforming not only the standard double-loop implementation but also other methods from the literature. Importantly, our results highlight both the wastefulness of “full anticipation” and the peril of “zero anticipation”. If a quick-and-dirty heuristic is needed for solving a really large SCG, the proposed single-loop algorithm with a one-step look-ahead makes an ideal candidate.

Recent research

How many are too many?

Leave a comment

If you had visited  big Chinese cities between 2016 and 2019, you might have noticed many sidewalks  rendered completely unwalkable by a myriad of shared bikes.  Thrown out there by well-meaning entrepreneurs and ambitious investors who funded their operations, the sight of these bikes clogging public space epitomizes the feverish quest for growth that has become the hallmark of the Chinese Model.  My sense was that most shared bike operators had no idea — or did not care —  how many bikes they need to serve a given city well and at what price they should charge the users in order to cover the operating cost, including the cost of routinely moving the bikes around to meet the demand.    However, as a transportation modeler and analyst, I  found these questions fascinating, and this paper was precisely the result of my attempt to answer them.

You can read the abstract below and a preprint can be downloaded here.

How Many Are Too Many? Analyzing Dockless Bikesharing Systems with a Parsimonious Model

Using a parsimonious model, this paper analyzes a dockless bikesharing (DLB) service that competes with walking and a generic motorized mode. The DLB operator chooses a fleet size and a fare schedule that dictate the level of service (LOS), as measured by the access time, or the walking time taken to reach the nearest bike location. The market equilibrium is formulated as a solution to a nonlinear equation system, over which three counterfactual design problems are defined to maximize (i) profit; (ii) ridership; or (iii) social welfare. The model is calibrated with empirical data collected in Chengdu, China and all three counterfactual designs are tested against the status quo. We show the LOS of a DLB system is subject to rapidly diminishing returns to the investment on the fleet. Thus, under the monopoly setting considered herein, the current fleet cap set by Chengdu can be cut by up to three quarters, even when the DLB operator aims to maximize social welfare. This indicates the city’s fleet cap decision might have been misguided by the prevailing conditions of a competitive yet highly inefficient market. For a regulator seeking to influence the DLB operator for social good, the choice of policy instruments depends on the operator’s objective. When the operator focuses on profit, limiting fare is much more effective than limiting fleet size. If, instead, they aim to grow their market share, then setting a limit on fleet size becomes a dominant strategy. We also show, both analytically and numerically, the ability to achieve a stable LOS with a low rebalancing frequency is critical to profitability. A lower rebalancing frequency always rewards users with cheaper fares and better LOS, even for a profit-maximizing operator.

Previous research

Paired-Line Hybrid Transit

Leave a comment

Paired-Line Hybrid Transit was the first in a series of “hybrid-transit” studies conducted by my group using a stylized design model.  This line of work, funded by an National Science Foundation between   2013 and 2016, was initiated by Peng Chen in his PhD thesis.  The main idea is to pair a demand-adaptive service with a fixed-route service so that the transit system can leverage the advantages of both while avoiding their drawbacks.  The paper was published in Transportation Research Part B in 2017.

For preprint, check  Hybrid Transit System Design_Journal_2.0

Abstract: This paper proposes and analyzes a new transit system that integrates the traditional fixed-route service with a demand-adaptive service. The demand-adaptive service connects passengers from their origin/destination to the fixed-route service in order to improve accessability. The proposed hybrid design is unique in that it operates the demand-adaptive service with a stable headway to cover all stops along a paired fixed-route line. Pairing demand-adaptive vehicles with a fixed-route line simplifies the complexity of on-demand routing, because the vehicles can follow a more predictable path and can be dispatched on intervals coordinated with the fixed-route line. The design of the two services are closely
coupled to minimize the total system cost, which incudes both the transit agency’s operating cost and the user cost. The optimal design model is formulated as a mixed integer program and solved using
a commercially available metaheuristic. Numerical experiments are conducted to compare the demand adaptive paired-line hybrid transit (DAPL-HT) system with two related transit systems that may be considered its special cases: a fixed-route system and a flexible-route system. We show that the DAPL-HT system outperforms the other two systems under a wide range of demand levels and in various scenarios of input parameters. A discrete-event simulation model is also developed and applied to confirm the correctness of the analytical results.

Previous research

Planning EV charging infrastructure

Leave a comment

This paper was our first on sustainability-related topics.  As mentioned in the Acknowledgment, it was  inspired by  Professor David Boyce’s 2012 trip from Chicago, IL to Madison, WI.  At the time, he just bought a Nissan Leaf (one of the first successful battery electric vehicle models, with a whooping range  of 70 miles！), and was eager to prove it can be used for long-distance travel.     Due to the limited availability of charging stations back then, however, he was forced to spend one night at a hotel that was less than 20 miles from Madison, turning a four-hour trip to an overnight one.

David’s adventure got me into the EV infrastructure planning, which eventually led to this paper, and a PhD thesis completed by Mehrnaz Ghamami.  The core idea  of this paper is the consideration of the tradeoff between battery cost and charging stations in EV infrastructure planning. That is, from a system point of view, how should social  resources be allocated between manufacturing larger batteries and building more charging facilities?  Check the abstract below for our main findings, and you can also download  Preprint  here.

The paper was published in Transportation Research Part B in 2013.

Abstract: The transition to electric vehicles (EV) faces two major barriers. On one hand, EV batteries are still expensive and limited by range, owing to the lack of technology breakthrough. On the other hand, the underdeveloped supporting infrastructure, particularly the lack of fast refueling facilities, makes EVs unsuitable for medium and long distance travel. The primary purpose of this study is to better understand these hurdles and to develop strategies to overcome them. To this end, a conceptual optimization model is proposed to analyze travel by EVs along a long corridor. The objective of the model is to select the battery size and charging
capacity (in terms of both the charging power at each station and the number of stations needed along the corridor) to meet a given level of service in such a way that the total social cost is minimized. Two extensions of the base model are also considered. The first relaxes the assumption that the charging power at the stations is a continuous variable. The second variant considers battery swapping as an alternative to charging. Our analysis suggests that (1) the current paradigm of charging facility development that focuses on level 2 charging delivers extremely poor level of service; (2) the level 3 charging method is necessary not only to achieve a reasonable level of service, but also to minimize the social cost, (3) investing
on battery technology to reduce battery cost is likely to have larger impacts on reducing the charging cost; and (4) battery swapping promises high level of service, but it may not be socially optimal for a modest level of service, especially when the costs of constructing swapping and charging stations are close.

Recent research

Are autonomous vehicles better off without signals?

Leave a comment

The arrival of autonomous vehicles has prompted many to imagine a world without annoying traffic signals.  If cars are smart enough to drive themselves, one is inclined to reason, why cannot they simply chart a crash-free path through at-grade intersections all by themselves?  In this paper, we ask: is eliminating signals from  intersection desirable, even if it is possible?  The abstract below provides a short answer (hint: Yes and No).   If you are interested in reading the full paper, a preprint may be found here. The paper recently appeared in Transportation Research Part B.

Abstract: We model and analyze a futuristic intersection that serves only connected, autonomous and centrally managed vehicles. Under consideration are three control strategies that aim to minimize the total system delay by choosing an optimal trajectory for each vehicle. The first two abandon the concept of signal timing all together whereas the third strategy keeps it. The difference between the two signal-free strategies has to do with a fail-safe buffer requirement introduced to provide redundancy. Each control strategy leads to a unique version of a trajectory-based autonomous intersection management (T-AIM) problem, which is formulated as a mixed integer linear program and solved using a variety of techniques. We found the signal-free strategy holds an overwhelming advantage over the signal-based strategy in terms of efficiency. However, its success is fragile and dependent on the faith in the safety and reliability of the system. When the fail-safe buffer is introduced, the efficiency of the signal-free strategy degrades to a level comparable to that of a properly designed signal-based strategy. Surprisingly, the signal-free strategy with redundancy tends to arrange vehicles in groups that take turns to cross the intersection together. This “signal-like behavior” manifests itself whenever congestion rises to certain threshold. In addition, solving the T-AIM problem based on signal timing enjoys significant computational benefits, because it eliminates cross conflicts. Thus, the basic logic of signal timing—if not the physical equipment—may survive even after humans are no longer allowed to drive.

Recent research

To pool or not to pool

Leave a comment
To Pool or Not to Pool: Equilibrium,  Pricing and Regulation

This paper was the first published based on  Kenan’s PhD research. It introduces ride-pooling into the equilibrium analysis of the ride-hail market and analyzes the effect of pricing strategies and various regulations on pooling.

After the first draft is completed in the Spring of 2019,  it took almost two years  to move the paper through various stages of the review process, first at Management Science, then at Transportation Research Part B (three rounds). While the long waiting was no doubt frustrating, the quality of the paper might have benefited from intensive scrutiny and repeated revisions.  For a preprint, please check here; the link to the final version is here.

Abstract: We study a monopoly transportation network company (TNC) in an aggregate market that offers on-demand solo and pooling e-hail services, while competing with transit for passengers. The market equilibrium is established based on a spatial driver-passenger matching model that characterizes the passenger wait time for both solo and pooling rides. We prove, under mild conditions, this system always has an equilibrium solution. Built on the market equilibrium, three variants of pricing problems are analyzed and compared, namely, (i) profit maximization, (ii) profit maximization subject to regulatory constraints, and (iii) social welfare maximization subject to a revenue-neutral constraint. A comprehensive case study is constructed using TNC data collected in the city of Chicago. We found pooling is desirable when demand is high, but supply is scarce. However, its benefit diminishes quickly as the average en-route detour time (i.e., the difference between the average duration of solo and pooling trips) increases. Without regulations, a mixed strategy—providing both solo and pooling rides—not only achieves the highest profit and trip production in most scenarios, but also gains higher social welfare. The minimum wage policy can improve social welfare in the short term. However, in the long run, the TNC could react by limiting the size of the driver pool, and consequently, render the policy counterproductive, even pushing social welfare below the unregulated level. Moreover, by maintaining the supply and demand of ride-hail at an artificially high level, the minimum wage policy tends to exacerbate traffic congestion by depressing the use of collective modes (transit and pooling). A congestion tax policy that penalizes solo rides promotes pooling, but consistently harms social welfare. However, it promises to increase both social welfare and pooling ratio, when jointly implemented with the minimum wage policy.