{"id":148,"date":"2015-09-12T00:00:09","date_gmt":"2015-09-12T00:00:09","guid":{"rendered":"http:\/\/ajhassoc.com\/?p=148"},"modified":"2017-05-17T01:45:11","modified_gmt":"2017-05-17T01:45:11","slug":"my-life-with-msa","status":"publish","type":"post","link":"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/","title":{"rendered":"My Life with MSA*"},"content":{"rendered":"
\n

QRS II had always had a form of feedback to trip distribution (more correctly to trip generation, although the trip generation step was insensitive to network travel times).<\/p>\n

In 1988 or so when I was testing a new installation of a \u201cmodified\u201d Evans\u2019 algorithm I had put into QRS II, which was quite similar to Franke-Wolfe decomposition, I noticed a peculiar pattern of averaging weights. The first weight always seemed to be close to 0.5, the second weight always seemed to be close to 0.33, etc. This same pattern emerged no matter which network I tested. The modified Evans\u2019 algorithm wanted a 1\/k sequence or something not so different.<\/p>\n

Conjecture #1. Evans\u2019 algorithm doesn\u2019t really need the demand term in the line-search step.<\/p>\n

The modified Evans\u2019 algorithm worked, sort of. (I published a short research note on it, \u201dTests of an Ad Hoc Algorithm of Elastic- Demand Equilibrium Traffic Assignment\u201d, in an attempt to get someone to tell me whether I was onto something important.) The modified Evans\u2019 algorithm found exactly the same answer as the unmodified Evans algorithm, if it found any answer at all. However, in rare occasions it locked up and failed to give any results. There was a very nice follow-up paper by Haung and Lam proving that the algorithm was fantastic when it was working, but failed dramatically when it wasn\u2019t working. We were close to a solution to the feedback problem, but not yet close enough.<\/p>\n

So not so long afterward I am having a phone conversation with Roger Tobin about traffic assignment and he said \u201cPatrice thinks that one over kay might solve the elastic demand assignment problem\u201d. Of course, Roger was referring to Patrice Marcotte, the brilliant network theorist who had quite an influence on my thinking. OK, 1\/k was being generally discussed, but were there any papers about it in the published literature? I found some mention in the literature about how 1\/k assignment was similar to incremental traffic assignment, but nothing about feedback. Eventually, by flipping through old, dusty journals, I stumbled across an article by Powell and Sheffi proving that MSA (method of successive averages, a generalization of the 1\/k concept) gave correct equilibrium solutions for the static, inelastic demand problem.<\/p>\n

Powell and Sheffi\u2019s article was minimally cited at the time, probably because of a mind-bogglingly incorrect conclusion. After a really great paper, otherwise, those guys concluded that MSA was at best a poor substitute for Frank-Wolfe decomposition, since it was always slower computationally.<\/p>\n

The modified Evans\u2019 algorithm was locking up because the line-search failed (rarely, but enough to be of concern). What if we eliminated the line-search altogether?<\/p>\n

Conjecture #2. Evans\u2019 algorithm\u2019s line-search step can be replaced entirely by a 1\/k weighting scheme.<\/p>\n

This was going to be difficult to prove, and I am not nearly the network theorist of Tobin, Marcotte, Lam, et. al, so I decided to demonstrate the truth of the 1\/k idea by much testing on toy and real-world networks. These first tests were summarized in the article “Convergence Properties of Some Iterative Traffic Assignment Algorithms”. In brief, the MSA modification of Evans\u2019 worked perfectly.<\/p>\n

\u201cYou might ask, \u201cWhat\u2019s the problem with Evans\u2019 line search?\u201d First, the demand term adds a lot of computation. Second, the line search would not be easily extensible to newer demand models that were brewing. There is yet another looming reason that I didn\u2019t know about at the time.<\/p>\n

Here is the whole algorithm in a nutshell.<\/p>\n

Step 1: Compute OD table; AON assignment; compute new travel times.<\/p>\n

Step 2. Compute OD table with new travel times; AON assignment; take average of all AON assignments; compute new travel times.<\/p>\n

Step 3. Check for convergence; if good, stop; if not good, do Step 2 again.<\/p>\n

As an accounting task, it is necessary to average all the OD tables, but the average table does not ever get assigned to the network. We need the average table later so it agrees with the averaged volumes, since we never run the algorithm close enough to complete convergence.<\/p>\n

Even though MSA with feedback has been part of QRS II for more than 2 decades, there was no rush by other software vendors or MPOs to put it in their models. First, the necessity still needed to be demonstrated. And second, it was very difficult to get modular software packages to do it correctly. That is still the case. Eventually, the double-loop feedback scheme was hatched.<\/p>\n

The double-loop feedback scheme overcomes the issue of modularity at the cost of a lot of computation. The double-loop feedback scheme is sometimes referred to as MSA, but it is not MSA. It will do the same thing for limited networks, if you are patient enough. The outer loop deals with demand and the inner loop deals with assignment. So let\u2019s say you need 10 iterations to get demand to settle down and you need 20 iterations to get good convergence for your Frank-Wolfe decomposition. This means you will need upwards of 200 AON assignments.\u00a0 However, MSA solves the exact same problem in maybe 25 AON assignments, allowing 5 more iterations to account for the slowness of MSA relative to Frank-Wolfe decomposition. MSA beats the double loop by a factor of 8.<\/p>\n

Sometime in 1990 Dane Ismart, then of FHWA, asked me to look into how the 1985 Highway Capacity Manual should affect the BPR curve. I could get the BPR curve to fit freeways and multilane arterials, but I had no success getting the BPR curve or, indeed any other VDF, to fit stop signs or signals. While working on this project I programmed into QRS II the HCM\u2019s operational analysis procedures for signals and two-way stops. Frank-Wolfe decomposition simply would not converge with signals and stop signs. However, switching to MSA gave me convergence. Thus\u2026<\/p>\n

Conjecture #3. MSA solves the traffic assignment problem with signals and signs.<\/p>\n

I knew from Marcotte, Nagurney and others that I was venturing into the realm of variational inequalities, which took us far away from familiar optimization theory, but nobody had yet taken on anything as complex as what was found in the HCM. So without much help available from theorists, I again turned to repeated testing of toy and real networks. The results of these tests were published in three papers, the first of which appeared in the Transportation Research Record as “Implementing Travel Forecasting with Traffic Operational Strategies”.<\/p>\n

You may have noticed that many of my papers were published in the Transportation Research Record rather than in some of the more academic journals known for their network theory. I was deliberately avoiding network theorists as referees, who I felt would not be receptive to such radical concepts without a lot of math to back them up.<\/p>\n

So MSA is a remarkably strong and resilient algorithm. It is grounded in the theory of numerical analysis rather than in the highly restrictive optimization theory of Beckmann. Where MSA has the most trouble is with the issue of multiple equilibrium solutions; however, the real world has multiple equilibrium solutions, so this is not an issue with MSA itself but an issue of the way we have collectively formulated the urban traffic assignment problem.<\/p>\n

Subsequent years and many tests have shown that MSA can handle dynamic traffic assignments and multiclass traffic assignments \u2026 and rather surprisingly, everything all at once.<\/p>\n

Alan Horowitz, Whitefish Bay WI, September 12, 2015<\/em><\/p>\n

*\u201cMy Life with Marilyn\u201d is more interesting. I recommend it.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

QRS II had always had a form of feedback to trip distribution (more correctly to trip generation, although the trip generation step was insensitive to network travel times). In 1988 or so when I was testing a new installation of a \u201cmodified\u201d Evans\u2019 algorithm I had put into QRS II, which was quite similar to …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"enabled":false},"version":2}},"categories":[10],"tags":[],"class_list":["post-148","post","type-post","status-publish","format-standard","category-travel-modeling","anons"],"yoast_head":"\nMy Life with MSA* - QRS II Page<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"My Life with MSA* - QRS II Page\" \/>\n<meta property=\"og:description\" content=\"QRS II had always had a form of feedback to trip distribution (more correctly to trip generation, although the trip generation step was insensitive to network travel times). In 1988 or so when I was testing a new installation of a \u201cmodified\u201d Evans\u2019 algorithm I had put into QRS II, which was quite similar to ...\" \/>\n<meta property=\"og:url\" content=\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/\" \/>\n<meta property=\"og:site_name\" content=\"QRS II Page\" \/>\n<meta property=\"article:published_time\" content=\"2015-09-12T00:00:09+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2017-05-17T01:45:11+00:00\" \/>\n<meta name=\"author\" content=\"horowitz\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"horowitz\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"6 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/\"},\"author\":{\"name\":\"horowitz\",\"@id\":\"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070\"},\"headline\":\"My Life with MSA*\",\"datePublished\":\"2015-09-12T00:00:09+00:00\",\"dateModified\":\"2017-05-17T01:45:11+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/\"},\"wordCount\":1234,\"commentCount\":0,\"articleSection\":[\"Travel Modeling\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/\",\"url\":\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/\",\"name\":\"My Life with MSA* - QRS II Page\",\"isPartOf\":{\"@id\":\"https:\/\/ajhassoc.com\/#website\"},\"datePublished\":\"2015-09-12T00:00:09+00:00\",\"dateModified\":\"2017-05-17T01:45:11+00:00\",\"author\":{\"@id\":\"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070\"},\"breadcrumb\":{\"@id\":\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/ajhassoc.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"My Life with MSA*\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/ajhassoc.com\/#website\",\"url\":\"https:\/\/ajhassoc.com\/\",\"name\":\"QRS II Page\",\"description\":\"Information about the travel forecasting package, Quick Response System II\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/ajhassoc.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070\",\"name\":\"horowitz\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g\",\"caption\":\"horowitz\"},\"url\":\"https:\/\/ajhassoc.com\/index.php\/author\/horowitz\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"My Life with MSA* - QRS II Page","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/","og_locale":"en_US","og_type":"article","og_title":"My Life with MSA* - QRS II Page","og_description":"QRS II had always had a form of feedback to trip distribution (more correctly to trip generation, although the trip generation step was insensitive to network travel times). In 1988 or so when I was testing a new installation of a \u201cmodified\u201d Evans\u2019 algorithm I had put into QRS II, which was quite similar to ...","og_url":"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/","og_site_name":"QRS II Page","article_published_time":"2015-09-12T00:00:09+00:00","article_modified_time":"2017-05-17T01:45:11+00:00","author":"horowitz","twitter_card":"summary_large_image","twitter_misc":{"Written by":"horowitz","Est. reading time":"6 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/#article","isPartOf":{"@id":"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/"},"author":{"name":"horowitz","@id":"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070"},"headline":"My Life with MSA*","datePublished":"2015-09-12T00:00:09+00:00","dateModified":"2017-05-17T01:45:11+00:00","mainEntityOfPage":{"@id":"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/"},"wordCount":1234,"commentCount":0,"articleSection":["Travel Modeling"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/","url":"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/","name":"My Life with MSA* - QRS II Page","isPartOf":{"@id":"https:\/\/ajhassoc.com\/#website"},"datePublished":"2015-09-12T00:00:09+00:00","dateModified":"2017-05-17T01:45:11+00:00","author":{"@id":"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070"},"breadcrumb":{"@id":"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/ajhassoc.com\/index.php\/2015\/09\/12\/my-life-with-msa\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/ajhassoc.com\/"},{"@type":"ListItem","position":2,"name":"My Life with MSA*"}]},{"@type":"WebSite","@id":"https:\/\/ajhassoc.com\/#website","url":"https:\/\/ajhassoc.com\/","name":"QRS II Page","description":"Information about the travel forecasting package, Quick Response System II","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/ajhassoc.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/ajhassoc.com\/#\/schema\/person\/b982087d07e1397f2767543367fb6070","name":"horowitz","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/ef1125ea06cd56c8e360e1ff9c4eaf53600e7d1a0b3cc8dfa44a8bf78396e898?s=96&d=mm&r=g","caption":"horowitz"},"url":"https:\/\/ajhassoc.com\/index.php\/author\/horowitz\/"}]}},"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8zKPW-2o","_links":{"self":[{"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/posts\/148","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/comments?post=148"}],"version-history":[{"count":3,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/posts\/148\/revisions"}],"predecessor-version":[{"id":175,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/posts\/148\/revisions\/175"}],"wp:attachment":[{"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/media?parent=148"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/categories?post=148"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ajhassoc.com\/index.php\/wp-json\/wp\/v2\/tags?post=148"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}