Problém překládky - Transshipment problem

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Problém s překládkou“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Květen 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Problémy s překládkou tvoří podskupinu dopravních problémů, kde překládka je povoleno. Při překládce může nebo může přeprava procházet mezilehlými uzly, což může změnit způsoby dopravy.

The Problém překládky má svůj původ ve středověku^{[pochybný – diskutovat]} když se obchodování začalo stávat masovým fenoménem. Hlavní prioritou bylo získání trasy s minimálními náklady. Technologický rozvoj však pomalu upřednostňoval problémy s přepravou na minimum.

Přehled

Překládka nebo Překládka je náklad z zboží nebo kontejnery do mezilehlého cíle a odtud do dalšího cíle. Jedním z možných důvodů je změna dopravní prostředek během cesty (například z lodní doprava na silniční doprava ), známý jako překládka. Dalším důvodem je spojit malé zásilky do velké zásilky (konsolidace) a rozdělit velkou zásilku na druhém konci (dekonsolidace). Překládka se obvykle koná v dopravní uzly. Velká část mezinárodní překládky se rovněž odehrává ve určených celní oblasti, čímž se zabrání nutnosti celních kontrol nebo cel, jinak by to bylo velkou překážkou účinné dopravy.

Formulace problému

K úplnému formulování problému s překládkou je zapotřebí několik počátečních předpokladů:

• Systém se skládá z m původy a n destinace s následujícím indexováním: ${ displaystyle i = 1, ldots, m}$, ${ displaystyle j = 1, ldots, n}$
• Existuje jedno jednotné zboží, které je třeba odeslat
• Požadované množství zboží v cílech se rovná produkovanému množství dostupnému na počátku
• Přeprava současně začíná v počátcích a je možná z jakéhokoli uzlu do jakéhokoli jiného (také do původu a z cíle)
• Přepravní náklady jsou nezávislé na dodané částce
• Problém překládky je jedinečný problém lineárního programování (LLP) v tom, že zohledňuje předpoklad, že všechny zdroje a propady mohou přijímat a distribuovat zásilky současně (funkce v obou směrech)^[1]

Zápisy

• ${ displaystyle t_ {r, s}}$: doba přepravy z uzlu r do uzlu s
• ${ displaystyle a_ {i}}$: zboží k dispozici na uzlu i
• ${ displaystyle b_ {m + j}}$: poptávka po zboží v uzlu (m + j)
• ${ displaystyle x_ {r, s}}$: skutečné množství přepravené z uzlu r do uzlu s

Matematická formulace problému

Cílem je minimalizovat ${ displaystyle sum limity _ {i = 1} ^ {m} suma limity _ {j = 1} ^ {n} t_ {i, j} x_ {i, j}}$ podléhá:

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

Řešení

Vzhledem k tomu, že ve většině případů neexistuje explicitní výraz pro objektivní funkci, navrhuje alternativní metodu Rajeev a Satya. Metoda používá dvě po sobě jdoucí fáze k odhalení minimální doby trvání trasy od počátku k cílům. První fáze je ochotna vyřešit ${ displaystyle n cdot m}$ problém minimalizující čas, v každém případě pomocí zbytku ${ displaystyle n + m-2}$ mezilehlé uzly jako překladiště. To také vede k minimální přepravě mezi všemi zdroji a cíli. Během druhé fáze je třeba vyřešit standardní problém minimalizující čas. Řešení problému překládky s minimalizací času je výsledkem společného řešení těchto dvou fází.

Fáze 1

Vzhledem k tomu, že náklady jsou nezávislé na dodaném množství, lze u každého jednotlivého problému normalizovat dodané množství na 1. Problém je nyní zjednodušen na problém s přiřazením od i na m + j. Nechat ${ displaystyle x '_ {r, s} = 1}$ být 1 pokud hrana mezi uzly r a s se používá během optimalizace a 0 v opačném případě. Nyní je cílem určit vše ${ displaystyle x '_ {r, s}}$ které minimalizují objektivní funkci:

${ displaystyle T_ {i, m + j} = součet _ {r = 1} ^ {m + n} součet _ {s = 1} ^ {m + n} {t_ {r, s} cdot x „_ {r, s}}}$,

takhle

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

Důsledek

