A traffic-based model to the p-median problem in congested networks

Articles in Press

Document Type : Original paper

Authors

Department of Applied Mathematics, Hakim Sabzevari University, Sabzevar, Iran

Abstract

In real urban transportation networks, the traffic counts of links affect their travel times, so considering fixed traffic-independent link travel times causes a lack of reliability in network models. In this paper, a traffic congestion model to the capacitated p-median problem is introduced to evaluate the effect of congestion on determining the optimal locations of facilities and allocating demands. Limited capacities for both nodes and links are considered, where increasing the traffic flow on one link would inevitably increase its travel time. Therefore, aside from considering the capacities of candidate points, the proposed model aims to locate facilities at nodes where their connected links also have enough capacities for passing through. Also, the effect of congestion imposed by the current flows corresponding to the existing origin-destination pairs in the network is considered. A generalized Benders decomposition algorithm is applied to reduce the problem to more manageable sub-problems, solved by the sub-gradient algorithm through consecutive iterations.

Keywords

Main Subjects

References

[1] M. Abareshi and M. Zaferanieh, A bi-level capacitated p-median facility location problem with the most likely allocation solution, Transportation Research Part B: Methodological 123 (2019), 1–20.
https://doi.org/10.1016/j.trb.2019.03.013
[2] M. Abareshi, M. Zaferanieh, and B. Keramati, Path flow estimator in an entropy model using a nonlinear l-shaped algorithm, Networks and Spatial Economics 17 (2017), no. 1, 293–315.
https://doi.org/10.1007/s11067-016-9327-9
[3] R. Aboolian, O. Berman, and M. Karimi, Probabilistic set covering location problem in congested networks, Transp. Sci. 56 (2022), no. 2, 528–542.
https://doi.org/10.1287/trsc.2021.1096
[4] T. Abrahamsson, Estimation of origin-destination matrices using traffic countsa literature survey, 1998.
[5] M.J. Bagajewicz and V. Manousiouthakis, On the generalized benders decomposition, Comput. Chem. Eng. 15 (1991), no. 10, 691–700.
https://doi.org/10.1016/0098-1354(91)85015-M
[6] M.S. Bazaraa, H.D. Sherali, and C.M. Shetty, Nonlinear Programming: Theory and Algorithms, John wiley & sons, 2006.
[7] M.J. Beckmann, C.B. McGuire, and C.B. Winsten, Studies in the economics of transportation, Yale University Press, New Haven, 1956.
[8] C. Beltran, C. Tadonki, and J.P. Vial, Solving the p-median problem with a semi-Lagrangian relaxation, Comput. Optim. Appl. 35 (2006), no. 2, 239–260.
https://doi.org/10.1007/s10589-006-6513-6
[9] J.F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numer. Math. 4 (1962), no. 1, 238–252.
https://doi.org/10.1007/BF01386316
[10] P. Bergendorff, D.W. Hearn, and M.V. Ramana, Congestion Toll pricing of Traffic Networks, Network Optimization (Berlin, Heidelberg) (P.M. Pardalos, D.W. Hearn, and W.W. Hager, eds.), Springer Berlin Heidelberg, 1997, pp. 51–71
https://doi.org/10.1007/978-3-642-59179-2_4
[11] C. Bütün, S. Petrovic, and L. Muyldermans, The capacitated directed cycle hub location and routing problem under congestion, European J. Oper. Res. 292 (2021), no. 2, 714–734.
https://doi.org/10.1016/j.ejor.2020.11.021
[12] J.A. DÍaz and E. Fernandez, Hybrid scatter search and path relinking for the capacitated p-median problem, European J. Oper. Res. 169 (2006), no. 2, 570–585.
https://doi.org/10.1016/j.ejor.2004.08.016
[13] J. Dupuit, De la measure de l’utilit´e des travaux publiques, Annales des Ponts et Chauss´ees 8 (1844), 255–283.
[14] D. Eppstein, Finding the k shortest paths, SIAM J. comput. 28 (1998), no. 2, 652–673.
https://doi.org/10.1137/S0097539795290477
[15] K. Fleszar and K.S. Hindi, An effective VNS for the capacitated p-median problem, European J. Oper. Res. 191 (2008), no. 3, 612–622.
https://doi.org/10.1016/j.ejor.2006.12.055
[16] C.A. Floudas, A. Aggarwal, and A.R. Ciric, Global optimum search for nonconvex NLP and MINLP problems, Comput. Chem. Eng. 13 (1989), no. 10, 1117–1132.
https://doi.org/10.1016/0098-1354(89)87016-4
[17] M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval research logistics quarterly 3 (1956), no. 1-2, 95–110.
[18] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979.
[19] A.M. Geoffrion, Duality in nonlinear programming: a simplified applications-oriented development, SIAM review 13 (1971), no. 1, 1–37.
https://doi.org/10.1137/1013001
[20] A.M. Geoffrion, Generalized benders decomposition, J. Optim. Theory Appl. 10 (1972), no. 4, 237–260.
https://doi.org/10.1007/BF00934810
[21] M. Golabi, S.M. Shavarani, and L. Idoumghar, A congested capacitated location problem with continuous network demand, RAIRO Oper. Res. 56 (2022), no. 5, 3561–3579.
https://doi.org/10.1051/ro/2022167
[22] S.L. Hakimi, Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Oper. Res. 13 (1965), no. 3, 462–475.
https://doi.org/10.1287/opre.13.3.462
[23] O. Kariv and S. Hakimi, An algorithmic approach to network location problems. II: the p-medians, SIAM J. Appl. Math 37 (1979), 539–560.
https://doi.org/10.1137/0137041
[24] L.A.N. Lorena and E.L.F. Senne, A column generation approach to capacitated p-median problems, Comput. Oper. Res. 31 (2004), no. 6, 863–876.
https://doi.org/10.1016/S0305-0548(03)00039-X
[25] V. Maniezzo, A. Mingozzi, and R. Baldacci, A bionomic approach to the capacitated p-median problem, J. Heuristics 4 (1998), no. 3, 263–280.
https://doi.org/10.1023/A:1009665717611
[26] M.D. Meyer, Transportation Planning Handbook, Wiley, 2016.
[27] A.W. Neebe, Branch and bound algorithm for the p-median transportation problem, J. Oper. Res. Soc. 29 (1978), no. 10, 989–995.
https://doi.org/10.1057/jors.1978.212
[28] M. Patriksson, The Traffic Assignment Problem: Models and Methods, Dover Publications, 2015.
[29] A.C. Pigou, The Economics of Welfare, Creative Media Partners, LLC, 2022.
[30] J. Reese, Solution methods for the p-median problem: An annotated bibliography, Networks 48 (2006), no. 3, 125–142.
https://doi.org/10.1002/net.20128
[31] C.S. ReVelle and R.W. Swain, Central facilities location, Geographical Analysis 2 (1970), no. 1, 30–42.
https://doi.org/10.1111/j.1538-4632.1970.tb00142.x
[32] H. Shamsipoor, M.A. Sandidzadeh, and M. Yaghini, Solving capacitated p-median problem by a new structure of neural network., Int. J. Indus. Eng. 19 (2012), no. 8. 305–319.
[33] Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, Prentice-Hall, New Jersey, 1984.
[34] S. Shiripour, N. Mahdavi-Amiri, and I. Mahdavi, A transportation network model with intelligent probabilistic travel times and two hybrid algorithms, Transp. Lett. 9 (2017), no. 2, 90–122.
https://doi.org/10.1080/19427867.2016.1187893
[35] A. Tamir, An O(pn2) algorithm for the p-median and related problems on tree graphs, Oper. Res. Lett. 19 (1996), no. 2, 59–64.
https://doi.org/10.1016/0167-6377(96)00021-1
[36] J.G. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the Institute of Civil Engineers 1 (1952), no. 2, 325–362.
[37] M. Zaferanieh, The most probable allocation solution for the p-median problem, Iranian Journal of Numerical Analysis and Optimization 10 (2020), no. 2, 155–176.
https://doi.org/10.22067/ijnao.v10i2.84892
[38] M. Zaferanieh, M. Abareshi, and J. Fathali, The minimum information approach to the uncapacitated p-median facility location problem, Transp. Lett. 14 (2022), no. 3, 307–316.
https://doi.org/10.1080/19427867.2020.1864595
[39] M. Zaferanieh, M. Abareshi, and M. Jafarzadeh, A bi-level p-facility network design problem in the presence of congestion, Comput. Indus. Eng. 176 (2023), Article ID: 109010.
https://doi.org/10.1016/j.cie.2023.109010
[40] M. Zaferanieh, M. Sadra, and T. Basirat, P-facility capacitated location problem with customer-equilibrium decisions: a recreational case study in mazandaran province, J. Modelling in Management (2024), In press.
https://doi.org/10.1108/JM2-08-2023-0194
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 18 July 2024

Files

Share

How to cite

Statistics