До класифікації задач маршрутизації транспортних засобів

Суть розглянутих задач полягає у розробцi маршрутiв для групи гетерогенних транспортних засобiв, якi базуються у певному мiсцi чи мiсцях (депо) i мають доставити товари клiєнтам згiдно їх обсягами замовлень. Класична задача маршрутизацiї транспортних засобiв вiдноситься до задач комбiнаторної оптимiзацiї, якi можна подати у виглядi графу, у якого множина вершин вiдображає як депо, так i точки доставки, тобто клiєнтiв, а множина ребер вiдповiдає шляхам. У цiй задачi вважаються заданими: матриця ваг ребер мiж вершинами, що визначаються вартостями/довжинами шляхiв; кiлькiсть транспортних засобiв, задiяних у доставцi товару; обсяги товару, що має постачатися клiєнтам у кожну точку доставки. Актуальнiсть задачi маршрутизацiї транспортних засобiв спричинила появу багаточисельних її дослiджень, якi проводилися протягом останнiх десятилiть, та вiдповiдних публiкацiй. При формуваннi наведеного в статтi перелiку наукових публiкацiй автори не ставили мету подати iсторичний ракурс дослiдження маршрутизацiї транспортних засобiв (вiн досить повно вiдображається в бiльшостi робiт), а надавали перевагу публiкацiям останнiх рокiв, якi дають картину актуальних нинi дослiджень. У бiльшостi реальних задач маршрутизацiї транспортних засобiв присутнi додатковi обмеження, що породжують цiлий спектр нових задач. У роботi наведено низку класiв задач маршрутизацiї транспортних засобiв. Основним обмеженням є вантажопiдйомнiсть, а критерiєм – загальна вартiсть перевезень. У задачах маршрутизацiї з часовими обмеженнями або «часовими вiкнами» мiнiмiзацiя загальної вартостi перевезень поєднується з мiнiмiзацiєю кiлькостi задiяних транспортних засобiв та загального часу очiкування клiєнтами транспортних засобiв. Мiнiмiзацiя вартостi перевезень i розмiру парку залучених транспортних засобiв може вiдбуватися i у випадку, коли цi транспортнi засоби вирушають iз декiлькох депо, причому як старт, так i завершення маршруту може вiдбуватися не у фiксованих, а iз/в альтернативних, зокрема, динамiчних депо. Розглядаються також проблеми маршрутизацiї за можливостi поверненням i доставкою товарiв, маршрутизацiя з двовимiрними обмеженнями завантаження транспортних засобiв, максимiзацiя заощаджень вiд перевезення товару, з рiзними видами транспорту, перiодична маршрутизацiя, з випадковими даними, з можливiстю дозавантаження з дотриманням заданого термiну доставляння. Для кожного типу задач наведено додатковi обмеження, що вiдрiзняють їх вiд класичної задачi.