Category Archives: Recent research

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

Wardrop equilibrium can be boundedly rational

1 Comment

As one of the most fundamental concepts in transportation science, Wardrop equilibrium (WE) was the cornerstone of countless large mathematical models that were built in the past six decades to plan, design, and operate transportation systems around the world. However, like Nash Equilibrium, its more famous cousin, WE has always had a somewhat flimsy behavioral foundation. The efforts to beef up this foundation have largely centered on reckoning with the imperfections in human decision-making processes, such as the lack of accurate information, limited computing power, and sub-optimal choices. This retreat from behavioral perfectionism was typically accompanied by a conceptual expansion of equilibrium. In place of WE, for example, transportation researchers had defined such generalized equilibrium concepts as stochastic user equilibrium (SUE) and boundedly rational user equilibrium (BRUE). Invaluable as these alternatives are to enriching our understanding of equilibrium and advancing modeling and computational tools, they advocate for the abandonment of WE, predicated on its incompatibility with more realistic behaviors. Our study aims to demonstrate that giving up perfect rationality need not force a departure from WE, since WE may be reached with global stability in a routing game played by boundedly rational travelers. To this end, we construct a day-to-day (DTD) dynamical model that mimics how travelers gradually adjust their valuations of routes, hence the choice probabilities, based on past experiences.

Our model, called cumulative logit (CULO), resembles the classical DTD models but makes a crucial change: whereas the classical models assume routes are valued based on the cost averaged over historical data, ours values the routes based on the cost accumulated. To describe route choice behaviors, the CULO model only uses two parameters, one accounting for the rate at which the future route cost is discounted in the valuation relative to the past ones (the passivity measure) and the other describing the sensitivity of route choice probabilities to valuation differences (the dispersion parameter).  We prove that the CULO model always converges to WE, regardless of the initial point, as long as the passivity measure either shrinks to zero as time proceeds at a sufficiently slow pace or is held at a sufficiently small constant value. Importantly, at the aggregate (i.e., link flow) level, WE is independent of the behavioral parameters. Numerical experiments confirm that a population of travelers behaving differently reaches the same aggregate WE as a homogeneous population, even though in the heterogeneous population, travelers’ route choices may differ considerably at WE.

By equipping WE with a route choice theory compatible with bounded rationality, we uphold its role as a benchmark in transportation systems analysis. Compared to the incumbents, our theory requires no modifications of WE as a result of behavioral accommodation. This simplicity helps avoid the complications that come with a “moving benchmark”, be it caused by a multitude of equilibria or the dependence of equilibrium on certain behavioral traits. Moreover, by offering a plausible explanation for travelers’ preferences among equal-cost routes at WE, the theory resolves the theoretical challenge posed by Harsanyi‘s instability problem. Note that we lay no claim on the behavioral truth about route choices. Real-world routing games take place in such complicated and ever-evolving environments that they may never reach a true stationary state, much less the prediction of a mathematical model riddled with a myriad of assumptions. Indeed, a relatively stable traffic pattern in a transportation network may be explained as a point in a BRUE set, an SUE tied to properly calibrated behavioral parameters, or simply a crude WE according to the CULO model. More empirical research is still needed to compare and vet these competing theories for target applications. However, one should no longer write off WE just because it has no reasonable behavioral foundation.

A preprint can be downloaded at ArXiv or SSRN.

Recent research

The sustainability appeal of URT

Leave a comment

Few would deny that public transit has an important role to play in any sensible solutions to the transportation’s sustainability problem. Yet, the consensus often dissolves at the question of how. A case in point concerns urban rail transit (URT), which has expanded rapidly in recent decades.   The ongoing debate about URT has been fueled by inconclusive, sometimes contradictory, empirical evidence reported in the literature.  Has URT consistently reduced driving and/or auto ownership to affirm its appeal to sustainability? We set out to address this question head-on in this study.

You may read the abstract below, and download a preprint here.

