Problemet med lokomotivplanering (eller problemet med lokomotivtilldelning) är att tilldela varje tåg en uppsättning (en uppsättning lokomotiv) i ett förplanerat tågschema för att ge dem tillräcklig kraft för att dra dem från ursprunget till destinationen. Lokooperativa planeringsproblem är bland de viktigaste problemen när det gäller tågplanering. I detta dokument rapporterar vi resultaten av en studie av det problem med tågplanering som CSX Transport, ett stort amerikanskt järnvägsbolag, står inför. Vi överväger planeringsversionen av loket schemaläggning modell (LSM), där det finns flera typer av lokomotiv och vi måste bestämma vilken uppsättning lokomotiv som ska tilldelas varje tåg. Vi presenterar en integrerad modell som bestämmer uppsättningen aktiva och dödhåriga lok för varje tåg, lätta resande lok från kraftkällor till kraftsänkor, och tåg-till-tåg anslutningar (ange vilka inkommande tåg och utgående tåg kan ansluta direkt). Ett viktigt inslag i vår modell är att vi uttryckligen anser att det handlar om missbruk och konsekvens. En sammansättning sägs vara trasig när den uppsättning lokomotiv som kommer på ett inkommande tåg bryts i undergrupper som ska omplaceras till två eller flera utgående tåg. En lösning sägs vara konsekvent över en vecka med avseende på ett tåg, om tåget får samma lokomotivuppdrag varje dag som det körs. Vi ger en blandad heltal programmering (MIP) formulering av problemet som innehåller cirka 197 tusen heltal variabler och 67 tusen begränsningar. Ett minimiimportpris av denna storlek kan inte lösas till optimalitet eller nära optimalitet i godtagbara drifttider med kommersiellt tillgänglig programvara. Med hjälp av problem sönderdelning, heltal programmering, och mycket storskalig kvarterssökning, utvecklade vi en lösningsteknik för att lösa detta problem inom 30 minuter av beräkningstid på en Pentium III dator. När vi jämförde vår lösning med den lösning som erhålls genom den inbyggda programvaran som utvecklats av CSX fick vi en besparing på över 400 lokomotiv, vilket innebär besparingar på över hundra miljoner dollar per år.
Papperet REF presentera en blandad heltal programmering formulering för ett lok schemaläggning problem.
Solving Real-Life Locomotive-Scheduling Problems
{'venue': 'Transportation Science', 'journal': 'Transportation Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}