Academic literature on the topic 'Time-Dependent Label-Constrained Shortest Path Pro'

We consider the shortest path problem with resource constraints arising as a subproblem in state-of-the-art branch-cut-and-price algorithms for vehicle routing problems. We propose a variant of the bidirectional label-correcting algorithm in which the labels are stored and extended according to the so-called bucket graph. This organization of labels helps to significantly decrease the number of dominance checks and the running time of the algorithm. We also show how the forward/backward route symmetry can be exploited and how to eliminate arcs from the bucket graph using reduced costs. The proposed algorithm can be especially beneficial for vehicle routing instances with large vehicle capacity and/or with time window constraints. Computational experiments were performed on instances from the distance-constrained vehicle routing problem, including multidepot and site-dependent variants, on the vehicle routing problem with time windows, and on the “nightmare” instances of the heterogeneous fleet vehicle routing problem. Significant improvements over the best algorithms in the literature were achieved, and many instances could be solved for the first time.

IntroductionThe death of Chris Cornell in the spring of 2017 shook me. As the lead singer of Soundgarden and a pioneer of early 1990s grunge music, his voice revealed an unbridled pain and joy backed up by the raw, guitar-driven rock emanating from the Seattle, Washington music scene. I remember thinking, there’s only one left, referring to Eddie Vedder, lead singer for Pearl Jam, and lone survivor of the four seminal grunge bands that rose to fame in the early 1990s whose lead singers passed away much too soon. Alice in Chains singer Layne Staley died in 2002 at the age of 35, and Nirvana front man Kurt Cobain’s death in 1994 had resonated around the globe. I thought about when Cornell and Staley said goodbye to their friend Andy Wood, lead singer of Mother Love Bone, after he overdosed on heroine in 1990. Wood’s untimely death at the age of 24, only days before his band’s debut album release, shook the close-knit Seattle music scene and remained a source of angst and inspiration for a genre of music that shaped youth culture of the 1990s.When grunge first exploded on the pop culture scene, I was a college student flailing around in pursuit of an English degree I had less passion for than I did for music. I grew up listening to The Beatles and Prince; Led Zeppelin and Miles Davis; David Bowie and Willie Nelson, along with a litany of other artists and musicians crafting the kind of meaningful music I responded to. I didn’t just listen to music, I devoured stories about the musicians, their often hedonistic lifestyles; their processes and epiphanies. The music spoke to my being in the world more than the promise of any college degree. I ran with friends who shared this love of music, often turning me on to new bands or suggesting some obscure song from the past to track down. I picked up my first guitar when John Lennon died on the eve of my eleventh birthday and have played for the past 37 years. I rely on music to relocate my sense of self. Rhythm and melody play out like characters in my life, colluding to make me feel something apart from the mundane, moving me from within. So, when I took notice of grunge music in the fall of 1991, it was love at first listen. As a pop cultural phenomenon, grunge ruptured the music and fashion industries caught off guard by its sudden commercial appeal while the media struggled to galvanize its relevance. As a subculture, grunge rallied around a set of attitudes and values that set the movement apart from mainstream (Latysheva). The grunge sound drew from the nihilism of punk and the head banging gospel of heavy metal, tinged with the swagger of 1970s FM rock running counter to the sleek production of pop radio and hair metal bands. Grunge artists wrote emotionally-laden songs that spoke to a particular generation of youth who identified with lyrics about isolation, anger, and death. Grunge set off new fashion trends in favor of dressing down and sporting the latest in second-hand, thrift store apparel, ripping away the Reagan-era starched white-collared working-class aesthetic of the 1980’s corporate culture. Like their punk forbearers who railed against the status quo and the trappings of success incurred through the mass appeal of their art, Kurt Cobain, Eddie Vedder, and the rest of the grunge cohort often wrestled with the momentum of their success. Fortunes rained down and the media ordained them rock stars.This auto-ethnography revisits some of the cultural impacts of grunge during its rise to cultural relevance and includes my own reflexive interpretation positioned as a fan of grunge music. I use a particular auto-ethnographic orientation called “interpretive-humanistic autoethnography” (Manning and Adams 192) where, along with archival research (i.e. media articles and journal articles), I will use my own reflexive voice to interpret and describe my personal experiences as a fan of grunge music during its peak of popularity from 1991 up to the death of Cobain in 1994. It is a methodology that works to bridge the personal and popular where “the individual story leaves traces of at least one path through a shifting, transforming, and disappearing cultural landscape” (Neumann 183). Grunge RootsThere are many conflicting stories as to when the word “grunge” was first used to describe the sound of a particular style of alternative music seeping from the dank basements and shoddy rehearsal spaces in towns like Olympia, Aberdeen, and Seattle. Lester Bangs, the preeminent cultural writer and critic of all things punk, pop, and rock in the 1970s was said to have used the word at one time (Yarm), and several musicians lay claim to their use of the word in the 1980s. But it was a small Seattle record label founded in 1988 called Sub Pop Records that first included grunge in their marketing materials to describe “the grittiness of the music and the energy” (Yarm 195).This particular sound grew out of the Pacific Northwest blue-collar environment of logging towns, coastal fisheries, and airplane manufacturing. Seattle’s alternative music scene unfolded as a community of musicians responding to the tucked away isolation of their musty surroundings, apart from the outside world, free to submerge themselves in their own cultural milieu of rock music, rain, and youthful rebellion.Where Seattle stood as a major metropolitan city soaked in rainclouds for much of the year, I was soaking up the desert sun in a rural college town when grunge first leapt into the mainstream. Cattle ranches and cotton fields spread across the open plains of West Texas, painted with pickup trucks, starched Wrangler Jeans, and cowboy hats. This was not my world. I’d arrived the year prior from Houston, Texas, an urban sprawl of four million people, but I found the wide-open landscape a welcome change from the concrete jungle of the big city. Along with cowboy boots and western shirts came country music, and lots of it. Garth Brooks, Reba McEntire, George Straight; some of the voices that captured the lifestyle of my small rural town, twangy guitars and fiddles blaring on local radio. While popular country artists recorded for behemoth record labels like Warner Brothers and Sony, the tiny Sub Pop Records championed the grunge sound coming out of the Seattle music scene. Sub Pop became a playground for those who cared about their music and little else. The label cultivated an early following through their Sub Pop Singles Club, mailing seven-inch records to subscribers on a monthly basis promoting new releases from up-and-coming bands. Sub Pop’s stark, black and white logo showed up on records sleeves, posters, and t-shirts, reflecting a no-nonsense DIY-attitude rooted in in the production of loud guitars and heavy drums.Like the bands it represented, Sub Pop did not take itself too seriously when one of their best-selling t-shirts simply read “Loser” embracing the slacker mood of newly minted Generation X’ers born between 1961 and 1981. A July 1990 Time Magazine article described this twenty-something demographic as having “few heroes, no anthems, no style to call their own” suggesting they “possess only a hazy sense of their own identity” (Gross & Scott). As a member of this generation, I purchased and wore my “Loser” t-shirt with pride, especially in ironic response to the local cowboy way of life. I didn’t hold anything personal against the Wrangler wearing Garth Brooks fan but as a twenty-one-year-old reluctant college student, I wanted to rage with contempt for the status quo of my environment with an ambivalent snarl.Grunge in the MainstreamIn 1991, the Seattle sound exploded onto the international music scene with the release of four seminal grunge-era albums over a six-month period. The first arrived in April, Temple of the Dog, a tribute album of sorts to the late Andy Wood, led by his close friend, Soundgarden singer/songwriter, Chris Cornell. In August, Pearl Jam released their debut album, Ten, with its “surprising and refreshing, melodic restraint” (Fricke). The following month, Nirvana’s Nevermind landed in stores. Now on a major record label, DGC Records, the band had arrived “at the crossroads—scrappy garageland warriors setting their sights on a land of giants” (Robbins). October saw the release of Soundgarden’s Badmotorfinger as “a runaway train ride of stammering guitar and psycho-jungle telegraph rhythms” (Fricke). These four albums sent grunge culture into the ether with a wall of sound that would upend the music charts and galvanize a depressed concert ticket market.In fall of 1991, grunge landed like a hammer when I witnessed Nirvana’s video for “Smells Like Teen Spirit” on MTV for the first time. Sonically, the song rang like an anthem for the Gen Xers with its jangly four-chord opening guitar riff signaling the arrival of a youth-oriented call to arms, “here we are now, entertain us” (Nirvana). It was the visual power of seeing a skinny white kid with stringy hair wearing baggy jeans, a striped T-shirt and tennis shoes belting out choruses with a ferociousness typically reserved for black-clad heavy metal headbangers. Cobain’s sound and look didn’t match up. I felt discombobulated, turned sideways, as if vertigo had taken hold and I couldn’t right myself. Stopped in the middle of my tracks on that day, frozen in front of the TV, the subculture of grunge music slammed into my world while I was on my way to the fridge.Suddenly, grunge was everywhere, As Soundgarden, Nirvana, and Pearl Jam albums and performances infiltrated radio, television, and concert halls, there was no shortage of media coverage. From 1992 through 1994, grunge bands were mentioned or featured on the cover of Rolling Stone 33 times (Hillburn). That same year, The New York Times ran the article “Grunge: A Success Story” featuring a short history of the Seattle sound, along with a “lexicon of grunge speak” (Marin), a joke perpetrated by a former 25-year-old Sub Pop employee, Megan Jasper, who never imagined her list of made-up vocabulary given to a New York Times reporter would grace the front page of the style section (Yarm). In their rush to keep up with pervasiveness of grunge culture, even The New York Times fell prey to Gen Xer’s comical cynicism.The circle of friends I ran with were split down the middle between Nirvana and Pearl Jam, a preference for one over the other, as the two bands and their respective front men garnered much of the media attention. Nirvana seemed to appeal to people’s sense of authenticity, perhaps more relatable in their aloofness to mainstream popularity, backed up with Cobain’s simple-yet-brilliant song arrangements and revealing lyrics. Lawrence Grossberg suggests that music fans recognise the difference between authentic and homogenised rock, interpreting and aligning these differences with rock and roll’s association with “resistance, refusal, alienation, marginality, and so on” (62). I tended to gravitate toward Nirvana’s sound, mostly for technical reasons. Nevermind sparkled with aggressive guitar tones while capturing the power and fragility of Cobain’s voice. For many critics, the brilliance of Pearl Jam’s first album suffered from too much echo and reverb muddling the overall production value, but twenty years later they would remix and re-release Ten, correcting these production issues.Grunge FashionAs the music carved out a huge section of the charts, the grunge look was appropriated on fashion runways. When Cobain appeared on MTV wearing a ragged olive green cardigan he’d created a style simply by rummaging through his closet. Vedder and Cornell sported army boots, cargo shorts, and flannel shirts, suitable attire for the overcast climate of the Pacific Northwest, but their everyday garb turned into a fashion trend for Gen Xers that was then milked by designers. In 1992, the editor of Details magazine, James Truman, called grunge “un fashion” (Marin) as stepping out in second-hand clothes ran “counter to the shellacked, flashy aesthetic of 1980s” (Nnadi) for those who preferred “the waif-like look of put-on poverty” (Brady). But it was MTV’s relentless airing of Nirvana, Pearl Jam, and Soundgarden videos that sent Gen Xers flocking to malls and thrift-stores in search grunge-like apparel. I purchased a pair of giant, heavyweight Red Wing boots that looked like small cars on my feet, making it difficult to walk, but at least I was prepared for any terrain in all types of weather. The flannel came next; I still wear flannos. Despite its association with dark, murky musical themes, grunge kept me warm and dry.Much of grunge’s appeal to the masses was that it was not gender-specific; men and women dressed to appear unimpressed, sharing a taste for shapeless garments and muted colors without reference to stereotypical masculine or feminine styles. Cobain “allowed his own sexuality to be called into question by often wearing dresses and/or makeup on stage, in film clips, and on photo shoots, and wrote explicitly feminist songs, such as ‘Sappy’ or ‘Been a Son’” (Strong 403). I remember watching Pearl Jam’s 1992 performance on MTV Unplugged, seeing Eddie Vedder scrawl the words “Pro Choice” in black marker on his arm in support of women’s rights while his lyrics in songs like “Daughter”, “Better Man”, and “Why Go” reflected an equitable, humanistic if somewhat tragic perspective. Females and males moshed alongside one another, sharing the same spaces while experiencing and voicing their own response to grunge’s aggressive sound. Unlike the hypersexualised hair-metal bands of the 1980s whose aesthetic motifs often portrayed women as conquests or as powerless décor, the message of grunge rock avoided gender exploitation. As the ‘90s unfolded, underground feminist punk bands of the riot grrrl movement like Bikini Kill, L7, and Babes in Toyland expressed female empowerment with raging vocals and buzz-saw guitars that paved the way for Hole, Sleater-Kinney and other successful female-fronted grunge-era bands. The Decline of GrungeIn 1994, Kurt Cobain appeared on the cover of Newsweek magazine in memoriam after committing suicide in the greenhouse of his Seattle home. Mass media quickly spread the news of his passing internationally. Two days after his death, 7,000 fans gathered at Seattle Center to listen to a taped recording of Courtney Love, Cobain’s wife, a rock star in her own right, reading the suicide note he left behind.A few days after Cobain’s suicide, I found myself rolling down the highway with a carload of friends, one of my favorite Nirvana tunes, “Come As You Are” fighting through static. I fiddled with the radio to clear up the signal. The conversation turned to Cobain as we cobbled together the details of his death. I remember the chatter quieting down, Cobain’s voice fading as we gazed out the window at the empty terrain passing. In that reflective moment, I felt like I had experienced an intense, emotional relationship that came to an abrupt end. This “illusion of intimacy” (Horton and Wohl 217) between myself and Cobain elevated the loss I felt with his passing even though I had no intimate, personal ties to him. I counted this person as a friend (Giles 284) because I so closely identified with his words and music. I could not help but feel sad, even angry that he’d decided to end his life.Fueled by depression and a heroin addiction, Cobain’s death signaled an end to grunge’s collective appeal while shining a spotlight on one of the more dangerous aspects of its ethos. A 1992 Rolling Stone article mentioned that several of Seattle’s now-famous international musicians used heroin and “The feeling around town is, the drug is a disaster waiting to happen” (Azzerad). In 2002, eight years to the day of Cobain’s death, Layne Staley, lead singer of Alice In Chains, another seminal grunge outfit, was found dead of a suspected heroin overdose (Wiederhorn). When Cornell took his own life in 2017 after a long battle with depression, The Washington Post said, “The story of grunge is also one of death” (Andrews). The article included a Tweet from a grieving fan that read “The voices I grew up with: Andy Wood, Layne Staley, Chris Cornell, Kurt Cobain…only Eddie Vedder is left. Let that sink in” (@ThatEricAlper).ConclusionThe grunge movement of the early 1990s emerged out of musical friendships content to be on their own, on the outside, reflecting a sense of isolation and alienation in the music they made. As Cornell said, “We’ve always been fairly reclusive and damaged” (Foege). I felt much the same way in those days, sequestered in the desert, planting my grunge flag in the middle of country music territory, doing what I could to resist the status quo. Cobain, Cornell, Staley, and Vedder wrote about their own anxieties in a way that felt intimate and relatable, forging a bond with their fan base. Christopher Perricone suggests, “the relationship of an artist and audience is a collaborative one, a love relationship in the sense, a friendship” (200). In this way, grunge would become a shared memory among friends who rode the wave of this cultural phenomenon all the way through to its tragic consequences. But the music has survived. Along with my flannel shirts and Red Wing boots.References@ThatEricAlper (Eric Alper). “The voices I grew up with: Andy Wood, Layne Staley, Chris Cornell, Kurt Cobain…only Eddie Vedder is left. Let that sink in.” Twitter, 18 May 2017, 02:41. 15 Sep. 2018 <https://twitter.com/ThatEricAlper/status/865140400704675840?ref_src>.Andrews, Travis M. “After Chris Cornell’s Death: ‘Only Eddie Vedder Is Left. Let That Sink In.’” The Washington Post, 19 May 2017. 29 Aug. 2018 <https://www.washingtonpost.com/newsmorning-mix/wp/2017/05/19/after-chris-cornells-death-only-eddie-vedder-is-left-let-that-sink-in>.Azzerad, Michael. “Grunge City: The Seattle Scene.” Rolling Stone, 16 Apr. 1992. 20 Aug. 2018 <https://www.rollingstone.com/music/music-news/grunge-city-the-seattle-scene-250071/>.Brady, Diane. “Kids, Clothes and Conformity: Teens Fashion and Their Back-to-School Looks.” Maclean’s, 6 Sep. 1993. Brodeur, Nicole. “Chris Cornell: Soundgarden’s Dark Knight of the Grunge-Music Scene.” Seattle Times, 18 May 2017. 20 Aug. 2018 <https://www.seattletimes.com/entertainment/music/chris-cornell-soundgardens-dark-knight-of-the-grunge-music-scene/>.Ellis, Carolyn, and Arthur P. Bochner. “Autoethnography, Personal Narrative, Reflexivity: Researcher as Subject.” Handbook of Qualitative Research. 2nd ed. Eds. Norman Denzin and Yvonna Lincoln. Thousand Oaks, CA: Sage, 2000. 733-768.Foege, Alec. “Chris Cornell: The Rolling Stone Interview.” Rolling Stone, 28 Dec. 1994. 12 Sep. 2018 <https://www.rollingstone.com/music/music-features/chris-cornell-the-rolling-stone-interview-79108/>.Fricke, David. “Ten.” Rolling Stone, 12 Dec. 1991. 18 Sep. 2018 <https://www.rollingstone.com/music/music-album-reviews/ten-251421/>.Giles, David. “Parasocial Interactions: A Review of the Literature and a Model for Future Research.” Media Psychology 4 (2002): 279-305.Giles, Jeff. “The Poet of Alientation.” Newsweek, 17 Apr. 1994, 4 Sep. 2018 <https://www.newsweek.com/poet-alienation-187124>.Gross, D.M., and S. Scott. Proceding with Caution. Time, 16 July 1990. 3 Sep. 2018 <http://content.time.com/time/magazine/article/0,9171,155010,00.html>.Grossberg, Lawrence. “Is There a Fan in the House? The Affective Sensibility of Fandom. The Adoring Audience” Fan Culture and Popular Media. Ed. Lisa A. Lewis. New York, NY: Routledge, 1992. 50-65.Hillburn, Robert. “The Rise and Fall of Grunge.” Los Angeles Times, 21 May 1998. 20 Aug. 2018 <http://articles.latimes.com/1998/may/31/entertainment/ca-54992>.Horton, Donald, and R. Richard Wohl. “Mass Communication and Para-Social Interactions: Observations on Intimacy at a Distance.” Psychiatry: Interpersonal and Biological Process 19 (1956): 215-229.Latysheva, T.V. “The Essential Nature and Types of the Youth Subculture Phenomenon.” Russian Education and Society 53 (2011): 73–88.Manning, Jimmie, and Tony Adams. “Popular Culture Studies and Autoethnography: An Essay on Method.” The Popular Culture Studies Journal 3.1-2 (2015): 187-222.Marin, Rick. “Grunge: A Success Story.” New York Times, 15 Nov. 1992. 12 Sep. 2018 <https://www.nytimes.com/1992/11/15/style/grunge-a-success-story.html>.Neumann, Mark. “Collecting Ourselves at the End of the Century.” Composing Ethnography: Alternative Forms of Qualitative Writing. Eds. Carolyn Ellis and Arthur P. Bochner. London: Alta Mira Press, 1996. 172-198.Nirvana. "Smells Like Teen Spirit." Nevermind, Geffen, 1991.Nnadi, Chioma. “Why Kurt Cobain Was One of the Most Influential Style Icons of Our Times.” Vogue, 8 Apr. 2014. 15 Aug. 2018 <https://www.vogue.com/article/kurt-cobain-legacy-of-grunge-in-fashion>.Perricone, Christopher. “Artist and Audience.” The Journal of Value Inquiry 24 (2012). 12 Sep. 2018 <https://link.springer.com/content/pdf/10.1007/BF00149433.pdf>.Robbins, Ira. “Ten.” Rolling Stone, 12 Dec. 1991. 15 Aug. 2018 <https://www.rollingstone.com/music/music-album-reviews/ten-25142>.Strong, Catherine. “Grunge, Riott Grrl and the Forgetting of Women in Popular Culture.” The Journal of Popular Culture 44.2 (2011): 398-416. Wiederhorn, Jon. “Remembering Layne Staley: The Other Great Seattle Musician to Die on April 5.” MTV, 4 June 2004. 23 Sep. 2018 <http://www.mtv.com/news/1486206/remembering-layne-staley-the-other-great-seattle-musician-to-die-on-april-5/>.Yarm, Mark. Everybody Loves Our Town: An Oral History of Grunge. Three Rivers Press, 2011.

