Preview

Вестник Воронежского государственного университета инженерных технологий

Расширенный поиск

Методы оптимизации развозки грузов потребителям несколькими транспортными средствами

https://doi.org/10.20914/2310-1202-2021-1-466-472

Полный текст:

Аннотация

Грузовой транспорт является одной из наиболее важных отраслей народного хозяйства. Увеличение эффективности работы логистической компании обеспечивается точной организации поставок, а также своевременной доставкой груза в пункты маршрута. Именно поэтому возникает потребность в оптимизации развозки грузов. Задача развозки – это транспортная задача по доставке негабаритных грузов из распределительного центра множеству получателей, расположенных в районе действия транспортной компании. Она является обобщением известной задачи коммивояжера, от которой отличается условием ограниченности грузоподъемности применяемого транспортного средства и, как следствие, необходимостью неоднократного возвращения на базу для пополнения перевозимого груза. В данной статье предлагается дополнить традиционную формулировку задачи требованием распределить клиентов по нескольким одновременно работающим транспортным средствам (ТС), чтобы максимальное время выполнения заказа было минимально. Тем самым учитываются не только интересы исполнителя развозки, но и клиентов. Решение задачи состоит из двух этапов. На первом каким-либо известным способом определяются рациональные кольцевые маршруты для каждого ТС, минимизирующие общий пробег. По результатам этапа рассчитывается время прохождения каждого маршрута. На втором этапе решается задача сокращения максимальное время прохождения маршрутов за счет использования нескольких ТС, производящих развозку в одно время. Для этого необходимо оптимально распределить ТС по индивидуальным маршрутам. Предлагается для решения этой задачи воспользоваться алгоритмом решения известной задачи «Упаковка предметов в контейнеры». Данная задача относится к классу NPтрудных задач в сильном смысле и не имеет точного алгоритма решения для произвольных исходных данных. В данной работе предлагается комплексный метод решения, сочетающий известный алгоритм «First fitted (FF)» – «первый подходящий», оригинальный алгоритм «First fitted with reordering (FFR)» – «первый подходящий с переупорядочением», а также нижние оценки С. Мартелло и П. Тота для контроля оптимальности полученного решения. Тестовые расчеты показали эффективность данного подхода при умеренной размерности задачи.

Об авторах

Ю. В. Бугаев
Воронежский государственный университет инженерных технологий
Россия

д.ф.-м.н., профессор, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия



Л. А. Коробова
Воронежский государственный университет инженерных технологий

к.т.н., доцент, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия



С. В. Гудков
Воронежский государственный университет инженерных технологий

магистрант, кафедра высшей математики и информационных технологий, пр-т Революции, 19, г. Воронеж, 394036, Россия



Список литературы

1. 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

2. 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.

3. 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.

4. Иванова А.А., Черноморова Т.С. Об алгоритме решения задачи развозки и его реализации // Бюллетень науки и практики. 2017 № 4. С. 107–114

5. Доценко С.И. Задача распределения расходов при развозке по кольцевому маршруту как кооперативная игра // Информатика. 2017. № 1. С. 12–19.

6. Просов С.Н., Кузьменко Е.А. Декомпозиция задачи маршрутизации по эвристикам метода Кларка-Райта. // Мир транспорта. 2018. 16(3). С. 190–199.

7. Бугаев Ю.В., Коробова Л.А., Зеленова Е.Е. Планирование грузовых перевозок модифицированным методом Кларка–Райта // В сборнике: Виртуальное моделирование, прототипирование и промышленный дизайн. Материалы III Международной научно-практической конференции. 2016. С. 179–182.

8. Бугаев Ю.В., Коробова Л.А., Гудков С.В. Решение задачи развозки негабаритных грузов несколькими транспортными средствами // Математические методы в технике и технологиях: сб. тр. междунар. науч. конф. СПб.: Изд-во Политехн. ун-та, 2021. С. 55–60.

9. Коновалова Т.В., Супрун О.С. К вопросу выбора критерия оптимизации маршрута при доставке грузов автомобильным транспортом // Электронный сетевой политематический журнал" Научные труды КубГТУ". 2017. №. 11. С. 143–150.

10. Подшивалова К.С., Подшивалов С.Ф. Исследование метода ветвей и границ при решении задачи развозки грузов по кольцевому маршруту // Проблемы качества и эксплуатации автотранспортных средств. 2017. С. 276–281.

11. 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

12. 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

13. 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

14. 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

15. 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

16. Чепикова А.В., Коробова Л.А., Бугаев Ю.В. Задача трехмерной упаковки элементов // Аллея науки. 2018. Т. 1. № 9 (25). С. 433–436. URL: https://www.elibrary.ru/download/elibrary_36430946_56294686.pdf

17. Фуремс Е.М. Обратная задача об упаковке в контейнеры при наличии качественных критериев – постановка и обзор применяемых методов // Искусственный интеллект и принятие решений. 2016. № 3. С. 31–43.

18. Орлов Б.Ю. Построение алгоритма последовательности перестановок в исследованиях и работе оборудования маслодобывающих предприятий // Научные исследования и современное образование. 2017. С. 183–185.

19. Шабля Ю.В., Кручинин Д.В., Репкин А.С. Сравнение подходов к разработке алгоритмов комбинаторной генерации на примере множеств перестановок и сочетаний // Прикладная математика и информатика: современные исследования в области естественных и технических наук. 2019. С. 75–80.

20. Титенко Е.А., Крипачев А.В., Марухленко А.Л. Коммутационная схема параллельных парных перестановок для специализированного продукционного устройства // Известия Южного федерального университета. Технические науки. 2018. №. 8 (202).


Для цитирования:


Бугаев Ю.В., Коробова Л.А., Гудков С.В. Методы оптимизации развозки грузов потребителям несколькими транспортными средствами. Вестник Воронежского государственного университета инженерных технологий. 2021;83(1):466-472. https://doi.org/10.20914/2310-1202-2021-1-466-472

For citation:


Bugaev Yu.V., Korobova L.A., Gudkov S.V. Methods for optimizing the delivery of goods to consumers by several vehicles. Proceedings of the Voronezh State University of Engineering Technologies. 2021;83(1):466-472. (In Russ.) https://doi.org/10.20914/2310-1202-2021-1-466-472

Просмотров: 44


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-910X (Print)
ISSN 2310-1202 (Online)