Omlastningsproblem

Omlastningsproblem utgör en undergrupp av transportproblem, där omlastning är tillåten. Vid omlastning kan eller måste transporten gå genom mellanliggande noder, eventuellt byta transportsätt.

Omlastningsproblemet har sitt ursprung i medeltiden när handel började bli ett massfenomen . Att erhålla minimikostnadsrutten hade varit huvudprioriteringen. Den tekniska utvecklingen prioriterade dock långsamt transportproblem med minsta varaktighet.

Översikt

Omlastning eller omlastning är transport av varor eller containrar till en mellanliggande destination och sedan därifrån till ytterligare en destination. En möjlig anledning är att byta transportmedel under resan (till exempel från fartygstransport till vägtransport ), så kallad omlastning . Ett annat skäl är att kombinera små försändelser till en stor försändelse (konsolidering), dela upp den stora försändelsen i andra änden (dekonsolidering). Omlastning sker vanligtvis i transportnav . Mycket internationell omlastning sker också i anvisade tullområden , vilket undviker behovet av tullkontroller eller tullar, annars ett stort hinder för effektiva transporter.

Formulering av problemet

Några inledande antaganden krävs för att formulera omlastningsproblemet helt:

• Systemet består av m ursprung och n destinationer, med följande indexering respektive: $i=1,\ldots ,m$ , $j=1, \ldots ,n$
• Det finns en enhetlig vara som måste skickas
• Den erforderliga mängden vara vid destinationerna är lika med den producerade kvantiteten som är tillgänglig vid ursprunget
• Transport startar samtidigt vid utgångspunkten och är möjlig från vilken nod som helst till vilken som helst annan (även till ett ursprung och från en destination)
• Transportkostnaderna är oberoende av fraktbeloppet
• Omlastningsproblemet är ett unikt linjärt programmeringsproblem (LLP) genom att det tar hänsyn till antagandet att alla källor och sänkor kan både ta emot och distribuera försändelser samtidigt (fungerar i båda riktningarna)

Noteringar

• $t_{r,s}$ : tid för transport från nod r till nod s
• $a_{i}$ : varor tillgängliga på nod i
• $b_{m+j}$ : efterfrågan på varan i noden (m+j)
• $x_{r,s}$ : faktisk mängd som transporteras från nod r till nod s

Matematisk formulering av problemet

Målet är att minimera $\sum \limits _{i=1}^{m}\sum \limits _{j=1} ^{n}t_{i,j}x_{i,j}$ med förbehåll för:

• $x_{r,s}\geq 0$ ; $\forall r=1\ldots m$ , $s=1\ldots n$
• $\sum _{s=1}^{m+n}{x_{i,s} }-\summa _{r=1}^{m+n}{x_{r,i}}=a_{i}$ ; $\forall i=1\ldots m$
• $\sum _{r=1}^{m+n}{ x_{r,m+j}}-\summa _{s=1}^{m+n}{x_{m+j,s}}=b_{m+j}$ ; $\forall j=1\ldots n$
• $\sum _{i=1}^{m}{a_{i}}=\summa _{j=1}^{n }{b_{m+j}}$

Lösning

Eftersom det i de flesta fall inte finns ett explicit uttryck för den objektiva funktionen, föreslås en alternativ metod av Rajeev och Satya . Metoden använder två på varandra följande faser för att avslöja den minimala varaktigheten från utgångspunkten till destinationerna. Den första fasen är villig att lösa $n\cdot m$ tidsminimerande problem, i varje fall att använda de återstående $n+m-2$ mellannoderna som omlastningspunkter. Detta leder också till den minimala varaktigheten av transporter mellan alla källor och destinationer. Under den andra fasen måste ett standardmässigt tidsminimerande problem lösas. Lösningen på det tidsminimerande omlastningsproblemet är det gemensamma lösningsresultatet av dessa två faser.

Fas 1

0 Eftersom kostnaderna är oberoende av det fraktade beloppet kan man i varje enskilt problem normalisera den fraktade kvantiteten till 1 . Problemet är nu förenklat till ett tilldelningsproblem från i till m+j . Låt $x'_{r,s}=1$ vara 1 om kanten mellan noderna r och s används under optimeringen och annars. Nu är målet att bestämma alla $x'_{r,s}$ som minimerar objektivfunktionen:

