Communications - Scientific Letters of the University of Zilina 2014, 16(2):83-91 | DOI: 10.26552/com.C.2014.2.83-91

Economically Optimal Road Subnetwork

Anna Cerna1, Jan Cerny1, Vladimir Pribyl1
1 University of Economics in Prague, Faculty of Management, Jindrichuv Hradec, Czech Republic

The paper deals with the following situation: An area is served by a transportation network, usually the road one. The current quality of the network is not satisfactory for the owner (e.g. a company or public administration), but the reconstruction or recovery of the whole network is not feasible for the economic reasons. Managers, who are responsible for the network, make decisions how to reduce the network and then to reconstruct or recover it meeting certain conditions and minimizing costs. The condition is formulated by means of the set W of important pairs of sources and sinks of transport flows and by the number q ≥ 1 representing the maximal acceptable elongation rate of routes between nodes (vertices) from the set W.

Such a problem can be met e.g. in rural road network reduction for winter maintenance, choice of tram or trolleybus network as a subnetwork of the bus one etc.

The paper describes the mathematical support for that decision making. The mathematical model of the problem is presented. Then a depth-first search type exact method is proposed and verified. Afterwards, a heuristics is described and verified as well. Finally, linear programming version of the problem is added.

The results were applied to urban bus network of Slovak town Piestany.

Keywords: road, network, subnetwork, optimization

