Robust p-median problem in changing networks

• Autorzy: Peško Š. , Majer T.

Warianty tytułu

DE

Das Problem des P-Medians in den sich wechselnden Netzen

• Języki publikacji: EN

Abstrakty

EN

The robust p-median problem in changing networks is a version of known discrete p-median problem in network with uncertain edge lengths where uncertainty is characterised by given interval. The uncertainty in edge lengths may appear in travel time along the edges in any network location problem. Several possible future scenarios with respect to the lengths of edges are presented. The planner will want a strategy of positioning p medians that will be working "as well as possible" over the future scenarios. We present MILP formulation of the problem and the solution method based on exchange MILP heuristic. The cluster of each median is presented by rooted tree with the median as root. The performance of the proposed heuristic is compared to the optimal solution found via Gurobi solver for MILP models through some illustrative instances of Slovak road network in Zilina.

DE

Das Problem des P-Medians in den sich wechselnden Netzen ist eines der Versionen des bekannten diskreten Problems über P-Median im Netz mit nicht gewissen Abschnittlängen, wo die Unbestimmheit durch das gegebene Intervall angesetzt wird.Nicht gewisse Länge der Abschitte kann sich als Fahrtlänge in dem Gebiet des jeweiligen Lokationsproblem bestimmen. Wir führen einige Szenare mit Rücksicht auf Kantenlänge ein. Der Planer sucht die Strategie "möglichst guter" Plazierung von P-Medianen mit Rücksicht auf zukünftige Szenare. Wir stellen MILP-Formulierung des Problems und Lösungsverfahren vor, die auf der Tausch-Heuristik gegründet werden. Die zu jedem Median gehörende Ansammlung wird als der Baum mit Würzeln als Median präsentiert. Die Qualität der vorgeschlagenen Heuristik vergleichen wir mit der optimalen Lösung der erworbenen Gurobi-Solver für MILP-Modelle auf einigen Illustrationsinstanzen der Strassennetze in der Slowakischen Republik im Region Zilina.

Słowa kluczowe

EN

robust p-median problem; uncertain edge length; mixed integer linear programming; MILP heuristic; Gurobi solver; network variables

PL

problem p medialny; niepewna długość krawędzi; programowanie liniowe mieszane; heurystyka; Gurobi; sieci zmienne

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Transport Problems
• Rocznik: 2015
• Tom: T. 10, z. 3
• Strony: 125--130
• Opis fizyczny: Bibliogr. 12 poz., tab., wykr.

Twórcy

autor

Peško Š.

• University of Žilina, Faculty of Management Science and Informatics, Univerzitná 8215/1,010 26 Žilina, Slovakia

autor

Majer T.

• University of Žilina, Faculty of Management Science and Informatics, Univerzitná 8215/1,010 26 Žilina, Slovakia

Bibliografia

• 1. Gurobi Optimization Inc. Gurobi Optimizer Reference Manual. 2015. Available at: http://www.gurobi.com.
• 2. Janošíková, L. Emergency Medical Service Planning. Communications, Scientific Letters of the University of Žilina. 2007. Vol. 9. No. 2. P. 64-68.
• 3. Janáček, J. Radial approach to emergency public service system design with generalised system utility. International journal of applied mathematics and informatics. 2014. Vol. 8. P. 7-14.
• 4. Janáček, J. & Kvet, M. Sequential zone adjustment for approximate solving of large p-median problems. Operations research proceedings. Berlin, Heidelberg: Springer-Verlag. 2012. P. 269-274.
• 5. Nikoofal, M.E. & Sadjadi, S.J. A robust optimization model for p-median problem with uncertain edge length. The International Journal of Advanced Manufacturing Technology. 2010. Vol. 50. P. 391-397. DOI 10.1007/s00170-009-2503-z.
• 6. Bertsimas, D. & Sim, M. Robust discrete optimization on network flows. Math. Program. Ser. B 98. 2003. P. 49-71.
• 7. Peško, Š. & Majer, T. Capacitated p-median problem on sparse networks using SOS constraints. In: VI international scientific conference “Transport problems”. 25-27 June 2014. Katowice. P. 586-591.
• 8. Reese, J. Solution methods for p-median problem: An annotated bibliography. Networks. 2005. Vol. 48. No. 3. P. 125-142.
• 9. Rossum, G. Python 2.7.9 documentation. 2015. Available at: http://docs.python.org/2/.
• 10. Jones, E. & Oliphant P. & Peterson P. & et all. Open source scientific tools for Python. 2001. Available at: http://www.scipy.org/.
• 11. Hunter, J.D. Matplotlib: A 2d graphics environment. Computing in Science and Engineering. 2007. Vol. 9(3). P. 90-95.
• 12. Gurobi Optization Inc. Guroby optimizer reference manual. Available at: http://www.gurobi.com.