Dergiler / Endüstri Mühendisliği / 2018 / Cilt: 29 - Sayı: 1-2

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

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

Sayfa
15–30
Yayın Tarihi
2018-11-09
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

Deneysel çalışmamızın sonuçları yaklaşımlarımızın büyük boyutlu problemleri makul sürelerde çözdüğünü göstermektedir.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez: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.
📊
Temel Bulgular & Veri: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.
💡
Sonuç & Katkı:Deneysel çalışmamızın sonuçları yaklaşımlarımızın büyük boyutlu problemleri makul sürelerde çözdüğünü göstermektedir.
🔬Tür:Modelleme & Sayısal Simülasyon
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:İki-objektifli programlama · çinli postacı problemi · karmaşık tam sayılı doğrusal programlama

Özet

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.

Abstract

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.

🔖

Bu Makaleye Atıf Yap

AZİZOĞLU, M., EROĞLU, E. (2018). YÖNLÜ İKİ OBJEKTİFLİ ÇİNLİ POSTACI PROBLEMİ İÇİN KESİN ÇÖZÜM YAKLAŞIMLARI. Endüstri Mühendisliği, Cilt: 29 - Sayı: 1-2, 15–30. https://ajindex.com/articles/70688

📄 Tam Metin PDF Okuyucu

📄

PDF görüntüleyici hazırlanıyor...

Kaynakça (13)

  1. 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.
  2. 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.
  3. Dewil, R., Vansteenwegen, P., & Cattrysse, D. 2011. Cutting path optimization using Tabusearch. Key Engineering Materials, vol. 473, p. 739–748.
  4. 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.
  5. Eiselt, H. A., Gendreau, M., & Laporte, G. 1995. "Arc Routing Problems, Part I: The Chinese Postman Problem." Operations Research, vol. 43, p. 231-242.
  6. Ford, L. R., Fulkerson, D. R. 1962. "Flows in Networks," Princeton University Press:
  7. 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.
  8. Grötschel, M., & Win, Z. 1992. "A Cutting Plane Algorithm for the Windy Postman Problem." Mathematical Programming, vol. 55, p. 339-358.
  9. Guan, M. 1962. Graphic programming using odd or even points. Chinese Math, vol. 110, p. 273-277.
  10. 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.
  11. 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.
  12. Imahori, S., Kushiya, M., Nakashima, T., & Sugihara, K. 2008. "Generation of Cutter Paths" Processing Technology, vol. 206 (1-3), p. 453–461.
  13. Lacomme, P., Prins, C., & Sevaux, M. 2006. "A Genetic Algorithm for a Bi-objective Capacitated Arc Routing Problem." Computers & Operations Research, vol. 33, p. 347