Shortest covering paths and other covering walks
Refinements and prospects for subtour prevention
Bibliographic Data
| ID | 7731632 |
|---|---|
| Authors | Timothy C Matisziw (0000-0003-2159-4904, University of Missouri, corresponding author) |
| Year | 2025 |
| Volume | 118 |
| Pages | 102247 |
| Publication date | 2025-06-01 |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Computers Environment and Urban Systems (JOURNAL) |
| Journal identifiers | ISSN: 0198-9715 • E-ISSN: 1873-7587 |
| Publisher | Elsevier BV (PUBLISHER) |
| DOI | 10.1016/j.compenvurbsys.2024.102247 |
| OpenAlex | W4407515025 |
| Language | EN |
| References cited | 19 |
The shortest covering path problem (SCPP) is a network optimization model in which a least-cost route connecting an origin and destination that can be accessed by all demand nodes in a network is sought. Thus, it is applicable to transportation planning tasks such as designing routes for public transit and distribution systems. However, deriving optimal solutions to the SCPP can be challenging as an iterative solution approach is often required. Also, problems can arise in accounting for coverage of network nodes and in the handling of certain types of cycles. To this end, a family of model variants for the SCPP is proposed to remedy these problems and to assist with the identification of covering paths and other walks. Additionally, the case in which the origin node is also the destination node is incorporated into the SCPP framework. A flow-constrained SCPP that does not require an iterative solution process is then proposed to identify optimal walks of different types. The flow-constrained SCPP and its iterative counterpart are solved for all origin-destination pairs in a network and their relative computational characteristics are assessed. The results demonstrate that optimal solutions to the flow-constrained SCPP can be obtained more quickly than those obtained using the iterative approach. The results also provide further evidence of the relevance of cycles, particularly those involving U-turns, in solutions to network routing problems. Together, the proposed refinements, extensions, and documented computational experience will extend the applicability and the utility of the SCPP and its counterpart path covering models. • Refinements to shortest covering path models address specific routing scenarios. • New subtour prevention strategy facilitates identification of exact solutions. • Optimal shortest covering paths identified for all pairs of network nodes. • Robust set of solutions provides comparison of key model characteristics
Art · Cartography · Geography · Humanities · Computer Science · Data Management and Algorithms · Evacuation and Crowd Dynamics · Transportation Planning and Optimization
| Highly cited | No |
|---|