I detta dokument utvecklar vi en intäktsförvaltningsmodell för att gemensamt fatta beslut om kapacitetstilldelning och överbokning över ett flygbolags nätverk. Vår strategi börjar med den dynamiska programmeringsformuleringen av problemet med kapacitetstilldelning och överbokning och använder en approximationsstrategi för att bryta ner den dynamiska programmeringsformuleringen av flygbenen. Denna sönderdelningsidé öppnar möjligheten att få ungefärliga lösningar genom att koncentrera sig på ett flygben i taget, men problemet med kapacitetstilldelning och överbokning som sker över ett enda flygben visar sig fortfarande vara oåtkomligt. Vi använder en statlig aggregeringsmetod för att få högkvalitativa lösningar på problemet med ett ben. Sammantaget bygger vår modell separata approximationer till värdefunktionerna, som kan användas för att fatta beslut om kapacitetstilldelning och överbokning för hela flygbolagets nätverk. Beräkningsförsök visar att vår modell presterar betydligt bättre än en mängd olika referensstrategier från litteraturen. Kapacitetstilldelning och överbokning är två huvudbeståndsdelar i förvaltningen av nätintäkter. I synnerhet behandlar kapacitetstilldelningen frågan om vilka resvägar som ska hållas öppna för köp och vilka resvägar som ska stängas eftersom återstående kapacitet på flygbenen uttöms med tiden med kundens inköp. Överbokning handlar om i vilken utsträckning försäljningen bör överstiga den fysiskt tillgängliga kapaciteten på flygbenen, med tanke på att inte alla med en bokning dyker upp vid avgångstiden. Besluten om kapacitetstilldelning och överbokning är i sig kopplade till varandra. Vilka prisklasser som ska göras tillgängliga för inköp beror på hur många platser som överstiger den fysiskt tillgängliga kapaciteten som flygbolaget är villigt att sälja. Å andra sidan, hur mycket att överboka beror på vilka resvägar flygbolaget håller öppet och sannolikheten att en kund som köper en bokning för en av de öppna resvägarna dyker upp vid avgångstiden. I detta dokument föreslår vi en intäktsförvaltningsmodell som gör den gemensamma kapacitetstilldelningen och överbokningsbeslut över ett flygbolags nätverk. Vårt tillvägagångssätt formulerar problemet som ett dynamiskt program och använder en approximationsstrategi för att bryta den dynamiska programmeringsformuleringen av flygbenen. Denna sönderdelningsidé öppnar möjligheten att få ungefärliga lösningar genom att koncentrera sig på ett flygben i taget, även om problemet med kapacitetstilldelning och överbokning som äger rum över ett enda flygben fortfarande är oåtkomligt. Statvariabeln i den dynamiska programmeringsformuleringen av problemet med ett enda ben omfattar ett stort antal dimensioner i praktiska tillämpningar. Vi övervinner denna svårighet genom att använda statsaggregation för att få högkvalitativa lösningar på problemet med kapacitetstilldelning och överbokning. I slutändan ger vår modell separata approximationer till värdefunktionerna, som kan användas för att konstruera en kapacitetstilldelning och överbokningspolicy för hela flygbolagets nätverk. Vårt arbete i denna artikel bygger på två strömningar av litteratur. Den första strömmen av litteratur är arbetet med dynamiska programplaneringsnedbrytningsmetoder i nätverksintäktshanteringen. Dynamisk programmering nedbrytningsmetoder går tillbaka till Belobaba (1987) och de är ungefärliga metoder som syftar till att bryta ner nätet intäktshantering problem av flygbenen. Den grundläggande tanken är att koppla ihop en deplacement justerat pris med varje resplan över varje flygben, vilket skiljer sig från det faktiska priset som flygbolaget tar ut. De ändrade biljettpriserna gör att vi omedelbart kan lösa en sekvens av inkomsthanteringsproblem i ett ben. När det gäller problemet med inkomsthantering på ett enda ben, som äger rum över ett visst flygben, koncentrerar vi oss bara på den återstående kapaciteten på detta flygben och antar att de biljettpriser som är förknippade med resvägarna är lika med de förskjutningsjusterade biljettpriserna för detta flygben. När vi har löst problemet med ett enda ben över varje flygben, lägger vi ihop de värdefunktioner som erhållits för olika flygben för att få åtskiljbara approximationer till värdefunktionerna. I detta dokument använder vi en liknande idé för att bryta kapacitetstilldelningen och överbokningsproblemen. Den viktiga skillnaden i vårt papper är att vi uttryckligen behandlar överbokning, medan de tidigare sönderdelningsmetoderna uteslutande fungerar under antagandet att överbokning inte är möjlig och alla reservationer visas vid avgångstiden. Vår utvidgning till överbokning är icke-trivial och har viktiga praktiska konsekvenser eftersom överbokning spelar en viktig roll i flygbolagens verksamhet. Den andra ström av litteratur som vi använder oss av är arbetet med att lösa problemet med kapacitetstilldelning och överbokning över ett enda flygben. Denna ström av litteratur blir särskilt användbar 2 när vi försöker lösa den enda ben kapacitet tilldelning och overbooking problem efter att bryta det ursprungliga problemet. Som nämnts ovan är problemet med kapacitetstilldelning och överbokning av ett enda ben oåtkomligt, eftersom dess dynamiska programmeringsformulering innebär en högdimensionell tillståndsvariabel. För att kunna lösa detta problem bygger vi på det tillvägagångssätt som föreslagits av Subramanian et al. (1999)................................................................................................ Vi utgår särskilt från att de andelar av reservationerna som vi har för olika resvägar är fastställda och kända. Detta gör att vi kan hålla reda på endast det totala antalet reservationer, snarare än antalet reservationer för varje resplan, i vår dynamiska programmering formulering. I detta fall kollapsar tillståndsvariabeln i den dynamiska programmeringsformuleringen av problemet med ett ben till en skalar och den dynamiska programmeringsformuleringen blir dragbar. I detta dokument gör vi följande forskningsbidrag. 1) Vi utvecklar en modell för att fatta beslut om kapacitetstilldelning och överbokning över ett flygbolags nätverk. Tanken bakom vår modell är att bryta ner problemet med flygbenen och lösa en sekvens av problem med ett ben. 2) Vi visar att vår strategi ger en övre gräns för den optimala totala förväntade vinsten så länge vi kan lösa problemen med enkelbenet på ett korrekt sätt. 3) Vi konstaterar dock att problemet med kapacitetstilldelning och överbokning över ett enda flygben fortfarande är oåtkomligt, och visar hur vi kan få ungefärliga lösningar på problemen med ett enda ben på ett dragbart sätt. 4) Beräkningsförsök visar att vår modell presterar betydligt bättre än många av de befintliga modellerna i litteraturen. Resten av tidningen är organiserad enligt följande. I Avsnitt 1 går vi igenom den andra litteraturen som är relaterad till vårt arbete. I avsnitt 2 ger vi en dynamisk programmeringsformulering för kapacitetstilldelning och överbokningsproblem över ett flygbolags nätverk. I Avsnitt 3 ger vi ett enkelt deterministiskt linjärt program som kan användas för att utveckla kontrollpolicyer. I Avsnitt 4 beskriver vi vår modell med hjälp av det deterministiska linjära programmet som utgångspunkt. I sektion 5 presenterar vi våra beräkningsexperiment. I avsnitt 6 ger vi slutkommentarer. Trots att det finns omfattande litteratur om kapacitetstilldelning över ett flygbolags nät studeras inte samspelet mellan kapacitetstilldelning och överbokning ingående. Tidiga modeller fokuserar på den enbenta versionen av problemet. Beckmann (1958), Thompson (1961) och Coughlan (1999) utvecklar enbenskapacitetstilldelning och överbokningsmodeller under antagandet att kraven från olika prisklasser är statiska slumpvariabler. Dessa modeller bortser från den tidsmässiga dynamiken i efterfrågeprocessen och deras mål är att bestämma hur många platser som ska fördelas till olika prisklasser. Senare modeller av Chatwin (1992), Chatwin (1999) och Subramanian et al. (1999) tar också hänsyn till problemet med ett enda ben, men de försöker fånga dynamiken i efterfrågeprocessen mer exakt. Subramanskt m.fl. (1999) noterar att den dynamiska utformningen av programplaneringen av problemet med ett enda ben är svåråtkomlig och föreslår den tillnärmningsstrategi som vi bygger vidare på i detta dokument. Det är viktigt att jämföra deras iakttagelse med problemet med tilldelning av kapacitet utan överbokning. Om överbokning inte är tillåten, då den dynamiska programmeringsformuleringen av problemet kapacitetstilldelning innebär en skalär tillståndsvariabel och kan enkelt lösas. Därför medför möjligheten att överboka, i sig själv, icke-triviala utmaningar även för enskilda fall. Karaesmen och van Ryzin (2004b) beskriver en 3 overbooking modell för flera flygben som fungerar mellan samma ursprung destination par och kan fungera som substitut för varandra. Det finns några papper som tar hänsyn till överbokningsbesluten över ett flygbolags nätverk. En populär metod för att fatta beslut om kapacitetstilldelning i nätintäktshanteringsproblem är att lösa ett deterministiskt linjärt program. Detta linjära program är byggt under antagandet att resplanen förfrågningar är kända i förväg och de antar sina förväntade värden. Det finns en begränsning i samband med varje flygben i det linjära programmet och de högra sidorna av dessa begränsningar är benkapaciteten. De optimala värdena för de dubbla variabler som är förknippade med dessa begränsningar används därför för att uppskatta alternativkostnaden för en sittplats på olika flygben. I detta fall kan man utforma en policy för kapacitetskontroll, där biljettpriset från en begäran om resväg jämförs med den totala alternativkostnaden för den kapacitet som skulle förbrukas av denna begäran om resväg. Om biljettpriset överstiger den totala alternativkostnaden, då resplan begäran godtas. Det finns många varianter av den linjära programmeringsidén och avsnitt 3.3 i Talluri och van Ryzin (2004) beskriver dessa varianter. Vi går inte in på detaljerna i dessa varianter, eftersom de flesta av dem endast handlar om beslut om kapacitetstilldelning. Bertsimas och Popescu (2003) visar dock hur man bygger ett deterministiskt linjärt program för att hantera overbooking och inga shower. Vi använder en variant av deras deterministiska linjära program som en referensstrategi i våra beräkningsexperiment. Karaesmen och van Ryzin (2004a) utvecklar en kapacitetstilldelning och överbokningsmodell, där de beräknar bokningsgränser genom att använda det optimala objektiva värdet av det deterministiska linjära programmet som en uppskattning av de totala förväntade intäkterna från resplansförfrågningar. Gallego och van Ryzin (1997) ger teoretiskt stöd till det deterministiska linjära programmet genom att visa att den kontrollpolitik som erhålls från en variant av det deterministiska linjära programmet är asymptotiskt optimal eftersom benkapaciteten och det förväntade antalet resplaner ökar linjärt i samma takt. Kleywegt (2001) konstruerar en pris- och överbokningsmodell i kontinuerlig tid. Den efterfrågeprocess som han använder är deterministisk och han använder Lagrangian dualitet för att lösa modellen. Litteraturen om nedbrytning av problem med förvaltning av nätintäkter är också relaterad till vårt dokument. Williamson (1992) är en av de första som bryter ner problemet med förvaltningen av nätets intäkter genom flygbenen. Hennes mål är att tillämpa Belobabas förväntade inkomstheuristiska marginalplats (1987) på varje flygben var för sig för att konstruera approximationer av värdefunktionen. Avsnitt 3.4.4 i Talluri och van Ryzin (2004) beskriver en mer förfinad variant av hennes tillvägagångssätt i den meningen att denna variant inte förutsätter att efterfrågan från olika prisklasser kommer över icke-överlappande tidsintervall. Liu och van Ryzin (2008) och Bront et al. (2008) visar hur man utökar nedbrytningsmetoder för att ta itu med kundernas val beteende bland de olika resvägar som är tillgängliga för köp. Topaloglu (2006) visar att nedbrytningsmetoder kan visualiseras som en tillämpning av Lagrangian avkoppling till den dynamiska programmering formulering av nätverket intäktshantering problem. Kunnumkal och Topaloglu (2007) visar att det är möjligt att utöka observationer av Topaloglu (2006) för att ta itu med kundernas val beteende. Det pågår nyligen en del arbete med att bryta ner kapacitetstilldelningen och överbokningsproblemen över ett flygbolags nätverk. Erdelyi och Topaloglu (2009) använder separerbara funktioner för att approximera värdefunktionerna i den dynamiska programmeringsformuleringen av kapacitetstilldelning och överbokningsproblem. I detta avseende är deras papper kopplat till vårt arbete. Deras approximationer kan dock särskiljas från resvägarna och antalet skalärfunktioner de har är lika många som antalet möjliga resvägar. Däremot är våra approximationer åtskilda av flygbenen och antalet skalärfunktioner vi har är lika med antalet flygben. Antalet flygben är i allmänhet mindre än antalet resvägar. Dessutom använder de simulering för att konstruera sina skalära funktioner, medan vi löser små dynamiska program för att konstruera vår värdefunktion approximationer. Vi använder deras modell som en referensstrategi. Det finns nyligen tillvägagångssätt för problemet med kapacitetstilldelning över ett flygbolags nät. Adelman (2007) använder linjära värdefunktions approximationer för kapacitetstilldelningsproblem och han väljer sluttningarna och avläsningarna av värdefunktionens approximationer genom att lösa ett linjärt program som representerar problemets dynamiska programmeringsformulering. Zhang och Adelman (2006) utvidgar detta tillvägagångssätt för att hantera kundernas val beteende. De visar också att nedbrytningsmetoder kan ge övre gränser för optimala totala förväntade intäkter. Meissner och Strauss (2008) förfinar det tillvägagångssätt som föreslagits av Adelman (2007) genom att använda linjära approximationer. En viktig fördel med de senaste tillvägagångssätten är att de ger övre gränser för de optimala totala förväntade intäkterna. De senaste strategierna tar dock inte upp samspelet mellan kapacitetstilldelning och överbokning och målet med vårt dokument är att fylla denna lucka. Vi anser att en uppsättning flygben över ett flygbolag nätverk som kan användas för att tjäna resplanen önskemål anländer slumpmässigt över tiden. Vid varje tidpunkt anländer en begäran om resväg och vi måste besluta om vi ska godta eller avslå denna begäran om resväg. En godkänd resplan blir en reservation, medan en avvisad resplan helt enkelt lämnar systemet. Vid avgångstiden för flygbenen dyker en viss del av bokningen upp och vi måste besluta vilken av dessa bokningar som ska tillåtas ombordstigning. Målet är att maximera den totala förväntade vinsten som definieras som skillnaden mellan de förväntade intäkter som erhålls genom att acceptera begäran om resväg och den förväntade påföljdskostnad som uppstår genom att neka ombordstigning till reservationer. Den uppsättning flygben är L och uppsättningen av resvägar är J. Vi noterar att ett flygben kallas en resurs och en resplan kallas en produkt i vissa inställningar. Problemet äger rum över den ändliga planeringshorisonten {τ,. .......................... Resplan begäran anländer över tidsperioderna T = {τ,. .., 1} och flygningarna avgår vid tidpunkt 0. Sannolikheten att det finns en begäran om resplan j vid tidsperiod t är p jt. Att acceptera en begäran om resplan j genererar en intäkt på f j och denna bokning visar upp vid avgångstidpunkten med sannolikhet q j. Om en bokning för resplan j dyker upp vid avgångstiden och det nekas ombordstigning, då vi ådrar oss förneka straffkostnad för j. Om vi tillåter ombordstigning till en bokning för resplan j, då vi förbrukar en ij enheter kapacitet på flygben i. Kapaciteten på flygbenet i är c i. Vi utgår från att ankomsten av resplan begäran vid olika tidsperioder och uppvisningen beslut av olika reservationer vid avgångstiden är oberoende. Vi antar också att reservationerna inte ställs in över tidsperioder {τ,. ., 1} och vi ger inte återbetalning till no shows, men dessa antaganden är för korthet och man kan göra förlängningar för att ta itu med inställda och återbetalningar. Vi låter x jt betecknar det totala antalet bokningar för resplan j i början av tidsperioden t så att x t = {x jt : j  till J } fångar läget för reservationerna. Om man antar att antalet 5 bokningar för resplan j i början av tidsperioden 0 är x j0, Vi använder S j (x j0 ) för att beteckna antalet bokningar för resplan j som dyker upp vid avgångstiden. Med tanke på antagandet att visa upp beslut av olika reservationer är oberoende, S j (x j0 ) har en binomial fördelning med parametrar (x j0, q j ). Om vi använder S(x 0 ) = {S j (x j0 ) : j  till J } för att beteckna tillståndet för de reservationer som visar upp vid avgångstiden, då kan vi beräkna straffkostnaden i samband med de nekade reservationer genom att lösa problemet där w j är antalet bokningar för resplan j att vi nekar ombordstigning. Problemets objektiva funktion motsvarar de påföljdskostnader som är förknippade med de avvisade reservationerna. Restriktioner (2) säkerställa att de reservationer som vi tillåter ombordstigning inte överstiger benkapaciteten, medan begränsningar (3) säkerställer att antalet nekade reservationer inte överstiger antalet reservationer som visas vid avgångstiden. Det är viktigt att konstatera att problemet (1)- (4) förutsätter att vi gemensamt kan avgöra vilka reservationer som bör nekas ombordstigning i hela nätet, och detta kan vara ett optimistiskt antagande. Att låta e j vara den dimensionella enhetsvektorn med en i elementet som motsvarar j, kan vi hitta den optimala policyn genom att beräkna värdefunktionerna genom optimalitetsekvationen med gränstillståndet att V 0 (x 0 ) = −E{(S(x 0 ))}. I detta fall, om läget för reservationer i början av tidsperioden t ges av x t, då är det optimalt att acceptera en begäran om resplan j vid tidpunkten period t när Tyvärr, även för blygsamma applikationer, staten vektorn x t innebär hundratals dimensioner rendering exakt lösning till den optimala ekvationen i (5) beräkningsbart intractable. I nästa avsnitt börjar vi med att beskriva en ungefärlig lösningsmetod som innebär att lösa ett deterministiskt linjärt program. Därefter bygger vi på det deterministiska linjära programmet för att utveckla en mer sofistikerad approximativ lösningsmetod. En standardlösningsmetod för nätverkets intäktshanteringsproblem som beskrivs i föregående avsnitt handlar om att lösa ett deterministiskt linjärt program. Detta linjära program är formulerat under antagandet att ankomsten av resplan begäran och uppvisningen beslut reservationer tar på sina förväntade värden. I synnerhet, om vi låter z j vara antalet förfrågningar om resplan j att vi 6 planerar att acceptera över planeringshorisonten och w j vara antalet reservationer som vi planerar att neka ombordstigning, då detta linjära program kan formuleras som i problemet ovan, vi antar att om vi accepterar z j förfrågningar om resplan j, sedan q j z j bokningar för resplan j visa upp vid avgångstiden. Restriktioner (8) säkerställer att antalet bokningar som vi tillåter ombordstigning inte överstiger benkapaciteten. Restriktioner (9) säkerställer att antalet ansökningar om resväg som vi accepterar inte överstiger det förväntade antalet ansökningar om resväg. Restriktioner (10) säkerställer att antalet nekade reservationer inte överstiger det förväntade antalet bokningar som visas vid avgångstiden. Den deterministiska linjära programmeringsformuleringen för problemet med förvaltning av nätintäkter är allmänt känd under antagandet att överbokning inte är möjlig och alla reservationer visas vid avgångstiden, se Talluri och van Ryzin (1998). Problem (7)- (11) utvidgar denna formulering till att hantera overbooking och inga shower. Även om denna förlängning är ganska intuitiv, så är Bertsimas och Popescu (2003) den enda hänvisningen till denna förlängning. En användning av problemet (7)– (11) är att dess dubbla lösning kan användas för att utforma en policy för att godta eller avslå begäran om färdväg. Låta {λ * i : i  på L} vara optimala värden för de dubbla variabler som är förknippade med begränsningar (8) i problem (7)-(11), är tanken att använda λ * i för att uppskatta alternativkostnaden för en kapacitetsenhet på flygben i. I detta fall, om intäkterna från en resplan begäran överstiger den totala förväntade alternativkostnaden för den kapacitet som förbrukas av denna resplan begäran eller om intäkterna från en resplan begäran överstiger den förväntade straffkostnaden, då accepterar vi resplan begäran. Med andra ord, om vi har då accepterar vi en begäran om resplan j. De två argumenten från min\·, ·} operatör ovan fångar två effekter. Om den totala förväntade alternativkostnaden för den kapacitet som förbrukas av en begäran om resplan j är liten nog att vi har f j ≥ q j i och L a ij λ * i, då vi accepterar en begäran om resplan j. Dessutom, om vi har f j ≥ q j  på j, då kan vi generera intäkter, i förväntan, helt enkelt genom att acceptera en begäran om resplan j och neka ombordstigning till denna bokning vid avgångstiden. Vi hänvisar till beslutsregeln i (12) som DLP-policyn, som står för deterministiskt linjärt program. Denna beslutsregel används också av Bertsimas och Popescu (2003). En annan användning av problem (7)- (11) är att dess optimala objektiva värde ger en övre gräns för den optimala totala förväntade vinsten. Med andra ord, låta z LP vara det optimala objektiva värdet av problemet (7)-(11) och0 vara den  på J  på dimensional vektorn av nollor, är det möjligt att visa att V τ (0) ≤ z LP. För 7 framtida referens anger vi detta resultat som ett förslag nedan. Beviset för detta förslag finns i Erdelyi och Topaloglu (2009). Den övre gränsen i proposition 1 kan vara användbar vid bedömning av det optimala gapet i en suboptimal beslutsregel som DLP-policyn i (12). Det finns flera brister i det deterministiska linjära programmet. Den använder bara det totala förväntade antalet resruttsförfrågningar, utan att bry sig om sannolikhetsfördelningen och temporal dynamiken i ankomsten av resplansförfrågningar. Dessutom utgår man från att det antal reservationer som dyker upp vid avgångstiden tar hänsyn till deras förväntade värden. I detta avsnitt bygger vi på det deterministiska linjära programmet för att utveckla en lösningsmetod som fångar tidsdynamiken i resplanen begär något mer exakt. Utgångspunkten för vårt tillvägagångssätt är ett duality argument om det deterministiska linjära programmet för att bryta ner problemet med nätintäktshantering i en sekvens av problem med enbent intäktshantering. Vi börjar låta {λ * i : i  på L} vara de optimala värdena för de dubbla variabler som är förknippade med begränsningar (8) i problem (7)-(11). Vi väljer ett godtyckligt flygben i och slappna av begränsningar (8) i problem (7)-(11) för alla andra flygben genom att koppla ihop de dubbla multiplikatorerna {λ * l : l  till L\ {i}}. I detta fall innebär linjär programmering dualitet att problemet (7)-(11) har samma optimala objektiva värde som problemet Vi noterar att problemet ovan inkluderar kapacitetsbegränsningen endast för flygben i. När det gäller notationell korthet låter vi ρ utelämna den konstanta termen l till L\ {i} λ * l c l, vi skriver problemet ovan som föremål för (9), (10), (11), 8 i vilket fall, det optimala objektiva värdet av problem (14)- (16) Beslutsvariablerna z j och w j inte visas i begränsning (15) när resplan j inte använder kapaciteten på flygben i. Denna observation gör det möjligt för oss att bryta ner problem (14)-(16) i två problem, varav det ena inbegriper resvägarna som använder kapaciteten på flygbenet i och det andra inbegriper de återstående resvägarna. I detta syfte låter vi J i = {j  till J : a ij > 0} så att J i är den uppsättning resvägar som använder kapaciteten på flygben i. I detta fall är det lätt att se att det optimala objektiva värdet av problemet (14) (16) är lika med summan av de optimala objektiva värdena för det problem som är föremål för vilket endast beslutsvariabler {z j : j  och J i } och {w j : j  och J i }, och det problem som endast omfattar beslutsvariabler {z j : j  till J \ J i } och {w j : j  till J \ J i }. Det visar sig att problemets optimala objektiva värde (22)- (25) lätt kan uppnås genom enbart inspektion. I synnerhet visar vi i bilaga A att det optimala objektiva värdet av problemet (22)- (25) är lika med. Därför, sammanfatta diskussionen hittills i detta avsnitt, om vi låter z i LP vara det optimala objektiva värdet av problem (17- (21), då har vi jämförelse problem (17- (21) med problem (7)- (11), kan vi observera att problemet (17- (21) är det deterministiska linjära programmet som motsvarar ett enda ben intäktshantering problem som äger rum över flygben i. I denna enda ben intäktsförvaltning problem, endast förfrågningar om resvägar i uppsättningen J i beaktas. Om vi accepterar en begäran om resplan j, då genererar vi en inkomst av F i j. Om vi nekar ombordstigning till en bokning för resplan j, då vi ådrar oss en påföljd kostnad av i j. Att notera att det optimala objektiva värdet av problem (17)- (21) betecknas av z i LP, Proposition 1 innebär att z i LP ger en övre gräns på den optimala totala förväntade vinsten för den enda ben intäktshantering problem som sker över flygben i. Å andra sidan kan vi beräkna den optimala totala förväntade vinsten för ovan beskrivna enskilda ben intäktshantering problem som äger rum över flygben i genom att lösa motsvarande dynamiska program. I detta syfte introducerar vi en ny notation. Vi låter R i (·) vara den operatör som begränsar komponenterna i en "J" dimensional vektor till de som motsvarar de delar av J i. Till exempel har vi R i (x t ) = {x jt : j  till J i } och R i (S(x 0 )) = {S j (x j0 ) : j  till J i }. I detta fall, optimalitet ekvationen för det enda benet intäktshantering problem som äger rum över flygbenet i läser (27) med gränsvillkoret att Här, ρ i (·) står för påföljdskostnaden för nekad ombordstigning vid avgångstiden i det enda benet intäktshantering problem som sker över flygben i och det ges genom förbehåll för Vi kommer ihåg att z i LP ger en övre gräns på den optimala totala förväntade vinsten för det enda benet intäktshantering problem som äger rum över flygben i. Denna optimala totala förväntade vinst ges av V i τ (R i (0)) så att vi får V i τ (R i (0)) ≤ z i LP. Nästa förslag visar sambandet mellan lösningarna och optimala ekvationer i (5) och (27). Dess bevis finns i bilaga B. Använda Proposition 2 med t = τ och x t = 0, diskussionen strax innan detta förslag innebär att där den sista jämställdhet följer från (26). Därför kan vi få en övre gräns på den optimala totala förväntade vinsten genom att lösa den optimala ekvationen i (27) och denna övre gräns är snävare än den som tillhandahålls av det optimala objektiva värdet av problem (7)- (11). Icke desto mindre har tillståndsvariabeln i 10 optimalitetsekvationen i (27) fortfarande dimensioner, som kan vara ganska stor för många praktiska tillämpningar. Innan vi beskriver en metod för att approximera lösningen till denna optimalitetsekvation tar vi en snabb omväg i nästa avsnitt och beskriver hur vi kan använda den övre gränsen i Proposition 2 för att konstruera en policy för att acceptera eller avvisa resplansförfrågningar. Proposition 2 föreslår en approximering av V t (x t ) med den övre gräns som ges av uttrycket på höger sida av (32). I synnerhet med hjälp av t (x t ) för att beteckna uttrycket på höger sida av (32), kan vi ersätta V t-1 (x t ) − V t-1 (x t + e j ) i beslutsregeln i (6) med i t-1 (x t ) − till i t-1 (x t + e j ) och följa denna beslutsregel för att acceptera eller avslå begäran om färdväg. En tvetydig aspekt av detta tillvägagångssätt är att valet av flygben i är godtyckligt och att genomförandet av den föreslagna beslutsregeln kan bero på valet av detta flygben. Vi arbetar runt denna tvetydighet genom att computing { ska i t (·) : t  på T} för alla i  på L så att vi kan använda den genomsnittliga i till L till t (x t ) / till L som en approximation till V t (x t ). Observera att i t (x t ) ≥ V t (x t ) för alla i  på L, har vi fortfarande den övre gränsen som i till L till i t (x t ) / till L till ≥ V t (x t ). Därför föreslår vi en approximering av V t- 1 (x t ) − V t- 1 (x t + e j ) på höger sida av (6) av i- L- 1 (x t )/- L- 2 i- 1 (x t + e j )/- L. Definitionen av t (x t ) i (32) innebär därför att låta 1·) vara indikator funktion, om tillståndet för reservationer vid tidpunkten t ges av x t, då vi accepterar en begäran om resplan j när vi har ett möjligt sätt att titta på beslutsregeln i (33) är att varje flygben bidrar en term till uttrycket på höger sida. Om flygbenet i används av resplan j, då detta flygben bidrar med termen Om, å andra sidan, flygbenet i inte används av resplan j, då detta flygben bidrar med termen min{q j l en lj λ * l, q j }. Den viktiga iakttagelsen är att termen min{q j l på L a lj λ * l, q j j } är identisk med den högra sidan av DLP-policyn i (12). Därför ger de flygben som inte används av resplan j inte någon ytterligare information om vad som redan tillhandahålls av det deterministiska linjära programmet. Dessutom kommer antalet flygben som inte används av resplan j sannolikt att vara betydligt större än antalet flygben som används av resplan j, vilket innebär att den högra sidan av uttrycket ovan sannolikt kommer att domineras av termen min{q j l på L a lj λ * l, q j j }. Således antar man att beslutsregeln i (33) fungerar mycket likt DLP-politiken. En liten uppsättning beräkningsexperiment bekräftade detta antagande. För att övervinna denna brist, i stället för att genomsnitt över alla flygben och med hjälp av i pål i t (x t ) / pål som en approximation till V t (x t ), vi genomsnitt endast över de flygben som används av en viss resplan. I synnerhet låter vi L j = {i  på L : a ij > 0} så att L j är den uppsättning flygben som används av resplan j. I det här fallet, när vi behöver fatta ett beslut för resplan j, använder vi i.L j på t (x t ) / till L j  på en approximation till V t (x t ). Vi noterar att vi fortfarande har den övre gränsen som i och med att i i t (x t ) / till L j  till ≥ V t (x t ). Således, om tillståndet för reservationer vid tidpunkten t ges av x t, då vi accepterar en begäran om resplan j när vi har Tillståndsvariabeln i den optimala ekvationen i (27) har  till J i  på dimensioner. Teoretiskt sett är detta en förbättring i jämförelse med optimalitetsekvationen i (5), vilket innebär en tillståndsvariabel med dimensioner. Praktiskt taget är dock denna förbättring irrelevant eftersom  på beställning av hundratals eller tusentals även för blygsamma tillämpningar. Därför är det fortfarande ganska svårt att beräkna värdefunktionerna {V i t (·): t  på T } och att använda beslutsregeln i (34). I nästa avsnitt ger vi en metod för att approximera värdefunktionerna {V i t (·) : t  på T }, som verkar fungera särskilt bra för vårt applikationssammanhang. I detta avsnitt anser vi att problemet med inkomsthantering med ett enda ben som äger rum över flygbenet i vars dynamiska programmeringsformulering ges i (27). Vårt mål är att approximera värdefunktionerna {V i t (·) : t  på T} genom att använda enkla skalorfunktioner. Vi observerar att den optimala ekvationen i (27) måste hålla reda på "identiteterna" i reservationerna så att den straffkostnad som ges av det optimala objektiva värdet av problem (28)-(31) kan beräknas korrekt. Å andra sidan, om vi antar att veta det totala antalet reservationer är tillräckligt för att beräkna påföljdskostnaden, då staten variabel i optimalitet ekvationen i (27) kollapsar till en skalar. Vår approximation bygger på denna iakttagelse och bygger på en approximation av den förväntade straffkostnaden vid avgångstiden genom att endast använda det totala antalet reservationer. Vi börjar med att införa en ny notation. Vi använder A i (·) för att beteckna den operatör som lägger upp komponenterna i en  på J  på dimensional vektor som motsvarar elementen i den uppsättning J i. Till exempel har vi A i (x t ) = j till J i x jt och A i (x t ) är det totala antalet bokningar i början av tidsperioden t för de resvägar som använder flygben i. Vår approximation bygger på antagandet att om vi har totalt A i (x 0 ) reservationer i början av tidsperiod 0 för resvägar som använder flygben i, sedan en fast del, säger α i j, av dessa bokningar är för resplan j. I detta fall, erinrar om att den slumpmässiga variabeln S j (·) fångar antalet bokningar för resplan j som visar upp vid avgångstiden och definierar vektorerna kan vi approxima påföljdskostnaden vid avgångstiden av Ε i (S i (α i A i (x 0 ))). I detta uttryck, vektorn α i A i (x 0 ) ungefärliga antalet reservationer som vi har i början av tidsperioden 0, medan vektorn S i (α i A i (x 0 )) ger antalet bokningar som visar upp vid avgångstiden. Funktionen i (·) ges av det optimala objektiva värdet av problemet (28)- (31) och den beräknar påföljdskostnaden för problemet med inkomsthantering i det enskilda benet som äger rum över flygbenet i. Denna approximation till straffkostnaden vid avgång 12 gånger, i sin tur, gör att vi kan approximera lösningen till optimalitetsekvationen i (27) genom att använda lösningen till optimalitetsekvationen (35) med gränsvillkoret att Vi noterar att optimalitetsekvationen ovan innebär en skalarstatsvariabel och det kan lösas ganska effektivt. Det finns tre frågor som behöver lösas för att kunna hitta en numerisk lösning på den optimala ekvationen i (35). Den första frågan är relaterad till valet av α i j. Vi använder DLP-policyn i (12) för detta ändamål. I synnerhet simulerar vi utvecklingen av DLP-policyn under M resplan begäran förverkligar. Låta {x m jt : j  till J, t  till T } vara den statliga banan i mth resplan begäran förverkliga, vi låter I praktiken är det vanligt att använda DLP-policyn för att komma fram med en genomsnittlig sannolikhet att en bokning visar upp vid avgångstiden. Vårt val av α i j följer noga detta tillvägagångssätt. Den andra frågan uppstår på grund av det faktum att argumentet om S j (·) i vektorn ) är en binomially distribuerad slumpmässig variabel med parametrar (x j0, q j ), men en binomially distribuerad slumpmässig variabel med en fraktionerad försök parameter är dåligt definierad. Vi övervinna denna fråga genom att alltid visualisera S j (x j0 ) som en blandning av två binomially fördelade slumpvariabler. I synnerhet, låta · vara avrundning funktion, med sannolikhet x j0 + 1 − x j0, S j (x j0 ) är lika med en binomially distribuerad slumpmässig variabel med parametrar ( x j0, q j ), och med sannolikhet x j0 − x j0, S j (x j0 ) är lika med en binomially distribuerad slumpmässig variabel med parametrar ( x j0 + 1, q j ). Med denna konvention, om x j0 är heltal, då S j (x j0 ) fortsätter att vara binomially distribueras med parametrar (x j0, q j ). Om, dock, x j0 är fraktionerat, då S j (x j0 ) inte nödvändigtvis binomialt distribueras, men dess förväntade värde fortsätter att vara ( Slutligen, den tredje frågan blir uppenbar när vi noterar att gränstillståndet för optimalitet ekvation i (35) kräver datorförväntning ). Det finns inget slutet formuttryck för denna förväntan och vi bara approximerar det genom Monte Carlo prover. När vi är överens om att lösa de tre frågor som beskrivs ovan, kan vi få {v i t (·) : i  på L, t T } genom optimalitetsekvationen i (35) och använda {v i t (·) : i  på L, t T } som approximationer till {V it (·) : i  på L, t T } i beslutsregeln i (34). I synnerhet, om läget för reservationerna i början av tidsperioden t ges av x t, då vi accepterar en begäran om resplan j när vi har Vi hänvisar till denna beslutsregel som DPD politik, som står för dynamisk programmering nedbrytning. 13 I detta avsnitt jämför vi resultaten av beslutsreglerna i (12) och (36) tillsammans med andra referensstrategier. Vi börjar med att beskriva det experimentella upplägget och riktmärkesstrategierna. Därefter presenterar vi våra beräkningsresultat. Vi anser att ett flygbolag nätverk som består av ett nav och N ekrar. Detta är en viktig nätverksstruktur som ofta uppstår i praktiken. Det finns två flygben i samband med varje talade. En av dessa är från navet till talade, medan den andra är från talade till navet. Flygbolaget erbjuder ett högt pris och en låg biljettväg i samband med varje ursprung destination par. Därför är antalet flygben 2N och antalet resvägar 2N (N + 1). Det biljettpris som är förknippat med en hög biljettväg är δ gånger det biljettpris som är förknippat med motsvarande lågprisrutt. Påföljden för att neka ombordstigning till en bokning för resplan j ges av  ska j = δ f j + σ max{f : ska J }, där δ och σ är två parametrar som vi ändrar. Sannolikheten för att en bokning dyker upp vid avgångstiden är q och det beror inte på resplanen. Med tanke på att den totala förväntade efterfrågan på kapaciteten på flygbenet i ges av q t och J a ij p jt, mäter vi tätheten hos benkapaciteten genom att vi anger våra testproblem genom att (N, σ, σ, q, ρ) och använda N  till {4, 8}, ε till {4, 8}, (δ, σ) till {(4, 0), (8, 0), (1, 1)}, q 0.90, 0.95} och ρ till {1.2, 1.6}. Detta ger 48 testproblem för vår experimentella installation. I alla våra testproblem har vi τ = 240. Online-tillägget ger datafiler för alla våra testproblem. Vi beskriver formatet på datafilerna i bilaga C. Det är värt att notera att samspelet mellan δ och (σ, σ) skapar intressanta situationer. Till exempel, när vi har σ = 8 och (δ, σ) = (4, 0), om intäkterna i samband med en låg biljettväg är f, då straffkostnaden i samband med denna resplan är 4f och intäkterna i samband med motsvarande hög biljettväg är 8f. I detta fall, om vi har en begäran om den höga biljetten resplanen och ett flygben i denna resplan redan överbokas med en bokning för den låga biljetten resplanen, då kan vi fortfarande acceptera den höga biljetten resplan begäran och neka ombordstigning till den låga biljettbokningen för att göra en nettovinst på 8f - 4f. Detta motsvarar det fall då en färdväg med höga biljettpriser på ett trivialt sätt förhindrar motsvarande färdväg med låga biljettpriser. Å andra sidan, när vi har σ = 4 och (σ, σ) = (1, 1), sådana företräden förekommer inte. Vi noterar också att testproblemen med (σ, σ) = (1, 1) tenderar att ha högre straffkostnader än testproblemen med (σ, σ) = (8, 0), som i sin tur tenderar att ha högre straffkostnader än testproblemen med (σ, σ) = (4, 0). Vi jämför resultaten av följande sju referensstrategier. Denna referensstrategi motsvarar den DPD-policy som gavs av (36). Vi använder M = 100 vid beräkning {α i j : i  på L, j  på J }. Vi uppskattar alla 14 förväntningar genom 1000 Monte Carlo prover. Med dessa inställningar, 95% konfidensintervall för förväntan av α i j har precision  och 4,1% i genomsnitt, medan 95% konfidensintervall för den förväntade straffkostnad som uppstår vid avgångstidpunkten har precision  och 1,8% i genomsnitt. Denna referensstrategi motsvarar DLP-policyn i (12). Den grundläggande varianten av denna strategi löser helt enkelt problem (7)– (11) för att uppnå optimala värden för de dubbla variabler som är förknippade med begränsningar (8) och använder dessa dubbla variabler för att genomföra DLP-politiken. Vi använder en omoptimerad variant av denna strategi, där vi delar upp planeringshorisonten i K lika segment och löser en uppdaterad version av problem (7)- (11) för varje segment. Särskilt med tanke på att läget för reservationerna i början av kth-segmentet är x τ (K‐k+1)/K, ersätter vi den högra sidan av begränsningar (8) med {c i − j-j a ij j x j,τ (K‐k+1)/K : i-L}, den högra sidan av begränsningar (9) med { τ (K‐k+1)/K t=1 p-jt : j-J } och den högra sidan av begränsningar (10) med {q j x j,τ (K‐k+1)/K : j-J } och lösa denna ändrade version av problem (7)- (11). Låta {λ * i : i  på L} vara de optimala värdena för de dubbla variabler som är förknippade med begränsningar (8), använder vi dessa uppdaterade värden i beslutsregeln i (12) tills vi löser problem (7)- (11) i början av nästa segment. Vi använder K = 20 i våra beräkningsförsök. Finita skillnader i det deterministiska linjära programmet (FDD) Med tanke på att läget för reservationer i början av tidsperioden t är x t, FDD approximerar den optimala totala förväntade vinst över tidsperioderna {t,. ., 0} genom att använda det optimala objektiva värdet av problemet Således, låta L t (x t ) vara det optimala objektiva värdet av problemet ovan, använder FDD L t (x t ) som en approximation till V t (x t ). I detta fall kan vi fatta besluten genom att ersätta {V t (·) : t. T } i beslutsregeln i (6) med {L t (·) : t. Detta tillvägagångssätt föreslås i Bertsimas och Popescu (2003). I likhet med DLP använder vi en omoptimerad version av FDD, där vi delar upp planeringshorisonten i K lika segment och justerar beslutsregeln i början av varje segment. Med tanke på att läget för reservationerna i början av kth-segmentet följer beslutsregeln i (6), om vi har då alltid acceptera en begäran om resplan j tills vi når början av nästa segment och justera beslutsregeln. Vi använder K = 20. Virtuella kapaciteter baserade på en naiv beräkning (VPN) I denna referensstrategi sätter flygbolaget virtuella kapaciteter på flygbenen genom att anta att ingen visar ta på sina förväntade värden. Efter detta fattar flygbolaget beslut om tilldelning av kapacitet under förutsättning att alla reservationer dyker upp, men kapaciteten på flygbenen är lika stor som den virtuella kapaciteten. Med andra ord, med tanke på att en bokning dyker upp vid avgångstiden med sannolikhet q, sätter flygbolaget den virtuella kapaciteten på flygbenet i som u i = c i /q och löser en version av det deterministiska linjära programmet i (7)- (11), som kan anges som Letting {λ * i : i  på L} vara de optimala värdena för de dubbla variablerna i samband med den första uppsättningen begränsningar ovan, VCN använder DLP-policyn i (12). Liknar DLP och FDD använder vi en återoptimerad version av VCN med 20 återoptimeringar. Virtuell kapacitet baserad på en ekonomisk modell (VCE) En kritik för VCN är att den väljer den virtuella kapaciteten under antagandet att nej visar ta på sina förväntade värden. Beroende på avvägningarna mellan biljettpriser, straffkostnader och sannolikheter kanske vi vill vara mer eller mindre aggressiva än vad de förväntade värdena för noshowerna antyder. Målet med VCE är att kompensera för denna brist. VCE föreslås i Karaesmen och van Ryzin (2004a) och baseras på följande tre antaganden. För det första är intäkterna från en kapacitetsenhet på ett flygben kända. Vi låter r i vara intäkterna som vi gör från en enhet av kapacitet på flight ben i. För det andra, om en bokning använder kapaciteten på flera flygben, kan vi tillåta ombordstigning till denna bokning på ett flygben, medan vi nekar ombordstigning till samma bokning på ett annat flygben. Dessutom är viteskostnaden för att neka ombordstigning till en bokning på ett flygben känd. Vi lät g i vara straffkostnaden för att neka ombordstigning till en bokning på flight ben i. För det tredje, om flygbolaget sätter den virtuella kapaciteten på flight ben i som u i, då det säljer exakt u i bokningar på flight ben i. Med det tredje antagandet, om vi sätter den virtuella kapaciteten på flight ben i som u i, då säljer vi u i reservationer på flight ben i, i vilket fall, det första antagandet innebär att vi genererar en inkomst av r i u i. Å andra sidan, om vi låter B i (u i) vara en binomialt distribuerad slumpmässig variabel med parametrar (u i, q), då antalet reservationer som visar upp vid avgångstiden ges av B i (u i ) och det andra antagandet innebär att den förväntade straffkostnad som vi ådrar oss på flygbenet i är g i E{max{B i (u i))‐c i, 0}}. VCE löser därför problemet max u i r i u i - g i E{max{B i (u i ) − c i, 0}} för att ställa in den virtuella kapaciteten på flygben i. När den virtuella kapaciteten väl har fastställts fortsätter VCE på samma sätt som VCN. Karaesmen och van Ryzin (2004a) föreslår flera val för r i och g i. Efter deras arbete låter vi R j = f j / l.L a lj och G j =  på j / l.L a lj för alla j  på J för att jämnt fördela intäkter och straffkostnader i samband med en resplan över flygbenen som den använder. I detta fall försöker vi välja r i som 16 Använda alla kombinationer av dessa val, vi har nio olika val för r i och g i. Vi testar resultaten av alla dessa nio val för alla våra testproblem, men för korthet, bara rapportera de resultat som motsvarar det bästa valet. För olika testproblem kan det bästa valet för r i och g i vara annorlunda. I likhet med VCN använder vi en återoptimerad version av VCE med 20 återoptimeringar. Virtuella kapaciteter tillsammans med beslut om kapacitetstilldelning (VCJ) Både VCN och VCE använder antagandet att vi kan ställa in den virtuella kapaciteten först, och sedan komma med en policy för att acceptera eller avvisa resplansförfrågningar. Däremot använder VCJ påföljdskostnaden g i E{max{B i (u i ) − c i, 0}} i problem (37)- (40) för att gemensamt ställa in den virtuella kapaciteten och komma med en policy för att acceptera eller avvisa resplan begäran. I synnerhet, VCJ löser problemet där vi använder interpolations av funktionen E{max{B i (u i) − c i, 0}} för att kunna beräkna det på en bråkdel u i. VCJ använder DLP-policyn i (12). Detta tillvägagångssätt föreslås i Karaesmen och van Ryzin (2004a). I likhet med VCE, försöker vi tre olika val för g i och rapportera resultaten som motsvarar det bästa valet. Vi använder en återoptimerad version av VCJ med 20 återoptimeringar. Denna benchmarkingstrategi utvecklas av Erdelyi och Topaloglu (2009). Den grundläggande observationen bakom SPC är att om påföljdskostnaden för att neka ombordstigning på reservationerna gavs av en separat funktion av blanketten Ε(S(x 0 )) = j-J γ j (S j (x j0 )), då skulle optimalitetsekvationen i (5) brytas ner av resvägarna. För att utnyttja denna observation, approximerar SPC (S(x 0 )) i problem (1)-(4) med en åtskiljbar funktion av formen j-J γ j (S j (x j0 )) och löser optimalitetsekvationen i (5) med det ungefärliga gränsvillkoret att V 0 (x 0 ) = −E{ j-J γ j (S j (x j0 ))}. Värdefunktionerna {V t (·) : t  till T} som erhålls på detta sätt används för att skapa en policy för att acceptera eller avslå begäran om resväg. Produktresumén använder en simuleringsbaserad metod för att konstruera den åtskiljbara approximationen j-J γ j (S j (x j0 )) till straffkostnaden. Grovt taget simulerar vi DLP-policyn i (12) för att få en allmän uppfattning om antalet reservationer som dyker upp vid avgångstiden. Efter detta beräknar vi sluttningarna av ρ(·) vid dessa antal reservationer längs olika riktningar och använder dessa sluttningar för att konstruera skalor funktioner {γ j (·) : j  på J }. En exakt beskrivning av denna referensstrategi ligger utanför tillämpningsområdet för vårt papper och vi hänvisar läsaren till Erdelyi och Topaloglu (2009) för detaljer. I likhet med de andra referensstrategierna justerar vi den åtskiljbara approximationen fem gånger över planeringshorisonten. Det visar sig att ändring av produktresumén mer än fem gånger inte ger några ytterligare fördelar. 17 Våra viktigaste beräkningsresultat sammanfattas i tabellerna 1 och 2. Framför allt visar dessa två tabeller resultaten för testproblemen med fyra respektive åtta ekrar. Den första kolumnen i tabellerna 1 och 2 anger testproblemets egenskaper. I den andra kolumnen anges den övre gränsen för den optimala totala förväntade vinsten på grund av problemets optimala objektiva värde (7)–(11). De följande sju kolumnerna ger den totala förväntade vinsten från DPD, DLP, FDD, VCN, VCE, VCJ och SPC. Dessa totala förväntade vinster beräknas genom att man simulerar resultaten av de olika policyerna under 50 resplansförfrågningar. Vi använder gemensamma resplansförfrågningar när vi simulerar de olika politikernas resultat. Den tionde kolumnen ger den procentuella skillnaden mellan den totala förväntade vinst som erhålls av DPD och DLP. Denna kolumn innehåller också en " närhelst DPD presterar betydligt bättre än DLP och en " när det inte finns något statistiskt signifikant prestationsgap mellan de två metoderna på 95% nivå. De fem sista kolumnerna gör samma sak som den tionde kolumnen, men de jämför DPD:s prestanda med FDD, VCN, VCE, VCJ och SPC. Resultaten visar att DPD presterar betydligt bättre än alla referensstrategier som använder en linjär programmeringsformulering. Bland de linjära programplaneringsbaserade referensstrategierna utför FDD det bästa och följs av VCJ, DLP, VCE och VCN. FDD:s överlägsenhet över DLP observeras också av Bertsimas och Popescu (2003). Prestandaskillnaderna mellan DPD och DLP, FDD, VCN, VCE och VCJ är statistiskt signifikanta för alla testproblem. De genomsnittliga prestandaskillnaderna mellan DPD och DLP, FDD, VCN, VCE och VCJ är 4,09, 2,85 6,82, 4,76 och 2,82 för testproblemen med fyra ekrar. Samma luckor ökar till 5. 39, 2.87, 8.18, 6.08 och 3.53 för testproblemen med åtta ekrar. Bland de tre referensstrategier som använder virtuella kapaciteter presterar VCJ bättre än VCN och VCE. Det är intressant att notera att VCJ presterar bättre än DLP också. Det finns testproblem där VCN presterar bättre än DLP, trots att VCN i huvudsak är en ad hoc-modifiering av DLP som inte noggrant tar itu med möjligheten av inga shower. VCN:s prestanda är dock inte robust, vilket framgår av testproblemen med (σ, σ) = (4, 0). Det finns ingen tydlig skillnad mellan DLP och VCE, men det finns testproblem där VCE kan prestera betydligt sämre än DLP. Prestandagapet mellan DPD och SPC är i storleksordningen en halv procent till en procent. Vi betonar att en procentuell intäktsskillnad fortfarande anses vara betydande i intäktsstyrningen. På en majoritet av testproblemen presterar DPD bättre än produktresumén och i de återstående testproblemen finns det ingen statistiskt signifikant skillnad mellan de två referensstrategierna. I likhet med DPD utför SPC märkbart bättre än alla referensstrategier som använder en linjär programmeringsformulering. Därför ger DPD och SPC, genom att arbeta med den dynamiska programmering formulering av kapacitetstilldelning och overbooking problem, betydande förbättringar jämfört med att använda en deterministisk linjär programmering formulering, som bortser från temporal dynamiken i ankomsten av resplan förfrågningar. Det är möjligt att observera några trender i prestandaluckorna. Framför allt tenderar skillnaderna i prestanda mellan DPD och de linjära programplaneringsbaserade referensstrategierna att öka i takt med att skillnaden i biljettpriser mellan högpris- och lågprisrutter, påföljdskostnader och den allmänna tätheten för 18-benskapaciteten ökar. För testproblem med stora prisskillnader, stora straffkostnader och snäva benkapaciteter är den "regel" som är förknippad med att fatta ett "okorrekt" beslut relativt stor. När t.ex. prisskillnaden mellan de höga biljettpriserna och de låga biljettpriserna är stor, kan ett godkännande av en begäran om en låg biljettväg "okorrekt" förhindra att man godtar en begäran om en hög biljettväg senare i planeringshorisonten och inkomstbortfallet i detta fall kan vara ganska stort. Likaså, när påföljdskostnaderna är stora, är det dyrt att neka ombordstigning till en reservation som accepterades "av misstag". När benkapaciteten är stram är det viktigt att göra besluten om godkännande av resplanen mer "varsamt", eftersom det inte är möjligt att tillmötesgå alla resplansförfrågningar. Det är därför uppmuntrande att en försiktig stokastisk modell lönar sig och att DPD presterar betydligt bättre än de linjära programplaneringsbaserade riktmärkesstrategierna i takt med att prisskillnaderna, straffkostnaderna och benkapacitetens täthet ökar. För att visa några av dessa trender visar tabell 3 prestandaskillnaderna mellan DPD och de andra referensstrategierna i genomsnitt över ett antal testproblem med en särskild egenskap. I den andra kolumnen visas till exempel prestandaluckorna i genomsnitt över testproblemen med fyra ekrar. De trender som vi nämner framgår av denna tabell. Tabell 4 visar de CPU sekunder som krävs för att beräkna en uppsättning värde funktion approximationer för DPD och SPC. Alla beräkningsförsök körs på en stationär PC i Pentium IV med 2,4 GHz-processor och 1 GB RAM. Eftersom antalet ekrar verkar vara den primära faktorn som påverkar beräkningstiderna, ger vi den genomsnittliga CPU sekunder över olika testproblem. De två raderna i tabell 4 visar CPU sekunder för DPD och SPC. Den andra respektive tredje kolumnen motsvarar testproblemen med fyra respektive åtta ekrar. Processorn sekunder för DPD innehåller de åtgärder som krävs för att uppskatta {α i j : i  till L, j  till J } och för att beräkna { v i t (·) : i  på L, t T }. Resultaten tyder på att DPD tar betydligt mindre tid än produktresumén och skalar mer gynnsamt. Med tanke på dess prestanda verkar DPD vara att föredra framför produktresumén. DLP, FDD, VCN, VCE och VCJ tar högst några sekunder för att återoptimera sina beslutsregler. Trots denna extra beräkningsbörda är beräkningskravet för DPD fortfarande rimligt. Med tanke på de betydande förbättringar som det innebär i förhållande till de andra referensstrategierna förefaller DPD vara ett lönsamt val. I detta dokument har vi utvecklat en modell för hantering av nätverksintäkter för att gemensamt kunna fatta beslut om kapacitetstilldelning och överbokning över ett flygbolags nätverk. Vår strategi bygger på att bryta ner problemet med nätintäktsförvaltning i en sekvens av problem med enbent intäktsförvaltning och utnyttja observationen att om proportionerna av reservationerna vid avgångstidpunkten var kända, då skulle den dynamiska programmeringsformuleringen av problemen med enbent intäktsförvaltning endast omfatta en skaklar statsvariabel. Med hjälp av dessa observationer konstruerade vi dragbara approximationer till värdefunktionerna. Beräkningsförsök visade att den resulterande politiken presterar betydligt bättre än referensstrategierna. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning.
REF arbetar med samma dynamiska programmeringsformulering och föreslår en dynamisk sönderfallsstrategi för programmering för att bryta ner nätverksproblemet i ett antal problem med enskilda flygben.
A Dynamic Programming Decomposition Method for Making Overbooking Decisions Over an Airline Network
{'venue': 'INFORMS J. Comput.', 'journal': 'INFORMS J. Comput.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}