Транспорт логистикаси” кафедраси

2. Маршрутлаштиришни транспорт масаласига келтириб ечиш

Йирик партияли юк ташишни маршрутлаштиришда бир-биридан фарқли икки йўналиш мавжуд. Биринчи йўналишда маршрутлаштириш транспорт масаласига келтириб ечилади, иккинчи сида эса у чизиқли программалаштиришнинг умумий масаласига келтирилади.

Биринчи йўналиш усулларини кўриб чиқамиз. Чизиқли программалаштиришнинг транспорт масаласи бирмунча содда ечиш усуликасига эга бўлиб, маршрутлаштириш масаласи илк бор илмий таҳлил этилган пайтлардаёқ шу масалага келтириб ечилган эди.
Маршрутлаштириш масаласини бир неча ҳолда қуйиш мумкин:
- автотранспорт корхоналарининг (АТК) жойлашишини ҳисобга олмасдан берилган райондаги юк ташишни маршрутлаштириш, кейин эса топилган маршрутларни корхоналарга биркитиш (ягона АТК учун маршрутлар тузганда масалани бу кўринишда қўйиш мумкин);
- маршрутларни корхоналарнинг жойланишини ҳисобга олиб тузиш.
Биринчи кўринишда қўйилган маршрутлаштириш масаласини кўриб чиқайлик.


Масалани математик модели

Энг оддий кўринишда қўйилган маршрутлаштириш масаласини кўриб чиқайлик.

Айтайлик юк жўнатувчи ва қабул қилувчи манзиллар рақамлари тўплами бўлсин. Манзиллардан юк жўнатиш ҳажмлари ва манзилларга юк қабул қилиш ҳажмлари берилган. Юк туширувчи ва ортувчи пунктлар орасидаги масофалар матрицаси берилган бўлсин, соддалик учун деб қабул қиламиз. Пунктлараро (манзиллараро) юк ташиш режаи берилган, бунда ташилиши лозим бўлган тонналар ёки бажарилиши керак бўлган қатновлар сонлар кўринишида ҳам берилиши мумкин.
Маршрутлаштириш – бу пунктлараро ҳаракатланишнинг шундай схемаларини топиш демакки, юксиз юрилган йўл узунлиги энг кам бўлсин ва берилган юк ташиш режаи бажарилсин. Бизга юк билан юриш режаи берилган. Демак шундай юксиз юриш режаини топиш керакки, бунда режаи бажарилиб юксиз ўтилган йўллар йиғиндиси энг кам бўлсин,
бу ерда - тушириш ортиш пунктлари орасидаги юксиз юриш режаи;
- эса ва пунктлари орасида бажариладиган юксиз автотонналар ёки қатновлар сони.
Юксиз юришнинг оптимал режаи _опт қуйидаги шартларга жавоб бериши керак:
пунктга келадиган юксиз қатновлар ёки автотонналар шу пунктдан ҳамма пунктларига кетадиган қатновлар ёки автотонналар сонига тенг бўлади:
,
бу ерда
пунктидан чиқадиган юксиз қатнов ёки автотонналар шу пунктга ҳамма пунктларидан келадиган юкли қатнов ёки автотонналар сонига тенг бўлади:
,
бу ерда
юксиз юришдаги қатновлар ёки автотонналар сони манфий бўла олмайди
,
юксиз юриладиган умумий йўл узунлиги энг қисқа бўлиши керак
,
бунда юксиз ақтновлар сони;
ёки юксиз юришда юқотилаётган тонна кмдаги транспорт иши ҳажмини ўртача бир тонна 1 т юк кўтарувчанликка тўғри келадиган миқдори

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

ва юкли ва юксиз қатновлар сони ёки бу қатновларда ташиладиган тонналар сони ҳам ўзаро тенгдир:

Юқорида баён этилган кўринишда юксиз юриш оптимал режаини аниқлаш математик жиҳатдан чизикли программалаштиришнинг транспорт масаласини ўзгинасидир, ифодалар эса транспорт масаласининг математик моделидир. Бунда тенгликлар чеклаш тенгламалари, оптималлик критерияси ёки самарадорлик функцияси дейилади. Шундай қилиб, юксиз юришнинг оптимал режаини топиш транспорт масаласини оптимал ечишга олиб келинади. Юқорида модели берилган транспорт масаласини ечиш усуликасини соддалаштирилган мисолда кўриб чиқамиз.
Айтайлик автотранспорт корхонаси жадвалида берилган юк ташиш талабномасини бажариши керак бўлсин.
жадвал
Юк ташиш талабномаси

