<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">vguit</journal-id><journal-title-group><journal-title xml:lang="ru">Вестник Воронежского государственного университета инженерных технологий</journal-title><trans-title-group xml:lang="en"><trans-title>Proceedings of the Voronezh State University of Engineering Technologies</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">2226-910X</issn><issn pub-type="epub">2310-1202</issn><publisher><publisher-name>VSUET</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.20914/2310-1202-2021-1-466-472</article-id><article-id custom-type="elpub" pub-id-type="custom">vguit-2671</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Экономика и управление</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>Economics and Management</subject></subj-group></article-categories><title-group><article-title>Методы оптимизации развозки грузов потребителям несколькими транспортными средствами</article-title><trans-title-group xml:lang="en"><trans-title>Methods for optimizing the delivery of goods to consumers by several vehicles</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0002-1043-7682</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Бугаев</surname><given-names>Ю. В.</given-names></name><name name-style="western" xml:lang="en"><surname>Bugaev</surname><given-names>Y. V.</given-names></name></name-alternatives><bio xml:lang="ru"><p>д.ф.-м.н., профессор, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия</p></bio><bio xml:lang="en"><p>Dr. Sci. (Phys.-Math.), professor, higher mathematics and information technologies department, Revolution Av., 19 Voronezh, 394036, Russia</p></bio><email xlink:type="simple">y_bugaev52@mail.ru</email><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0003-1349-732X</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Коробова</surname><given-names>Л. А.</given-names></name><name name-style="western" xml:lang="en"><surname>Korobova</surname><given-names>L. A.</given-names></name></name-alternatives><bio xml:lang="ru"><p>к.т.н., доцент, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия</p></bio><bio xml:lang="en"><p>Cand. Sci. (Engin.), associate professor, higher mathematics and information technologies department, Revolution Av., 19 Voronezh, 394036, Russia</p></bio><email xlink:type="simple">lyudmila_korobova@mail.ru</email><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Гудков</surname><given-names>С. В.</given-names></name><name name-style="western" xml:lang="en"><surname>Gudkov</surname><given-names>S. V.</given-names></name></name-alternatives><bio xml:lang="ru"><p>магистрант, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия</p></bio><bio xml:lang="en"><p>master student, higher mathematics and information technologies department, Revolution Av., 19 Voronezh, 394036, Russia</p></bio><email xlink:type="simple">gudkov3@yandex.ru</email><xref ref-type="aff" rid="aff-1"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Воронежский государственный университет инженерных технологий</institution><country>Россия</country></aff><aff xml:lang="en"><institution>Voronezh State University of Engineering Technologies</institution><country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2021</year></pub-date><pub-date pub-type="epub"><day>19</day><month>04</month><year>2021</year></pub-date><volume>83</volume><issue>1</issue><fpage>466</fpage><lpage>472</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Бугаев Ю.В., Коробова Л.А., Гудков С.В., 2021</copyright-statement><copyright-year>2021</copyright-year><copyright-holder xml:lang="ru">Бугаев Ю.В., Коробова Л.А., Гудков С.В.</copyright-holder><copyright-holder xml:lang="en">Bugaev Y.V., Korobova L.A., Gudkov S.V.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://www.vestnik-vsuet.ru/vguit/article/view/2671">https://www.vestnik-vsuet.ru/vguit/article/view/2671</self-uri><abstract><p>Грузовой транспорт является одной из наиболее важных отраслей народного хозяйства. Увеличение эффективности работы логистической компании обеспечивается точной организации поставок, а также своевременной доставкой груза в пункты маршрута. Именно поэтому возникает потребность в оптимизации развозки грузов. Задача развозки – это транспортная задача по доставке негабаритных грузов из распределительного центра множеству получателей, расположенных в районе действия транспортной компании. Она является обобщением известной задачи коммивояжера, от которой отличается условием ограниченности грузоподъемности применяемого транспортного средства и, как следствие, необходимостью неоднократного возвращения на базу для пополнения перевозимого груза. В данной статье предлагается дополнить традиционную формулировку задачи требованием распределить клиентов по нескольким одновременно работающим транспортным средствам (ТС), чтобы максимальное время выполнения заказа было минимально. Тем самым учитываются не только интересы исполнителя развозки, но и клиентов. Решение задачи состоит из двух этапов. На первом каким-либо известным способом определяются рациональные кольцевые маршруты для каждого ТС, минимизирующие общий пробег. По результатам этапа рассчитывается время прохождения каждого маршрута. На втором этапе решается задача сокращения максимальное время прохождения маршрутов за счет использования нескольких ТС, производящих развозку в одно время. Для этого необходимо оптимально распределить ТС по индивидуальным маршрутам. Предлагается для решения этой задачи воспользоваться алгоритмом решения известной задачи «Упаковка предметов в контейнеры». Данная задача относится к классу NPтрудных задач в сильном смысле и не имеет точного алгоритма решения для произвольных исходных данных. В данной работе предлагается комплексный метод решения, сочетающий известный алгоритм «First fitted (FF)» – «первый подходящий», оригинальный алгоритм «First fitted with reordering (FFR)» – «первый подходящий с переупорядочением», а также нижние оценки С. Мартелло и П. Тота для контроля оптимальности полученного решения. Тестовые расчеты показали эффективность данного подхода при умеренной размерности задачи.</p></abstract><trans-abstract xml:lang="en"><p>Freight transport is one of the most important sectors of the national economy. The increase in the efficiency of the logistics company is ensured by the accurate organization of supplies, as well as the timely delivery of goods to the points of the route. That is why there is a need to optimize the delivery of goods. A delivery task is a transport task of delivering oversized cargo from a distribution center to a multitude of recipients located in the area of operation of a transport company. It is a generalization of the well-known traveling salesman problem, from which it differs in the condition of the limited carrying capacity of the vehicle used and, as a consequence, the need to repeatedly return to the base to replenish the transported cargo. This article proposes to supplement the traditional formulation of the problem with the requirement to distribute customers among several simultaneously operating vehicles (TC) so that the maximum lead time is minimal. This takes into account not only the interests of the delivery contractor, but also the customers. The solution to the problem consists of two stages. On the first one, in some known way, rational ring routes for each vehicle are determined, minimizing the total mileage. Based on the results of the stage, the time for passing each route is calculated. At the second stage, the problem of reducing the maximum travel time of routes is solved by using several vehicles delivering at the same time. To do this, it is necessary to optimally distribute vehicles along individual routes. It is proposed to use the algorithm for solving the well-known problem "Packing items into containers" to solve this problem. This problem belongs to the class of NP-hard problems in the strong sense and does not have an exact solution algorithm for arbitrary input data. This paper proposes a complex solution method combining the well-known First fitted (FF) algorithm, the original First fitted with reordering (FFR) algorithm, and S. Martello's lower bounds and P. Thoth to control the optimality of the obtained solution. Test calculations have shown the effectiveness of this approach for a moderate dimension of the problem.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>математические методы</kwd><kwd>экономика</kwd><kwd>задача развозки</kwd><kwd>оптимальный маршрут</kwd><kwd>упаковка в контейнеры</kwd></kwd-group><kwd-group xml:lang="en"><kwd>mathematical methods</kwd><kwd>economics</kwd><kwd>delivery problem</kwd><kwd>optimal route</kwd><kwd>packing in containers</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Zhou L., Baldacci R., Vigo D., Wang X. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution // European Journal of Operational Research. 2018. V. 265. № 2. P. 765–778. doi: 10.1016/j.ejor.2017.08.011</mixed-citation><mixed-citation xml:lang="en">Zhou L., Baldacci R., Vigo D., Wang X. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. European Journal of Operational Research. 2018. vol. 265. no. 2. pp. 765–778. doi: 10.1016/j.ejor.2017.08.011</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Kampf R., Hlatka M., Savin G. Proposal for optimizing specific distribution routes by means of the specific method of operational analysis // Communications-Scientific letters of the University of Zilina. 2017. V. 19. №. 2. P. 133–138.</mixed-citation><mixed-citation xml:lang="en">Kampf R., Hlatka M., Savin G. Proposal for optimizing specific distribution routes by means of the specific method of operational analysis. Communications-Scientific letters of the University of Zilina. 2017. vol. 19. no. 2. pp. 133–138.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Parhusip S.F. Composite Algorithm Based on Clarke-Wright and Local Search for the Traveling Salesman Problem // Proceedings of the 2019 5th International Conference on Industrial and Business Engineering. 2019. P. 87–90.</mixed-citation><mixed-citation xml:lang="en">Parhusip S.F. Composite Algorithm Based on Clarke-Wright and Local Search for the Traveling Salesman Problem. Proceedings of the 2019 5th International Conference on Industrial and Business Engineering. 2019. pp. 87–90.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Иванова А.А., Черноморова Т.С. Об алгоритме решения задачи развозки и его реализации // Бюллетень науки и практики. 2017 № 4. С. 107–114</mixed-citation><mixed-citation xml:lang="en">Ivanova A.A., Chernomorova T.S. On the algorithm for solving the delivery problem and its implementation // Bulletin of Science and Practice. 2017 No. 4. P. 107–114. (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Доценко С.И. Задача распределения расходов при развозке по кольцевому маршруту как кооперативная игра // Информатика. 2017. № 1. С. 12–19.</mixed-citation><mixed-citation xml:lang="en">Dotsenko S.I. The problem of distribution of costs during transportation along a circular route as a cooperative game. Informatics. 2017. no. 1. pp. 12–19. (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Просов С.Н., Кузьменко Е.А. Декомпозиция задачи маршрутизации по эвристикам метода Кларка-Райта. // Мир транспорта. 2018. 16(3). С. 190–199.</mixed-citation><mixed-citation xml:lang="en">Prosov S.N., Kuzmenko E.A. Decomposition of the routing problem according to the heuristics of the Clark-Wright method. World of transport. 2018. vol. 16. no. 3. pp. 190–199. (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Бугаев Ю.В., Коробова Л.А., Зеленова Е.Е. Планирование грузовых перевозок модифицированным методом Кларка–Райта // В сборнике: Виртуальное моделирование, прототипирование и промышленный дизайн. Материалы III Международной научно-практической конференции. 2016. С. 179–182.</mixed-citation><mixed-citation xml:lang="en">Bugaev Yu.V., Korobova L.A., Zelenova E.E. Freight traffic planning by the modified Clark-Wright method. In the collection: Virtual modeling, prototyping and industrial design. Materials of the III International Scientific and Practical Conference: Electronic resource. General edition: V.A. Nemtinov. 2016. pp. 179–182. (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Бугаев Ю.В., Коробова Л.А., Гудков С.В. Решение задачи развозки негабаритных грузов несколькими транспортными средствами // Математические методы в технике и технологиях: сб. тр. междунар. науч. конф. СПб.: Изд-во Политехн. ун-та, 2021. С. 55–60.</mixed-citation><mixed-citation xml:lang="en">Bugaev Yu.V., Korobova L.A., Gudkov S.V. Solution of the problem of delivery of oversized cargo by several vehicles. Mathematical methods in engineering and technology: collection of articles. tr. international scientific. SPb, Publishing house of Polytechnic. University, 2021. pp. 55–60. (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Коновалова Т.В., Супрун О.С. К вопросу выбора критерия оптимизации маршрута при доставке грузов автомобильным транспортом // Электронный сетевой политематический журнал" Научные труды КубГТУ". 2017. №. 11. С. 143–150.</mixed-citation><mixed-citation xml:lang="en">Konovalova T.V., Suprun O.S. To the question of choosing a route optimization criterion for the delivery of goods by road. Electronic network polythematic journal "Scientific works of KubSTU". 2017. no. 11. pp. 143–150. (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Подшивалова К.С., Подшивалов С.Ф. Исследование метода ветвей и границ при решении задачи развозки грузов по кольцевому маршруту // Проблемы качества и эксплуатации автотранспортных средств. 2017. С. 276–281.</mixed-citation><mixed-citation xml:lang="en">Podshivalova K.S., Podshivalov S.F. Research of the branch and bound method in solving the problem of delivering goods along a circular route. Problems of quality and operation of vehicles. 2017. pp. 276–281. (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Christensen H.I. et al. Approximation and online algorithms for multidimensional bin packing: A survey // Computer Science Review. 2017. V. 24. P. 63–79. doi: 10.1016/j.cosrev.2016.12.001</mixed-citation><mixed-citation xml:lang="en">Christensen H.I. et al. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review. 2017. vol. 24. pp. 63–79. doi: 10.1016/j.cosrev.2016.12.001</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Delorme M., Iori M., Martello S. Bin packing and cutting stock problems: Mathematical models and exact algorithms // European Journal of Operational Research. 2016. V. 255. №. 1. P. 1–20. doi: 10.1016/j.ejor.2016.04.030</mixed-citation><mixed-citation xml:lang="en">Delorme M., Iori M., Martello S. Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research. 2016. vol. 255. no. 1. pp. 1–20. doi: 10.1016/j.ejor.2016.04.030</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Boyar J., Larsen K.S., Kamali S., L?pez-Ortiz A. Online bin packing with advice // Algorithmica. 2016. V. № 1. P. 507–527. doi: 10.1007/s00453-014-9955-8</mixed-citation><mixed-citation xml:lang="en">Boyar J., Larsen K.S., Kamali S., L?pez-Ortiz A. Online bin packing with advice. Algorithmica. 2016. no. 1. pp. 507–527. doi: 10.1007/s00453-014-9955-8</mixed-citation></citation-alternatives></ref><ref id="cit14"><label>14</label><citation-alternatives><mixed-citation xml:lang="ru">D?sa G., Epstein L. The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints // Journal of Computer and System Sciences. 2018. V. 96. P. 33–49. doi: 10.1016/j.jcss.2018.03.004</mixed-citation><mixed-citation xml:lang="en">D?sa G., Epstein L. The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints. Journal of Computer and System Sciences. 2018. vol. 96. pp. 33–49. doi: 10.1016/j.jcss.2018.03.004</mixed-citation></citation-alternatives></ref><ref id="cit15"><label>15</label><citation-alternatives><mixed-citation xml:lang="ru">Asta S., ?zcan E., Parkes A.J. CHAMP: Creating heuristics via many parameters for online bin packing // Expert Systems with Applications. 2016. V. 63. P. 208–221. doi: 10.1016/j.eswa.2016.07.005</mixed-citation><mixed-citation xml:lang="en">Asta S., ?zcan E., Parkes A.J. CHAMP: Creating heuristics via many parameters for online bin packing. Expert Systems with Applications. 2016. vol. 63. pp. 208–221. doi: 10.1016/j.eswa.2016.07.005</mixed-citation></citation-alternatives></ref><ref id="cit16"><label>16</label><citation-alternatives><mixed-citation xml:lang="ru">Чепикова А.В., Коробова Л.А., Бугаев Ю.В. Задача трехмерной упаковки элементов // Аллея науки. 2018. Т. 1. № 9 (25). С. 433–436. URL: https://www.elibrary.ru/download/elibrary_36430946_56294686.pdf</mixed-citation><mixed-citation xml:lang="en">Chepikova A.V., Korobova L.A., Bugaev Yu.V. The problem of three-dimensional packing of elements. Alley of Science. 2018. vol. 1. no. 9 (25). pp. 433–436. Available at: https://www.elibrary.ru/download/elibrary_36430946_56294686.pdf (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit17"><label>17</label><citation-alternatives><mixed-citation xml:lang="ru">Фуремс Е.М. Обратная задача об упаковке в контейнеры при наличии качественных критериев – постановка и обзор применяемых методов // Искусственный интеллект и принятие решений. 2016. № 3. С. 31–43.</mixed-citation><mixed-citation xml:lang="en">Furems E.M. Inverse problem of packing into containers in the presence of qualitative criteria – formulation and review of applied methods. Artificial Intelligence and Decision Making. 2016. no. 3. pp. 31–43. (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit18"><label>18</label><citation-alternatives><mixed-citation xml:lang="ru">Орлов Б.Ю. Построение алгоритма последовательности перестановок в исследованиях и работе оборудования маслодобывающих предприятий // Научные исследования и современное образование. 2017. С. 183–185.</mixed-citation><mixed-citation xml:lang="en">Orlov B.Yu. Construction of an algorithm for the sequence of permutations in the research and operation of equipment of oil-extracting enterprises. Scientific research and modern education. 2017. pp. 183–185. (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit19"><label>19</label><citation-alternatives><mixed-citation xml:lang="ru">Шабля Ю.В., Кручинин Д.В., Репкин А.С. Сравнение подходов к разработке алгоритмов комбинаторной генерации на примере множеств перестановок и сочетаний // Прикладная математика и информатика: современные исследования в области естественных и технических наук. 2019. С. 75–80.</mixed-citation><mixed-citation xml:lang="en">Shablya Yu.V., Kruchinin D.V., Repkin A.S. Comparison of approaches to the development of algorithms for combinatorial generation on the example of sets of permutations and combinations. Applied mathematics and informatics: modern research in the field of natural and technical sciences. 2019. pp. 75–80. (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit20"><label>20</label><citation-alternatives><mixed-citation xml:lang="ru">Титенко Е.А., Крипачев А.В., Марухленко А.Л. Коммутационная схема параллельных парных перестановок для специализированного продукционного устройства // Известия Южного федерального университета. Технические науки. 2018. №. 8 (202).</mixed-citation><mixed-citation xml:lang="en">Titenko E.A., Kripachev A.V., Marukhlenko A.L. Switching scheme of parallel paired permutations for a specialized production device. Bulletin of the Southern Federal University. Technical science. 2018. no. 8 (202). (in Russian).</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