TRANSIMS (Transportation Analysis Simulation System) is part of a multi-track Travel Model Improvement Program sponsored by the U. S. Department of Transportation (DOT), and the Environmental Protection Agency (EPA). The main objective of this thesis is to enhance and implement a principal module in TRANSIMS, called the Route Planner Module. The purpose of the Route Planner Module is to find time-dependent label-constrained shortest paths for transportation activities performed by travelers in the system. There are several variations of shortest path problems and algorithms that vary by application, contexts, complexity, required data, and computer implementation techniques. In general, these variants require some combination of the following inputs: a network consisting of nodes and links, and a travel time function on each link, which could be a time-independent or a time-dependent function, where the time-dependent functions account for time-of-day delays resulting from actual travel conditions such as peak-hour congestion. The problem then seeks a shortest path between one or more origin-destination pairs. A new variant, introduced in the context of TRANSIMS and which is the focus of the present study, also specifies labels for each arc denoting particular modes of travel, along with strings of admissible labels that delineate the permissible travel mode sequences that could be adopted by the user in traveling from the origin to the destination of the trip. The technique adopted by TRANSIMS to identify a suitable travel route for any user is a variant of Dijkstra's procedure for finding shortest paths, which is suitably modified to accommodate time-dependent travel times and label sequence constraints. The underlying problem is referred to as a Time-Dependent Label-Constrained Shortest Path Problem. The main objective of this research is to improve upon this procedure and study its implementation in order to develop a more effective scheme for determining time-dependent label-constrained shortest paths as a practical routing tool in multimodal transportation networks. Specifically, we enhance the following features of this procedure: (a) We recommend a method to work implicitly with a certain composition graph G* that combines the transportation network with the admissible label-sequence graph. This graph G* captures all possible paths for a given single trip starting from the origin node and ending at the destination node, while conforming with the admissible mode string. (b) We use more modern partitioned shortest path algorithmic schemes to implement the time-dependent label-constrained procedure. (c) We introduce the notion of curtailing search based on various indicators of progress and projected travel times to complete the trip. Finally, computer programs in C++ are written to implement the proposed overall algorithm, and are applied to solve some real multimodal transportation network problems. The indicators used to evaluate the performance of the algorithm include (i) time taken for computation on the real network, (ii) quality of solution obtained, (iii) ease of implementation, and (iv) extensibility of the algorithm for solving other variants of the shortest path problem. The results exhibit that the proposed algorithm, even without the approximate curtailing of the search process, exhibits good performance in finding optimal routes for real multimodal transportation networks. Although the various heuristic curtailments result in only approximate solutions, typically, they run much faster than the exact algorithm for the intuitive reason that the shortest path tree developed grows more pointedly in the direction of the destination. Among the different strategies implemented, our results suggest that the scheme based on the geometric structure of the underlying network, using either a constant predictive term, or multiplying this term with a suitable exponential decay function, yields an attractive candidate for heuristically curtailing the search.
Master of Science