Abstract: Urban rail transit (URT) has expanded rapidly since the dawn of the century. While the high cost of building and operating URT systems is increasingly justified by their presumed contribution to sustainability — by stimulating transit-oriented development, promoting the use of public transportation, and alleviating traffic congestion — the validity of these claims remains the subject of heated debates. Here we examine the impact of URT on auto ownership, traffic congestion, and bus usage and service, by applying fixed-effects panel regression to time series data sets compiled for major urban areas in China and the US. We find that URT development is strongly and negatively correlated with auto ownership in both countries. This URT effect has an absolute size (as measured by elasticity) in China three times that in the US, but is much larger in the US than in China, relative to other factors such as income and unemployment rate. Importantly, the benefit transpires only after a URT system reaches the tipping point that unleashes the network effect.  Where this condition is met, we estimate about 14,012 and 31,844 metric tons of greenhouse gas emissions can be eliminated each year in China and the US, respectively, for each additional million URT vehicle kilometers traveled. We also uncover convincing evidence of cannibalization by URT of bus market share in both countries. However, rather than undermining bus services, developing URT strongly stimulates their growth and adaptation. Finally, no conclusive evidence is found that confirms a significant association between URT and traffic congestion. While traffic conditions may respond positively to URT development in some cases, the relief is likely short-lived.

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.

Recent research

Bi-criteria traffic assignment

Leave a comment

The traffic assignment problem (TAP) aims to find the distribution of agents—travelers, goods or data—in a network according to certain rules that govern how the agents make choices and move in the network. This problem lies at the heart of numerous applications, ranging from infrastructure planning to travel demand management. In these applications, it is often important to differentiate the agents according to the governing rules.  The trade-off between two attributes by agents with heterogeneous preferences is ubiquitous in route choice, traffic assignment, congestion games and beyond, and it leads to the bi-criteria traffic assignment (BiTA) problem concerned herein.  In this study, we develop a novel  algorithm to solve a continuous version of the BiTA problem. See Abstract for details.

This is a joint work with my former visiting PhD student and  Postdoc Jun Xie (currently Associate Professor at Southwest Jiaotong University, Chengdu, China) and Qianni Wang, an MS student currently at Northwestern University. The paper is currently under revision at Operations Research; a preprint can be downloaded here.

Abstract: This paper studies the continuous bi-criteria traffic assignment (C-BiTA) problem, which aims to find the distribution of agents with heterogeneous preferences in a network. The agents can be seen as playing a congestion game and their payoff is a linear combination of time and toll accumulated over the selected path. We rediscover a formulation that enables the development of a novel and highly efficient algorithm. The novelty of the algorithm lies in a decomposition scheme and a special potential function. Together, they reduce a complex assignment problem into a series of single boundary adjustment (SBA) operations, which simply shift flows between “adjacent” efficient paths connecting an origin-destination (OD) pair using a Newton method. The SBA algorithm is capable of producing highly detailed path-based solutions that hitherto are not widely available to C-BiTA. Our numerical experiments, which are performed on networks with up to forty thousand links and millions of OD pairs, confirmed the consistent and significant computational advantage of the SBA algorithm over the Frank-Wolfe (FW) algorithm, the widely-held benchmark for C-BiTA. In most cases, SBA offers a speedup of an order of magnitude.  We also uncovered evidence suggesting the discretization-based approach—or the standard multi-class formulation—-is likely to produce far more used paths per OD pair than C-BiTA, a potential computational disadvantage. Equipped with the proposed algorithm, C-BiTA, as well as its variants and extensions, could become a viable tool for researchers and practitioners seeking to apply multi-criteria assignment models on large networks.

Recent research

Mitigating TNC-induced traffic congestion

Leave a comment

While the e-hail service offered by TNCs is widely credited for boosting productivity and enhancing level of service, its adverse traffic impact in already-congested city centers has drawn increased scrutiny.   Several cities have started to implement  policies aiming to mitigate the traffic impact induced by excessive TNC operations.   The purpose of this study is to support such policy analysis by developing a model that captures the complex interactions among various stakeholders (riders, drivers and the platform) and those between them and the regulator.   Please read the abstract below for main findings.

