Conference Paper
BibTex RIS Cite

AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM

Year 2023, Volume: 16 Issue: 1, 33 - 42, 22.06.2023
https://doi.org/10.20854/bujse.1218139

Abstract

In industrial engineering, transportation planning, vehicle routing problem, warehousing, inventory management, and customer service are logistics problems. Graph theory algorithms provide solutions to logistics problems such as the shortest path, minimum spanning tree, and vehicle routing problems. In a logistics company system with branches and transfer centers to which the branches are affiliated, if the sorting process is carried out in the transfer centers, the deliveries collected from the branches must be transported to a transfer center. Thus, there are situations where delivery is transferred in the sending branch, the sending transfer center, the receiving transfer center, and the receiving branch, respectively. In this flow, transferring with a single transfer center without visiting two transfer centers reduces the total cost. While moving from the sender transfer center to the receiver transfer center, stopping by some branches on the way allows us to complete the transfer process with a single transfer center and eliminates the necessity of leaving the vehicle from the receiver transfer center to these branches again. Thus, the number of vehicles that need to go from the receiver transfer center to the branches is reduced. The mentioned logistics structure is defined as a graph that is considered a network design problem. Given the sender transfer center S, the receiver transfer center T, the set of branches A connected to S, and the set of branches C that are not connected to S or T, a counting algorithm that gives the minimum value route among all combinations are designed in order to find the optimal route from the source node s ∈ A∪{S}, to the target node t=T. The algorithm has been implemented in Python and Gams and tested by the different number of elements of the set A and the set C.

References

  • Balinski, M. L., & Quandt, R. E. (1964). On an integer program for a delivery problem. Operations Research, 12(2), 300–304. https://doi.org/10.1287/opre.12.2.300
  • Bellmore, M., & Nemhauser, G. L. (1968). The traveling salesman problem: A survey. Operations Research, 16(3), 538–558. https://doi.org/10.4018/978-1-7998-3970- 5.ch006
  • Boruvka, O. (1926). Borůvka, Otakar: Scholarly works. The Czech Digital Matematics Library. 37-58.
  • Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20(3), 309–318.
  • Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568–581. https://doi.org/10.1287/opre.12.4.568
  • Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6), 791-812.
  • Eilon, S., Watson-Gandy, C. D. T., & Heilbron, A. (1971). A vehicle fleet costs more. International Journal of Physical Distribution, 1(3), 126–132. https://doi.org/10.1108/eb038836
  • Feremans, C., Labbé, M., & Laporte, G. (2003). Generalized network design problems. European Journal of Operational Research, 148(1), 1–13. https://doi.org/10.1016/S0377-2217(02)00404-6
  • Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2), 340–349.
  • Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13(5), 533–549. https://doi.org/10.1016/0305- 0548(86)90048-1
  • Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). Formal basis for the heuristic determination Eijj. Systems Science and Cybern􀄞tic􀆐, 4(2), 100–107.
  • Holland, J. H. (1962). Outline for a logical theory of adaptive systems. Journal of the ACM (JACM), 9(3), 297–314. https://doi.org/10.1145/321127.321128
  • Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. https://doi.org/10.1007/978-3-642-24974-7_7
  • Kruskal, J. B., Jr. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. American Mathematical Society, 7(1), 48–50.
  • Lin, S., & Kernighan, B. W. (1973). An e􀄫ective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498–516. https://doi.org/10.1007/s10489-006- 8514-7
  • Open Routing Service. (n.d.). https://openrouteservice.org/
  • Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1389–1401. https://doi.org/10.1002/j.1538- 7305.1957.tb01515.x

GERÇEK HAYAT AKTARMA PROBLEMİNE TAM ÇÖZÜM

Year 2023, Volume: 16 Issue: 1, 33 - 42, 22.06.2023
https://doi.org/10.20854/bujse.1218139

Abstract

Şubelerin ve şubelerin bağlı olduğu aktarma merkezlerinin bulunduğu bir lojistik firma sisteminde, eğer ayrıştırma işlemi aktarma merkezlerinde yapılıyorsa, şubelerden toplanan gönderilerinbir aktarma merkezine taşınması gerekir. Böylece gönderiler sırasıyla gönderen şubede, gönderen transfer merkezinde, alıcı transfer merkezinde ve alıcı şubede transfer edildiği durumlar ortaya çıkmaktadır. Bu akışta iki aktarma merkezine uğramadan tek bir aktarma merkezi ile aktarma yapılması toplam maliyeti düşürmektedir. Gönderici aktarma merkezinden alıcı aktarma merkezine hareket ederken yol üzerindeki bazı şubelere uğramak aktarma işlemini tek bir aktarma merkezi ile tamamlamamızı sağlar ve alıcı aktarma merkezinden bu şubelere tekrar araç yönlendirme zorunluluğunu ortadan kaldırır. Böylece alıcı aktarma merkezinden şubelere gitmesi gereken araç sayısı azaltılmış oluyor. Söz konusu lojistik yapı, bir ağ tasarım problemi olarak ele alınan bir çizge olarak tanımlanmaktadır. Gönderici transfer merkezi S, alıcı transfer merkezi T, S'ye bağlı A şubeleri kümesi ve S veya T'ye bağlı olmayan C şubeleri kümesi verildiğinde, s ∈ A∪{S} kaynak düğümünden t=T hedef düğümüne giden en uygun rotayı bulmak için tüm kombinasyonlar arasından minimum değerli rotayı veren bir sayma algoritması tasarlanmıştır.
Algoritma Python ve Gams'da uygulanmış ve A ve C kümelerinin farklı eleman sayıları ile test edilmiştir.

