AN EXACT SOLUTION FOR REAL-LIFE TRANSSHIPMENT PATH PROBLEM

Year 2023, Volume: 16 Issue: 1, 33 - 42, 22.06.2023

Zehra Hafızoğlu Gökdağ , Salih Cebeci

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.

Keywords

graph theory, logistics, network design problem, combinatory problem

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

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.

Keywords

grafik teorisi, lojistik, ağ tasarımı problemi, kombinasyon problemi

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