6-мавзу: майда партияли ташишлпрни маршрутлаштириш масаланинг қўйилиши ва математик модели

6-мавзу: МАЙДА ПАРТИЯЛИ ТАШИШЛПРНИ МАРШРУТЛАШТИРИШ


1. Масаланинг қўйилиши ва математик модели

Майда партияли ташишни маршрутлаштириш - бу юк ва йўловчиларни бир пунктдан бир неча манзилларга кетма-кет рационал тарқатиш ёки йиғиш маршрутларини тузиш демакдир. Математик моҳиятига кўра бу масала бир неча манзилларни ўзаро боғлайдиган схемани аниқлашдан иборат бўлиб, бунда бошлағич ва охирги пунктлар ягона бўлиши ҳамда қолган манзиллардан фақат бир марта ўтилиши лозим. Энг оддий кўринишда бу масала математиканинг классик “коммивояжер масала”сига келтирилади.

Юк жўнатиш пункти -дан олувчи пунктларга юк ташилиши лозим. Ҳар бир олувчига ташиладиган юк миқдори берилган. Юк ташишни бажаришда сондаги автомобиллар иштирок этиши мумкин. Ҳар бир – автомобил учун юк кўтарувчанлик маълум . Автомобилларнинг тартиб номерлари шундай белгиланки, бунда қуйидаги шарт

Ҳар бир -автомобил учун тузилган -маршрут бу маълум манзиллар кетма-кетлигидир, бунда . Ҳар бир -автомобил учун шундай маршрут аниқлаш керакки, бунда манзиллар оладиган юк миқдорларининг йиғиндиси автомобил юк кўтарувчанлигидан ошмаслиги керак, яъни

Бунда барча маршрутлар тўплами учун қуйидаги шартлар бажарилиши лозим:
-бирорта ҳам олувчи манзил иккита маршрутга масалан ( ва ) маршрутларига кирмаслиги, бошқача айтганда ва маршрутларга тегишли бўлган олувчи пунктлар кесишмаси бўм-бўш бўлиши керак, яъни

ҳамма олувчиларга юк олиб берилиши лозим, яъни

тузилган маршрутлар системаси энг кам юриладиган йўл узунлигини таъминлаши керак.

бу ерда
- автомобил маршрутидаги жуфт пунктлар тўплами;
ҳамма маршрутлардаги жуфт пунктлар тўпламидир;
- пунктлараро энг қисқа масофалар матрицасининг элементлари.
Масаланинг қўйилиши ва модели йиғиш маршрути учун ҳам юқоридагидан айтарли фарқ қилмайди.
Шуни айтиш керакки, ҳозирги пайтга қадар майда партияли юк ташишни маршрутлаштиришнинг универсал усуллари ишлаб чиқилмаган. Манзиллар сони айтарли кўп бўлмаган ҳолларда масалани ҳамма вариантларни солиштириб чиқиш воситасида ечиш мумкин. Аммо кўп сонли пунктлар учун бундай тарзда масалани ечиш мумкин бўлмай қолади, чунки бунда солиштирилиб чиқилиши лозим бўлган вариантлар сони n! га тенг бўлади.
Амма вариантларни текширмасдан қисқароқ йўллар билан оптимал маршрутлар системасини топишнинг бир қанча усуллари мавжуд. Бу усуллар оптимал вариантга яқин ечимларни топишга имкон беради.