第八章物流管理 物流工程

Dantzig-Wolfe[1]8.18.1.1KVehiclecommodityTaskactivity-on-nodediagramactivity-on-arcdiagramGk=(Vk,Ek)kKko(k)d(k)kNkVkNk{o(k),d(k)}EkVk(time-spacenetwork)IIs(I,s)Istj(I,s)(j,t){(I,s),(j,t)}EKtkIjtTask(I,j,k)EKtReskkK[1]G.B.DantzigandP.Wolfe.Decompositionprincipleforlinearprograms.OperationResearch,8:101-111,1960.108.1.2RLBkrikKiVkrReskr-unitsr-unitsrRUBkrikKiVkrReskr-unitsRkrijIjrr-unitskIjjrYkrjIrYkri{}krijkrikrjkrjRYRLBY+=,max8.1.3XkijkIj10Ykri(0)kIr(r-units)8.1.4W∑∈=KkkkdYW0)(0kKd(k)∑∈∈∀=tEKkjikijTasktX),,(12ko(k)d(k){}∑∑∈∈=−∈∈∀∈∀==−kkEjijEjijkkkjikijkdiKkVikdkoVikoiXX),(:),(:)(1,)(),(\0)(1k(I,j)()()()KkAjisrYRYXkkkrjkrijkrikij∈∈∈∀≤+⇒=,,,Re1{}KksrkdkoiRUBYRLBkkrikrikri∈∈∈∀≤≤,Re,)(),(KksrNiXRUBYXRLBkkEjijkijkrikriEjijkijkrikk∈∈∈∀≤≤∑∑∈∈,Re,),(:),(:8.2Dantzig-Wolfe[1]Dantzig-Wolfe(masterproblem)subproblemkK]o(k)d(k)kKPk()KkPpyxkkpkp∈∈,,xpkxkijpypkykijpkKXkijYki3[1]G.B.DantzigandP.Wolfe.Decompositionprincipleforlinearprograms.OperationResearch,8:101-111,1960.KkPpKkKkViyYKkEjixXkkpPpkpkPpkpkripkriPpkkpkijpkijkkk∈∀∈∀≥∈∀=∈∀∈∀=∈∀∈∀=∑∑∑∈∈∈,01,,),(θθθθkp(pathvariable)XkijYkij{}KkEjiXKkPpKkKkEjixXTasktxtsyMinkkijkkpPpkpkPpkpkijpkijEKkjiPpkpkijpKkPpkpkpkdkktkk∈∈∀∈∈∈∀≥∈∀=∈∈∀=∈∀=∑∑∑∑∑∑∈∈∈∈∈∈,),(1,0,01,),(1..),,(0)(θθθθθXkij0-1kp0-1{}KkPpTasktxtsyMinkkpEKkjiPpkpkijpKkPpkpkdtkk∈∈∀∈∈∀=∑∑∑∑∈∈∈∈,1,01..),,(0)(θθcolumngenerationmethodkkkPP⊆~restrictedmasterproblem{}KkPpTasktxtsyMinkkpEKkjiPpkpkijpKkPpkpkpkdtkk∈∈∀∈∈∀=∑∑∑∑∈∈∈∈,~1,0)1.8(1..),,(~~0)(θθθxkijp014Lagrange8.1t(tTask)kp∑∑∈∈∈∈∈∀−=ktEjiEKkjiTasktkkijptkpkdkpKkPpxyc),(),,(:0)(,λkKXkijYkiKkKkKkKktsXYMinktEjiEKkjiTasktkijtkkd∈∈∈∈−∑∑∈∈∈..),(),,(:0)(λbranchandpricemethod8.38.3.1nttTaskP+ttnt1P-ttnt1+ttTask-ttTask()∑∑∈∈−−++Ξ+Ξ+=KkTasktttttkkdPPYW0)(5∑∈−+∈∀=Ξ+Ξ−tEKkjitttkijTasktnX),,(8.3.2IjrRkrijIjresourceextensionfunctionExtkrijkYkijr(){}kikrijrkjkrjYExtRLBY,max=ExtkrijExtkrij()()()()KkAjisrYYExtxkkkrjkikrijKIJ∈∈∈∀≤⇒=,,,Re1()()()()KkAjisrYYExtxkkkrjkikrijKIJ∈∈∈∀≤⇒=,,,Re13.2.1.()krijkrikikrijRYYExt+=8.44flight,flightsegmentdeadheadduty11paring,rotationhomebasepersonalizedmonthlyblock41timetablingproblem62fleetassignmentproblem3crewparingproblem15~78.3.1.+tP+t4monthlyblockassignmentproblem,crewassignmentproblem33abidingproblembcrewrosteringproblem,rostingproblemdesideratacpreferentialbidingproblem[2][2]M.Gamache,F.Soumis,D.Villeneuve,J.Desrosiers,andE.Glinas.ThepreferentialbidingsystematAirCanada.TransportationScience,32(3):246-255,1998.7