All posts by yni957

Bi-criteria traffic assignment

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.

Paired-Line Hybrid Transit

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.

A theory of justice

Until I come across John Rawls’ book, I have never thought the word Theory can be associated with Justice (公正).  I was reluctant to commit my leisure time to reading “theories” (my job gives me plenty already), but my better judgement was overridden by the charisma of the loaded buzzword of our time.  Don’t get me wrong: the book is worth reading.  However, getting through five hundred pages of hard (and dry) reasoning and argument—with few stories or quips to catch a break—was quite a mental exercise.  Well, here is what I have learned.

A theory of justice is a set of principles designed to resolve the conflict of interests arising from human cooperation.  These principles form the basis for regulating social behaviors and arranging political institutions.   Rawls’ theory, which earned him the reputation as one of the most influential political philosophers of the 20th century, is dubbed “Justice as Fairness”.   It consists of three principles. The first principle (A) guarantees an equal right to “most extensive” basic liberties.  The other two state social and economic inequalities are just if and only if they (B) are attached to positional goods open to all under conditions of equal opportunity, and (C) maximize primary goods enjoyed by the least advantaged members of society.  The three principles follow a lexical order: the equal liberty principle (A) takes priority, followed by the equal opportunity principle (B) and the difference principle (C).

At first glance justice as fairness seems decisively egalitarian.  Rawls advocates compensation for the “undeserved inequalities” from birth and natural endowment.  Under the difference principle (C), “society must give more attention to those with fewer native assets and to those born into the less favorable social positions”.  An example is spending greater resources on “the education of the less rather than the more intelligent”.  In fact, Rawls has gone so far as to assert the willingness to make an effort is also contingent upon social circumstances. In other words, even inequalities caused by laziness may be undeserved and thus warrant social redress.    To be sue, Rawls does not support eradicating inequalities all together. Instead, inequalities are to be tolerated in so far as they benefit everyone, especially the most disadvantaged.    Moreover, positional goods should be distributed based on the equal opportunity principle, and if doing so leads to inequalities, so be it.  Thus, Rawls seems to prefer meritocracy to equal-outcome when it comes to positional goods. There is a catch though: everyone must “have reasonable opportunity to acquire the skills on the basis of which merit is assessed”.  Needless to say, compensations are necessary to meet such a requirment.

Rawls contends justice as fairness is preferred by moral persons at the original position.   He assumes moral persons know what is right (i.e., have a sense of justice) and what constitutes their own good.  As such, moral persons are entitled to equal justice. As Rawls puts it, “those who can give justice are owed justice”.   The original position, on the other hand, wraps everyone with a veil of ignorance. From behind this veil, nobody knows their social status or natural asset.  As a result, they cannot and will not tailor the principles to their own advantage.   Rawls’ moral persons are not altruistic, but mutually disinterested and rational.  This means they (i) strive to maximize their own good, as defined by the rational plan of life, and (ii) are indifferent to the good of others, in both absolute and relative terms.    Rawls’ faith in the better angels of our nature is admirable, but I am not sure our cravings for justice can resist the incessant onslaught of envy, vanity, and self-serving biases.   A society built on justice as fairness may be ideal, even optimal. But will it be stable?  Perhaps that’s what Benjamin Franklin had in mind when he proclaimed, “A republic if YOU CAN KEEP IT!”

Rawls staunchly opposes utilitarianism, the idea that a society is property arranged when its institutions maximize the net balance of welfare.  He believes “each person possesses an inviolability founded on justice that even the welfare of society as a whole cannot override.”   Therefore, justice “denies that the loss of freedom for some is made right by a greater good shared by others.”   These words ring so true as I am, like many of my friends are, trying to understand what the heck is going on in Shanghai.

Mitigating TNC-induced traffic congestion

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.

Blueprint

To the heatedly debated nature vs. nurture question, Plomin’s Blueprint gives an unnuanced answer: it is the nature that makes you who you are.  According to the book, DNA explains half of the differences among us, in both physical and psychological traits.  At first glance, this verdict seems to leave at least the other half to the impact of nurture or the environment.  But here is the catch: the environmental effects are not only strongly correlated with DNA, but also unsystematic and unstable.  In other words, there is very little we can do about them. Your weight, for example, is almost 70% heritable (i.e., 70% of the differences in weight among a population come from genetical differences).   To cite another example that many might dismiss as a reductio ad absurdum, even your likelihood of getting a divorce has a heritability of 40%.

