One to One SystemOne to Many SystemLCF for One to Many SystemOne to Many SystemOne to Many SystemAn Aside: Routing & SchedulingOne to Many SystemOne to Many SystemOne to Many SystemOne to Many SystemOne to Many SystemOne to Many SystemOne to Many SystemTransportation II CapliceLecture 16ESD.260 Fall 2003© Chris Caplice, MIT2MIT Center for Transportation & Logistics – ESD.260One to One SystemMode 11($ / )sr MAX i MAX i m s d vsndLCitemcHcHctc c cvv+⎛⎞⎛⎞=+++ ++⎜⎟⎜⎟⎝⎠⎝⎠Shipment SizevMAX2vMAXCost per Item citm© Chris Caplice, MIT3MIT Center for Transportation & Logistics – ESD.260One to Many SystemSingle Distribution Center:• Products originate from one origin• Products are demanded at many destinations• All destinations are within a specified Service RegionAssumptions:• Vehicles are homogenous•Same capacity, vMAX• Fleet size is constant© Chris Caplice, MIT4MIT Center for Transportation & Logistics – ESD.260LCF for One to Many System Cost Function Storage (Rent) Holding Costs Inventory Holding Costs Transportation Costs Handling CostsKey Cost Drivers?© Chris Caplice, MIT5MIT Center for Transportation & Logistics – ESD.260One to Many SystemFinding the estimated total distance:• Divide the Service Region into Delivery Districts• Estimate the distance required to service each district© Chris Caplice, MIT6MIT Center for Transportation & Logistics – ESD.260One to Many SystemRoute to serve a specific district:• Line haul from origin to the 1stcustomer in the district• Local delivery from 1stto last customer in the district• Back haul (empty) from the last customer to the origin© Chris Caplice, MIT7MIT Center for Transportation & Logistics – ESD.260An Aside: Routing & SchedulingProblem: How do I route vehicle(s) from origin(s) to destination(s) at a minimum cost? A HUGE literature and area of researchOne type of classification (by methodology)1. One origin, one destination, multiple paths Shortest Path Problem2. Single path to reach all the destinationsMinimum Spanning Tree3. Many origins, many destinations, constrained supplyTransportation Method (LP)4. One origin, many destinations, sequential stops -Traveling Salesman ProblemVehicle Routing Problem Stops may require delivery & pick up Vehicles have different capacity (capacitated) Stops have time windows Driving rules restricting length of tour, time, number of stops© Chris Caplice, MIT8MIT Center for Transportation & Logistics – ESD.260One to Many SystemFind the estimated distance for each tour, dTOUR Capacitated Vehicle Routing Problem Cluster-first, Route-second Heuristic2TOUR LineHaul Localdd d≈+dLineHaul= Distance from origin to center of gravity of delivery districtdLocal= Local delivery between c customers in district (TSP)© Chris Caplice, MIT9MIT Center for Transportation & Logistics – ESD.260One to Many SystemWhat can we say about the expected TSP distance to cover n stops in district of area A? Hard bound and some network specific estimates:[][]1.15TSPTSPEdnAEdknA≤≈For n>25 over Euclidean space, k=.7124For straight line (Manhattan Metric), k=.7650/TSPstopnAdnA kdknnδδ===⋅=Density, δ, number of stops per areaAverage distance per stop, dstop© Chris Caplice, MIT10MIT Center for Transportation & Logistics – ESD.260One to Many SystemLength of local tours Number of customer stops, c, times dstopover entire region Exploits property of TSP being sub-divided – TSP of disjoint sub-regions ≥ TSP over entire region© Chris Caplice, MIT11MIT Center for Transportation & Logistics – ESD.260One to Many SystemFinding the total distance traveled on all, l, tours: [][][]22TOUR LineHaulAllTours TOUR LineHaulckEd dnkEd lEd ldδδ=+==+The more tours I have, the shorter the line haul distanceMinimize number of tours by maximizing vehicle capacity []2MAXAllTours LineHaulMAXDlvQnkEd dvδ++⎡⎤=⎢⎥⎣⎦⎡⎤=+⎢⎥⎣⎦[x]+is lowest integer value greater than x – a step functionEstimate this with continuous function:E([x]+ ) ~ E(x) + ½© Chris Caplice, MIT12MIT Center for Transportation & Logistics – ESD.260One to Many SystemSo that expected distance is: [][][]122AllTours LineHaulMAXED EnkEd dvδ⎡⎤=+ +⎢⎥⎣⎦Note that if each delivery district has a different density, then: [][][]122iiiAllTours LineHauliiMAXiED EnEd d kvδ⎡⎤=++⎢⎥⎣⎦∑∑For identical districts, the transportation cost becomes: [][][][][]11222sdLineHaulvsMAX MAXED ED EnkTransportCost c E n c d c E Dvvδ⎛⎞⎡⎤⎡⎤=+++ + ++⎜⎟⎢⎥⎢⎥⎜⎟⎣⎦⎣⎦⎝⎠© Chris Caplice, MIT13MIT Center for Transportation & Logistics – ESD.260One to Many SystemFleet Size Find minimum number of vehicles required, M Base on, W, amount of required work time tw= available worktime for each vehicle per period s = average vehicle speed l = number of shipments per period tl=loading time per shipment ts= unloading time per stop[][]212AllTourswlsLineHaullsMAXdMt W lt ntsEDdkWt Entsvδ≥= ++⎡⎤⎛⎞⎛⎞=++++⎢⎥⎜⎟⎜⎟⎝⎠⎝⎠⎣⎦© Chris Caplice, MIT14MIT Center for Transportation & Logistics – ESD.260One to Many SystemNote that W is a linear combination of two random variables, n and D22[][][][][][]2[,]EaX bY aEX bEYVar aX bY a Var X b Var Y abCov X Y+= ++= + +Substituting in, we can find E[W] and Var[W]21LineHaullMAXsdatsvkbtδ⎡⎤⎛⎞=+⎢⎥⎜⎟⎝⎠⎣⎦⎛⎞=+⎜⎟⎝⎠Given a service level, SLP[W<Mtw]=SL Thus,M= (E[W] + k(SL)
View Full Document