YÖNLÜ İKİ OBJEKTİFLİ ÇİNLİ POSTACI PROBLEMİ İÇİN KESİN ÇÖZÜM YAKLAŞIMLARI

Yıl 2018, Cilt: 29 Sayı: 1-2, 15 - 30, 09.11.2018

Meral Azizoğlu , Ezgi Eroğlu

Öz

Bu çalışmada iki toplamsal kriterli (toplam maliyet ve toplam mesafe gibi) yönlü çinli postacı problemi ele alınmış ve tüm bastırılamayan objektif vektörlerini yaratmak için iki çözüm yaklaşımı geliştirilmiştir.  Birinci yaklaşım, klasik yaklaşım, karmaşık kesikli doğrusal programların optimal çözümlerini kullanmakta ve bastırılamayan objektif vektör setini seri olarak yaratmaktadır. İkinci yaklaşım, dal ve sınır algoritması, doğrusal programlama gevşetimlerinin optimal çözümlerini kullanmakta ve bastırılamayan objektif vektör setindeki çözümleri aynı anda yaratmaktadır. Deneysel çalışmamızın sonuçları yaklaşımlarımızın büyük boyutlu problemleri makul sürelerde çözdüğünü göstermektedir.

Anahtar Kelimeler

İki-objektifli programlama, çinli postacı problemi, karmaşık tam sayılı doğrusal programlama, klasik yaklaşım

EXACT SOLUTION APPROACHES FOR THE DIRECTED BI-OBJECTIVE CHINESE POSTMAN PROBLEM

Öz

In this study, we consider a directed bi-objective Chinese Postman Problem with two additive objectives (like total cost and total distance) and propose two solution approaches to generate all non-dominated objective vectors.  The first approach, namely classical approach, uses the optimal solutions of the mixed integer linear programs and generates the non-dominated objective vectors’ set sequentially. The second approach, namely branch and bound algorithm takes its spirit from the optimal solutions of the linear programming relaxations and generates the non-dominated objective vectors’ set simultaneously. The results of our extensive computational study show that our approaches are capable of solving large-sized problem instances in reasonable times.

Anahtar Kelimeler

Bi-objective programming, chinese postman problem, mixed ınteger linear programming, classical approach

Kaynakça

• Amine, K. & Djellab, R. 2013. Industrial and Urban Applications of Eulerian and Chinese Walks, In Graph Theory for Operations Research and Management: Applications in Industrial Engineering, IGI-Global, Hershey,. 271-279.
• Brucker, P. 1981. "The Chinese Postman Problem For Mixed Graphs. Graph Theoretic Concepts in Computer Science," Springer Berlin Heidelberg. Christofides, N., Benavent, E., Campos, V., Corberán, A., & Mota, E. 1984. "An Optimal Method for the Mixed Postman Problem." System Modelling and Optimization. Springer Berlin Heidelberg. Corberán, A., Oswald, M., Plana, I., Reinelt, G., & Sanchis, J. M. 2012. "New Results on the Windy Postman Problem."  Mathematical Programming, vol. 132, p. 309-332. Dewil, R., Vansteenwegen, P., & Cattrysse, D. 2011. Cutting path optimization using Tabusearch. Key Engineering Materials, vol. 473, p. 739–748. Edmonds, J. 1963. Chinese postmen problem. Operations Research, 13, B73-B77. Edmonds, J., & Johnson, E. L. 1973. "Matching, Euler Tour and the Chinese Postman Problem." Mathematical Programming, vol. 5, p. 88-124. Eiselt, H. A., Gendreau, M., & Laporte, G. 1995. "Arc Routing Problems, Part I: The Chinese Postman Problem." Operations Research, vol. 43, p. 231-242. Ford, L. R., Fulkerson, D. R. 1962.  "Flows in Networks," Princeton University Press: Princeton. Grandinetti, L., Guerriero, F., Laganà, D., & Pisacane, O. 2012. "An Optimization-Based Heuristic for the Multi-objective Undirected Capacitated Arc Routing Problem." Computers & Operations Research, 39, 2300-2309. Grötschel, M., & Win, Z. 1992. "A Cutting Plane Algorithm for the Windy Postman Problem." Mathematical Programming, vol. 55, p. 339-358. Guan, M. 1962. Graphic programming using odd or even points. Chinese Math, vol. 110, p. 273-277. Haimes, Y. Y., Lasdon, L. S., & Wismer, D. A. 1971. "On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization." IEEE Transactions on Systems Man and Cybernetics, vol. 1, p. 296-297. Han, G., & Na, S. 1999. "A Study on Torch Path Planning in Laser Cutting Processes Part 2: Cutting Path Optimization Using Simulated Annealing." Journal of Manufacturing Processes, 1, 62–70. Imahori, S., Kushiya, M., Nakashima, T., & Sugihara, K. 2008. "Generation of Cutter Paths" Processing Technology, vol. 206 (1-3), p. 453–461. Lacomme, P., Prins, C., & Sevaux, M. 2006. "A Genetic Algorithm for a Bi-objective Capacitated Arc Routing Problem." Computers & Operations Research, vol. 33, p. 3473-3493. Malandraki, C., & Daskin, M. S. 1993. "The Maximum Benefit Chinese Postman Problem and the Maximum Benefit Traveling Salesman Problem." European Journal of Operational Research, vol. 65, p. 218-234. Manber, U., & Israni, S. 1984. "Pierce Point Minimization and Optimal Torch Path Determination in Flame Cutting." Journal of Manufacturing Systems, vol. 3, p.81–89. Martello, S., & Toth, P. 1990. "An Exact Algorithm for Large Unbounded Knapsack Problems." Operations Research Letters, vol. 9, p. 15-20. Mei, Y., Tang, K., & Yao, X. 2011. "Decomposition-Based Memetic Algorithm for Multiobjective Capacitated Arc Routing Problem." IEEE Transactions on Evolutionary Computation, vo. 15, p. 151-165. Minieka, E. 1979. "The Chinese Postman Problem For Mixed Networks." Management Science, vol. 25, p. 643-648. Nobert, Y. & Picard, J. 1991. "An Optimal Algorithm for the Mixed Chinese Postman Problem." Centre de Recherche Sur Les Transports Publication. Papadimitriou, C. H. 1976. "On the Complexity of Edge Traversing." Journal of the ACM, vol. 23, p. 544-554. Prakash, S., Sharma, M. K., & Singh, A. 2009. "A Heuristic For Multi-Objective Chinese Postman Problem." Computers & Industrial Engineering Conference Proceedings, p. 596-599. Rodrigues, A. M., & Ferreira, J. S. 2012. "Cutting path as a Rural Postman Problem: Solutions by memetic algorithms." International Journal of Combinatorial Optimization Problems and Informatics, vol. 3, p. 31–46. Win, Z. 1989. "On the Windy Postman Problem on Eulerian Graphs." Mathematical Programming, vol. 44, p.97-112.