You are currently browsing articles tagged con­ges­tion.

Braess’ para­dox is a counter-intu­it­ive res­ult in trans­port­a­tion sci­ence, which in essence states that if you add addi­tion­al capa­city to a net­work, over­all net­work per­form­ance may in fact decrease, if agents are free to (greed­ily) choose a path that min­im­ises their own latency. In this post, I’ll explain Braess’ para­dox, and provide a new example that uses only non-increas­ing cost func­tions.

Let’s con­sider the fol­low­ing net­work setup:

Braess’ paradox - initial setup

We have four towns, s, v, w and t, and one unit of traffic that needs to get from s to t using this net­work. The cost func­tions c(x) on the links indic­ate how long it takes to use that route as a func­tion of the frac­tion of the traffic that will take that link (in some unit of time, say hours). For example, if the link’s cost func­tion is c(x) = x and half the traffic goes along that link, then it will take every­one half an hour to tra­verse that link. You can think of these roads as nar­row roads that are rather sus­cept­ible to con­ges­tion. The links with cost func­tions c(x) = 1 are not affected by the traffic flow at all; these are ana­log­ous to long, but very wide, high­ways.

In the above case, because the top route (s-v-t) is identic­al to the bot­tom route (s-w-t), traffic will spread itself out between the two routes: half will go up the top and the oth­er half will go down the bot­tom. The aver­age time taken is 1.5 hours. But what if the loc­al gov­ern­ment decided to improve the net­work by adding a new super-fast high­way from v to w that takes abso­lutely no time to tra­verse?

Braess’ paradox - augmented network

The people tak­ing the s-w link will think, “Hey, going via s-v-w is no worse than tak­ing s-w, and it can actu­ally be quick­er. I’ll take that instead!” The same logic goes for why every­one will end up tak­ing v-w-t instead of v-t, because v-w-t can­not be worse, but it can actu­ally be faster, if a small frac­tion of people don’t take it (note the cost func­tion on w-t). So every­one ends up on s-v-w-t, which means an aver­age time of 2 hours. Oops.

If you think back to the real world, that’s why build­ing a new high­way doesn’t solve all our traffic night­mares, and can, in some cases, make the prob­lem worse. People using sides roads or tak­ing the train to work con­verge on the new high­way, and you’re back to square one.

Braess’ para­dox doesn’t just occur for net­works where the cost of a link goes up as the num­ber of people use it. For net­works with non-increas­ing cost func­tions (e.g. the cost of a link goes down as the num­ber of people use it goes up), where con­ges­tion is a good thing, we can find an ana­log­ous situ­ation. Con­sider the fol­low­ing net­work, where 1 unit of traffic needs to be routed from s1 to t1, and anoth­er unit from s2 to t2:

Decreasing case - initial setup

You’ll find that the total cost is 6 (3 each for the s1-t1 and s2-t2 guys). Now, someone with deep pock­ets builds a new link to shave a little off the s1-t1 route:

Decreasing case - augmented network

The dir­ect s1-t1 route is more attract­ive than the 3 hour hike via u and v, so every­one who wants to go from s1 to t1 takes that route instead. Because the u-v link isn’t shared any­more, its cost goes up quite a bit, and the total cost now becomes 6.5. Shar­ing is caring.

Tags: , , , ,

Grace men­tioned this quite a while ago, but her par­ents’ shop at Suth­er­land sta­tion will be for­cibly taken away by Rail­Corp, which wishes to widen the con­course at the sta­tion to, appar­ently, ease con­ges­tion. Des­pite their invest­ment in the busi­ness, from what I under­stand, the prob­lem lies in the fact that their con­tract does not provide for recom­pense in the event that Rail­Corp needs to do some­thing with it.

I’d say that most people would be sup­port­ive of rail­way infra­struc­ture devel­op­ment — who doesn’t want bet­ter sta­tions, and bet­ter trains, and bet­ter ser­vices. The prob­lem here is the way in which this devel­op­ment has been ear­marked to pro­ceed — to the det­ri­ment of one fam­ily, and with dubi­ous bene­fits to rail­way com­muters as a whole. RailCorp’s alleged atti­tude (i.e. silence) doesn’t instill con­fid­ence in the abil­ity of this case to res­ult in an equit­able solu­tion. As I com­men­ted (on the news­pa­per art­icle), just because it’s leg­al doesn’t mean you should do it. If the redevel­op­ment of the sta­tion must go ahead, oth­er solu­tions, such as buy­ing out the busi­ness, or offer­ing to relo­cate the busi­ness to anoth­er part of the sta­tion, are both reas­on­able altern­at­ives that Rail­Corp should con­sider. Rail­Corp is a cor­por­at­ised busi­ness, but at the same time, as a busi­ness owned by the people of New South Wales, a more caring atti­tude would not go amiss, and should be man­dated in the organisation’s prac­tices.

Some­how, I get the impres­sion that push­ing Rail­Corp but­tons won’t work in this case. The Ngs will have to search for oth­er, big­ger but­tons to push. Let’s all rally behind them in their moment of need.

Tags: , , , , , ,