The paper was recently published in Transportation Research Part A.   A preprint can be downloaded here.

Abstract: This paper analyzes and evaluates several policies aiming to mitigate the congestion effect a Transportation Network Company (TNC) brings to bear on an idealized city that contains a dense central core surrounded by a larger periphery. The TNC offers both solo and pooling e-hail services to the users of public transport. We develop a spatial market equilibrium model over two building blocks: an aggregate congestion model describing the traffic impact of TNC operations on all travelers in the city, including private motorists, and a matching model estimating the TNC’s level of service based on the interactions between riders and TNC drivers. Based on the equilibrium model, we formulate and propose solution algorithms to the optimal pricing problem, in which the TNC seeks to optimize its profit or social welfare subject to the extra costs and/or constraints imposed by the congestion mitigation policies. Three congestion mitigation policies are implemented in this study: (i) a trip-based policy that charges a congestion fee on each solo trip starting or ending in the city center; (ii) a cordon-based policy that charges TNC vehicles entering the city center with zero or one passenger; and (iii) a cruising cap policy that requires the TNC to maintain the fleet utilization ratio in the city center above a threshold. Based on a case study of Chicago, we find TNC operations may have a significant congestion effect. Failing to anticipate this effect in the pricing problem leads to sub-optimal decisions that worsen traffic congestion and hurt the TNC’s profitability. Of the three policies, the trip-based policy delivers the best performance. It reduces traffic congestion modestly, keeps the TNC’s level of service almost intact, and improves overall social welfare substantially. The cruising cap policy benefits private motorists, thanks to the extra congestion relief it brings about. However, because other stakeholders together suffer a much greater loss, its net impact on social welfare is negative. Paradoxically, the policy could worsen the very traffic conditions in the city center that it is designed to improve.

Recent research

Pricing carpool rides

Leave a comment

The initial idea of the paper was proposed by Ruijie Li, then a visiting student from Southwest Jiaotong University. He read about the mechanism design issues in ride-sharing, and was convinced that more research is needed in this direction.  In this paper we focus on a feature that many ridesharing users care about: the schedule displacement (i.e., the difference between the desired and actual arrival time) in matching.   By assuming the users bid for shared rides by reporting their valuation of the displacement, we are able to analyze the matching and pricing problem using the auction theory, including the well-known VCG scheme.    The paper was published in Transportation Science in 2020.    A preprint may be downloaded here.

Abstract: This paper considers a carpool matching (CaMa) problem in which participants price shared rides based on both operating cost and schedule displacement (i.e, the absolute difference between the desired and actual arrival times). By reporting their valuation of this displacement, each participant in effect bids for every possible shared ride that generates a unique value to her. The CaMa problem can be formulated as a mixed integer program (MIP) that maximizes the social welfare by choosing matching pairs and a departure time for each pair. We show the optimal departure time can be determined for each pair a prior, independent of the matching problem. This result reduces the CaMa problem to a standard bipartite matching problem. We prove that the classical Vickrey-Clarke-Groves (VCG) pricing policy ensures no participant is worse off or has the incentive to misreport their valuation of schedule displacement. To control the large deficit created by the VCG policy, we develop a single-side reward (SSR) pricing policy, which only compensates participants who are forced by the system to endure a schedule displacement. Under the assumption of overpricing tendency (i.e., no participant would want to underreport their value), we show the SSR policy not only generates substantial profits, but also retains the other desired properties of the VCG policy, notably truthful reporting. Even though it cannot rule out underreporting, our simulation experiments confirm that the SSR policy is a robust and deficit-free alternative to the VCG policy. Specifically, we find that (1) underreporting is not a practical concern for a carpool platform as it never reduces the number of matched pairs and its impact on profits is largely negligible; and (2) participants have very little to gain by underreporting their value.