The Maximal Covering/Shortest Path Problem Revisited: An Examination and Reformulation of the Problem to Allow the Elimination or Attachment of Sub-Tours.

摘要

There are many problems that can be addressed as a spatial optimization problem, including location, districting, and routing. The problem addressed here is a routing problem that is inspired by transit system design. Transit systems in small to medium sized systems tend to utilize routes that involve loops. Routes in larger systems rarely have loops, other than the simple ones forced when travelling along parallel one-way streets. In larger cities, most routes can be considered as linear features. The literature on optimal routing design began with the work of Euler (1741) who defined the Euler Tour problem, which is commonly referred to as a postman problem. More recently, Dantzig et al.(1954) presented a formal mathematical model of the Travelling Salesman Problem and the Orden (1956) formulated the Shortest Path Problem as a mathematical programming problem. More recently, Current et al. (1984) formulated the shortest path covering problem. The shortest path covering problem represents the underlying design problem involved in transit system layout. This shortest path covering model and its variants optimize route coverage and route efficiency (as measured by route time or distance). Geographers and operations researchers have used the optimal covering-path model (Current et al. 1984 & 1985) in a number of ways to design systems of efficient transit routes. In fact, all optimal design problem formulations are based upon the original, classic work of Current.;Past research has built upon the ground-breaking work of Current et al (1984 & 1985) almost without question. This thesis revisits this classic research within the context of transit route design. It is demonstrated that the classic models are built with an implicit assumption that optimal routes will not contain loops. It is also shown that the proposed algorithmic solution approach of Current et al. (1984 & 1985) prevents the occurrence of most loops in a solution. It is shown that loops may indeed be part of an optimal route and that the original models and solution approach are therefore flawed. This is, in itself, a substantial finding.;A new model formulation is proposed for the maximal covering/shortest route problem which allows loops to be utilized in a solution, which would otherwise be excluded. In addition, a revised solution procedure is presented which allows loops to form whenever embedded loops are optimal. This new model, as well as the original models, are applied to a hypothetical network derived from the classic Swain dataset. The optimal tradeoff curve between route coverage and route distance is generated for vi both the classic model as well as the new, revised model. Solutions that contain loops are identified which are superior to what is generated by the original models.;This thesis has called into question the very underpinnings of a classic design problem and has shown that the original assumptions about embedded loops are wrong and that the classic model formulations and solution process are flawed. The work describe here will have a significant impact on future model development for cover-path problems and applications.