References

  • Balinski, M. L., & Quandt, R. E. (1964). On an integer program for a delivery problem. Operations Research, 12(2), 300–304. https://doi.org/10.1287/opre.12.2.300
  • Bellmore, M., & Nemhauser, G. L. (1968). The traveling salesman problem: A survey. Operations Research, 16(3), 538–558. https://doi.org/10.4018/978-1-7998-3970- 5.ch006
  • Boruvka, O. (1926). Borůvka, Otakar: Scholarly works. The Czech Digital Matematics Library. 37-58.
  • Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20(3), 309–318.
  • Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568–581. https://doi.org/10.1287/opre.12.4.568
  • Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6), 791-812.
  • Eilon, S., Watson-Gandy, C. D. T., & Heilbron, A. (1971). A vehicle fleet costs more. International Journal of Physical Distribution, 1(3), 126–132. https://doi.org/10.1108/eb038836
  • Feremans, C., Labbé, M., & Laporte, G. (2003). Generalized network design problems. European Journal of Operational Research, 148(1), 1–13. https://doi.org/10.1016/S0377-2217(02)00404-6
  • Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2), 340–349.
  • Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13(5), 533–549. https://doi.org/10.1016/0305- 0548(86)90048-1
  • Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). Formal basis for the heuristic determination Eijj. Systems Science and Cybern􀄞tic􀆐, 4(2), 100–107.
  • Holland, J. H. (1962). Outline for a logical theory of adaptive systems. Journal of the ACM (JACM), 9(3), 297–314. https://doi.org/10.1145/321127.321128
  • Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. https://doi.org/10.1007/978-3-642-24974-7_7
  • Kruskal, J. B., Jr. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. American Mathematical Society, 7(1), 48–50.
  • Lin, S., & Kernighan, B. W. (1973). An e􀄫ective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498–516. https://doi.org/10.1007/s10489-006- 8514-7
  • Open Routing Service. (n.d.). https://openrouteservice.org/
  • Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1389–1401. https://doi.org/10.1002/j.1538- 7305.1957.tb01515.x
There are 17 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Zehra Hafızoğlu Gökdağ 0000-0002-5804-3105

Salih Cebeci 0000-0003-2200-6318

Publication Date June 22, 2023
Published in Issue Year 2023 Volume: 16 Issue: 1

Cite

APA Hafızoğlu Gökdağ, Z., & Cebeci, S. (2023). AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM. Beykent Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi, 16(1), 33-42. https://doi.org/10.20854/bujse.1218139
AMA Hafızoğlu Gökdağ Z, Cebeci S. AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM. BUJSE. June 2023;16(1):33-42. doi:10.20854/bujse.1218139
Chicago Hafızoğlu Gökdağ, Zehra, and Salih Cebeci. “AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM”. Beykent Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi 16, no. 1 (June 2023): 33-42. https://doi.org/10.20854/bujse.1218139.
EndNote Hafızoğlu Gökdağ Z, Cebeci S (June 1, 2023) AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM. Beykent Üniversitesi Fen ve Mühendislik Bilimleri Dergisi 16 1 33–42.
IEEE Z. Hafızoğlu Gökdağ and S. Cebeci, “AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM”, BUJSE, vol. 16, no. 1, pp. 33–42, 2023, doi: 10.20854/bujse.1218139.
ISNAD Hafızoğlu Gökdağ, Zehra - Cebeci, Salih. “AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM”. Beykent Üniversitesi Fen ve Mühendislik Bilimleri Dergisi 16/1 (June 2023), 33-42. https://doi.org/10.20854/bujse.1218139.
JAMA Hafızoğlu Gökdağ Z, Cebeci S. AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM. BUJSE. 2023;16:33–42.
MLA Hafızoğlu Gökdağ, Zehra and Salih Cebeci. “AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM”. Beykent Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi, vol. 16, no. 1, 2023, pp. 33-42, doi:10.20854/bujse.1218139.
Vancouver Hafızoğlu Gökdağ Z, Cebeci S. AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM. BUJSE. 2023;16(1):33-42.