In this dissertation, we consider two important problems pertaining to the analysis of transportation systems. The first of these is an approach-dependent, time-dependent, label-constrained shortest path problem that arises in the context of the Route Planner Module of the Transportation Analysis Simulation System (TRANSIMS), which has been developed by the Los Alamos National Laboratory for the Federal Highway Administration. This is a variant of the shortest path problem defined on a transportation network comprised of a set of nodes and a set of directed arcs such that each arc has an associated label designating a mode of transportation, and an associated travel time function that depends on the time of arrival at the tail node, as well as on the node via which this node was approached. The lattermost feature is a new concept injected into the time-dependent, label-constrained shortest path problem, and is used to model turn-penalties in transportation networks. The time spent at an intersection before entering the next link would depend on whether we travel straight through the intersection, or make a right turn at it, or make a left turn at it. Accordingly, we model this situation by incorporating within each link's travel time function a dependence on the link via which its tail node was approached. We propose two effective algorithms to solve this problem by adapting two efficient existing algorithms to handle time dependency and label constraints: the Partitioned Shortest Path (PSP) algorithm and the Heap-Dijkstra (HP-Dijkstra) algorithm, and present related theoretical complexity results. In addition, we also explore various heuristic methods to curtail the search. We explore an Augmented Ellipsoidal Region Technique (A-ERT) and a Distance-Based A-ERT, along with some variants to curtail the search for an optimal path between a given origin and destination to more promising subsets of the network. This helps speed up computation without sacrificing optimality. We also incorporate an approach-dependent delay estimation function, and in concert with a search tree level-based technique, we derive a total estimated travel time and use this as a key to prioritize node selections or to sort elements in the heap. As soon as we reach the destination node, while it is within some p% of the minimum key value of the heap, we then terminate the search. We name the versions of PSP and HP-Dijkstra that employ this method as Early Terminated PSP (ET-PSP) and Early Terminated Heap-Dijkstra (ETHP-Dijkstra) algorithms. All of these procedures are compared with the original Route Planner Module within TRANSIMS, which is implemented in the Linux operating system, using C++ along with the g++ GNU compiler. Extensive computational testing has been conducted using available data from the Portland, Oregon, and Blacksburg, Virginia, transportation networks to investigate the efficacy of the developed procedures. In particular, we have tested twenty-five different combinations of network curtailment and algorithmic strategies on three test networks: the Blacksburg-light, the Blacksburg-full, and the BigNet network. The results indicate that the Heap-Dijkstra algorithm implementations are much faster than the PSP algorithmic approaches for solving the underlying problem exactly. Furthermore, mong the curtailment schemes, the ETHP-Dijkstra with p=5%, yields the best overall results. This method produces solutions within 0.37-1.91% of optimality, while decreasing CPU effort by 56.68% at an average, as compared with applying the best available exact algorithm. The second part of this dissertation is concerned with the Classification and Regression Tree (CART) algorithm, and its application to the Activity Generation Module of TRANSIMS. The CART algorithm has been popularly used in various contexts by transportation engineers and planners to correlate a set of independent household demographic variables with certain dependent activity or travel time variables. However, the algorithm lacks an automated mechanism for deriving classification trees based on optimizing specified objective functions and handling desired side-constraints that govern the structure of the tree and the statistical and demographic nature of its leaf nodes. Using a novel set partitioning formulation, we propose new tree development, and more importantly, optimal pruning strategies to accommodate the consideration of such objective functions and side-constraints, and establish the theoretical validity of our approach. This general enhancement of the CART algorithm is then applied to the Activity Generator module of TRANSIMS. Related computational results are presented using real data pertaining to the Portland, Oregon, and Blacksburg, Virginia, transportation networks to demonstrate the flexibility and effectiveness of the proposed approach in classifying data, as well as to examine its numerical performance. The results indicate that a variety of objective functions and constraints can be readily accommodated to efficiently control the structural information that is captured by the developed classification tree as desired by the planner or analyst, dependent on the scope of the application at hand.
Ph. D.