Published: April 30, 2014  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Cerna, A., Cerny, J., & Pribyl, V. (2014). Economically Optimal Road Subnetwork. Communications - Scientific Letters of the University of Zilina, 16(2), 83-91. doi: 10.26552/com.C.2014.2.83-91
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. CERNA, A.: Economic and Social Harmonization of Sustainable Public Transport. Prague Economic Papers, 21(1) 83-100, 2012. Go to original source...
    2. YANG, H., BELL, M. G. H.: Models and Algorithms for Road Network Design: A Review and Some New Developments. Transport Reviews, 18(3), 257-278, 1998. Go to original source...
    3. GAO, Z. Y., WU, J. J., SUN, H. J.: Solution Algorithm for the Bi-level Discrete Network Design Problem. Transportation Research Part B - Methodological, 39(6), 479-495, 2005. Go to original source...
    4. MENG, Q., YANG, H., BELL, M. G. H.: An Equivalent Continuously Differentiable Model and a Locally Convergent Algorithm for the Continuous Network Design Problem. Transportation Research Part B - Methodological 35(1), 83-105, 2002. Go to original source...
    5. MENG, Q., YANG, H.: Benefit Distribution and Equity in Road Network Design. Transportation Research Part B - Methodological 36(1), 19-35, 2002. Go to original source...
    6. MIANDOABCHI, E., ZANJIRANI FARAHANI, R., SZETO, W. Y.: Bi-objective Bimodal Urban Road Network Design Using Hybrid Metaheuristics. CEJOR 20(4), 583-621, 2012. Go to original source...
    7. XIE, F., LEVINSON, D.: Modeling the Growth of Transportation Networks: A Comprehensive Review. Networks and Spatial Economics, 9(3), 291-307, 2009. Go to original source...
    8. GUTIERREZ, J., GARCIA-PALOMARES, J. C.: New Spatial Patterns of Mobility within the Metropolitan Area of Madrid: Towards more complex and dispersed flow networks. J. of Transport Geography, 15(1), 18-30, 2007. Go to original source...
    9. KELLY, M. E., NIEDZIELSKI, M. A.: Efficient Spatial Interaction: Attainable Reductions in Metropolitan Average Trip Length. J. of Transport Geography, 16(5), 313-323, 2008. Go to original source...
    10. JENELIUS, E.: Network Structure and Travel Patterns: Explaining the Geographical Disparities of Road Network Vulnerability. J. of Transport Geography, 17(3), 234-244, 2009. Go to original source...
    11. DREZNER, Z., WESOLOWSKY, G. O.: Network Design: Selection and Design of Links and Facility Location. Transportation Research Part A - Policy and Practice 37(3), 241-256, 2003. Go to original source...
    12. BORUVKA, O.: About a Certain Minimal Problem (in Czech, German summary), Prace mor. prirodoved. spol. v Brne, III (3), 37-58, 1926.
    13. CAI, L., CORNEIL, D. G.: Tree Spanners. SIAM J. Discrete Mathematics, 8 (3), 359-387, 1995. Go to original source...
    14. EADES, P., FOULDS, L. R., GIFFIN, J. W.: An Efficient Heuristic for Identifying a Maximum Weight Planar Subgraph. Combinatorial Mathematics IX, Lecture Notes in Mathematics, No. 952. Springer-Verlag, Berlin 1982, 2003. Go to original source...
    15. GABOW, H. N., GOEMANS, M. X., TARDOS, E., WILLIAMSON, D. P.: Approximating the Smallest k-Edge Connected Spanning Subgraph by LP-Rounding. SODA '05 Proc. of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, 562-571, 2005.
    16. CHERIYAN, J., THURIMELLA, R.: Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching. SIAM J. Comput., 30 (2), 528-560, 2000. Go to original source...
    17. FERNANDES, C. G.: A Better Approximation Ratio for the Minimum Size k-Edge-Connected Spanning Subgraph Problem. J. Algorithms, 28 (1), 105-124, 1998. Go to original source...
    18. CARR, R., RAVI, R.: A New Bound for the 2-Edge Connected Subgraph Problem. R. E. Bixby, E. A. Boyd, and R. Z. Rios-Mercado (Eds.): IPCO VI, LNCS 1412. Springer-Verlag Berlin Heidelberg 1998, 112-125, 1998. Go to original source...
    19. SUZUKI, A. TOKUYAMA, T.: Dense Subgraph Problem Revisited. Proc. Joint Workshop New Horizons in Computing" and "Statistical Mechanical Approach to Probabilistic Information Processing, 2005, Sendai, 1-2, 2005.
    20. SAFARI, M. A., SALAVATIPOUR, M. R.: A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs. A. Goel et al. (Eds.): APPROX and RANDOM 2008, LNCS 5171. Springer-Verlag Berlin Heidelberg, 233-246, 2008. Go to original source...
    21. CHERIYAN, J., VEMPALA, S., VETTA, A.: An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph. SIAM J. Computing, 32(4), 1050-10552003. Go to original source...
    22. AMINI, O., PELEG, D., PERENNES, S., SAU, I., SAURABH, S.: Degree-Constrained Subgraph Problems: Hardness and Approximation Results. E. Bampis and M. Skutella (Eds.): WAOA 2008, LNCS 5426. Springer-Verlag Berlin : Heidelberg 2009, 29-42, 2009. Go to original source...
    23. VASSILEVSKA, V., WILLIAMS, R., YUSTER, R.: Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems. M. Bugliesi et al. (Eds.): ICALP 2006, Part I, LNCS 4051. Springer-Verlag Berlin Heidelberg 2006, 262-273, 2006. Go to original source...
    24. HINTSANEN, P.: The Most Reliable Subgraph Problem. J.N. Kok et al. (Eds.): PKDD 2007, LNAI 4702. Springer-Verlag Berlin Heidelberg 2007, 471-478, 2007. Go to original source...
    25. FERRER, M., SERRATOSA, F., VALVENY, E.: On the Relation between the Median and the Maximum Common Subgraph of a Set of Graphs. F. Escolano and M. Vento (Eds.): GbRPR 2007, LNCS 4538. Springer-Verlag Berlin Heidelberg 2007, 351-360, 2007. Go to original source...
    26. BERGER, B., SHOR, P. W.: Approximation Algorithms for the Maximum Acyclic Subgraph Problem. SODA '90 Proc. of the first annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics Philadelphia, 236-243, 1990.
    27. CZIMERMAN, P., CERNA, A., CERNY, J., PESKO, A.: Network Reduction Problems. J. of Information, Control and Management Systems, 5 (2), 139-147, 2007.
    28. POORZAHEDY, H., ABULGHASEMI, F.: Application of Ant System to Network Design Problem. Transportation 32(3), 251-273, 2005. Go to original source...
    29. POORZAHEDY, H., ROUHANI, O.: Hybrid Meta-heuristic Algorithms for Solving Network Design Problem. European J. of Operational Research, 182(2), 578-596, 2007. Go to original source...

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content