В каждый банкомат загружается di 4 кассеты наличности, вместимость каждой инкассаторской машины Q 16. Расстояния между банкоматами и филиалами банка известны.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Ïîñòðîåíèåèíêàññàòîðñêèõìàðøðóòîââñåòèñ
íåñêîëüêèìèôèëèàëàìèáàíêà
ÃóáàðÅ.À,ÏëàòîíîâàÂ.À.
Ñàíêò-ÏåòåðáóðãñêèéÓíèâåðñèòåò,
ÔàêóëüòåòÏðèêëàäíîéÌàòåìàòèêèèÏðîöåññîâÓïðàâëåíèÿ,
Óíèâåðñèòåòñêèéïð.35,Ñàíêò-Ïåòåðáóðã,198504,Ðîññèÿ
fax:+7(812)4287159
http://www.apmath.spbu.ru,
[email protected],
[email protected]
Êëþ÷åâûåñëîâà
:
Multi-DepotsLocationRoutingProblem,Multi-Depots
VehicleRoutingproblem,îïòèìàëüíûéìàðøðóò,ãåíåòè÷åñêèéàëãîðèòì,¾ñóïåð-
áàíêîìàòû¿.
Àííîòàöèÿ
Íàñåãîäíÿøíèéäåíüïðîáëåìàôóíêöèîíèðîâàíèÿñåòè
áàíêîìàòîâèêàðòî÷íîéïëàòåæíîéñèñòåìûÿâëÿåòñÿàêòóàëüíîéäëÿ
ìíîãèõáàíêîâ.Ïîýòîìóâîçíèêàåòíåîáõîäèìîñòüâîïòèìèçàöèèïðî-
öåññàîáñëóæèâàíèÿáàíêîìàòîâ,êî-òîðàÿïîçâîëèòñíèçèòüáàíêîâñêèå
èçäåðæêèèîáåñïå÷èòüêà-÷åñòâåííîåôóíêöèîíèðîâàíèåáàíêîìàòíîé
ñåòè.Âäàííîéðàáîòåðàññìàòðèâàåòñÿïðîáëåìàïîñòðîåíèÿìàðøðóòîâ
èíêàññàöèèâñåòèáàíêîìàòîâ,êîòîðàÿñîäåðæèòáàíêîìàòû,ðàñïîëà-
ãàþùèåñÿâêðóïíîìãîðîäå,àòàêæåâíåáîëüøèõíàñåëåííûõïóíêòàõ.
Äëÿïîñòðîåíèÿìàðøðóòîâèíêàññàöèèèñïîëüçóþòñÿàëãîðèòìûðåøå-
íèÿçàäà÷ìàðøðóòèçàöèèòðàíñïîðòà(VehicleRoutingProblems,VRP)
èååìîäèôèêàöèé,òàêèõêàêMDVRPèMDLRP.îñíîâíîåâíèìàíèå
âðàáîòåóäåëåíîñëåäóþùèììåòîäàì:Êëàðêà-Ðàéòà,ãåíåòè÷åñêèéè
ìåòîä¾ñóïåð-áàíêîìàòîâ¿.
1.Ââåäåíèå
Ñöåëüþïðèáëèæåíèÿìîäåëèêðåàëüíîéñèòóàöèè,âäàííîéðàáîòåðàññìàò-
ðèâàåòñÿñåòüáàíêîìàòîâ,ñîñòîÿùàÿèçîñíîâíîãîïîäìíîæåñòâàáàíêîìàòîâ,
ðàñïîëîæåííûõâêðóïíîìãîðîäå,àòàêæåîñòàëüíûõáàíêîìàòîâ,ðàñïîëî-
æåííûõíàäîñòàòî÷íîìóäàëåíèèîòöåíòðàãîðîäà,âðàçëè÷íûõðàéîíàõîá-
ëàñòè.Îáñëóæèâàíèåáàíêîìàòîâïðîèñõîäèòèçèíêàññàòîðñêîãîöåíòðà,êîòî-
ðûéðàñïîëîæåíâáàíêå.Ïðèýòîìîáñëóæèâàíèåóäàëåííûõîòöåíòðàãîðîäà
áàíêîìàòîââûçûâàåòäîïîëíèòåëüíûåèçäåðæêè.Ïîýòîìóâîçíèêàåòâîïðîñî
öåëåñîîáðàçíîñòèðàçìåùåíèÿäîïîëíèòåëüíîãîèíêàññàòîðñêîãîöåíòðàèïåðå-
ñòðîåíèÿìàðøðóòîâèíêàññàöèè.Äàííàÿçàäà÷àðåøàåòñÿñïîìîùüþàëãîðèò-
ìîâçàäà÷èìàðøðóòèçàöèèòðàíñïîðòà(VehicleRoutingProblems,VRP)èåå
ìîäèôèêàöèé.Âðàáîòåèñïîëüçóþòñÿñëåäóþùèåìîäèôèêàöèèçàäà÷èìàðø-
ðóòèçàöèèòðàíñïîðòà:çàäà÷àñíåñêîëüêèìèôèëèàëàìèáàíêà(Multi-Depots
VRP)èçàäà÷àðàçìåùåíèÿôèëèàëàáàíêà(LocationRoutingProblem).
Âçàäà÷àõìàðøðóòèçàöèèòðàíñïîðòà(VRP)ñòðîÿòñÿìàðøðóòû,áåðóùèå
íà÷àëîîòîáùåéâåðøèíû(äåïî)êíåñêîëüêèìãåîãðàôè÷åñêèðàñïðåäåëåí-
íûìêëèåíòàìñìèíèìàëüíûìèñóììàðíûìèçàòðàòàìè.Âíàøåìñëó÷àåðàñ-
ñìàòðèâàåòñÿçàäà÷àìàðøðóòèçàöèèñîäíèìáàíêîìèñåòüþáàíêîìàòîâ,÷òî
âïðàêòèêåâñòðå÷àåòñÿðåäêî.Ðîñòîìáàíêîâñêèõñåòåé,ïðîâîöèðóåòóâåëè-
÷åíèåèçäåðæåêáàíêàíàèíêàññàöèþ,âîñîáåííîñòèïðèóâåëè÷åíèè÷èñëà
áàíêîìàòîâ,ðàñïîëîæåííûõâíåöåíòðàãîðîäà.Òåìñàìûìâîçíèêàåòíåîáõî-
äèìîñòüèçìåíåíèÿêîëè÷åñòâîôèëèàëîâáàíêà,èçêîòîðûõîñóùåñòâëÿåòñÿ
èíêàññèðîâàíèåñåòèáàíêîìàòîâ.×òîïðèâîäèòêíåîáõîäèìîñòèèñïîëüçîâà-
íèÿçàäà÷èñíåñêîëüêèìèäåïî(Multi-DepotsVRP).Âýòîìñëó÷àåáàíêìîæåò
èìåòüíåñêîëüêîèíêàññàòîðñêèõöåíòðîâ,ðàñïîëîæåííûõâðàçëè÷íûõôèëè-
àëàõáàíêà.
Ïðèðåøåíèèòàêîéçàäà÷èâûïîëíÿåòñÿãðóïïèðîâêàáàíêîìàòîâñîäíèì
èçôèëèàëîâáàíêàâçàâèñèìîñòèîòðàññòîÿíèéìåæäóíèìè.Ãðóïïèðîâêà
áàíêîìàòîââîêðóãäîïîëíèòåëüíûõôèëèàëîâáàíêàïîçâîëèòñîêðàòèòüèç-
äåðæêèíàïåðååçäûèíêàññàòîðîââóäàëåííûåîáëàñòíûåöåíòðûäëÿâîñïîë-
íåíèÿçàïàñàíàëè÷íîñòèâáàíêîìàòå.Îäíàêîðåøåíèåçàäà÷èòàêîãîêëàññà
çíà÷èòåëüíîóñëîæíèòñÿ,òàêêàêâïðîöåññåïîñòðîåíèÿìàðøðóòîâ,òàêæå
ó÷èòûâàåòñÿêîëè÷åñòâîôèëèàëîâ,ïðèýòîìïî-ïðåæíåìóäîëæíûâûïîëíÿòü-
ñÿîãðàíè÷åíèÿçàäà÷èìàðøðóòèçàöèè,íàïðèìåð,îãðàíè÷åíèåíàâìåñòèìîñòü
òðàíñïîðòíûõñðåäñòâ.
Èñïîëüçóÿôîðìóëèðîâêóçàäà÷èðàçìåùåíèÿMDLRP(Multi-DepotsLocation
RoutingProblem)êïðîáëåìåèíêàññàöèèáàíêîìàòîâ,ìîæíîîïðåäåëèòüîï-
òèìàëüíîåðàçìåùåíèåíîâîãîôèëèàëàáàíêà,âêîòîðîìáóäåòáàçèðîâàòüñÿ
íîâûéöåíòðèíêàññàöèè.Òàêàÿïîñòàíîâêàçàäà÷èìîæåòäîïîëíèòüèññëåäî-
âàíèÿïîîïòèìèçàöèèìàðøðóòîâèíêàññàòîðñêèõáðèãàäâòîìñëó÷àå,åñëèó
áàíêàèìåþòñÿíåñêîëüêîôèëèàëîâ,ñèíêàññàòîðñêèìèöåíòðàìè.
Îñíîâíîéöåëüþäàííîéðàáîòûÿâëÿþòñÿìîäèôèêàöèèèçâåñòíîéçàäà÷è
MDVRPèMDLRP.Ïîñòðîåíèåîïòèìàëüíûõìàðøðóòîâèíêàññàöèèäëÿìî-
äèôèöèðîâàííîéïðîáëåìû.Èññëåäîâàíèåòàêæåâêëþ÷àåòâñåáÿïîñòðîåíèå
ìàðøðóòîâèíêàññàöèèíàïðèìåòåîäíîãîèçáàíêîâã.Ñàíêò-Ïåòåðáóðãà.
2.Ïîñòàíîâêàçàäà÷è
Ðàññìîòðèìñåòüáàíêîìàòîâ,îäíîãîèçáàíêîâã.Ñàíêò-Ïåòåðáóðãà,ñîñòîÿùóþ
èç
L
áàíêîìàòîâèíåñêîëüêèõôèëèàëîâ.Êàæäûéôèëèàëîòâå÷àåòçàñâîþ
ïîäñåòüáàíêîìàòîâ,èìåÿâðàñïîðÿæåíèèíåñêîëüêîèíêàññàòîðñêèõáðèãàä.
Êàæäàÿáðèãàäàèíêàññàòîðîâíà÷èíàåòèçàêàí÷èâàåòðàáîòóâîäíîìèòîìæå
ôèëèàëå.Ïðåäïîëàãàåòñÿ,÷òîâñåòðàíñïîðòíûåñðåäñòâàèìåþòîäèíàêîâûå
õàðàêòåðèñòèêè(âìåñòèìîñòüèãðóçîïîäúåìíîñòü).Ïðåäïîëîæèì,÷òîâèí-
êàññàòîðñêèéöåíòð,ïîäàíàçàÿâêàíàèíêàññèðîâàíèå
J
áàíêîìàòîâ.Ðàññìàò-
ðèâàþòñÿ,áàíêîìàòû,èìåþùèå÷åòûðåõêàññåòíóþêîíôèãóðàöèþ,ïîýòîìó
êàæäûéôèëèàëäîëæåíèìåòüäîñòàòî÷íîåêîëè÷åñòâîêàññåòäëÿîáñëóæèâà-
íèÿñâîåéïîäñåòèáàíêîìàòîâ.Ðàññòîÿíèÿìåæäóáàíêîìàòàìèèôèëèàëàìè
ñåòèèçâåñòíû.
Îñíîâíûåîáîçíà÷åíèÿìîäåëè:
I
ìíîæåñòâîâñåõôèëèàëîâáàíêà,
J
ìíîæåñòâîâñåõáàíêîìàòîâ,
K

