An Extended Mathematical Programming Model to Optimize the Cable Trench Route of Power Transmission in a Metro Depot

Document Type : Research Paper

Authors

1 Assistant Professor, School of Industrial Engineering, University of Tehran, Tehran, Iran

2 MSc. Student, School of Industrial Engineering, University of Tehran, Tehran, Iran

Abstract

The necessary electricity of the workshops and buildings (W&Bs) located at the metro depot are provided by lighting power substation (LPS). To transmit electricity between LPS and W&Bs, some trenches should be dig and the requisite cables should be located in the trenches. This paper presents a new mixed integer linear programming (MILP) long-term decision model to find the best cable trench route between LPS and W&Bs and also the location of all W&Bs and LPS are fixed. In this problem, the objective is to minimize (1) used cables cost, and (2) trench digging cost. It should be considered that there exist many cases in which the minimum either used cables or trench digging does not result in minimum total cost. Therefore, in optimum solution, a tradeoff between these objectives should be achieved. Finally, the proposed model is applied to a real case study at the metro depot in Iran and the optimum solution is analyzed.

Keywords

References

-Arkin, E. M., Carmi, P., Katz, M. J., Mitchell, J. S. B. and Segal, M. (2014) “Locating battery charging stations to facilitate almost shortest paths”, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’14), Vol. 42, pp. 25–33
-Baxter, M., Elgindy, T., Ernst, A. T., Kalinowski, T. and Savelsbergh, M. (2014) “Incremental network design with shortest paths”, European Journal of Operational Research
-Bhattacharya, A. and Kumar, A. (2014) “A shortest path tree based algorithm for relay placement in a wireless sensor network and its  performance analysis”, Computer Networks, Vol. 71, pp. 48–62
-Booth, H. and Westbrook, J. (1994) “A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs”, Algorithmica, Vol. 11, No. 4, pp. 341–352
-Eppstein, D. (1999) “Spanning trees and spanners”, California, Elsevier.
-Erlebach, T. and Hoffmann, M. (2014) “Minimum spanning tree verification under uncertainty”, Graph Theoretic Concepts in Computer Science, pp. 164–175
-Gouveia, L., Leitner, M. and Ljubi, I. (2014) “A polyhedral study of the diameter constrained minimum spanning tree problem”
-Hochuli, A., Holzer, S. and Wattenhofer, R. (2014) “Distributed approximation of minimum routing cost trees”, arXiv preprint arXiv:1406.1244, pp. 1–18
-Jeng, D. J., Kim, I. and Watada, J. (2006) “DNA-based evolutionary algorithm for cable trench problem”, Springer-Verlag Berlin Heidelberg Part III, Vol. 4253, No. 3, pp. 922–929
-Khuller, S., Raghavachari, B. and Young, N. (1995) “Balancing minimum spanning trees and shortest-path trees”, Algorithmica, Vol. 14, No. 4, pp. 305–321
-Kumar, V. and Kumar, S. (2014) “Spanningtree-based position-based routing in WSNs”, Intelligent Computing, Networking, and Informatics, pp. 1267–1275
-Liu, G., Qiu, Z., Qu, H., Ji, L. and Takacs, A. (2014) “Computing k shortest paths from a source node to each other node”, Soft Computing, pp. 1–12
-Marianov, V., Gutiérrez-Jarpa, G., Obreque, C. and Cornejo, O. (2012) “Lagrangean relaxation heuristics for the p-cable-trench problem”, Computers & Operations Research, Vol. 39, No. 3, pp. 620–628
-Nagarajan, A. and Ayyanar, R. (2014) “Application of minimum spanning tree algorithm for network reduction of distribution systems”, North American Power Symposium (NAPS), IEEE, pp. 1–5
-Pérez-galarce, F., Álvarez-miranda, E., Candiavéjar, A. and Toth, P. (2014) “On exact solutions for the minmax regret spanning tree problem”, Computers & Operations Research, Vol. 47, pp. 114–122
-Ralphs, T. K., Saltzman, M. J. and Wiecek, M. M. (2004) “An improved algorithm for biobjective integer programming and its application to network routing problems”, Annals of Operations Research
-5DOSKV Ɍ Ʉ and Hartman, J. C. (2001) “Capacitated Node Routing Problems (Preliminary Progress Report)”
 
-Xiaoqiang, R. (2014) “Position prediction in mine personnel RFID positioning system based on shortest path principle”, Journal of Chemical and Pharmaceutical Research, Vol. 6, No. 6, pp. 2159 2162
 
-Saravanan, M. and Madheswaran, M. (2014) “A hybrid optimized weighted minimum spanning tree for the shortest intrapath selection in wireless sensor network”, Mathematical Problems in Engineering
-Trudeau, C. (2014) “Minimum cost spanning tree problems with indifferent agents”, Games and Economic Behavior, Vol. 84, pp. 137–151
-Vasko, F. J., Barbieri, R. S., Rieksts, B. Q., Reitmeyer, K. L. and Stott Jr, K. L. (2002) “The cable trench problem: combining the shortest path and minimum spanning tree problems”, Computers & Operations Research, Vol. 29, No. 5, pp. 441–458
-Zhong, C., Malinen, M., Miao, D. and Fränti, P. (2015) “A fast minimum spanning tree algorithm based on k-means” Information Sciences, Vol. 295, pp. 1–17
-Zhou, J., He, X. and Wang, K. (2014) “Uncertain quadratic minimum spanning tree problem”, Journal of Communications, Vol. 9, No. 5, pp. 385–390
International Journal of Transportation Engineering
Volume 3, Issue 2 - Serial Number 2
October 2015
Pages 109-123

Files

Share

How to cite

Statistics