Report

Eat Fast, Just Better. An Organic Food Supply Network Maj Tony DeMarco Maj Art Terry Fast Food Nation • Americans eat ~ 25% of all meals at fast food restaurants. • Among the various reasons that Americans enjoy fast food, the top three according to the USDA in 2006 are: • TASTE • NUTRITION • CONVENIENCE Nutrition Health Choices? Possible New Alternatives • Provide fresh, organic food in a fast food setting. • Examine a network of organic farms and potential restaurant locations within a given state. • Operate a network to minimize the delivery time of the food…(freshness, cost…) to find the top 3 build sites among 10 locations. Maryland The Farms Farm nodes were abstracted to zipcode locations The Potential Restaurants Potential restaurant nodes were centered around the Baltimore and Capital Beltways The Potential Restaurants 9 8 7 6 4 5 3 2 1 0 No de Location (Google Maps) Name Zip 0 38.833289,-76.876831 Forestville 20747 1 38.948729,-76.860352 Mitchellville 20716 2 38.993572,-76.889191 Greenbelt Park 20768 3 39.024518,-76.952362 Hillandale 20903 4 39.030919,-77.140503 North Bethesda 20852 5 38.974357,-77.180328 Potomac 20854 6 39.208847,-76.598053 Brooklyn Park 21225 7 39.254588,-76.68457 Arbutus 21227 8 39.305613,-76.743622 Woodlawn 21207 9 39.374649,-76.746368 Pikesville 21208 The Network The arcs, from all farms to potential restaurants, are the travel times along state roads. Complete Bipartite Graph Farm 1 Restaurant 1 Farm 2 Restaurant 2 … Farm … Some More Information • Only 3 restaurant nodes are within the budget for final construction. • Each restaurant must be supplied with Meat, Dairy and Produce. • Farms may produce 1, some or all of the necessary supplies. • The operator seeks to minimize time. Attacks? A very large corporate fast food provider is aware of the potential competition and has successfully lobbied the MD state and federal government into instituting organic food inspections. Such inspections will delay food shipment times from inspected farms. The Model • Inner Problem – Minimize the total transit time of the supply network. – Subject to: • The total number of restaurants that can be built within budget. • Each restaurant must receive a supply of each type (produce, meat/poultry and dairy). The Model • Outer Problem – Maximize the solution to the inner problem. – Subject to: • There is a maximum of one inspection station for each farm. • The total number of inspection stations must not exceed a certain number. Mathematical Formulation • SETS – r R potential restaurant locations – f F farm locations – g G food type, G = {‘produce’,’meat/poultry’,’dairy’} Mathematical Formulation cont… • GIVEN DATA – tfr – pfg – delay – restaurants – stations transit time from farm f to restaurant r [seconds] 1 if farm f can produce food type food g, 0 otherwise inspection station delay [seconds] number of restaurants to build number of inspection stations Mathematical Formulation cont… • DECISION VARIABLES – br – sfrg – if 1 if build on restaurant location r, 0 otherwise 1 if farm f provides restaurant r with food type g, 0 otherwise 1 if there is an inspection i station for farm f, 0 otherwise Mathematical Formulation cont… • INNER PROBLEM min b,s s.t. (t fr delay·i f ) s frg f ,r , g b r restaurants r s frg br g , r f s frg p fg r , f , g Mathematical Formulation cont… • OUTER PROBLEM max [solution to inner problem] i s.t i f 1 f i f f stations Mathematical Formulation cont… • Notice the inner problem is not an LP but a MIP • The dual-trick not used to solve the max-min problem. • Bender's decomposition. Bender’s Algorithm • 1) Set UB= “+infinity,” LB= “-infinity,” X=0. • 2) Solve inner problem to get s variables and optimal objective, obj, corresponding to attack X. • 3) If obj>LB then set LB=obj, record X*=X as current incumbent attack. • 4) Add new cut to outer problem based on optimal flows s from (2). • 5) Solve master problem to get attack X and objective master_obj corresponding to all flows so far. • 6) If master_obj<UB then set UB=master_obj. • 7) If LB>UB then goto (2). • 8) Set X=X*, Solve inner problem for flows s* and objective (=LB) corresponding to attack X*. • 9) Report X* as optimal attack, and corresponding coefficients s*, with value obj. GAMS Bender’s Implementation set iter the iteration in Bender's algorithm /iter1*iter50/; set cutset(iter) a dynamic set which will define the new constraint for the iter; parameters coeff(iter,f,r,g) x(f) ; this corresponds to the s vector for the inner solution current attack plan equations constraint(iter) total_stations ; constraint(cutset).. master_obj =l= sum((f,r,g),(arcdata(f,r,'time')+delay*i(f))*coeff(cutset,f,r,g)) ; total_stations.. sum(f,i(f)) =l= stations ; GAMS Bender’s Implementation ub = INF; lb = -INF; converged = 0; loop(f,ibar(f)=0); loop(f,x(f)=0); cutset(iter)=no; loop(iter$(not converged), solve InnerProblem minimizing obj using MIP; if(obj.l>lb,lb=obj.l; loop(f,x(f)=ibar(f))); cutset(iter)=yes; loop((f,r,g),coeff(iter,f,r,g)=s.l(f,r,g)); solve OuterProblem maximizing master_obj using MIP; if(master_obj.l<ub,ub=master_obj.l); if(lb>=ub,converged=1); loop(f,ibar(f)=i.l(f)); ); loop(f,ibar(f)=x(f)); solve InnerProblem minimizing obj using MIP; Analysis • What locations are best with no attacks? • With attacks? Attacks increased in intensity from 1 to 6 hour inspections, ranging from 1 to 12 sites being inspected. • What are the best build (most resilient) sites? No Attacks… • Solution to Inner Problem with no inspection stations... • • • • • • • • • • • • • Build at Mitchellville Shipping PRODUCE from Woodmore_Farms Shipping MEAT_POULTRY from Good_Fortune_Farm Shipping DAIRY from Maryland_Sunrise_Farm_LLC Build at Hillandale Shipping PRODUCE from Organic_Acres Shipping MEAT_POULTRY from Nicks_Organic_Farm_LLC Shipping DAIRY from Maryland_Sunrise_Farm_LLC Build at Potomac Shipping PRODUCE from Nicks_Organic_Farm_LLC Shipping MEAT_POULTRY from Nicks_Organic_Farm_LLC Shipping DAIRY from Castle_Henry_Farm Total shipping time: 12258.00 ~ 3.4 hours 1 Attack… • • • Solution to Problem with 1.00 inspection stations Place inspection stations at: Nicks_Organic_Farm_LLC • • • • • • • • • • • • • Build at Mitchellville Shipping PRODUCE from Shipping MEAT_POULTRY from Shipping DAIRY from Build at Hillandale Shipping PRODUCE from Shipping MEAT_POULTRY from Shipping DAIRY from Build at Pikesville Shipping PRODUCE from Shipping MEAT_POULTRY from Shipping DAIRY from Total shipping time: 15312.00 ~ 4.25 hours Woodmore_Farms Good_Fortune_Farm Maryland_Sunrise_Farm_LLC Organic_Acres Maryland_Sunrise_Farm_LLC Maryland_Sunrise_Farm_LLC Rocky_Knoll Maryland_Sunrise_Farm_LLC Bellevale_Farms_Inc 2 Attacks… • • • • Solution to Problem with 2.00 inspection stations Place inspection stations at: Maryland_Sunrise_Farm_LLC Nicks_Organic_Farm_LLC • • • • • • • • • • • • • Build at Hillandale Shipping PRODUCE Shipping MEAT_POULTRY Shipping DAIRY Build at Woodlawn Shipping PRODUCE Shipping MEAT_POULTRY Shipping DAIRY Build at Pikesville Shipping PRODUCE Shipping MEAT_POULTRY Shipping DAIRY Total shipping time: 19155.00 ~ 5.32 from from from Organic_Acres Good_Fortune_Farm Castle_Henry_Farm from from from Rocky_Knoll Country_Pleasures_Farm Bellevale_Farms_Inc from from from Rocky_Knoll Country_Pleasures_Farm Bellevale_Farms_Inc Operator Resilience Curve Inspection Site Effectiveness 90000 80000 70000 60000 Delay 1 Hour 50000 2 Hour 40000 3 Hour 4 Hour 30000 5 Hour 20000 6 Hour 10000 0 0 1 2 3 4 5 6 7 Number Of Inspection Sites 8 9 10 11 12 Frequency of Potential Build Sites with Varying Delays 14 12 10 8 6 1 Hour Delay 2 to 6 hour delay 4 2 0 Total Frequency of Potential Build Sites 60 50 40 30 Frequency 20 10 0 Top Four Sites 9 8 7 6 4 5 3 2 1 0 No de Location (Google Maps) Name Zip 0 38.833289,-76.876831 Forestville 20747 1 38.948729,-76.860352 Mitchellville 20716 2 38.993572,-76.889191 Greenbelt Park 20768 3 39.024518,-76.952362 Hillandale 20903 4 39.030919,-77.140503 North Bethesda 20852 5 38.974357,-77.180328 Potomac 20854 6 39.208847,-76.598053 Brooklyn Park 21225 7 39.254588,-76.68457 Arbutus 21227 8 39.305613,-76.743622 Woodlawn 21207 9 39.374649,-76.746368 Pikesville 21208 Graphic Visualization of Attacks Some Attack Characteristics • The network seeks to make use of close, multi-item producers. • Attacks on farms that deliver multiple items are the most effective at interfering with the network. • Protecting them is important. How? Network Solution Under 7 Attacks 8 New Attack Placements Updated Solution Recommended Build Sites 9 8 7 6 4 5 3 2 1 0 No de Location (Google Maps) Name Zip 0 38.833289,-76.876831 Forestville 20747 1 38.948729,-76.860352 Mitchellville 20716 2 38.993572,-76.889191 Greenbelt Park 20768 3 39.024518,-76.952362 Hillandale 20903 4 39.030919,-77.140503 North Bethesda 20852 5 38.974357,-77.180328 Potomac 20854 6 39.208847,-76.598053 Brooklyn Park 21225 7 39.254588,-76.68457 Arbutus 21227 8 39.305613,-76.743622 Woodlawn 21207 9 39.374649,-76.746368 Pikesville 21208 Other Considerations • Effects of different minimum product delivery times? – We were unable to implement this correctly. It would make for an interesting follow-on analysis. • Effects of customer volume in the model: – Suppose it is known that customer flow in locations is projected with an accepted accuracy. – Costumer flow will directly impact profitability. – Arcs to those more profitable restaurants are now offset by a number corresponding to the projected profitability of the restaurant. Effects • Making Forestville, Artibus and Woodlawn our top three respective forecasted profit makers: Without Profit Adjustment 8 7 6 5 4 3 2 1 0 With 10 8 6 4 2 0 *Limits the usefulness of total shipping time as a cost factor Conclusion • The Network provides an adequate abstraction to study respective delays between certain locations. • The inner problem being a MIP makes for a much more computationally expensive model. • Min Cost flow should be further explored in the context of the problem, where build site construction is attacked, rather than the farms. • How does the adjacency of restaurants affect the model? Questions/Discussion