Розробка генетичного методу для вирішення задач маршрутизації з декількома транспортами та ваговими рамками
DOI:
https://doi.org/10.35681/1560-9189.2023.25.2.300589Ключові слова:
метаевристичні алгоритми, генетичний алгоритм, оптимізація, жадібний алгоритм, транспортна задачаАнотація
Розроблено модифікований генетичний метод для розв’язання задач маршрутизації з ваговими обмеженнями та кількома транспортними засобами. Основна відмінність цього методу полягає у використанні диплоїдного набору хромосом у популяції, яка еволюціонує. Ця модифікація робить залежність фенотипу від генотипу менш детермінованою і сприяє збереженню різноманітності генофонду та варіабельнос-ті ознак фенотипу. Результатом є підтримання високої варіабельнос-ті ознак у популяції під час еволюції, при цьому маючи невеликий вплив на фенотип особин. Також було запропоновано модифікацію генетичного оператора мутацій. Особини, які піддаються мутації, обираю-ться відповідно до їхньої мутаційної стійкості, тобто «слабкіші» особини мутують, а «сильніші» залишаються без змін. Це зменшує вірогід-ність втрати досягнутого екстремуму функції під час мутації і сприяє переходу до нового екстремуму при накопиченні «кращих» ознак у популяції. Така модифікація оператора дозволяє здійснювати пошук значень, наближених до оптимальних, без втрати досягнутих під час пошуку найкращих рішень.
Посилання
Skjoett Larsen T. European logistics beyond 2000. International Journal of Physical Distribution & Logistics Management. 2000. Vol. 30, No. 5. Р. 377–387. https://doi.org/10.1108/09600030010336144.
Sumaiya Iqbal, Kaykobad M., Sohel Rahman M. Solving the Multi-Object Vehicle Routing Problem with Soft Time Window with the help of bees. Swarm and Evolutionary Computation, 2015. Vol. 24. P. 50–64.
Li J., Guo H., Zhou Q., Yang B. Vehicle Routing and Scheduling Optimization of Ship Steel Distribution Center under Green Shipbuilding Mode. Sustainability. 2019. 11., 4248.
Kritikos M.N., Ioannou G. The balanced cargo vehicle routing problem with time windows. International Journal of Production Economics. 2010. 123(1). Р. 42–51.
Tania Rodrigues Pereira Ramos, Maria Isabel Gomes & Ana Paula Barbosa Povoa Multi-depot vehicle routing problem: a comparative study of alternative formulations. International Journal of Lo-gistics Research and Applications. 2020. 23:2, 103–120. DOI: 10.1080/13675567.2019.1630374. Vol. 1, P. 20–21.
Paul A., Kumar R.S., Rout C. et al. Designing a multi-depot multi-period vehicle routing problem with time window: hybridization of tabu search and variable neighbourhood search algorithm. Sadhana. 2021. 46, 183. https://doi.org/10.1007/s12046-021-01693-2.
Kang, He-Yau, and Amy H. I. Lee. An Enhanced Approach for the Multiple Vehicle Routing Problem with Heterogeneous Vehicles and a Soft Time Window. Symmetry. 2018. 10, No. 11: 650. https://doi.org/10.3390/sym10110650.
Yu-Wei Chen and Vincent F. Yu, Parida Jewpanya†. The Pickup and Delivery Multi-depot Vehicle Routing Problem. A Quarterly Journal of Operations Research, 2016. 14(3). Р. 223–259. 10.1007/s10288-016-0306-2. emse-01250603.13.
Window by Considering the Flexible End Depot in Each Route. International Journal of Supply and Operations Management. November 2016. Vol. 3, Issue 3. Р. 1373-1390. ISSN-Print: 2383-1359. ISSN-Online: 2383-2525.
Dembinski H., Schmelling M., Waldi R. Application of the iterated weighted least-squares fit to counting experiments. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment. 2019. Vol. 940. Р. 135–141. Available: DOI:10.1016/j.nima.2019.05.086
Bruck B.P. and Iori M. Non-elementary formulations for single vehicle routing problems with pickups and deliveries. Oper. Res. 2017. 65. 1597–1614.
Soebiyanto R.P., Kiang R.K., 2000. Modeling Influenza Transmission Using Environmental Parameters. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Science, XXXVIII, 8. Р. 330–334.
Feiyue Li, Bruce Golden, and Edward Wasil. Very large-scale vehicle routing: new test problems, algorithms, and results. Computers & Operations Research. 2005. 32(5):1165–1179.
Cantu-Paz, E., 2016. Solving Travelling Salesman Problem with an Improved Hybrid Genetic Algorithm. Journal of Computer and Communications, 4. ISSN Online: 2327–5227. ISSN Print: 2327–5219.
Haupt R., Haupt l. Practical genetic algorithms. John Wiley & Sons, 2004. 2. 261 p.
Inman James (1835). Navigation and Nautical Astronomy: For the Use of British Seamen (3 ed.). London, UK: W. Woodward, C. & J. Rivington. Retrieved 2015-11-09. Р. 1–9.
Oliinyk A. A Evolutionary method for solving the traveling salesman problem / A. Oliinyk, I. Fedorchenko, A. Stepanenko, M. Rud, D. Goncharenko // Problems of Infocommunications. Science and Technology: 5th International Scientific-Practical Conference PICST2018, Kharkiv, 9–12 October 2018: proceedings of the conference. Kharkiv: Kharkiv National University of Radioelectronics, 2018. P. 331–339. DOI: 10.1109/INFOCOMMST.2018.8632033.
Fedorchenko I., Oliinyk A., Stepanenko A., Zaiko T., Korniienko S., Burtsev N. Development of a genetic algorithm for placing power supply sources in a distributed electric network. Eastern European Journal of Enterprise Technologies. 2019. Issue 5/3 (101). Р. 6–16. DOI: 10.15587/1729-4061.2019. 180897.
Oliinyk A., Fedorchenko I., Stepanenko A., Rud M., Goncharenko D. Combinatorial optimi-zation problems solving based on evolutionary approach. In: 2019 15th International Conference on the Experience of Designing and Application of CAD Systems (CADSM), Р. 41–45 (2019). DOI: 10.1109/CADSM.2019.8779290.