$T_{i,m+j}=\summa _{r=1 }^{m+n}\summa _{s=1}^{m+n}{t_{r,s}\cdot x'_{r,s}}$ ,

Så att

• $\sum _{s=1}^{m+n}{x'_{r,s}}=1$
• $\sum _{r=1}^{m+n}{x'_{r,s}}=1$
• $x'_{m+j,i}=1$
• $x'_{r,s}=0,1$ .

Naturlig följd

• $x'_{r,r}=1$ och $x'_{m+j,i}=1$ måste vara exkluderas från modellen; å andra sidan, utan $x'_{m+j,i}=1$ -begränsningen skulle den optimala vägen endast bestå av $x' _{r,r}$ -typ loopar som uppenbarligen inte kan vara en genomförbar lösning.
• Istället för ${\displaystyle x'_{m+j,i}=1} ,$ t $\displaystyle t_{m+j,i}=- M}$ kan skrivas, där M är ett godtyckligt stort positivt tal. Med den modifieringen reduceras formuleringen ovan till formen av ett standarduppgiftsproblem , möjligt att lösa med den ungerska metoden .

Fas 2

Under den andra fasen löses ett tidsminimeringsproblem med m origo och n destinationer utan omlastning. Denna fas skiljer sig i två huvudsakliga aspekter från den ursprungliga installationen:

• Transport är endast möjlig från ett ursprung till en destination
• Transporttid från i till m+j är summan av varaktigheter som kommer från den optimala rutten beräknad i fas 1. Värt att betecknas med $t'_{i,m+j}$ i för att skilja den från de tider som infördes under det första steget.

I matematisk form

Målet är att hitta $x_{i,m+j}\geq 0$ som minimerar

${\displaystyle z=max\left\{t'_{i ,m+j}:x_{i,m+j}>0\;\;(i=1\ldots m,\;j=1\ldots n)\right\}} ,$ så att

• $\sum _{i=1}^{m}{x_{i,m+j}}=a_{i}$
• $\sum _{j=1}^{n}{x_{i,m+j}}=b_{m+j}$
• $\sum _{i=1}^{m}{a_{i}}=\summa _{j=1}^{n }{b_{m+j}}$

Detta problem är lätt att lösa med den metod som utvecklats av Prakash . Mängden $\left\{t'_{i,m+j},i=1\ldots m,\; j=1\ldots n\right\}$ måste delas in i undergrupper $L_{k},k=1\ldots q$ , där varje $L_{ k}$ innehåller $t'_{i,m+j}$ -s med samma värde. Sekvensen $L_{k}$ är organiserad som $L_{1}$ innehåller det största värdena $t'_{i,m+j}$ s $L_{2}$ den näst största och så vidare. Dessutom tilldelas ${\displaystyle M_{k}} positiva prioritetsfaktorer till undergrupperna$$\sum _{L_{k}}{x_{i,m+j} }$ , med följande regel:

$\alpha M_{k}-\beta M_{k+1}=\left\{{ \begin{array}{cc}-ve,&if\;\alpha <0\\ve,&if\;\alpha >0\end{array}}\right.$

för alla $\beta$ . Med denna notation är målet att hitta alla $x_{i,m+j}$ som minimerar målfunktionen

$z_{1}=\summa _{k=1}^{q}{M_{k}}\summa _{L_ {k}}{x_{i,m+j}}$

Så att

• $\sum _{i=1}^{m}{x_{i,m+j}}=a_{i}$
• $\sum _{j=1}^{n}{x_{i,m+j}}=b_{m+j}$
• $\sum _{i=1}^{m}{a_{i}}=\summa _{j=1}^{n }{b_{m+j}}$
• $\alpha M_{k}-\beta M_{k+1}=\left\{{ \begin{array}{cc}-ve,&if\;\alpha <0\\ve,&if\;\alpha >0\end{array}}\right.$

Förlängning

Vissa författare som Das et al (1999) och Malakooti (2013) har övervägt ett multiobjektiv omlastningsproblem.

• RJ Aguilar, Systemanalys och design. Prentice Hall, Inc. Englewood Cliffs, New Jersey (1973) s. 209–220
• HL Bhatia, K. Swarup, MC Puri, Indian J. pure appl. Matematik. 8 (1977) 920-929
• RS Gartinkel, MR Rao, Nav. Res. Logga. Quart. 18 (1971) 465-472
• G. Hadley, Linjär programmering, Addison-Wesley Publishing Company, (1962) s. 368–373
• PL Hammer, Nav. Res. Logga. Quart. 16 (1969) 345-357
• PL Hammer, Nav. Res. Logga. Quart. 18 (1971) 487-490
• AJHughes, DEGrawog, Linear Programming: An Emphasis On Decision Making, Addison-Wesley Publishing Company, s. 300–312
• HWKuhn, Nav. Res. Logga. Quart. 2 (1955) 83-97
• A. Orden, Management Sci, 2 (1956) 276-285
• S. Parkash, Proc. Indian Acad. Sci. (Math. Sci.) 91 (1982) 53-57
• CS Ramakrishnan, OPSEARCH 14 (1977) 207-209
• CRSeshan, VGTikekar, Proc. Indian Acad. Sci. (Math. Sci.) 89 (1980) 101-102
• JKSharma, K. Swarup, Proc. Indian Acad. Sci. (Math. Sci.) 86 (1977) 513-518
• W.Szwarc, Nav. Res. Logga. Quart. 18 (1971) 473-485
• Malakooti, ​​B. (2013). Drift- och produktionssystem med flera mål. John Wiley & Sons.
• Das, SK, A. Goswami och SS Alam. "Multiobjektiv transportproblem med intervallkostnad, källa och destinationsparametrar." European Journal of Operational Research, Vol. 117, nr 1, 1999, sid. 100–112