Category Archives: Recent research

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.

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

Fall and rise of taxi travel during COVID

Leave a comment

This is our second COVID19 related study, completed in 2020 and published in Transportation Research Part A in 2021. You may read  the other one here, which is about optimally adapting transit design and operations in a pandemic.

We examined taxi trajectory data collected in four weeks that cover the onset of COVID19, the shutdown, and phased reopening in the city of Shenzhen. Our analysis revealed how the pandemic and the travel restriction policies affected both the supply and the demand of the taxi market in the city.   One of the more interesting findings is that the city’s stimulus policy, designed to boost taxi supply and help taxi drivers, might have led to oversupply, by inducing taxi drivers to spend more time on the road than what the prevailing market condition would justify.  We uncovered direct evidence from data to support this finding through a clustering analysis.

A preprint is available here.

Abstract: This paper traces the plunge and rebound of the taxi market in Shenzhen, China through the COVID-19 lockdown. A four-week taxi GPS trajectory data set is collected in the first quarter of 2020, which covers the period of lockdown and phased reopening in the city. We conduct a spatiotemporal analysis of taxi demand using the data, and then select taxis that continued to operate through the analysis period to examine whether and how they adjusted operational strategies. We find, among other things: (i) the taxi demand in Shenzhen shrank more than 85% in the lockdown phase and barely recovered from that bottom even after the city began to reopen; (ii) the recovery of taxi travel fell far behind that of the overall vehicle travel in the city; (iii) most taxis significantly cut back work hours in response to the lockdown, and many adjusted work schedule to focus on serving peak-time demand after it was lifted; (iv) taxi drivers demonstrate distinct behavioral adaptations to the pandemic that can be identified by a clustering analysis; and (v) while the level of taxi service dropped precipitately at the beginning, it quickly rebounded to exceed the pre-pandemic level, thanks to the government’s incentive policy. These empirical findings suggest (i) incentives aiming at boosting supply should more precisely target where the boost is most needed; (ii) the taxi market conditions should be closely monitored to support and adjust policies; and (iii) when the demand is severely depressed by lockdown orders or when the market is oversupplied, taxi drivers should be encouraged and aided to use more centralized dispatching modes.

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.

Recent research

Travel demand management practice in China

Leave a comment

This article stemmed from a research report commissioned by World Bank back in 2019.   I’ve never tried to publish it in a journal, though my friend Daizong Liu had helped translate it into Chinese and published it online through his very successful Wechat public platform (一览众山小).  The article reviews the travel demand management practice in China and attempts to draw some useful lessons from it.  You may read the abstract below and download the Egnlish version at ChinaTDM.

Lessons Learned from China’s Travel demand management practice

China’s car ownership has been expanding at a staggering pace in the past two decades. The rapid motorization brought unprecedented level of traffic to its densely populated cities
unprepared to accommodate it, causing severe congestion and air pollution problems. Chinese cities have responded to these challenges with sweeping travel demand management (TDM) measures. The practice of TDM in China is unique not only because it is large in scale and broad in scope, but also because it occurs against the backdrop of a fast and historical transition of the most populous country on earth. The objective of this note is to review and document this practice, discuss its outcomes and lessons, and examine what the rest of the world could learn from it.

Recent research

Hyperbush

Leave a comment

Hyperbush Algorithm for Strategy-based Equilibrium Traffic Assignment Problems

This recent paper extends the concept of bush to hyperbush and uses it devise a new class of algorithms for strategy-based traffic equilibrium assignment problem, of which frequency-based transit assignment is an archetype.  One of the longest papers that I’ve ever written (nearly 50 pages), the paper just appeared online in Transportation Science.    Here is a preprint  Hyperbush.

Strategy-based equilibrium traffic assignment (SETA) problems define travel choice broadly as a strategy rather than a simple path. Travelers navigating through a network based on a strategy end up following a hyperpath. SETA is well suited to represent a rich set of travel choices that take place en-route at nodes, such as transit passengers’ transfer decision, truckers’ bidding decision and taxi drivers’ re-position decision. This paper recognizes and highlights the commonalities among classical and emerging SETA problems and proposes to unify them within a same modeling framework, built on the concept of hypergragh. A generic hyperbush algorithm (HBA) is developed by decomposing a hypergraph into destination-based hyperbushes. By constructing hyperbushes and limiting traffic assignment to them, HBA promises to obtain more precise solutions to larger instances of SETA problems at a lower computational cost, both in terms of CPU time and memory consumption. To demonstrate its generality and efficiency, we tailor HBA to solve two SETA problems. The results confirm HBA consistently outperforms the benchmark algorithms in the literature, including two state-of-the-art {hyperpath-based} algorithms. To obtain high-quality equilibrium solutions for SETA instances of practical size, HBA runs up to five times faster than the best competitor with a fraction of its memory consumption.