Çok Bölmeli Araç Rotalama Problemi için Bir Melez Genetik Algoritma

Bu çalışmada, Çok Bölmeli Araç Rotalama Problemi (ÇB-ARP) ele alınmıştır. Günlük hayatta marketler, firmalar ve kurumlar bazı ürünleri müşterilerine teslim ederken ya da belirli noktalardan toplarken, bu ürünleri araç içinde farklı bölmelere koymaları gerekmektedir. Bazı ürünlerin oda sıcaklığında, bazılarının soğuk olarak taşınması gerekmektedir. Bazı atıkların, kimyasal ürünlerin ya da yakıtların diğer ürünlerle karıştırılmadan taşınması gerekmektedir. Bu yüzden dağıtım ya da toplama yapan araç filosundaki her bir aracın birden fazla bölmeye sahip olması ve dağıtılan ya da toplanan ürünlerin ilgili bölmelerde taşınması gerekmektedir. Bu makalede çalışılan ÇB-ARP, bir, iki ve üç bölmeli araç senaryoları dahilinde ayrı ayrı ele alınmıştır. Çözüm yöntemi olarak melez bir Genetik Algoritma (GA) kullanılmış ve bu algoritma Araç Rotalama Problemi (ARP) literatüründe sıklıkla kullanılan bir problem örnek seti üzerinde uygulanmıştır. Sonuç olarak bu çalışmadaki ÇB-ARP modeli için yeni referans sonuçları üretilmiş ve sonuçlar yorumlanmıştır.

Anahtar Kelimeler:

Çok Bölmeli Araç Rotalama Problemi, Melez Genetik Algoritma, Sezgisel Arama

A Hybrid Genetic Algorithm for Multi-Compartment Vehicle Routing Problem

In this study, a Multi-Compartment Vehicle Routing Problem (MC-VRP) was studied. In daily life, markets, companies and organizations need to load their certain products into different compartments in vehicles during the delivery or collecting of these products. Some of the products need to be carried in cold temperature while others in ambient temperature. Some wastes, chemical products or fuel types need to be transported in the same vehicle separately. Therefore, the transportation fleet must have vehicles with separate compartments and the different products must be either delivered or collected in related compartments of these vehicles. The MC-VRP studied in this paper was taken into consideration with three scenarios of vehicles with one-, two-, or three-compartments. As the solution method, a hybrid Genetic Algorithm (GA) was used and applied on a well-known problem instance set in Vehicle Routing Problem (VRP) literature. As a result, new benchmark results were obtained for the version of MC-VRP in this study and these results were evaluated.

Keywords:

Multi-Compartment Vehicle Routing Problem, Hybrid Genetic Algorithm, Heuristic Search,

PDF

___

N. Christofides, A. Mingozzi, and P. Toth, “The Vehicle Routing Problem,” Rev. française d’automatique, informatique, Rech. opérationnelle. Rech. opérationnelle, vol. 10, 1979, doi: 10.1051/ro/197610V100551.
A. El Fallahi, C. Prins, and R. Wolfler Calvo, “A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem,” Comput. Oper. Res., vol. 35, no. 5, pp. 1725–1741, 2008, doi: 10.1016/j.cor.2006.10.006.
N. Christofides and S. Eilon, “An Algorithm for the Vehicle-Dispatching Problem,” OR, vol. 20, no. 3, p. 309, 1969, doi: 10.2307/3008733.
J. E. Mendoza, B. Castanier, C. Guéret, A. L. Medaglia, and N. Velasco, “A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands,” Comput. Oper. Res., vol. 37, no. 11, pp. 1886–1898, 2010, doi: 10.1016/j.cor.2009.06.015.
M. Reed, A. Yiannakou, and R. Evering, “An ant colony algorithm for the multi-compartment vehicle routing problem,” Appl. Soft Comput. J., vol. 15, pp. 169–176, 2014, doi: 10.1016/j.asoc.2013.10.017.
J. C. Goodson, “A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands,” Eur. J. Oper. Res., vol. 241, no. 2, pp. 361–369, 2015, doi: 10.1016/j.ejor.2014.09.031.
M. M. S. Abdulkader, Y. Gajpal, and T. Y. Elmekkawy, “Hybridized ant colony algorithm for the Multi Compartment Vehicle Routing Problem,” Appl. Soft Comput. J., vol. 37, pp. 196–203, 2015, doi: 10.1016/j.asoc.2015.08.020.
T. Henke, M. G. Speranza, and G. Wäscher, “The multi-compartment vehicle routing problem with flexible compartment sizes,” Eur. J. Oper. Res., vol. 246, no. 3, pp. 730–743, 2015, doi: 10.1016/j.ejor.2015.05.020.
A. Hübner and M. Ostermeier, “A multi-compartment vehicle routing problem with loading and unloading costs,” Transp. Sci., vol. 53, no. 1, pp. 282–300, 2019, doi: 10.1287/trsc.2017.0775.
L. Chen, Y. Liu, and A. Langevin, “A multi-compartment vehicle routing problem in cold-chain distribution,” Comput. Oper. Res., vol. 111, pp. 58–66, 2019, doi: 10.1016/j.cor.2019.06.001.
J. Chen and J. Shi, “A multi-compartment vehicle routing problem with time windows for urban distribution – A comparison study on particle swarm optimization algorithms,” Comput. Ind. Eng., 2019, doi: 10.1016/j.cie.2019.05.008.
M. M. Solomon, “Algorithms for the Vehicle Routing And Scheduling Problems with Time Window Constraints,” Oper. Res., vol. 35, no. 2, pp. 254–265, 1987, doi: 10.1287/opre.35.2.254.
I. Kaabachi, H. Yahyaoui, S. Krichen, and A. Dekdouk, “Measuring and evaluating hybrid metaheuristics for solving the multi-compartment vehicle routing problem,” Meas. J. Int. Meas. Confed., 2019, doi: 10.1016/j.measurement.2019.04.019.
L. Wang, J. Kinable, and T. van Woensel, “The fuel replenishment problem: A split-delivery multi-compartment vehicle routing problem with multiple trips,” Comput. Oper. Res., vol. 118, 2020, doi: 10.1016/j.cor.2020.104904.
R. Eshtehadi, E. Demir, and Y. Huang, “Solving the vehicle routing problem with multi-compartment vehicles for city logistics,” Comput. Oper. Res., vol. 115, 2020, doi: 10.1016/j.cor.2019.104859.
G. Clarke and J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Oper. Res., vol. 12, no. 4, pp. 568–581, 1964, doi: 10.1287/opre.12.4.568.
C. Prins, N. Labadi, and M. Reghioui, “Tour splitting algorithms for vehicle routing problems,” Int. J. Prod. Res., vol. 47, no. 2, pp. 507–535, 2009, doi: 10.1080/00207540802426599.
B. E. Gillett and L. R. Miller, “A Heuristic Algorithm for the Vehicle-Dispatch Problem,” Oper. Res., 1974, doi: 10.1287/opre.22.2.340.
G. A. Croes, “A Method for Solving Traveling-Salesman Problems,” Oper. Res., vol. 6, no. 6, pp. 791–812, 1958, doi: 10.1287/opre.6.6.791.
D. E. Goldberg and R. J. Lingle, “Alleles, Loci and the Traveling Salesman Problem,” in Proceedings of the 1st International Conference on Genetic Algorithms, 1985, pp. 154–159, [Online]. Available: http://dl.acm.org/citation.cfm?id=645511.657095.