These findings have fascinating implications for society at large, especially parenting and education.  For one thing, those who are obsessed with getting their kids into Ivy League should know schools contribute only 2% to educational achievements.   In other words, excellent students produce excellent schools, not the other way around.  More importantly, parents have much less systematic impact on their children’s outcomes than they are led to believe.   Tiger moms should not expect their kids to be “blobs of clay that can be molded however they wish”.   In fact, kids are not even quite a blank canvas on which you can paint your favorite pictures. They are more like a canvas with a blueprint that your paint brush could either refine or ruin.

The book is an easy and enjoyable read, and the DNA literacy it tries to provide is well delivered and much appreciated.  Yet, I was sometimes taken aback by the tacit fatalism in the book. and wondered how it might undermine our commitment to good parenting.  I am also deeply troubled by the prospect of using genomes as a scientific fortune teller, to label and classify human beings at birth.

Nevertheless, the book does convince me that we are all fundamentally shaped by our DNA, more so than any other factors.  To me, this means life is like a constrained optimization problem for which we may choose the objectives but not the constraints.  That is, your free will can still decide where you land, so long as the target is within the feasible set.

Planning EV charging infrastructure

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.

Pricing carpool rides

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.

Intellectuals and Society

Professor Sowell’s contempt for “intellectuals” is remarkable.  In his telling, intellectuals create and promote ideas that often harm society gravely; they pretend to master subjects on which they have no more expertise than a layman;  they advocate radical societal  changes to whose disastrous consequences they are neither accountable nor susceptible;  they demand society treat their lofty visions “as axioms to be followed, not as hypothesis to be tested”; they are self-righteous narcissists whose primary preoccupation is to gain and maintain moral hegemony over the mass.  In a nutshell, intellectuals are the “enemy of the people”, to quote Mr. Trump. Or in the words of the Dear Leader from another time, they are the filthy ninth (臭老九) who deserve to be condemned to the lowest rung of society and be continually reeducated by proletariat.

While Sowell’s sweeping denunciation apparently applies to all intellectuals, you need not to read between the lines to understand his real target is left-leaning liberals.  Conservative intellectuals—the likes of Friedman and Hayek—are the good ones.  To borrow a cliché from the gun advocates, only the good guys with ideas can stop the bad guys with ideas.

To be sure, Sowell’s harsh critiques of liberals contain more than a grain of truth. However, as a lifetime intellectual himself, his completely lopsided approach is still puzzling, and sometimes feels personal.   Shockingly, Sowell cannot even bring himself to praise liberals’ support for Civil Rights Act, which prohibits discrimination against his fellow African Americans.  “Even a stopped clock is right twice a day” is how he shrugs off the only good thing he has to say about liberals in the book.

Are autonomous vehicles better off without signals?

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.

Social Limits on Growth

Fred Hirsch was no big-time economist.  His brief academic career was cut short by ALS, the same disease that killed Tony Judt. Yet, his Social Limits on Growth is a masterpiece, probably not a book you could read for fun lying on the coach, but definitely worth the time and effort.

According to Hirsch, capitalism is doomed to trap everyone in counterproductive competition for positional goods such as Ivy League education and elite jobs.  This phenomenon may be best described as “involution” (内卷), to borrow a popular Chinese Internet Meme.   Economic growth cannot solve the involution trap. On the contrary, growth is bound to fortify it, by fulfilling the ever-increasing demand for material goods. Nor could redistribution overcome the scarcity of position goods. As Hirsch noted, “there is no such thing as leveling up” when reward is set by the position on the slope, because “the slope itself prevents a leveling”.    Therefore, the image of “a rising-tide-lifts-all-boats” is an illusion because the tide cannot keep rising and not all boats could stay above the water at the same time.

Hirsch seems rather pessimistic about finding any operational solution to the social limits on growth. In the end, he wonders whether the belief in incremental progress itself is but a pipe-dream, “a nonfiction version of the happy-ending”, or “a faith that is as utopian as the Utopianism it seeks to replace”.