Binary Weight Allocation for Multi-Objective Path Optimization: Efficient Earliest and Latest Path Discovery in Network Systems
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909568330629120 |
|---|---|
| author | Yeh, Wei-Chang |
| author_facet | Yeh, Wei-Chang |
| contents | This paper proposes earliest and latest path algorithms based on binary weight allocation, assigning weights of 2(i-1) and 2(m-i) to the i-th arc in a network. While traditional shortest path algorithms optimize only distance, our approach leverages Binary-Addition-Tree ordering to efficiently identify lexicographically smallest and largest paths that establish connectivity. These paths partition the solution space into three regions: guaranteed disconnection, transitional connectivity, and guaranteed no simple paths. Our weight allocation enables implicit encoding of multiple objectives directly in binary representations, maintaining the O((|V|+|E|)log|V|) complexity of Dijkstra's algorithm while allowing simultaneous optimization of competing factors like reliability and cost. Experimental validation demonstrates significant computational time reduction compared to traditional multi-objective methods. Applications span telecommunications, transportation networks, and supply chain management, providing efficient tools for network planning and reliability analysis under multiple constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04499 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Binary Weight Allocation for Multi-Objective Path Optimization: Efficient Earliest and Latest Path Discovery in Network Systems Yeh, Wei-Chang Combinatorics Discrete Mathematics Numerical Analysis This paper proposes earliest and latest path algorithms based on binary weight allocation, assigning weights of 2(i-1) and 2(m-i) to the i-th arc in a network. While traditional shortest path algorithms optimize only distance, our approach leverages Binary-Addition-Tree ordering to efficiently identify lexicographically smallest and largest paths that establish connectivity. These paths partition the solution space into three regions: guaranteed disconnection, transitional connectivity, and guaranteed no simple paths. Our weight allocation enables implicit encoding of multiple objectives directly in binary representations, maintaining the O((|V|+|E|)log|V|) complexity of Dijkstra's algorithm while allowing simultaneous optimization of competing factors like reliability and cost. Experimental validation demonstrates significant computational time reduction compared to traditional multi-objective methods. Applications span telecommunications, transportation networks, and supply chain management, providing efficient tools for network planning and reliability analysis under multiple constraints. |
| title | Binary Weight Allocation for Multi-Objective Path Optimization: Efficient Earliest and Latest Path Discovery in Network Systems |
| topic | Combinatorics Discrete Mathematics Numerical Analysis |
| url | https://arxiv.org/abs/2504.04499 |