ìíîæåñòâîâñåõìàøèí,òîãäà
i
íîìåðôèëèàëà,
j
íîìåðáàíêîìàòà,
k
íîìåð
ìàøèíû,
N
îáùååêîëè÷åñòâîìàøèí,
C
ij
ðàññòîÿíèåìåæäóïóíêòàìè
i
è
j
,
i;j
2
I
[
JV
i
êîëè÷åñòâîêàññåòñíàëè÷íîñòüþ,êîòîðûìðàñïîëàãàåò
i
ôèëèàë
áàíêà,
d
j
êîëè÷åñòâîêàññåòñíàëè÷íîñòüþ,êîòîðîåíåîáõîäèìîçàãðóçèòüâ
áàíêîìàò
j
,
F
ðàñõîäûçàðàáîòóèíêàññàòîðñêèõáðèãàä,
O
i
çàòðàòûíà
îòêðûòèåíîâîãîôèëèàëà,
Q
k
âìåñòèìîñòüòðàíñïîðòíîãîñðåäñòâàìàøèíû
2
k
.
y
i
áèíàðíàÿïåðåìåííàÿ,êîòîðàÿîáîçíà÷àåò,îòêðûòèëèçàêðûòôèëèàë
i
,
y
i
=

1
;
åñëèôèëèàë
i
îòêðûò
0
;
åñëèôèëèàë
i
çàêðûò
x
ijk
áèíàðíàÿïåðåìåííàÿ,êîòîðàÿïîêàçûâàåò,÷òîáàíêîìàò
j
âõîäèòâñî-
ñòàâìàðøðóòàìàøèíû
k
.
x
ijk
=

1
;
åñëè
i
ïðåäøåñòâóåò
j
ïîìàðøðóòók
0
;
âäðóãèõñëó÷àÿõ
z
ij
áèíàðíàÿïåðåìåííàÿ,êîòîðàÿïîêàçûâàåòîáúåäèíåíèåáàíêîìàòà
j
è
ôèëèàëà
i
.
z
ij
=

1
;
åñëèáàíêîìàò
j
îáúåäèíÿåòñÿñôèëèàëîì
i
0
;
âäðóãèõñëó÷àÿõ
3.Ìàòåìàòè÷åñêàÿìîäåëü
Çàïèøåììàòåìàòè÷åñêóþìîäåëü,îïèñûâàþùóþìèíèìèçàöèþèçäåðæåêáàí-
êàïðèèíêàññèðîâàíèèñåòèáàíêîìàòîâíàáàçåçàäà÷MDVRPèMDLRP:
min(
P
i
2
I
P
j
2
J
P
k
2
K
c
ij
x
ijk
+
P
j
2
J
P
k
2
K
c
jl
x
jlk
+
P
i
2
I
P
j
2
J
P
k
2
K
c
ji
x
jik
+
+
P
i
2
I
P
j
2
J
P
k
2
K
Fx
ijk
+
P
j
2
J
P
k
2
K
Fx
jlk
+
P
i
2
I
P
j
2
J
P
k
2
K
Fx
jik
+
P
i
2
I
O
i
y
i
);
(1)
X
k
2
K
X
i
2
I
x
ijk
=1
;
j
2
J;
(2)
X
i
2
I
X
j
2
J
x
ijk
+
X
j
2
J
X
l
2
J
x
jlk
=1
;
k
2
K
;
(3)
X
k
2
K
X
j
2
J
x
ijk
=1
;
i
2
I;
(4)
X
j
2
J
d
j
0
@
X
i
2
i
x
ijk
+
X
j;l
2
J
x
jlk
1
A

Q
k
;
k
2
K
;
(5)
X
i
2
S
X
j
2
S
x
ijk
j
S
j�
1
;
8
S

J
;
k
2
K;
(6)
X
j;l
2
J
x
jlk

X
j;l
2
J
x
ljk
=0
;
k
2
K;
(7)
X
j
2
J
d
j
z
ij

V
i
;
i
2
I;
(8)

z
ij
+
X
u
2
I
[
J
(
x
iuk
+
x
ujk
)

1
;
i
2
I
;
j
2
J
;
k
2
K;
(9)
3
x
ijk
2f
0
;
1
g
;
i
2
I
;
j
2
J
;
k
2
K
;
z
ij
2f
0
;
1
g
;
i
2
I
;
j
2
J;
(10)
Çäåñüâûðàæåíèå(1)ñîîòâåòñòâóåòöåëåâîéôóíêöèèçàòðàò;(2),(3),(4)
ãàðàíòèðóåòòî,÷òîèíêàññàòîðñêàÿáðèãàäàîáñëóæèâàåòáàíêîìàòòîëüêî
îäèíðàç;(5)îãðàíè÷åíèåíàâìåñòèìîñòüìàøèí;(6)óñòðàíÿåòïîäìàðø-
ðóòû,âõîäÿùèåâìàðøðóòìàøèíû
k
;(7)îãðàíè÷åíèå,îòñåêàþùååïîâòî-
ðÿþùèåñÿìàðøðóòû,ò.ê.ðàññòîÿíèåîòáàíêîìàòà
i
äî
j
ðàâåíðàññòîÿíèþîò
áàíêîìàòà
j
äî
i
;(8)îáùååêîëè÷åñòâîêàññåòñíàëè÷íîñòüþ,çàïðàøèâàåìîå
áàíêîìàòàìè,äëÿèõïîïîëíåíèÿ,âìàðøðóòå,ñâÿçàííîìñ
i
ôèëèàëîìáàíêà,
íåäîëæíîïðåâûøàòüêîëè÷åñòâîêàññåòñíàëè÷íîñòüþ,êîòîðûìèðàñïîëàãàåò
i
ôèëèàë;(9)áàíêîìàòèîäèíèçôèëèàëîâìîãóòáûòüîáúåäèíåíûâìàðø-
ðóòìàøèíû
k
,åñëèåñòüìàðøðóò,ïðîõîäÿùèé÷åðåçýòîòôèëèàëèáàíêîìàò;
(10)áèíàðíûåïåðåìåííûå;
4.Ìåòîäûðåøåíèÿçàäà÷MDVRPèMDLRP
Äëÿðåøåíèÿïîñòàâëåííûõçàäà÷âíàøåéðàáîòåèñïîëüçóåòñÿìåòîäÊëàðêà-
Ðàéòàèãåíåòè÷åñêèéàëãîðèòì.
ÌåòîäÊëàðêà-Ðàéòà
îòíîñèòñÿêêëàññóýâðèñòè÷åñêèõìåòîäîâ.Öåëüþ
äàííîãîìåòîäàÿâëÿåòñÿñâåäåíèåêìèíèìóìóêîëè÷åñòâîìàðøðóòîâ,íåíà-
ðóøàÿîãðàíè÷åíèÿ(5)è(8),èóìåíüøàÿèçäåðæêè.Åñëè÷èñëîìàðøðóòîâáó-
äåòáîëüøèì,òîèêîëè÷åñòâîèíêàññàòîðñêèõáðèãàäóâåëè÷èòñÿ,÷òî,âñâîþ
î÷åðåäü,ïîâëèÿåòíàóâåëè÷åíèåèçäåðæåê.
Ãåíåòè÷åñêèåàëãîðèòì
ÿâëÿåòñÿýâðèñòè÷åñêèì,îíîñíîâàííàìåõàíèçìå
ïàðàëëåëüíîãîïîèñêà,÷òîäåëàåòåãîáîëååýôôåêòèâíûì,÷åìäðóãèåêëàññè-
÷åñêèåìåòîäûîïòèìèçàöèè,òàêèåêàêìåòîäâåòâåéèãðàíèö,ìåòîäïîèñêàè
èìèòàöèèîòæèãà.Âãåíåòè÷åñêîìàëãîðèòìåèìèòèðóåòñÿìåõàíèçìåñòåñòâåí-
íîãîîòáîðàèâûæèâàíèÿíàèáîëååïðèñïîñîáëåííûõîñîáåé.
Ãåíåòè÷åñêèéàëãîðèòìýôôåêòèâåíïðèíàõîæäåíèèîïòèìàëüíîãîèëèïî-
÷òèîïòèìàëüíîãîðåøåíèÿ,íîñóùåñòâóþòäâåïðîáëåìû:
1.
íèçêàÿñêîðîñòüíàõîæäåíèÿðåøåíèÿ.
2.
ïðåæäåâðåìåííàÿñõîäèìîñòü.
ÌåòîäÊëàðêà-Ðàéòàèãåíåòè÷åñêèéàëãîðèòìíåäàþòîïòèìàëüíîãîðåøå-
íèÿ,íîïîçâîëÿþòïîëó÷èòüðåøåíèåáëèçêîåêîïòèìàëüíîìó,êîòîðîåìîæíî
èñïîëüçîâàòüïðèðåøåíèèïðàêòè÷åñêèõçàäà÷àõ.
Çàäà÷óòèïà
MDLRP
èç-çàñëèøêîìáîëüøîãîêîëè÷åñòâàâõîäíûõäàí-
íûõíåâîçìîæíîðåøèòüìåòîäàìèëèíåéíîãîïðîãðàììèðîâàíèÿ,ïîýòîìóäëÿ
óìåíüøåíèÿèõ÷èñëà,âîñïîëüçóåìñÿìåòîäîì¾ñóïåð-áàíêîìàòîâ¿,ïðåäëîæåí-
Äîïóñòèì,÷òîèìååòñÿíåñêîëüêîïðåäïîëàãàåìûõìåñòäëÿîòêðûòèÿíî-
âîãîôèëèàëà.Íàéäåìäîïóñòèìîåðåøåíèåèñõîäíîéñèñòåìû(1)(10)ëþ-
áûìýâðèñòè÷åñêèìàëãîðèòìîì,íàïðèìåðìåòîäîìÊëàðêà-Ðàéòà,ó÷èòû-
âàÿâñåâîçìîæíûåìåñòîïîëîæåíèÿôèëèàëîâ.
2.
Èñêëþ÷èìôèëèàëûèçïîñòðîåííûõìàðøðóòîâ.
3.
Îáúåäèíèìáàíêîìàòûêàæäîãîìàðøðóòàâ¾ñóïåð-áàíêîìàòû¿.
4.
Ïîñòðîèììàðøðóòûñíîâûìèîáúåäèí¼ííûìèáàíêîìàòàìèèôèëèàëàìè.
4
5.
Âêàæäîìïîñòðîåííîììàðøðóòåðàçîáüåì¾ñóïåð-áàíêîìàòû¿,òàêèìîá-
ðàçîì,ïîëó÷èìíîâîåðåøåíèå.
ÍàãëÿäíîåïðåäñòàâëåíèåäàííîãîìåòîäàèçîáðàæåíîíàÐèñ.1,Ðèñ.2,Ðèñ.3,
Ðèñ.4èÐèñ.5.
Ñïîìîùüþäàííîãîìåòîäàêîëè÷åñòâîâõîäíûõäàííûõçíà÷èòåëüíîóìåíü-
øàåòñÿ,ïîýòîìóçàäà÷óìîæíîðåøèòüñïîìîùüþìåòîäîâëèíåéíîãîïðîãðàì-
ìèðîâàíèÿ.
Ðèñ.1ÄîïóñòèìîåðåøåíèåÐèñ.2Èñêëþ÷åíèåôèëèàëîâèç
èñõîäíîéñèñòåìû
ïîñòðîåííûõìàðøðóòîâ
Ðèñ.3ÎáúåäèíåíèåáàíêîìàòîââÐèñ.4Ïîñòðîåíèåíîâûõ
ïîñòðîåííûõìàðøðóòàõâ
ìàðøðóòîâñ¾ñóïåð-áàíêîìàòàìè¿
¾ñóïåð-áàíêîìàòû¿
5
Ðèñ.5Ðàçúåäèíåíèå¾ñóïåð-áàíêîìàòîâ¿,èïîëó÷åíèåíîâûõìàðøðóòîâ
Îïèñàííûåâûøåàëãîðèòìûáûëèïðèìåíåíûäëÿïîñòðîåíèÿèíêàññàòîð-
ñêèõìàðøðóòîââñåòè,ñîñòîÿùåéèç89áàíêîìàòîâèäâóõôèëèàëîâáàíêà.
Äîïóñòèì,÷òîïîñòóïèëàçàÿâêàíàîáñëóæèâàíèå20áàíêîìàòîâ.Äâàôèëèà-
ëàáàíêàñïåöèàëèçèðóþòñÿíàèíêàññèðîâàíèèáàíêîìàòîâ,èâêàæäîìèõíèõ
íàõîäèòñÿäâåèíêàññàòîðñêèåáðèãàäû(
N
=4).
Àäðåñàáàíêîìàòîâ,âõîäÿùèõâçàÿâêó:
Âèòåáñêèéïðîñïåêò,53,ê.4;Çâåçä-
íàÿóëèöà,6;Ëåíèíñêèéïðîñïåêò,129;Íîâàòîðîâáóëüâàð,11/2;Íåâñêèéïðî-
ñïåêò,49;Ãàãàðèíàïðîñïåêò,27;Êîñìîíàâòîâïðîñïåêò,28;Êðàñíîïóòèëîâñêàÿ
óëèöà,121;Ëåíèíñêèéïðîñïåêò,151;ÊîëèÒîì÷àêàóëèöà,27;Äóìñêàÿóëè-
öà,4;Áóõàðåñòñêàÿóëèöà,89;Áàññåéíàÿóëèöà,17;Ìîñêîâñêèéïðîñïåêò,200;
Íîâîñìîëåíñêàÿíàáåðåæíàÿ,1/3;Âåòåðàíîâïðîñïåêò,43;Âåòåðàíîâïðîñïåêò,
89;ËåíèÃîëèêîâàóëèöà,3;Èçìàéëîâñêèéïðîñïåêò,4;Ìîñêîâñêèéïðîñïåêò,
133.Ïåðâûéôèëèàë(À)íàõîäèòñÿïîàäðåñóóë.Âåðåéñêàÿä.16ëèò.À,âòîðîé
ôèëèàë(Â)óë.Áóõàðåñòñêàÿä.23.
Òðåáóåòñÿïîñòðîèòüìàðøðóòûèíêàññàòîðñêèõáðèãàäòàêèìîáðàçîì,÷òî-
áûèçäåðæêèáûëèìèíèìàëüíû,çàÿâêèíàïîïîëíåíèåáàíêîìàòîâíàëè÷íî-
ñòüþâûïîëíåíû,âñåîãðàíè÷åíèÿó÷òåíû.Âêàæäûéáàíêîìàòçàãðóæàåòñÿ
d
i
=4
êàññåòûíàëè÷íîñòè,âìåñòèìîñòüêàæäîéèíêàññàòîðñêîéìàøèíû
Q
=
16.Ðàññòîÿíèÿìåæäóáàíêîìàòàìèèôèëèàëàìèáàíêàèçâåñòíû.Íàïåðâîì
øàãåáûëèñãðóïïèðîâàíûáàíêîìàòûñáëèæàéøèìôèëèàëîì.Ñôèëèàëîì
À
ñãðóïïèðîâàíûáàíêîìàòû:5,8,11,15,16,17,19,20;ñôèëèàëîì
Â
:1,2,3,
4,6,7,9,10,12,13,14,18.Òàêèìîáðàçîìçàäà÷àïîñòðîåíèÿèíêàññàòîðñêèõ
ìàðøðóòîâäëÿñåòèñäâóìÿôèëèàëàìèáàíêàáûëàðàçáèòàíàäâåïîäçàäà÷è.
Íàâòîðîìøàãåêêàæäîéèçïîäçàäà÷ïðèìåíèëèìåòîäÊëàðêà-Ðàéòàäëÿïî-
ñòðîåíèÿäîïóñòèìîãîðåøåíèÿ.Íàòðåòüåìøàãåèñïîëüçîâàëèãåíåòè÷åñêèé
àëãîðèòìäëÿîïòèìèçàöèèïîëó÷åííîãîðåøåíèÿ.
ÍàÐèñ.6èÐèñ.7ïîêàçàíûïîñòðîåííûåìàðøðóòûèíêàññàöèèäëÿïîñòàâ-
ëåííîéçàäà÷è.
6
Ðèñ.6Ìàðøðóòûáðèãàäèíêàññàöèèäëÿïåðâîãîôèëèàëà(A)
Ðèñ.7Ìàðøðóòûáðèãàäèíêàññàöèèäëÿâòîðîãîôèëèàëà(B)
Ñïèñîêëèòåðàòóðû
RandolphW.Hall.
HandbookofTransportationScience.
Springer,2003.
RalphsT.K.,KopmanL.,PulleyblankW.R.,TrotterL.E.
OntheCapacitatedVehicle
RoutingProblem
.MathematicalProgramming,2003.P.343359.
SurekhaP.,Dr.SumathiS.
SolutionToMulti-DepotVehicleRoutingProblemUsing
PrinsC.,ProdhonC.,RuizA.,SorianoP.,CalvoR.W.
SolvingtheCapacitatedLocation-
RoutingProblembyaCooperativeLagrangeanRelaxation-GranularTabuSearch
Heuristic.
TransportationScience,Vol.41,No.4,November2007,pp.470-483
NallusamiR.,DuraiswamyK.,DhanalaksmiR.,ParthibanP.
OptimizationofMultiple
VehicleRoutingProblemsusingapproximationalgorithms
InternationalJournalof
EngineeringScienceandTechnology,Vol.1(3),2009,129-135
GubarE.,MerzlyakovaJ.D.,ZubarevaM.L.
GubarE.,ZubarevaM.

Приложенные файлы

  • pdf 14998218
    Размер файла: 518 kB Загрузок: 0

Добавить комментарий