Vi studerar ett logistiknätverk där speditörer samarbetar och buntar ihop sina leveransförfrågningar för att förhandla fram bättre priser med en gemensam transportör. I denna miljö kan speditörer identifiera samarbetsrutter med minskade totala tomma lastbilsrörelser. Efter de optimala rutterna som minimerar den totala kostnaden för att täcka alla speditörers efterfrågan, fördelas denna kostnad mellan speditörerna. Vårt mål är att ta fram kostnadsfördelningsmekanismer som säkerställer hållbarheten i samarbetet. Vi utvecklar först kostnadsfördelningsmekanismer med välkända egenskaper från den kooperativa spelteorilitteraturen, såsom budgetbalans, stabilitet och monotonitet. Därefter definierar vi en uppsättning nya fastigheter, såsom en garanterad rabatt från montern ensam kostnad för varje avsändare, önskvärd i vår inställning och föreslår flera kostnadsfördelningssystem som kan leda till genomförbara lösningar. Vi utför också en beräkningsstudie på slumpmässigt genererade och verkliga data för att få insikter om hur de utvecklade fördelningssystemen fungerar. Nyckelord : samarbete, kostnadsfördelning, lastbilslast frakt. Historia : På grund av ökat tryck på att fungera mer effektivt och tillgodose ständigt ökande efterfrågan från kunder för bättre service, företag tvingas inse att leverantörer, konsumenter, och även konkurrenter kan vara potentiella samarbetspartners. Många företag använder sig därför av samarbetsmetoder som gruppinköp och kapacitet och informationsutbyte för att minska systemövergripande ineffektivitet och minska driftskostnaderna. Särskilt den senaste utvecklingen inom kommunikationsteknik gör det möjligt för företag att överväga en rad möjligheter som blir möjliga genom samarbete med andra. På en traditionell logistikmarknad för lastbilslast lämnar speditören in sina fraktförfrågningar till flera transportörer och förhandlar med dem. Dessa förfrågningar består av flera körfält som ska betjänas. En fil motsvarar en leverans från ursprunget till destinationen med full lastbilslast. Å andra sidan samlar ett transportföretag in fraktförfrågningar från flera speditörer och erbjuder priser baserade på sitt befintliga filnät och de körfält som det förutser att få vid tidpunkten för tjänsten. Avsändaren upphandlar transporttjänsten från transportören som erbjuder det lägsta priset för avsändarens fraktförfrågan. En viktig aspekt som påverkar transportföretagets driftskostnader är omplacering av tillgångar. Asset ompositionering, motsvarande dödskalle, är en tom lastbil rörelse från en leverans plats till en pickup plats. Transportörerna måste ofta omplacera sina tillgångar för att tillfredsställa de krav som olika speditörer ställer. Ompositioneringen av tillgångar minskar transportföretagets kapacitetsutnyttjande, vilket leder till ökade driftskostnader. Enligt beräkningar av American Trucking Association, förhållandet mellan tom körsträcka och total körsträcka för Large Truckload Carriers är cirka 17% medan samma förhållande är ungefär 22% för Small Truckload Carriers, vilket tillsammans motsvarar cirka 35 miljoner tomma miles månatliga (ATA 2005). Eftersom dessa deadhead miles i allmänhet är ett resultat av obalansen i olika speditörers önskemål om frakt, återspeglas kostnaderna för ompositionering av tillgångar i körfältspriserna. Ett samarbete för upphandling av transporttjänster etableras när speditörer träffas för att minimera sina totala transportkostnader genom att bättre utnyttja lastbilskapaciteten hos en transportör. Nistevo, Transplace och One Network Enterprises är exempel på samverkande logistiknätverk som gör det möjligt för speditörer och transportörer att hantera sin transportverksamhet. En mängd olika företag som General Mills, Georgia-Pacific och Land O'Lakes kan identifiera rutter med mindre tillgångar ompositionering för sina transportbehov, vilket resulterar i betydande besparingar i sina transportkostnader genom att vara medlemmar i sådana samverkande logistiknätverk. Till exempel, efter att ha bildat samarbetspartnerskap med andra i Nistevo Network, Georgia-Pacifics procentandel av tomma rörelser minskade från 18% till 3%, vilket motsvarar $11,250000 besparingar årligen (Strozniak 2003). Den samarbetsmiljö vi anser i detta dokument är relevant för företag som regelbundet skickar lastbilslast transporter, säger flera dagar i veckan, och letar efter samarbetspartners i liknande situationer för att kors utnyttja en dedikerad flotta. De lastbilslasttransporter som deltar i ett sådant samarbete utförs med jämna mellanrum. Eftersom särskilda flottor används för sådana transporter och lastbilarna förväntas återvända till den ursprungliga platsen i slutet av varje period, är avsändarna ansvariga för den förväntade kostnaden för omplacering av tillgångar. I praktiken kan olika lufttrafikföretag ha olika kostnadsberäkningssystem i samband med tomma lastbilsrörelser. Till exempel kan den förväntade kostnaden för ompositionering av tillgångar längs en körfältsfil vara en procentandel av körfältskostnaden och denna procentandel kan vara olika för varje körfält i nätet. Transportören får också ta ut ett fast belopp för ompositionering av tillgångar. Inledningsvis utgår vi ifrån att transportören tar ut en viss del av originalfilen Ö zener och Ergun: Tilldela kostnader i ett samarbetsnätverk för transportupphandling som lämnats in till Transport Science; manuskript nr. (Snälla, ange mansucript-numret!) 3 kostnad för varje ompositionering av tillgångar. Vi kallar denna fraktion för "dödskallekoefficienten" ( på engelska). Vi visar också att våra metoder är giltiga för andra allmänt använda prissättningsstrukturer. De totala kostnader för omplacering av tillgångar som ett lufttrafikföretag ådrar sig beror på hela uppsättningen körfält som lufttrafikföretaget betjänar vid tidpunkten för tjänsten. När en transportör ger ett pris till en avsändarfil har varken transportören eller avsändaren någon perfekt information om det slutliga filnätet som transportören kommer att täcka vid tidpunkten för tjänstgöringen. Det pris som transportören erbjuder en avsändare inkluderar därför en påslagning på grund av den förväntade omplaceringskostnaden i samband med transportörens körfält. Å andra sidan, om speditören kan bunta sina köer med kompletterande och ge en kontinuerlig förflyttning med minimal ompositionering vid tidpunkten för köpet, då speditören kommer att kunna förhandla om bättre priser från transportören. Även om fördelarna med att bilda samarbeten är tilltalande, är det nyckeln till att förverkliga dessa fördelar att säkerställa ett samarbetes hållbarhet. En framgångsrik medlemsmekanism bör fördela de gemensamma fördelarna/kostnaderna för samarbetet mellan samarbetsmedlemmarna på ett "stabilt sätt" (som kommer att presenteras senare i dokumentet). Nuvarande praxis på transportmarknaderna för lastbilslast är att fördela gemensamma kostnader i proportion till kostnaden för service av den deltagande speditörens körfält före samarbete. I denna studie visar vi först att även om sådana proportionella fördelningssystem är lätta att genomföra, är de inte stabila ur ett spelteoretiskt perspektiv. Dessutom visar vi att de potentiella fördelarna med ett avsändarsamarbete beror på synergierna mellan filerna, vilket innebär att även en liten ändring i filnätet kan leda till att kostnadsfördelningen för varje avsändare förändras avsevärt. Vi försöker sedan utforma kostnadsfördelningsmekanismer som är stabila, uppmuntra till ett ökat samarbete och garantera en minskning av baskostnaden för varje avsändare. Innan vi illustrerar begreppet samarbete kring detta problem och de utmaningar som är förknippade med denna samarbetsmiljö, introducerar vi först en viss terminologi. Låt "original körfältskostnad" vara kostnaden för att utföra en full lastbilslast leverans från körfältets ursprung till körfältets destination. Sedan, "tillgångar ompositionering kostnad" längs en båge är lika med  och gånger den ursprungliga körfält kostnaden. "Stå ensam kostnaden för en uppsättning körfält" är den lägsta kostnaden för att betjäna dessa körfält (de ursprungliga körfältskostnaderna plus kostnaderna för omplacering av tillgångar). På samma sätt är "allvarlig kostnad för en avsändare" den totala kostnaden för att täcka alla köer för avlastaren plus den tillgång ompositioneringskostnader i samband med dessa köer. Observera att stå ensam kostnaden för en avsändare kan vara mindre än summan av stå ensam kostnader för sina körfält på grund av samverkan mellan dessa körfält. Slutligen "total kostnad för samarbetet" eller motsvarande "total budget" är den totala kostnaden för att uppfylla alla krav på ett samarbete. I en proportionell kostnadsfördelningsmetod fördelas kostnaderna till filerna (eller till avlastarna) som står i proportion till de fasta kostnaderna för filerna (eller avlastarna). I vårt exempel, varje avsändare har bara en fil, därför båda metoderna ger samma resultat och fördela en kostnad på 1 till varje avsändare. till varje körfält (avsändare). Med denna tilldelning är det dock inte svårt att se att redarna A och B (motsvarande A och C) är bättre på att samarbeta på egen hand med en total kostnad på 2. Därför är den proportionella kostnadsfördelningen i detta fall inte stabil och en undergrupp, nämligen A och B (eller A och C), har ett incitament att dela företag med C (eller B) och samarbeta på egen hand. Eftersom vi betraktar alla möjliga kostnadsfördelningar, drar vi slutsatsen att den enda tilldelningen där den stora koalitionen inte hotas av någon undergrupp av dess medlemmar är tilldelningen av (0, 2, 2) till speditörer A, B respektive C. Eftersom speditören A har en högre förhandlingsposition jämfört med de andra två speditörerna, förväntas den debiteras mindre än B och C trots att de har samma fristående kostnader. Dessutom, enligt varje kostnadsfördelningsmetod där avsändare A har en positiv fördelning, kommer någon av de andra befraktarna att vara villig att täcka en del av kostnaderna för avsändare A för att komma in i en koalition med A. Att ladda avsändaren A ingenting gör dock en friryttare som kanske inte är önskvärd i ett samarbete. Dessutom, i den enda stabila tilldelning, där den stora artikeln överlämnades till transportvetenskap; manuskript nr. (Snälla, ange mansucript-numret!) 5 koalition upprätthålls tillsammans, både speditörer B och C fördelas sin ställning ensam kostnader, så att vara i ett samarbete ger inget positivt värde för dessa två speditörer. Därför drar vi slutsatsen att även på ett mycket enkelt exempel kan grundläggande metoder för kostnadsfördelning, såsom proportionell eller stabil kostnadsfördelning, ha vissa oönskade egenskaper för samverkansproblemet och utforma en kostnadsfördelningsmetod som har alla önskade egenskaper kanske inte är möjlig. Därför måste man välja en uppsättning önskvärda egenskaper och designallokeringsmetoder som passar det aktuella problemet och det är motivationen bakom vårt arbete. Det finns två strömningar av litteratur i kooperativ spelteori och lastbilslast transport som är relevanta för vårt arbete. Kooperativ spelteori studerar den klass av spel där själviska spelare bildar koalitioner för att få större fördelar. En stor del av litteraturen om kooperativa spel fokuserar på att hitta kostnadsfördelningar som är stabila och fördela den totala kostnaden till medlemmarna. Vi hänvisar läsaren till Young (1985) som ger en grundlig genomgång av grundläggande kostnadsfördelningsmetoder och Borm et al. (2001) för en undersökning av kooperativa spel med anknytning till verksamhetsforskningsproblem. De spel som genereras av linjär programmering optimering problem, som är relevanta för spelet vi anser i detta papper, studeras i Owen (1975). Owen (1975) visar att för sådana spel en kostnadsfördelning som är stabil och allokerar den totala kostnaden kan beräknas från en optimal lösning till dubbla linjära programmet. Owen (1975) visar också att för det linjära produktionsspel som den ansåg att det motsatta inte håller och ger ett exempel där en sådan kostnadsfördelning inte ingår i den optimala uppsättningen av det dubbla linjära programmet. Dessa resultat utökas ytterligare i Kalai och Zemel (1982), Samet och Zemel (1984), och Engelbrecht-Wiggans och Granot (1985). Kalai och Zemel (1982) fastställer korrespondensen mellan varje sådan kostnadsfördelning till en optimal dubbel lösning för ett flöde spel över ett enkelt nätverk. Samet och Zemel (1984) och EngelbrechtWiggans och Granot (1985) generaliserar detta resultat och utvidgar det till några LP-spel som inkluderar de spel där denna korrespondens är känd för att existera. Bidraget från denna studie är att tillhandahålla en allmän ram för de kostnadsfördelningsmekanismer som kan användas för att hantera verkliga samarbetsnätverk för lastbilslast. Det finns en uppsättning artiklar som går kooperativ spelteori och klassiska routing problem, såsom (1997), som studerar routing spel, och Tamir (1991), som överväger kontinuerliga och diskreta nätverk syntes spel. Dessa dokument i allmänhet studera förekomsten av kostnadsfördelning med välstuderade egenskaper från kooperativ spelteori och föreslå beräkningsmetoder för egenskaper för den givna ansökan bör vara och utveckla mekanismer baserade på dessa egenskaper. I det här dokumentet, när vi söker efter en kostnadsfördelningsmetod, begränsar vi oss inte bara till begreppen från kooperativ spelteori utan tar också hänsyn till de krav som är relevanta för kollaborativa transportnätverk för lastbilslast. Å andra sidan, problemet med att hitta effektiva rutter, kontinuerliga vägar och turer, som minimerar kostnader tillgång ompositionering i ett samarbete lastbilslast transportnätverk har studerats av Moore et al. (1991), Ergun et al........................................................................................................................ (2007) och Ergun et al. (2005)................................................................ Dessa dokument studerar de underliggande optimeringsproblemen med sidobegränsningar såsom tids- och förarbegränsningar och föreslår heuristiska algoritmer för att lösa dem. Resten av detta dokument är organiserat enligt följande. I Avsnitt 1 diskuterar vi kortfattat väl studerade kostnadsfördelningsfastigheter från kooperativ spelteori. I avsnitt 2 ger vi först en formell redogörelse för redarnas samarbetsproblem och utvecklar sedan en stabil kostnadsfördelningsmetod som fördelar den totala kostnaden (dvs. En fördelning i kärnan) för avsändarens samarbetsproblem med hjälp av linjär programmering dualitet och diskutera tre andra fördelningssystem: nucleolus, Shapley Value och cross monotona kostnadsfördelningar. I avsnitt 3 utvecklar vi kostnadsfördelningar, genom att lätta på budgetbalansen och stabilitetsegenskaperna, som inte gör det möjligt för de tilldelade kostnaderna att vara lägre än de ursprungliga körfältskostnaderna och garantera en minskning från montern ensam kostnad för varje avsändare. I avsnitt 4 undersöker vi hur olika prissättningssystem påverkar våra lösningsmetoder. I Avsnitt 5 visar vi beräkningsmässigt hur våra metoder fungerar på flera klasser av slumpmässigt genererade och verkliga fall. Slutkommentarer ges i avsnitt 6. I detta avsnitt diskuterar vi några av de välkända kostnadsfördelningsegenskaperna från den kooperativa spelteorilitteraturen. I en budget som är balanserad, eller effektiv, kostnadsfördelning är den totala kostnaden för samverkansmedlemmarna lika med den totala kostnaden för samarbetet. Det vill säga, ett budgetunderskott eller ett överskott skapas inte. De flesta tilldelningsmetoder som studeras i litteraturen försöker hitta budgetbalanserade anslag. Men i vissa spel, budgetbalans egendom strider mot en mer önskvärd egendom. I sådana spel är det möjligt att söka ungefärliga budgetbalanserade kostnadsfördelningar som täcker minst α-procent av kostnaden (se Pal och Tardos (2003) och Jain och Vazirani (2001) för två ansökningar). Artikel inlämnad till transportvetenskap; manuskript nr. (Snälla, ange mansucript-numret!) I en stabil kostnadsfördelning kan ingen koalition av medlemmar hitta ett bättre sätt att samarbeta på egen hand. Därför uppfattas den stora koalitionen som stabil och hotas inte av dess underkolonier. Därför är stabilitet nyckelbegreppet som håller ihop ett samarbete. Den uppsättning kostnadsfördelningar som är budgetbalanserade och stabila kallas kärnan i ett samarbetsspel. För ett samarbetsspel kan kärnan vara tom, det vill säga en budget balanserad och stabil kostnadsfördelning kanske inte finns. Även om stabilitet är en viktig aspekt när det gäller att upprätta ett hållbart samarbete är det inte helt meningslöst att överväga metoder för kostnadsfördelning med begränsade stabilitetskrav. På grund av kostnaderna för att hantera samarbeten, begränsad rationalitet för spelarna och medlemsavgifter, kan en underkoalition inte bildas även om den erbjuder ytterligare fördelar för sina medlemmar. Dessutom, för ett samarbete spel med en tom kärna, bör antingen budgetbalans eller stabilitet villkor lättas för att hitta en kostnadsfördelning. Därför kan det vara godtagbart att lätta på stabilitetsbegränsningen på ett begränsat sätt för en kostnadsfördelningsmetod. När det finns flera kostnadsfördelningar i kärnan kan vissa av dessa fördelningar vara mer önskvärda än de andra. En sådan tilldelning som är välstuderad i den kooperativa spelteori litteratur är nucleolus. Nucleolus, som infördes av Schmeidler (1969), är den kostnadsfördelning som lexikografiskt maximerar den minimala vinsten, skillnaden mellan den fristående kostnaden för en delmängd och den totala fördelade kostnaden för denna delmängd, över alla delmängder av samarbetet. Om kärnan är icketom, nukleolus ingår i kärnan. Nucleolus kan fortfarande finnas även om kärnan är tom om det finns en kostnadsfördelning som är budgetbalanserad och fördelar kostnader till de spelare som är mindre än eller lika med deras fristående kostnader. En välkänd kostnadsfördelningsmetod är Shapley Value, som för varje spelare definieras som det viktade genomsnittet av spelarens marginella bidrag till varje delmängd av samarbetet (Shapley 1953). Shapley Value kan tolkas som det genomsnittliga marginella bidrag varje medlem skulle ge till den stora koalitionen om den skulle bilda en medlem i taget (Ung (1985) ). Även om kärnan inte är tom, kan Shapley Value inte ingå i kärnan. Efter att samarbetet har inletts kan det med tiden finnas potentiella nya medlemmar som är villiga att delta i samarbetet. Även om det förväntas att expansionen kommer att gynna samarbetet som helhet på grund av ökade synergier mellan medlemmarna, kan dessa fördelar inte fördelas jämnt mellan medlemmarna. Faktum är att vissa av de befintliga medlemmarna i samarbetet kan vara sämre på grund av att nya medlemmar läggs till enligt vissa metoder för kostnadsfördelning. Att lägga till nykomlingar i samarbetet kan därför bryta ner samarbetet. För att undvika detta är det att föredra att ha en cross monoton kostnadsfördelningsmetod där någon medlems nytta inte minskar ) med tillägg av en nykomling. En allokering mellan monotona kostnader är också stabil om fördelningen är budgetbalanserad (Moulin 1995). Att ha en korsmonotonisk kostnadsfördelning är gynnsamt för avtal. Om en korsmonotonisk kostnadsfördelningsmetod används för att fördela kostnaderna kan en särskild kostnad i upphandlingsskedet tilldelas varje medlem i samarbetet och medlemmarna garanteras att aldrig betala mer än detta värde så länge ingen lämnar samarbetet. Se Tazari (2005) för en undersökning av system för fördelning av kostnader mellan monotona enheter. Tyvärr, som kommer att diskuteras, korsmonotonicitet egendom visar sig vara en mycket restriktiv i vår miljö. Ett samarbetsspel där spelarna kompenserar varandras kostnader med sidobetalningar, kallas en överförbar payoff spel. Likabehandling av lika egendom säkerställer att två deltagare i ett samarbete har samma fördelning om de är identiska i alla aspekter som är relevanta för tilldelningsproblemet i beaktande. När det gäller fartygsägarnas samarbetsproblem innebär inte lika behandling av jämlikar att de fördelade kostnaderna för köer som har samma ställning i sig bör vara desamma. Det säkerställer att den tilldelade kostnaden för två olika avsändare är densamma om de har körfält med samma ursprung och destination. Genom hela tidningen hålls denna egendom som en invariant. En spelare i är en dummy spelare om den inkrementella kostnaden för att lägga i till någon koalition är noll och den dummy axiom säger att en dummy spelare bör få en kostnad allokering lika med noll. En metod för kostnadsfördelning är additiv, om allokering av summan för eventuella gemensamma kostnadsfunktioner är lika med summan av deras individuella tilldelningar. Slutligen finns det några extra kostnadsfördelning fastigheter vi önskar i vår miljö. Som i exemplet i inledningen är det enligt vissa metoder för kostnadsfördelning möjligt att ha medlemmar, som betalar mindre än sina ursprungliga körfältskostnader eller betalar sin ställning ensam kostnad. Vi anser att båda dessa situationer kan betraktas som icke önskvärda. Vi studerar tilldelningar med "minimiansvar" begränsning där avsändare är ansvariga för åtminstone deras ursprungliga körfält kostnad. Vi studerar också fördelningsmetoder där varje avsändare garanteras en tilldelning som är lägre än dess fristående kostnad, så att en medlem i samarbetet erbjuder en "positiv fördel" som kompenserar de svårigheter (t.ex. integration) att samarbeta. Observera att när någon av dessa två begränsningar införs är det inte möjligt att ha en budgetbalanserad och stabil kostnadsfördelning för speditörens samarbetsproblem, vilket framgår av exemplet i inledningen. Därför mildrar vi budgetbalansen och stabilitetsegenskaperna på ett begränsat sätt och utvecklar anslag med de ovan nämnda två begränsningarna. Artikel inlämnad till transportvetenskap; manuskript nr. (Snälla, ange mansucript-numret!) 9 I detta avsnitt definierar vi "Lane Täckning Problem" som syftar till att identifiera den optimala uppsättningen cykler som täcker filerna i samarbetet och det kooperativa spelet i samband med detta optimeringsproblem. Vi listar också våra antaganden i detta avsnitt. Vi fastställer sedan en mekanism för kostnadsfördelning i kärnan av speditörens samarbetsproblem med hjälp av linjär programmeringsdualitet. Därefter nämner vi kort nucleolus och ett alternativt kostnadsfördelningssystem, Shapley Value. Slutligen diskuterar vi förhållandet mellan kärnan i spelet och korsmonotoniska kostnadsfördelningar och utformar tilldelningar med denna egendom. I speditörens samarbetsproblem överväger vi en samling av speditörer var och en med en uppsättning körfält som måste serveras. Med tanke på kostnaden för att täcka varje körfält och de förväntade ompositioneringskostnaderna är samarbetets mål att minimera den totala transportkostnaden så att efterfrågan på varje avsändare i samarbetet är tillfredsställd. Kostnaderna för omplacering av tillgångar beror på den fullständiga körfältsuppsättningen av avlastarna. Som komplementaritet (synergi) av körfält från olika avsändare ökar (dvs. De bildar kontinuerliga turer med ingen eller minimal dödring) vinster från samarbete och incitament att samarbeta ökar. Därefter sammanfattar vi våra antaganden. För det första utgår vi ifrån att varje avsändare accepteras vara medlem i samarbetet även om en avsändare inte skapar ett positivt värde för någon annan avsändare i samarbetet. Frågan om vilka speditörer som bör ingå i samarbetet ligger utanför ramen för detta arbete. För det andra motsvarar varje körfält en leverans av lastbilslast mellan körfältets ursprung och destination. Vi utgår från att kostnaden för att samarbeta mellan medlemmarna i samarbetet är försumbar. Dessutom är en avsändare inte skyldig att lämna alla sina filer till samarbetet. Därför kan en avsändare utesluta en delmängd av sina körfält från samarbetet, och individuellt förhandla priser med transportören för dessa körfält eller bilda ett annat samarbete med andra avsändare, om det är lönsamt att göra det. Vi antar också att körfältsuppsättningen endast består av repeterbara körfält vilket innebär att varje avsändare har samma körfält som ska passeras varje period. Slutligen antar vi att det inte finns några sidobegränsningar (som time windows, förarbegränsningar. ................................... Detta anslag är avsett att täcka utgifter för tjänstemän och tillfälligt anställda som arbetar inom politikområdet Migration och inrikes frågor samt administrativa utgifter för tjänstemän och tillfälligt anställda som arbetar inom politikområdet Migration och inrikes frågor. om problemet. Vi kommer att hänvisa till denna totala transportkostnader minimering problem som Lane Täcka LCP, problemet med att hitta den minsta kostnaden uppsättning cykler som passerar bågen i L, kan lösas genom att hitta en lösning på följande heltal linjärt program: I P, x ij representerar antalet gånger körfält (i, j) L är täckt med en full lastbilslast och z ij representerar antalet gånger båge (i, j)  till A korsas som en deadhead båge. Vi låter r ij vara antalet gånger körfält (i, j) L krävs för att täckas med en lastbil last och r vara matrisen för r ij s. Restriktioner (2) är flödesbalansbegränsningar för alla noder i nätverket. Restriktioner (3) säkerställer att transportkraven för varje körfält i L uppfylls. Eftersom P är ett minimering problem, är det klart att variabler x ij kommer att vara lika med r ij i någon optimal lösning och de kan tas bort från P resulterar i en enklare formulering. För tydlighetens skull arbetar vi dock med ovanstående formulering. I det här dokumentet fokuserar vi på det kostnadsfördelningsspel som LCP genererar. I det kooperativa spelet anser vi att körfälten i L är spelarna och försöker fördela den totala kostnaden för samarbetet mellan alla körfält som serveras. Eftersom vi antar att en avsändare kan besluta att ta ut en delmängd av sina filer från samarbetet, allokering av kostnaden till filerna snarare än till avsändare är lämpligare i vår miljö. Den totala fördelade kostnaden för en avsändare är då summan av de fördelade kostnaderna för de köer som tillhör avsändaren. Den karakteristiska funktionen z * är den optimala kostnaden för att täcka alla körfält i S. För en given uppsättning körfält, kan det vara mycket svårt att identifiera dynamiken i en instans och bidrag av varje körfält till nätverket utan att lösa en LCP, eftersom det finns många undergrupper av körfält och bestämma förhållandet mellan dessa undergrupper är en enorm utmaning. Även med en liten förändring i nätverket kan optimala cykler förändras helt och hållet vilket kräver att vi löser en ny LCP för att bestämma den nya optimala uppsättningen. Därför kan kostnadsfördelningarna förändras avsevärt med en liten förändring av inputen. Ö zener och Ergun: Tilldela kostnader i ett samarbetsnätverk för transportupphandlingArtikel inlämnad till transportvetenskap; manuskript nr. (Snälla, ange mansucript-numret!) 11 Som tidigare nämnts, Owen (1975) visar att de optimala dubbla lösningarna leder till kärnkostnadstilldelning för LP-spel, kooperativa spel som uppstår från ett linjärt program. Kalai och Zemel (1982) visar att samma resultat håller för flow games, som kan omvandlas till spelet diskuteras av Owen (1975). Med tanke på dessa resultat visar vi först att LCP är ett linjärt optimeringsproblem, vilket visar att de optimala dubbla lösningarna för LCP ger kostnadsfördelningar i kärnan för problemet med speditörens samarbete. Därefter visar vi att omvänt i uttalandet också håller; varje kostnadsfördelning i kärnan motsvarar en optimal dubbel lösning till skillnad från spelet som beaktas i Owen (1975). PROOF P är en minimal kostnad cirkulation problem, varför lösa sin linjära avslappning är tillräckligt för att hitta en heltal lösning (se Ahuja et al. (1993)........................................................................................................................... Strukturen av P är likvärdig med det flödesproblem som diskuteras av Kalai och Zemel (1982), eftersom det finns en godtycklig kostnad vektor (c), tjänstekrav begränsningar som motsvarar varje spelare i samarbetet (constraints (3)), och flödesbalans begränsningar för varje nod i nätverket (constraints (2)). Därför spelet vi anser är en LP-spel. Därför kärnan för detta spel är nontomy och en kostnadsfördelning i kärnan kan erhållas från en optimal dubbel lösning (Owen (1975) ). Låt Ij vara de dubbla variabler som är förknippade med begränsningar (3) och y i vara de dubbla variabler som är förknippade med begränsningar (2), då den dubbla av LP avslappning av P är följande: Låt α ij vara den tilldelade kostnaden för att täcka körfält (i, j) L och (I *, y * ) vara en optimal lösning av D. ger en kostnadsfördelning i kärnan och vi kan beräkna I * ij värden genom att lösa D i polynom tid. Därefter visar vi att varje balanserad och stabil kostnadsfördelning motsvarar en optimal dubbel lösning. För det första ges ett nödvändigt och tillräckligt villkor för att en viss kostnadsfördelning ska vara stabil i nästa lemma. Ö zener och Ergun: Tilldela kostnader i ett samarbetsnätverk för transportupphandling Artikel inlämnad till transportvetenskap; manuskript nr. (Snälla, ange mansucript-numret!) PROOF Låt C S vara den uppsättning cykler som täcker filerna i S  till L med minsta totala kostnad z * S. Därför z * S = C till C S z (C) där z (C) representerar kostnaden för cykeln C. Observera också att för varje cykel C, (i, j) C (y i − y j ) = 0. För varje α som uppfyller ojämlikheterna ovan, är den totala kostnaden för varje cykel C C S mindre än eller lika med kostnaden för cykeln, eftersom ojämlikheten ovan gäller för alla S  på L, vilket innebär att α är en stabil kostnadsfördelning. Vi bevisar nödvändigheten av villkoret genom motsägelse. Antag att det för en stabil kostnadsfördelning α inte finns en vektor y som tillfredsställer den givna linjära ojämlikheten. Då är det linjära programmet som anges nedan ogenomförbart.P: max 0 Därför är motsvarande dubbla LP nedan antingen ogenomförbart eller obundet. Artikel inlämnad till transportvetenskap; manuskript nr. (Snälla, ange mansucript-numret!) Det är lätt att se att D är genomförbart (x = z = 0 är en möjlig lösning). Om D är obundet ska dess optimala objektiva funktionsvärde vara lika med −∞. Observera att på grund av flödesbalansbegränsningarna kan en möjlig lösning toD brytas ned i cykler med positiva flöden (där detta flöde representeras av en kombination av positiva x- och z-värden). För att uppnå ett objektivt funktionsvärde på −∞ måste vi öka flödet över minst en cykel till oändligheten. Låt C vara en sådan cykel och L C = C  på L och A på C på A. Om vi sedan ökar flödet över cykel C med en, ökas det objektiva funktionsvärdet med (i,j) och L C c ij + (i,j) och A C c ij − (i,j) till L C α ij, vilket är lika med kostnaden för cykeln minus den tilldelade kostnaden för cykeln med en stabil kostnadsfördelning. Enligt definitionen av stabilitet är denna term alltid icke-negativ för alla cykler. Därför måste den optimala objektiva funktionen för D vara icke-negativ. D är därför varken obundet eller ogenomförbart, vilket innebär att P är genomförbart. Vi drar slutsatsen att det för en stabil kostnadsfördelning finns en vektor y som uppfyller de linjära ojämlikheter som anges ovan. Därefter överväger vi frågan om huruvida uppsättningen kostnadsfördelningar i kärnan för avsändarens samarbetsproblem helt kan karakteriseras av uppsättningen av optimala lösningar till D. Det vill säga, om från varje kostnadsfördelning i kärnan, en optimal lösning till D kan konstrueras och vice versa. Om så är fallet, då ytterligare egenskaper av dessa kostnadsfördelningar kan fastställas genom att studera uppsättningen av optimala lösningar till D. I relaterade arbete, Kalai och Zemel (1982) bevisa tillfälligheten av kärnan med uppsättningen av dubbla optimala lösningar för enkla nätverksspel, Samet och Zemel (1984) utvidga detta resultat till enkla noll-one LP-system, och Engelbrecht- Wiggans och Granot (1985) visar samma resultat för en linjär produktion spel med en specifik struktur. Ingen av dessa inställningar inkluderar avsändare samarbetsspel, eftersom vi tillåter flera spelare på bågen. Vi utökar ovanstående resultat till det flödesspel som beskrivs av LCP med följande följd som fastställer likvärdigheten av kärnan och den optimala uppsättningen av D. PROOF Med tanke på Lemma 1 kommer vi bara att visa att varje kostnadsfördelning i kärnan motsvarar en genomförbar lösning för D med det optimala objektiva funktionsvärdet. Anta att α är en kostnadsfördelning i kärnan. På grund av budgetbalansen är egendomen α och den starka dualiteten (i, j) och L r ij α ij lika med det optimala objektiva funktionsvärdet för D. α uppfyller begränsningar (9) eftersom kostnadsfördelningarna inte kan vara negativa. På grund av Lemma 2, för en stabil kostnadsfördelning, finns det en vektor y som uppfyller den linjära Därför, för vissa icke-negativa matris ρ, vi har; Därför, ( ska, y) där att = α + ρ och ρ ≥ 0 är en genomförbar lösning till D. Om någon ρ ij är positiv, då det optimala objektiva funktionsvärdet för D skulle vara större än (i, j) till L r ij α ij som motsäger budgetbalansen egendom α. Därför drar vi slutsatsen att ρ = 0 och (α, y) är en optimal lösning för D. Kärnan motsvarar alltså den optimala uppsättningen av D. Därefter diskuterar vi egenskaperna hos kostnadsfördelningen i kärnan. Om, r ij, antalet gånger som en körfält (i, j) måste täckas ökas, då kostnadsfördelning av den körfältet, α ij, förväntas öka på grund av dubbel känslighet. På motsvarande sätt ökar kostnadsfördelningen för körfält (i, j) i takt med att den marginella fördelen med körfält (i, j) för nätet minskar. med ett) kommer inte att öka den totala kostnaden för samarbetet. Sedan, på grund av LP dualitet, den dubbla optimala objektiv funktionsvärdet inte ändras även om en koefficient för en dual variabel ökas, vilket innebär att motsvarande dubbla variabel, I ij, och kostnadsfördelningen måste vara noll för den körfält. Låt de optimala cyklerna vara den uppsättning enkla cykler som erhålls genom att bryta den optimala lösningen av LCP. Observera att den totala kostnaden för att täcka körfälten i L är lika med summan av kostnaderna för de optimala cyklerna. Med tanke på varje optimal cykel är den totala fördelade kostnaden för körfälten i den cykeln lika med kostnaden för att täcka cykeln, eftersom en tilldelning av en kostnad som är större än kostnaden för att täcka en optimal cykel skulle göra fördelningen instabil och fördela en mindre kostnad utan att öka kostnaden för en annan optimal cykel skulle inte kunna återvinna hela budgeten.  Kom ihåg att nukleolus är den kostnadsfördelning som lexikografiskt maximerar den minimala vinsten. Intuitivt, målet att hitta kärnan i ett kooperativt spel med en icke-tom kärna är att hitta en kostnadsfördelningsmetod i kärnan som undviker att gynna någon av spelarna eller undergrupper i samarbetet så mycket som möjligt. Helt klart, om det finns en unik tilldelning i kärnan, då denna tilldelning är nukleolus i spelet. Tyvärr, bestämma vinsten för alla undergrupper för ett samarbete uttryckligen kommer att ta exponentiellt tid, därför alla nukleolus typ kostnadsfördelning är inte effektivt beräkningsbar. Därför använder vi ett liknande tillvägagångssätt som är lämpligt i vårt sammanhang genom att utforma en kostnadsfördelning där de fördelade kostnaderna står i proportion till de ursprungliga körfältskostnaderna så mycket som möjligt. Låt "minimiintervallkostnadsfördelningen" vara den kostnadsfördelning i kärnan som minimerar avvikelsen av den tilldelade kostnaden för en fil från den ursprungliga körfältskostnaden över alla körfält i samarbetet när det finns alternativa optimala lösningar i kärnan av redarnas samarbetsproblem. En minsta kärnkostnadsallokering kan göras från en lösning till följande LP: (i,j)L En lösning är möjlig för N om och endast om den är en optimal lösning för det linjära programmet D. Därför hittar en kostnadsallokering konstruerad från en optimal lösning till N en tilldelning i kärnan som minimerar den procentuella avvikelsen mellan den tilldelade kostnaden och den ursprungliga körfältskostnaden över alla körfält i nätverket. Dessutom är värdet av k 2 avgränsat mellan 1 och 1 + 0 och värdet av k 1 avgränsas mellan 1 - och 1. Därför är det optimala objektiva funktionsvärdet, som ger "omfånget" av avvikelsen från kostnaderna för körfälten, högst 22. Detta förfarande avslutar med att uppnå en lösning som minimerar den maximala avvikelsen från de ursprungliga körfältskostnaderna över alla körfält. Observera att denna lösning kanske inte är en unik optimal lösning. Dessutom kan olika delar av nätverket ha olika egenskaper och därför kommer denna stegalgoritm inte att minimera det maximala avvikelsevärdet för varje del individuellt. För att lösa dessa problem kan ett iterativt förfarande utformas som använder LP ovan som en subrutin och successivt fördelar kostnader till körfält i olika delar av nätet. Tanken bakom detta iterativa förfarande bör vara att minimera intervallet för varje körfält lexikografiskt för att få en unik kostnadsfördelning.
Framför allt uppgav Özener och Ergun REF att "vi inte känner till en effektiv teknik för att beräkna Shapley-värdet för avsändarens samarbetsspel".
Allocating Costs in a Collaborative Transportation Procurement Network
{'venue': 'Transportation Science', 'journal': 'Transportation Science', 'mag_field_of_study': ['Economics', 'Computer Science']}