Tag Archives: optimization

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.

Recent research

Transit Design in Response to a Global Pandemic

Leave a comment

Optimizing Operational Strategies for Mass Transit Systems in Response to a Global Pandemic

This is one of my COVID inspired research projects that was started in 2020.  The idea is that, in order to operate safety during a pandemic, transit agencies might have to adjust their operational strategies, in terms of service frequency and capacity.  The underlying tradeoff we are trying to explore here is that between the benefit of frequently testing drivers (as it reduces the transmission risk) and the cost of lowering the number of passengers allowed in buses, subject to the need to maintain certain safety standard, measured by infection risks. A novelty of the work is a physical model aiming to estimate infection risks based on vehicle size/type, service capacity and a few external risk factors.

The paper is currently under revision at Journal of Transportation Research Part A.   Please download a preprint here.

Abstract              This study analyzes the risk involved in riding various transit modes during and after a global pandemic. The goal is to identify which factors are related to this risk, how such a relationship can be represented in a manner amenable to analysis, and what a transit operator can do to mitigate the risk while running its service as efficiently as possible. The resulted infection risk model is sensitive to such factors as prevalence of infection, baseline transmission probability, social distance, and expected number of human contacts. Built on this model, we formulate, analyze and test three versions of a transit operator’s design problem. In the first, the operator seeks to jointly optimize vehicle capacity and staff testing frequency while keeping the original service schedule and satisfying the infection risk requirement. The second model assumes the operator is obligated to meet the returning demand after the peak of the pandemic. The third allows the operator to run more than one transit line and to allocate limited resources between the lines, subject to the penalty of unserved passengers. We find: (i) The optimal profit, as well as the testing frequency and the vehicle capacity, decreases when passengers expect to come in close contact with more fellow riders in a trip; (ii) Using a larger bus and/or reducing the testing cost enables the operator to both test drivers more frequently and allow more passengers in each bus; (iii) If passengers weigh the risk of riding bus relative to taxi, a higher prevalence of infection has a negative effect on transit operation, whereas a higher basic transmission probability has a positive effect; (iv) The benefit of improving service capacity and/or testing more frequently is limited given the safety requirement imposed. When the demand rises beyond the range of the capacity needed to maintain sufficient social distancing, the operator has no choice but to increase the service frequency; and (v) In the multi-line case, the lines that have a larger pre-pandemic demand, a higher penalty for each unserved passenger, or a greater exposure risk should be prioritized.