Юк жўнатувчи	Юк қабул қилувчи	Юкнинг номи	Ташиш ҳажми, т
Товар станцияси (А1)	Савдо базаси (В1) Тўқимачилик фабрикаси (В2)	контейнер пахта толаси	1300 400
Кишлоқ хўжалиги машиналар заводи (А2)	Товар станцияси (В3)	қишлоқ хўжалиги машиналари	600
Мой – ёғ комбинати (А3)	Мол боқиш базаси (В4)	кунжара	550
Ёғоч қайта ишлайдиган завод (А4)	Ёғоч склади (В5) Мебель фабрикаси (В6)	Кесилган тахта, фанер	700 500
Кабель заводи (А5)	Товар станцияси (В7)	Изоляц. сим.	300

Юқорида кўрсатилган юк ташиш режасини бажариш учун оптимал маршрутлар системасини тузиш керак. Ҳамма юклар 5т юк кўтарувчанликка эга бўлган юк автомобилида ташилади ( т).

Пунктлараро масофалар таблица жадвал катакларининг юқори ўнг бурчагида берилган. Берилган мисол учун юксиз юриш оптимал режаини топиш масаласининг математик модели қуйидагича бўлади:
ҳар бир ортиш пунктига юбориладиган юксиз қатновлардаги тонналар йиғиндиси шу манзилдан ташиладиган юк миқдорига тенг бўлиши керак, яъни:

ҳар бир юк қабул қилиш пунктидан чиқадиган юксиз қатновлардаги тонналар сони шу пунктга ташиладиган юк миқдорига тенг бўлади:



ҳамма юксиз қатновлардаги автотонналар манфий бўлмаслиги


... ,

ҳамда юксиз юриладиган барча йўллар йиғиндиси энг қисқа бўлиши лозим

Транспорт масаласининг хусусияти шундан иборатки, уни матрица шаклидаги маълум таблица формасида ҳам ёзиш мумкин. Масаланинг ўзгарувчилари ва уларнинг коэффициентлари с_ji шу таблицанинг - қатори ва – устуни кесишишидан ҳосил бўлган катакларда ёзилади, - катталиклар қийматлари охирги устунда, - эса охирги қаторда келтирилади.

Транспортмасаласини ечиш икки босқичдан иборат бўлади:

3. 
   бошланғич базис режани тузиш;
   
4. 
   бошланғич режани оптималлаштириш.
   

Бошланғич базис режаи сифатида чеклаш тенгламаларини қаноатлантирадиган ва ўзгарувчилари манфий бўлмаган ҳар қандай режани қабул қилиш мумкин. Аммо базис режаси қанчалик яхши тузилган бўлса ундан оптимал режагача бўлган итерациялар (режани ўзгартириш – яхшилаш цикллари) сони шунча кам бўлади. Шунинг учун оптималга яқин бошланғич режа тузиш мақсадга мувофиқдир. Ҳозирги пайтда бошланғич базис режа тузишнинг бир қанча усуллари ишлаб чиқилган:
1) минимал элемент усули;
2) иккиёқлама афзал кўриш усули;
3) шимолий – ғарб бурчак усули;
4) фогель апроксимацияси усули ва ҳоказо.

Минимал элементлар усули билан бошланғич базис тузиш ва уни оптималликка текшириш.

Юк олувчи пунктлар,	Коэффициентлар	Юк жўнатувчи пунктлар										Бор бўлган юксиз автотонналар,
		А1		А2		А3		А4		А5
		0		-65		27		5		12
В1	20	20 150 N 8 (100)		60 +25		67		15 1150 N7 (1200)		42		1300
В2	-64	30		1 400 N2		57		75		77		400
В3	0	0 600 N1		30 +35		27		46		41		600
В4	22	57 ( 50) N10		87 200 N11		30		17 50		10 300 N6		550
В5	37	37 150 N9		57 +65		10 +550		57		30		700
В6	10	10 500 N4		40 +35		37		35		57		500
В7	1	1 300 N3		30 +36		27		45		47		300
Кераксиз бўлган автотонналар,			1700		600		550		1200		300		4350