Överväga problemet med schemaläggning av tåg och containrar (eller lastbilar och pallar) mellan en depå och en destination. Varor anländer dynamiskt över tid till depån och har tydliga förfallodagar på destinationen. Det finns en fast avgift transportkostnad för varje fordon, och varje fordon har samma kapacitet. Kostnaden för att inneha varor kan variera mellan depån och destinationen. Målet är att minimera summan av transport- och hållandekostnader. För det fall då alla varor har samma innehavskostnader tar vi hänsyn till två variationer: en där innehavskostnaden vid destinationen är mindre än den vid ursprunget, och en där förhållandet är omvänt. För den första varianten får vi egenskaper hos den optimala lösningen som utgör grunden för ett O T 2-lösningsförfarande. För den andra varianten introducerar vi en ny definition av ett regenereringstillstånd, härleder starka karakteriseringar av leveransschemat inom ett regenereringsintervall och utvecklar ett O T 4-förfarande. Vi analyserar också två flerpunktsscenarier. I den första, för varje post, är jordbrukskostnaden vid ursprunget lägre än den vid destinationen; i den andra, förhållandet är omvänd för alla poster. Vi generaliserar flera av de strukturella resultaten för en-punkts problemet till motsvarande multi-punkt fall. Vi visar också att den optimala fordonsschemat kan erhållas genom att lösa ett relaterat enpunktsproblem där postens krav aggregeras på ett visst sätt. Den optimala tilldelningen av kundorder till fordon kan då hittas genom att lösa ett linjärt program. Vårt arbete motiveras av problemet med att schemalägga tåg eller lastbilar som kommer ut från en enda depå och tilldela varor till dessa fordon, i syfte att uppnå leverans i tid till lägsta kostnad. Vi anser att en ändlig tidshorisont under vilken kundorder dynamiskt blir tillgängliga vid ursprung, och har olika förfallodagar på sina destinationer. Vi utgår från att efterfrågan, skild efter ursprung, ankomstdatum vid ursprung, destination och förfallodag på destinationen, är känd i förväg, eller kan förutses tillräckligt noggrant över tidshorisonten för planeringsändamål. Vi överväger direkta transporter mellan en depå och var och en av de olika destinationerna. Om det inte finns något beroende bland destinationerna kan vi bryta ner problemet efter destination. Även om vår ursprungliga motivation härrörde från tågplanering, uppstår en liknande situation även när färdiga varor måste transporteras med lastbil från en fabrik till avlägsna marknader eller break-bulk lager. Kundorder med tydliga förfallodagar och avsedda för en viss marknad tillverkas på fabriken och blir tillgängliga för leverans över tid. Tillverkaren står inför beslutet om när lastbilar ska avsändas och vilka kundorder som ska tilldelas varje lastbil. Detta problem skulle naturligtvis förenklas om varor som är avsedda för en viss marknad tillverkades nära tillsammans i tid. Det finns dock ofta konkurrerande och/eller överskuggande överväganden vid fastställandet av produktionsschemat, vilket gör det nödvändigt att lösa problemet med transportplanering. Som är typiskt i järnvägs-, lastbils- och sjötransporter, finns det en (nästan) fast avgift i samband med den direkta förflyttningen av fordonet eller fartyget från ursprunget till destinationen som inkluderar kostnaden för arbetskraft för förflyttning av fordonet och andra kostnader som inte är volymberoende, inklusive den del av bränsle- och underhållskostnader som inte beror på mängden varor i fordonet. Dessutom är transportfordonets kapacitet känd. Eftersom vi tar itu med ett korthorisontellt problem utgår vi från att de fasta transportkostnaderna per fordon är konstanta över tiden och oberoende av antalet fordon som skickas. I de allra flesta situationer kommer de totala volymberoende kostnaderna endast att variera något, om alls, i takt med att tidtabellen ändras. Till exempel skulle den extra kostnaden för bränsle i samband med transport av en viss vikt eller volym av varor via lastbil från ursprung till destination, utöver den kostnad som krävs för att driva lastbilen/lastbilarna, vara ungefär densamma oavsett fördelningen av varor mellan lastbilar. Det skulle naturligtvis vara mer effektivt att transportera alla varor på så få lastbilar som möjligt, förutsatt att deras kapacitet inte överskrids, och denna aspekt fångas upp av den fasta transportkostnaden. Vi antar att de totala volymberoende kostnaderna är okänsliga för detaljerna i fraktschemat. På samma sätt skiljer sig i många sammanhang kostnaden för att hålla varorna vid ursprunget inte mycket från kostnaden på destinationen, men de kan skilja sig mycket åt i andra miljöer. Därför analyserar vi också situationer där innehavskostnaderna skiljer sig åt mellan olika poster och mellan olika platser. Eftersom påföljder för försenad leverans kan vara betydande, vårt främsta mål är att minimera summan av fasta transportkostnader samtidigt leverera varorna i tid. Vi kommer dock att överväga det mer allmänna problemet där innehavskostnaderna kan variera mellan ursprung och destination för att återspegla den relativa kostnaden för lagringsutrymme, samt i vilken utsträckning kunden är villig att acceptera tidiga transporter. I vissa fall, kunden kan vilja ta emot transporten så tidigt som möjligt, medan i andra fall en just-in-time leverans schema kan vara att föredra. Den tidigare situationen kan modelleras genom att en högre jordbrukskostnad införs vid ursprunget än vid destinationen, medan det senare scenariot representeras av det omvända förhållandet. Vi noterar att eventuella kapitalkostnader i samband med innehav av varorna i transit vanligtvis bärs av avsändaren eller mottagaren, och inte av transportören. Transportören står dock för kostnaden för att ha utrustning, t.ex. släpvagnar och containrar, som inte är tillgänglig för användning. Vi analyserar i vilket fall varor har homogena innehavskostnader, där innehavskostnaden är dyrare på destinationen än vid ursprunget. Det motsatta förhållandet mellan innehavskostnader kan hanteras genom samma tillvägagångssätt med hjälp av en lämplig omvandling av problemet. Vi modellerar också versioner av problemet med postberoende innehavskostnader. Vi presenterar resultat för det fall i vilket, för varje post, innehavskostnaden på destinationen är högre än den vid ursprunget. Om det omvända förhållandet gäller för alla poster kan en omvandling som liknar den som nämns ovan användas för att lösa problemet. Vi anser inte att det är det mest allmänna fallet där det är billigare att hålla vissa objekt vid ursprunget än vid destinationen, och det omvända innehar för de andra objekten. Den senare situationen kan till exempel uppstå om godset har olika temperaturkrav; lagringskostnaderna beror på vädret i omgivningen. Vårt problem liknar andra kapacitiva problem med fasta laddningsnät men innehåller tre viktiga komplicerande funktioner: (i) inte alla varor är tillgängliga i början av horisonten, dvs. varor anländer dynamiskt, (ii) det kan vara nödvändigt och/eller optimalt att skicka mer än ett fordon under en viss period, dvs. att ådra sig "multiple setups", och (iii) varor är inte homogena och har skilda förfallodatum på destinationen, och måste därför behandlas som separata kundorder. Vi antar dock att varorna är homogena när det gäller användningen av transportkapacitet. Även om det finns en stor mängd litteratur om lottningsproblem med en fast laddning struktur, lite arbete har gjorts på problem där det finns en Iwaniec (1979) stokastisk, dynamisk en nej ja Lee (1989) deterministisk, dynamisk en nej ja Ben- Kheder (1990) deterministisk, dynamisk multipel nej ja Vårt papper deterministiska, dynamiska en eller flera ja ja kapacitet i samband med varje fast laddning uppstår. Florian och Klein (1971) överväga en enda punkt kapaciated parti-sizing problem där alla material finns tillgängliga för bearbetning (eller, alternativt, för transport) i början av horisonten, och det finns en fast avgift för varje produktionskörning med fast kapacitet. Högst en produktionskörning är tillåten under varje period. De visar att när kapaciteten är konstant över tiden har den optimala lösningen en produktionsnivå som är lika med antingen noll eller kapaciteten under alla perioder utom högst en mellan två på varandra följande regenereringspunkter. (För Florian och Kleins problem definieras en regenereringspunkt som en punkt i tiden utan direkt inventering.) Detta resultat utgör grunden för ett effektivt lösningsförfarande baserat på ett underliggande problem med kortast möjliga väg. Lippman (1969) tar upp problemet med en enda produkt med statiska ankomster och flera inställningar. Han tar fram flera egenskaper hos den optimala lösningen och utvecklar en O T 3-algoritm för problemet. Vi relaterar hans karakterisering av den optimala lösningen till våra strukturella resultat allteftersom vår diskussion fortskrider. I en senare tidning behandlar Lippman (1971) en kontinuerlig, konstant behovsversion av problemet. Iwaniec (1979) studerar en bas aktiepolicy, avrundad upp till nästa fullfordon, i samband med en diskret tidsversion av problemet med stokastisk efterfrågan. Lee (1989) tar upp flera installationsproblem där alla material finns tillgängliga för leverans i början av horisonten och det finns en separat installationskostnad per order. Han presenterar ett OT4-förfarande för problemet. Alla ovannämnda artiklar behandlar endast en enda produkt. Den enda forskning som vi är medvetna om som behandlar multi-punkt fall (där posterna har olika innehavskostnader) i Ben-Kheder (1990). Han studerar fallet med dynamiska krav under antagandet att jordbrukskostnaden vid destinationen är högre än vid ursprunget. Han presenterar en lösning förfarande med en underliggande kortaste sökväg nätverk, där sökvägen kostnader beräknas med hjälp av en gren och-bundna algoritm. Tabell 1 ställer våra modeller i kontrast till andra i litteraturen. Observera att ingen av modellerna i litteraturen tillåter dynamiska ankomster av varor. Resten av tidningen är organiserad enligt följande. I §1 presenterar vi en dynamisk programmeringsformulering av problemet. I §2 karakteriserar vi den optimala lösningen och presenterar en optimal O T4-algoritm för det fall då alla varor har samma innehavskostnader, och innehavskostnaden är större på destinationen än vid ursprunget. Vi förklarar också hur förhållandet mellan de omvända innehavskostnaderna kan hanteras genom en lämplig omvandling av nätet. I §3 utökar vi dessa resultat för att möjliggöra poster med olika innehavskostnader. Avsnitt 4 avslutar dokumentet med en diskussion om relationen mellan våra resultat och de för relaterade modeller med statiska ankomster.
Yano och Newman REF föreslog en modell där tågscheman ska fastställas baserat på en dynamisk ankomst av gods till ursprung.
Scheduling Trains and Containers with Due Dates and Dynamic Arrivals
{'venue': 'Transportation Science', 'journal': 'Transportation Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}