• ${ displaystyle x '_ {r, r} = 1}$ a ${ displaystyle x '_ {m + j, i} = 1}$ je třeba z modelu vyloučit; na druhé straně bez ${ displaystyle x '_ {m + j, i} = 1}$ omezení, optimální cesta by sestávala pouze z ${ displaystyle x '_ {r, r}}$-typové smyčky, které samozřejmě nemohou být proveditelným řešením.
• Namísto ${ displaystyle x '_ {m + j, i} = 1}$, ${ displaystyle t_ {m + j, i} = - M}$ lze napsat, kde M je libovolně velké kladné číslo. S touto modifikací je výše uvedená formulace redukována na formu a standardní problém s přiřazením, možné vyřešit pomocí Maďarská metoda.

Fáze 2

Během druhé fáze je problém s minimalizací času vyřešen pomocí m původy a n destinace bez překládky. Tato fáze se od původního nastavení liší ve dvou hlavních aspektech:

• Přeprava je možná pouze z místa původu do cíle
• Doba přepravy z i na m + j je součet dob ​​pocházejících z optimální trasy vypočtené ve Fáze 1. Je třeba jej označit ${ displaystyle t '_ {i, m + j}}$ aby se oddělil od časů zavedených během první etapy.

V matematické formě

Cílem je najít ${ displaystyle x_ {i, m + j} geq 0}$ které minimalizují

${ displaystyle z = max left {t '_ {i, m + j}: x_ {i, m + j}> 0 ; ; (i = 1 ldots m, ; j = 1 ldots n) doprava }}$,
takhle

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

Tento problém lze snadno vyřešit metodou vyvinutou Prakash. Sada ${ displaystyle left {t '_ {i, m + j}, i = 1 ldots m, ; j = 1 ldots n right }}$ je třeba rozdělit do podskupin ${ displaystyle L_ {k}, k = 1 ldots q}$, kde každý ${ displaystyle L_ {k}}$ obsahují ${ displaystyle t '_ {i, m + j}}$-s se stejnou hodnotou. Sekvence ${ displaystyle L_ {k}}$ je organizována jako ${ displaystyle L_ {1}}$ obsahuje největší hodnotu ${ displaystyle t '_ {i, m + j}}$je ${ displaystyle L_ {2}}$ druhý největší a tak dále. Dále ${ displaystyle M_ {k}}$ podskupinám jsou přiřazeny pozitivní prioritní faktory ${ displaystyle sum _ {L_ {k}} {x_ {i, m + j}}}$, s následujícím pravidlem:

${ displaystyle alpha M_ {k} - beta M_ {k + 1} = left {{ begin {pole} {cc} -ve, & if ; alpha <0 ve, & if ; alfa> 0 end {pole}} vpravo.}$

pro všechny ${ displaystyle beta}$. Cílem této notace je najít vše ${ displaystyle x_ {i, m + j}}$ které minimalizují funkci cíle

${ displaystyle z_ {1} = součet _ {k = 1} ^ {q} {M_ {k}} součet _ {L_ {k}} {x_ {i, m + j}}}$

takhle

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

Rozšíření

Někteří autoři, jako Das et al (1999) a Malakooti (2013), uvažovali o víceúčelovém problému překládky.

Reference

• R.J Aguilar, Systémová analýza a design. Prentice Hall, Inc. Englewood Cliffs, New Jersey (1973), str. 209–220
• H. L. Bhatia, K. Swarup, M. C. Puri, indický J. pure appl. Matematika. 8 (1977) 920-929
• R. S. Gartinkel, M. R. Rao, Nav. Res. Log. Kvart. 18 (1971) 465-472
• G. Hadley, Lineární programování, Addison-Wesley Publishing Company, (1962), str. 368–373
• P. L. Hammer, Nav. Res. Log. Kvart. 16 (1969) 345-357
• P. L. Hammer, Nav. Res. Log. Kvart. 18 (1971) 487-490
• AJ Hughes, D.E. Grawog, Lineární programování: Důraz na rozhodování, Addison-Wesley Publishing Company, str. 300–312
• HW Kuhn, Nav. Res. Log. Kvart. 2 (1955) 83-97
• A.Orden, Management Sci, 2 (1956) 276-285
• S.Parkash, Proc. Indian Acad. Sci. (Math. Sci.) 91 (1982) 53-57
• C.S. Ramakrishnan, OPSEARCH 14 (1977) 207-209
• CR Sehan, V.G. Tikekar, Proc. Indian Acad. Sci. (Math. Sci.) 89 (1980) 101-102
• J. K. Sharma, K. Swarup, Proc. Indian Acad. Sci. (Math. Sci.) 86 (1977) 513-518
• W. Szwarc, Nav. Res. Log. Kvart. 18 (1971) 473-485
• Malakooti, ​​B. (2013). Provozní a výrobní systémy s více cíli. John Wiley & Sons.
• Das, S. K., A. Goswami a S. S. Alam. „Problém multiobjektivní dopravy s intervalovými náklady, zdroji a cílovými parametry.“ European Journal of Operational Research, Vol. 117, č. 1, 1999, s. 100–112