UC Santa Barbara
On the Development of a New Class of Covering Path Models
- Author(s): Niblett, Timothy John
- Advisor(s): Church, Richard L
- et al.
The basis of this dissertation work stems from the fact that if one examines system route maps for many bus transit systems in U.S. cities, an interesting pattern emerges. Routes often utilize embedded loops to increase accessibility coverage of a system at the expense of adding a marginal amount of length to the overall path. Further, such routes frequently share a common corridor with respect to traveling in opposing directions, but they may depart spatially from each other in terms of direction. These departures in direction represent embedded loops that are traversed in only one direction. However, the literature has not explored this issue, and in fact, often discourages or outright prevents any loops from occurring whether they are loops that are traversed in both directions or traversed in only one direction. Furthermore, past research on covering path models has not accounted for travel in opposing directions, even when attempting to model transit lines. This is due in part to the roots of the covering path literature.
This dissertation presents an analysis of past work and from that defines several new problems that are ‘loop agnostic’ – that is, they neither prevent nor encourage the formation of loops in an optimal route, essentially a new class of covering path problems. Although several loop agnostic models are developed in this dissertation to better represent the maximal covering shortest path problem, these models only capture one aspect of loop use. In the classic Maximal Covering Shortest Path problem, it is assumed that its use in transit will be traversed in both directions. Further, the classic formulation prevents most loops from occurring. A new form of this model is developed that allows loops to be part of a solution, whenever such loops provide an improvement in the objective function value. This model is called “loop agnostic” as the model neither prevents nor requires loops to be used in a solution. This means that a loop can be present as part of the path, as an out-and-back path or a more complex loop which visits several other nodes before returning to a previously visited node, or even as a ‘lollipop’ shaped route attached to the origin node or the destination node. If one assumes that the covering path can be traversed both in the outbound and inbound directions (which past work has done), any loops that are present will be traversed in both directions and is what we refer to as a bi-directional loop. When addressing the question of bi-directionality in real world systems it is possible that a loop is traversed in only one direction. Such “uni-directional” loops are formed whenever inbound/outbound paths diverge and can be observed in many transit system maps, like those of Bozeman, MT; Eau Claire, WI; and San Luis Obispo, CA. This dissertation also proposes a new problem, the Bi-Directional MCSP, and formulates two new models that account for travel based upon inbound and outbound path directions which allows for the use of shared arcs and uni-directional loops as well as bi-directional loops.
This dissertation also presents results from the application of these new models as well as a new heuristic to a hypothetical test network as well as a real world network from Richardson/Garland, Texas. Results demonstrate that loops are present in many optimal solutions and that the route designs that utilize loop structures such as a ‘lollipop,’ ‘barbell,’ and ‘figure eight’ may well be superior to route designs that do not incorporate loops. This gives credence to the designs of virtually all transit systems in small and medium sized cities in the United States.