1Collaborative LogisticsÖzlem ErgunSchool of Industrial & Systems EngineeringGeorgia Institute of TechnologyWhy collaborate?§ Increasing pressure on companies to operate more efficiently§ Increasing pressure from customers for better service§ Realization that suppliers, consumers, and even competitors, can be potential collaborative partners in logistics§ Connectivity provided by the Internet2Examples§ Buyers’ collaboration§ Group Purchasing Organizations (GPO)§ Economies of scale§ Logistics exchanges: shippers’ collaboration§ Operational synergies§ Sellers’ collaboration§ Alliances among airlines’, ocean-carriers, and trucking companies§ Coordinate/regulate prices§ Operational synergies§ Sellers collaborating with buyers§ Vendor managed inventory§ Information sharing§ Operational synergiesTools§ Model and solve the underlying problems§ Optimization§ Allocate cost/benefit among members in a fairway for sustainable collaborations§ Concepts from cooperative game theory3Outline§ Shippers’ collaboration§ Trucking§ Finding the system optimal solution with G. Kuyzu, M. Savelsbergh§ Allocating cost/benefitswith O. Ozener§ Shipper-carrier collaboration§ Carrier collaborations§ Containerized sea-cargo§ Network design from an alliance perspectivewith R. AgarwalTrucking IndustryEach shipper plans each shipment with only a handful of carriersEach carrier works with only a handful of shippersU.S. Truckload capacity moves empty nearly 20% of the time$165 billion + inefficiency yearlyHighly fragmented: 100,000+ shipper & 250,000+ Carriers4Asset Repositioning§ Asset repositioning is a “hidden” cost that everybody pays for, but no one controls individually§ Neither shipper understands how its actions affect the costs of asset repositioning§ Carrier must optimize asset utilization to respond to both shipper requirementsTuesdayShipper AWednesdayThursdayShipper BShipper Collaboration§ Asset repositioning§ The cost of asset repositioning is included in the price charged by carriers§ Shipper collaboration§ By providing continuous moves shippers can negotiate better rates from carriers§ Increase the opportunities for continuous moves by collaborating5§ Since no single player controls asset repositioning costs, they are a “hidden”cost paid for by all … this problem may be relieved through use of collaborationCollaborative LogisticsCollaborative Logistics§ Business Model§ Shippers collaborate with shippers and selected carriers§ Create and execute regularly scheduled and dynamic collaborative routes§ Major Benefits§ Reduced asset repositioning§ Cost reductions ~10%6State-of-the-art§ Shippers meet quarterly§ Identify load matching opportunities§ Build regularly scheduled continuous moves§ Jointly negotiate with a carrier§ Allocate the costs among themselves§ Industry standard: proportional allocationsContinuous Move Example from Nistevo NetworkKentChicagoNew JerseyChicago: Land O’ Lakes packaging vendor Kent: Land O’ Lakes plantNew Jersey: Land O’ Lakes distribution centerThrough Nistevo a third company with New Jersey – Chicago traffic was identified• 2.5 % savings of Land O’ Lakes $40 - $50 million finished goods freight bill• Carrier avoids any empty movements and uses 1 truck instead of 27Goal: Collaborative RoutesCedar RapidsBangorWellsMechanicsburgChicagoBuffaloGreen BayCompany 1Company 2Stand AloneStand Alone$3,821K$3,821KTogetherTogether$3,090K$3,090KSavingsSavings$ 731K$ 731K19% Savings19% SavingsCollaborative ResultsCollaborative Results••Efficiency gain Efficiency gain ……19%19%••Driver turnover Driver turnover ……under 10%under 10%••Service reliability Service reliability ……over 99%over 99%Collaborative Tours§ Optimization Problem§ Given a set of lanes, find a minimum cost set of routes covering all lanesTraversing a laneRepositioning8Lane Covering Problem (LCP)§ Given § A complete bidirected graph D=(N,A)§ A nonnegative cost cijfor each arc (i,j)§ A subset of arcs L (lane set)§ Find § A set of simple directed cycles (not necessarily disjoint) of minimum total cost covering all arcs in LLane Covering Problem § LCP can be solved in polynomial time:§ Solve min-cost network flow problem § Decompose the solution into simple cycles9Designing a Sustainable Collaboration MechanismDesign a mechanism to allocate gains from collaboration such that§ All costs are allocated§ No one (no subset of the members) should have an incentive to break away from the collaboration. The Core§ Does there exist a cost allocation α in the core:§ The total payment collected from the shippers is equal to the total cost of covering all the lanes§ No group of shippers would be better off if they decided to opt out and collaborate only among themselvescost recovery budget balancecompetitiveness stability10Stable Cost AllocationCost of each lane = 1Total cost without collaboration = 6Total cost with collaboration = 4If blue + green collaborate, their total cost = 2If blue + green collaborate, their total cost = 2Payment(blue + green) = 8/3 > 2Payment(red + green) = 8/3 > 2NOABIs an allocation of 4/3 per lane stable?Stable Cost Allocation?Primal problemDual problem11Cost Allocation From Dual§ Payment that is allocated for covering lane (i,j) 2 L § Then§ Budget:§ Stable:Cost Allocation From Dual§ Given any S µ L, let (lS,yS) be the optimal dual solution for the associated linear program LP(S)§ Note that the optimal solution (l,y) to the original dual when restricted to S is feasible for LP(S)12Fair Cost Allocation§ Is this solution fair?§ By complementary slackness:If a lane is traversed more than once the cost allocated to that lane is 0Stable Cost AllocationABCost of each lane = 1Total cost w/o collaboration = 6Total cost with collaboration = 4The only stable cost allocation:Green lane pays 0 Blue and red lanes pay 2Is this a fair cost allocation?13Cross Monotonic Allocations§ No shipper will be worse off if the size of the collaborative network is increased§ The dual-based cost allocation is not cross monotonic§ There does not exist a cross monotonic allocation in the coreABABPayment(green) = 1Payment(blue) = 1Payment(green) = 0Payment(blue) = 2Payment(red) = 2Cross Monotonic Allocations§ There does not exist a cross monotonic allocation which recovers more than ½ of the total cost§ Add more lanes from A to B§ Cost of each edge goes to 2§ Can allocate at most 1 to each edge§ ½ is