Google Maps alapú új típusú megközelítés korlátos elosztási rendszer optimalizálására
Kulcsszavak:
mTSP, VRP, genetikus algoritmus, multi-kromoszóma, optimalizációAbsztrakt
A fuvarszervezési probléma (VRP) egy komplex kombinatorikus optimalizálási feladat, ami a következőképpen írható le: adott a járművek egy halmaza, előre meghatározott, közös kapacitással, egy központi depó, és adottak vásárlói igények; a feladat egy minimális összköltségű útvonalhálózat keresése, mely az összes vásárlói igényt kielégíti. A többes utazóügynök probléma (mTSP) a jól ismert utazóügynök probléma (TSP) egy általánosítása, ahol egy vagy több utazóügynök lehet a feladat megoldásában. Ismeretes, hogy a mTSP alapú algoritmusok VRP-k megoldására is használhatóak, további kikötések definiálásával. Több egzakt algoritmus is létezik az irodalomban, melyek néhány megszorítás relaxációját tartalmazzák mTSP-nek. Ezen algoritmusok elméletileg igazolt optimumot szolgáltatnak. Az mTSP probléma kombinatorikus komplexitása miatt szükséges valamilyen heurisztika alkalmazása a megoldásban, különösen valós méretű feladatok esetén. Jelen munka célja annak tárgyalása, hogy hogyan alkalmazhatóak a genetikus algoritmusok ilyen típusú problémák megoldására. Áttekinti a korábbi megközelítéseket azok hátrányaival együtt, és ajánl egy újszerű reprezentáción alapuló megoldást, és több példán keresztül szemlélteti annak hatékonyságát. A cikk kitér a megvalósított szoftver megoldásokra is, bemutat egy új Google Maps API-n alapuló távolságmátrix-generáló programot, és egy kényelmes eszközt az eredmények megjelenítésére. Továbbá ajánl egy teljes keretrendszert és módszert valós elosztási feladatok megoldására. Az újszerű algoritmus, az új eszközök és a kapott útvonalhálózatok gazdaságilag hatékonynak bizonyulnak logisztikai problémák esetén, amelyet a cikk egy valós életből vett példán szemléletet.
Hivatkozások
Ali, A. I., Kennington, J. L. (1986). The asymmetric m-traveling salesmen problem: a duality based branch-and-bound algorithm. Discrete Applied Mathematics, 13. 2–3. 259–276. https://doi.org/10.1016/0166-218X(86)90087-9
Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34. 3. 209–219. https://doi.org/10.1016/j.omega.2004.10.004
Bhide, S., John, N., Kabuka, M. R. (1993). A boolean neural network approach for the traveling salesman problem. IEEE Transactions on Computers, 42. 10. 1271–1278. https://doi.org/10.1109/12.257714
Burns, L. D., Hall, R. W., Blumenfeld, D. E., and Daganzo, C. F. (1985). Distribution strategies that minimize transportation and inventory costs. Operations Research, 33. 3. 469–490. https://doi.org/10.1287/opre.33.3.469
Carter, A. E., Ragsdale, C. T. (2006). A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, 175. 1. 246–257. https://doi.org/10.1016/j.ejor.2005.04.027
Cavill, R., Smith, S., Tyrrell, (2005). A. Multi-chromosomal genetic programming. In Proceedings of the 2005 conference on Genetic and evolutionary computation, ACM New York, NY, USA, 1753–1759. https://doi.org/10.1145/1068009.1068300
Christopher, M. (1999). Logistics and supply chain management: strategies for reducing cost and improving service. International Journal of Logistics Research and Applications, 2. 1. 103–104. https://doi.org/10.1080/13675569908901575
Finke, G. (1986). Network flow based branch and bound method for asymmetric traveling salesman problems. In XI Symposium on Operations Research, Darmstadt, 117–119.
Glover, F. (1990). Artificial intelligence, heuristic frameworks and tabu search. Managerial and Decision Economics, 11. 5. 365–375. https://doi.org/10.1002/mde.4090110512
Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA
Gromicho, J., Paixao, J., Bronco, I. (1992). Exact solution of multiple traveling salesman problems. Combinatorial optimization: new frontiers in theory and practice, 291–292. https://doi.org/10.1007/978-3-642-77489-8_27
Holland, J. H. (1975). Adaptation in natural and artificial systems. The University of Michigan Press
Király A., Abonyi J. (to be published in 2011). Optimization of multiple traveling salesmen problem by a novel representation based genetic algorithm. In M. Koeppen, G. Schaefer, A. Abraham, and L. Nolle, editors, Intelligent Computational Optimization in Engineering: Techniques & Applications, Advances in Intelligent and Soft Computing. Springer. https://doi.org/10.1007/978-3-642-21705-0_9
Laporte, G., Nobert, Y. (1980). A cutting planes algorithm for the msalesmen problem. Journal of the Operational Research Society, 31. 11. 1017–1023. https://doi.org/10.1057/jors.1980.188
Malmborg, C. J. (1996). A genetic algorithm for service level based vehicle scheduling. European Journal of Operational Research, 93. 1. 121–134. https://doi.org/10.1016/0377-2217(95)00185-9
Miliotis, P. (1978). Using cutting planes to solve the symmetric travelling salesman problem. Mathematical Programming, 15. 1. 177–188. https://doi.org/10.1007/BF01609016
Park, Y.-B. (2001). A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines. International Journal of Productions Economics, 73. 2. 175–188. https://doi.org/10.1016/S0925-5273(00)00174-2
Pierrot, H. J., Hinterding, R. (1997). Multi-chromosomal genetic programming, vol. 1342/1997 of Lecture Notes in Computer Science. Springer, Berlin / Heidelberg, ch. Using multi-chromosomes to solve a simple mixed integer problem, 137–146. https://doi.org/10.1007/3-540-63797-4_66
Ronald, S., Kirkby, S. (1998). Compound optimization. solving transport and routing problems with a multi-chromosome genetic algorithm. In The 1998 IEEE International Conference on Evolutionary Computation, ICEC'98, 365–370.
Ross, S. M. (1984). Introduction to Probability Models. Macmillian, New York
Tanga, L., Liu, J., Rongc, A., Yanga, Z. (2000). A multiple traveling salesman problem model for hot rolling scheduling in shangai baoshan iron & steel complex. European Journal of Operational Research, 124. 2. 267–282. https://doi.org/10.1016/S0377-2217(99)00380-X
Toth, P., Vigo, D. (1987) The vehicle routing problem. Society for Industrial Mathematics
Yoshiji, F., Yuki, A., Tsuyoshi, Y. (2001). Applying the genetic algorithm with multi-chromosomes to order problems. Proceedings of the Annual Conference of JSAI, 13. 468–471.
Yu Z, Jinhai L, Guochang G, Rubo Z, and Haiyan Y. (2002). An implementation of evolutionary computation for path planning of cooperative mobile robots. Proceedings of the fourth world congress on intelligent control and automation, 3. 1798–1802.
Zhang, T., Gruver, W., Smith, M. (1999). Team scheduling by genetic search. Proceedings of the second international conference on intelligent processing and manufacturing of materials, 2. 839–844. https://doi.org/10.1109/IPMM.1999.791495
Letöltések
Megjelent
Folyóirat szám
Rovat
License
Copyright (c) 2010 Király András, Abonyi János
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
