### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Sply Chain ModLogistics ISYE 3103

GPA 3.82

### View Full Document

## 10

## 0

## Popular in Course

## Popular in Industrial Engineering

This 0 page Class Notes was uploaded by Maryse Thiel on Monday November 2, 2015. The Class Notes belongs to ISYE 3103 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/234207/isye-3103-georgia-institute-of-technology-main-campus in Industrial Engineering at Georgia Institute of Technology - Main Campus.

## Reviews for Sply Chain ModLogistics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15

ISyE 3103 Supply Chain Modeling Transportation and Logistics Spring 2006 Winters7 Method Forecasting Example A scatterplot of the following actual demand data suggests the existence of seasonal quar terly variation coupled with an overall increasing trend consequently7 this data is a strong candidate for utilizing Winters7 Method aka Triple Exponential Smoothing 2003 2004 Quarter 1 Quarter 2 155 Quarter 3 98 Quarter 4 219 In this note we will t a Winters model to this data set7 compute the a postem39om39 forecast errors for 2003 20057 and provide a demand forecast for 2006 The smoothing constants are a 027 B 017 and y 005 Recall that the underlying demand process assumed for the Winters model is D a bt It 6 In order to initialize the model7 we need estimates7 do 30 and f3f2f1f0 The method we will use to obtain these estimates is very approximate This is in contrast to the method we used to obtain the initial trend estimates in the Holt modeliregression on a subset of the data If we wanted to utilize a similar methodology for the Winters model7 it would be unnecessarily complicated The implication of using this approximation method of obtaining the initial estimates is that we will still denote time period 1 at the beginning of 2003 In the Holt model we threw out77 the rst few observations after we used them to obtain the initial parameter estimates and denoted time period 1 as the rst period after these initial observations The method we are using basically estimates the average level and trend over the rst two years If we started7 then7 by using those estimates starting with the rst quarter of 2005 as I did in correctly in class today7 we would see that the trend is woefully lagging behind the actual demand realizations We should use the initial model parameters as a basis for forecasting the rst quarter of 2003 and beyond Now we are ready to initialize the model by computing the initial estimates for do and 30 using the data from 2003 and 2004 The estimate of the slope 30 is found by taking the difference in the average demand for the two years and dividing by the number of seasonal periods 7 7 0 7 4 7 4 7 4 We can solve for the level estimate do using the following equation 938 D2003 do Joe5 ISyE 3103 Spring 2006 Winter39s7 Method Example 2 where the trend value equals 25 because that was the average period number for the year 2003 23 Solving the equation7 we obtain do 8505 The next step in the initialization process is to compute trend line estimates for the two years of data using the trend function Dt 8505 A9381t7 t 17 78 Some representative calculations are D1 8505 938 1 9443 and D7 8505 938 gtk 7 15071 2004 Quarter 1 Quarter 2 10381 Quarter 3 11319 Quarter 4 12257 14133 15071 16009 We can use these trend line estimates to develop initial seasonal indices by taking the actual demand for each period and dividing by the trend line estimate for that period For example7 155 and 1413733 090 We average the two indices for each quarter to obtain the average index for that quarter7 and then we normalize the average indices by dividing each by 406 and multiplying by 400 to ensure that they all add up to 4 2003 2004 Average Initial Index Index Quarter 1 155 146 151 14828 Quarter 2 092 090 091 08965 Quarter 3 052 052 052 05123 Quarter 4 109 116 112 11084 E 406 E 400 The values in the Initial Index77 column above are our initial estimates ofthe seasonal factors at time t 1 which denotes the rst quarter of 2003 Speci cally7 we have 3 148287 2 089657 1 051237 and f0 11084 We are now in position to make the rst forecast7 which is for the rst quarter of 20037 according to the following formula flgo a0 301 113 8505 938 14828 1400169 Since we have a new data realization D1 1467 we can incorporate it into the model via the Winters model updating equations to obtain new estimates for the parameters The general Winters7 method updating equations to be used at the end of period t are A D A A at 04 A t 1 04 171 bt71gt Item bt B at dt7117 tA D A It th 1 YIt7m at Using these equations7 we obtain the following updated parameter estimates at the end of time period 1 lSyE 3103 and lSyE 6203 Transportation and Supply Chain Systems Automatic Identi cation and Data Collection Technologies 1 Introduction Item identification and data collection are extremely important in supply chain systems Many different models are used to optimize and control various portions of a supply chain All these models depend on having quality data inputs without the data the models are useless Anyone who has ever done any work in industry can tell a story of a problem they have had with data when working on a problem Manual collection of data can be slow and hence costly and more importantly is highly prone to errors For example if part numbers are manually input by a keyboard the error rate is approximately 1 in 300 However if the same data is collected with bar codes the error rate is approximately 1 in 3 million a huge difference Thus we turn our attention to automatic identification and data collection AIDC technologies that can be used to collect the required data accurately and at a reasonable cost After data has been collected with these technologies it must be stored and processed by information systems typically a database this subject is covered elsewhere We mentioned that models require quality data to be useful What exactly is meant by quality data Some characteristics of quality data are the following 0 Accuracy The data must be correct 0 Timely The data must be available when it is needed for making decisions 0 Effective The data must be relevant for the decisions being made For exam ple data about the exact specifications of a product is probably not necessary for making decisions about which mode the product should be shipped by c Reliable The data must satisfy the above qualities consistently Data that is occasionally of poor quality won t be trusted and hence is less likely to be used even if it is usually good 2 Types of AIDC Technologies Below we list some of the many different types of AIDC technologies 0 Bar coding The is the most prevalent form of AIDC and it will be discussed more extensively later in this document Radio Frequency Identi cation With this technology identi cation and data cap ture is done via radio waves Optical Character Recognition This technology can read the same printed words and symbols that we read and convert them into electronic format This technology is heavily used by the United States Postal Service for reading addresses IlIagnetic Ink Character Recognition This technology is heavily used in the banking industry for example by encoding the check and bank routing number on checks in magnetic ink The data can then be read in a similar to optical character recognition Magnetic stripes Data is stored in a magnetic stripe such as on the back of a credit card Smart cards Data is stored in a small chip embedded in a card such American Express cards One advantage over magnetic stripes is that more data can be stored in the chip Biometrics This includes technologies that can identify a person by looking at their ngerprints or eye This document will focus on bar coding and radio frequency identi cation RFID since they are the most widely used AIDC technologies in supply chain systems 3 Uses of AIDC AIDC technologies are used in a wide range of industries In this section we describe some examples Retail Bar codes are on essentially every product we buy By one estimate the retail industry does 35 million bar code scans per minute Manufacturing Bar codes and increasingly RFID are used extensively in the manufacturing industry to track inventory and work in progress and to assist in quality assurance Distribution AIDC technologies are used in distribution systems to automatically record incoming and outgoing shipments Healthcare This is an industry that has been slower to adopt AIDC technologies in all areas but there is great potential For example consider a nurse administering medicine Before administering he scans the patient tag his own id and the medicine If he is attempting to administer the wrong medicine or medicing that should not be taken with other medications the patient is taking a warning goes off Bar codes have even been used to keep track of bees in experiments Little bar codes have been placed on the bottoms of the bees for identi cation purposes 4 Bar Coding We now turn to talking speci cally about bar coding the most prevalent type of AIDC technology A bar code is de ned a spacial representation of encoded characters 41 Bar Code System Steps There are a number of steps that typically must be followed when implementing a bar code system H Coding requirement The rst step is to determine what data needs to be stored on the bar code For example are we storing part numbers lot numbers etc 3 Machine readable language A standard format for the bar code that can be read by a machine must be decided upon This is referred to in the bar coding terminology symbology S Bar code printing The bar codes must be printed onto labels or directly onto the items they will be identifying 3 Bar code veri cation Quality control measures must be taken to ensure the bar codes can be read reliably C Bar code scanning This is the step where data is actually captured 333 Transmit data After being captured the data must be transmitted to an informa tion system gt1 Use the data This step is almost too obvious to mention but it s too important not to mention If there is no use for the data the bar code system is just a waste of resources 513 cm Slop 09 I I muel Gum Zone Dimenslon 10 mm a m 1 we myan 4 2 qvmbulugy and Dam gumm a 1m mmmm 1m r mum w r mm mucwm NullVow a W m mama w mm we ummmm m mm Wm mum mucwm a w mo Ath mde m Mum wwwmch 0 mm mm um m m m We mmm m manqqu mm mum on m 5 tut100mb mamm um w W m new m mime om chockwwumu u o ummm mukmwuwonmrw Amuwhomw mu m M a m Figure 2 The top bar code is a twodimensional stacked bar code and the next one down is a matrix bar code Data structures are used for both bar coding and RF lDA The Global Trade ltem Number GTlN is an umbrella group under which all different types of data structures now l39alL The GTlN allows for 14 digits but the specilic data structures that fall under GTE may not use all 14 digits The most common example of a speci c data structure is the UPC which is on most of the products you purchase The data structure that is becoming standard for use in RF lD chips is known as EPCT The ET C structure consists of a header plus three sets of data The header includes information such as the EPC version number so that changes to the EPC structure itself can be managed The lirst set of data is a code for the EPC manager such as the manager of the product The second set of data indicates the object clas which specilies the exact type of product eg Diet Coke 330 ml can The linal data set stores a serial number which is specilic to the specilic iteml 43 Bar Code Readers Bar code readers can be handheld or handsl39reel Hands l39ree scanners are more ef cient when it is easier to bring the bar code to the scanner than it is to bring a handheld reader to the bar code Hands l39ree laser quotanners are often used in checkout lines in grocery stores We discuss three of the most common types ol39handheld bar code readers belowi Figure 4 A Charged Couple Device Wands Wands are penlike readers with a laser at the tip see gure 3 A bar code is read by a wand by moving the wand over the bar code The advantages of wands are that they are lightweight inexpensive and rugged In addition they require less power than other types of readers and hence could be good for mobile use in which the reader must be powered by a battery One disadvantage of a wand is that there is relatively more training required for people to use them In addition because wands have to be moved across the bar code they are less efficient and because they come in contact with the code during the scan they can eventually damage the bar codes if they are read repeatedly Charged Couple Devices CCD CCDs work by flooding the entire bar code with light An example of a GOD is shown in gure 4 CCDs are moderately costly and are to use In addition they are rugged because they do not have any moving parts to break Other advantages of CCDs is that they are lightweight and typically produce decoded output The primary disadvantage of CCDs is their limited depth of eld The eld of depth of a reader is the distance from the bar code which the reader must be in order to successfully read the code Laser The most commonly used handheld bar code reader is the laser an example is shown in gure 5 Because they are so common lasers have the advantage of being widely accepted Figure 5 A Laser Bar Code Scanner Figure 6 These bar codes can dissolve in water by users The other primary advantage of lasers is that they have a wider depth of eld than the other handheld readers One disadvantage of lasers is that they have moving parts mirrors to direct laser beams and hence can breakdown easier In addition they have higher power requirements than the other types of readers and are more expensive 44 Bar Code Labels It is often more convenient to print bar codes on a label which is subsequently placed on a product than to put the bar code directly on a product There are a huge variety of different types of bar code labels that can be useful for widely different applications Bar code labels characteristics include cost texture ease of application resistance to the elements tendency to peel life eXpectancy and resistance to scratching and tearing There are even bar code labels that are made that are designed to dissolve in water see gure 6 Bar code labels can be made from a variety of materials including paper vinyl and polystyrene When choosing the type of bar code label to use it is important to nd the bar code label that meets the speci c needs of the application they will be used for 45 Bar Code Printing The rst major decision to make with bar code printing is whether to have the printing done onsite or offsite With onsite printing also known as imprint or ondemand printing there is a large initial investment that must be made to purchase the printers w ammo 1mm wa ma mam w aumuo m mu m m M 11 Vow I M1 o4 mwmnw n w oVrA ltd1Lol lt m Vmowm Jomm m mm a m mm 1 Km L0 mm m m mm m md woman m m MAM am cm W w a mm mewwww L0 Mable L0 um um m ury w u mwm nmww 1 um mm W nx a u ML Mauro1mmMuomucu r Yo rwdo a m m uumuwul m m WWW we am mum w Ld M WHRmrmuwmrmu p L mwmw mqu Mawmmmoomam wmuqumxo of mm mm 11 m 1mm gown w m V W cm am mm m MW Mme Wm M rm 1 mumm ww r mmmwowmoka w wVwoowm m mm 11 m r mu KW1101 mm l ltumoltql L mm we of u q mm MaIL mm mm 1qu o m m wwwk mm mm m x m armm mwmuw m w v 1 mm Mquot u ww Wm mm mmmmoi m mm mm mmuocwImuwcoi m a Mm LNN LNNM mu ltmmm wmamomWmwwmmw M w Curls Vuriiimtiuu m we mmuow 1 1 00 w mm1W w LNIm WW mo1a u m 14 m V x m mumwmuw am1mm r mm mm wva m mam um um WW 1 mm m mmuo mm m nmm 01me m lm mm 1 L0 uwwwwouon w mm Mkltme ham u mm mm mow L m m Wm M tomc m wquo mm mm m be effectively lost Companies take the quality of bar codes on their products seriously For example VValmart has been known to fine its suppliers 50000 for having poor bar codes on the cases they supply Bar code verification involves more than just scanning the bar code after printing to see if it scans Separate machines are used for verification which measure various characteristics of the printed bar codes to judge whether the bar code can be read reliably by different types of readers and whether it is likely to continue to be readable even after slight degradation At a minimum verification should be done at the beginning sometime at the middle and at the end of the printing process In addition any time something is done to the bar code such being laminated or varnished verification should be done again Some major users of bar codes such the Department of Defense have specific guidelines on how bar code verification should be done 47 Costs of Bar Coding The average bar coding implementation can cost between 50 and 250 thousand dollars However companies have reported that the average payback on this investment is typi cally quite short averaging about 5 months When considering the costs of a bar coding implementation it is important to compare it to the costs of not implementing bar cod ing and the data errors that can result For example there are costs associated if you ship the wrong item to a customer Imagine the potential costs if a company installs the wrong part on an aircraft Some costs of potential data errors cannot even be measured for example if the wrong medicine is administered to a patient leading to a fatal reaction Considering the potential costs of data errors bar coding will generally be considered a bargain 48 Advantages and Disadvantages Two advantages of bar coding are that it is relatively inexpensive and widely used and accepted in industry In addition bar coding is based on an open system Thus the standards for symbologies and data structures are not owned by a single company and are open knowledge so that no royalties have to paid for the use of a specific bar coding method In addition the prevalence of established standards for bar codes facilitates the use of bar codes that can be used throughout the supply chain by different companies A primary disadvantage of bar codes is that the symbol must be visible to be read For example if there is a bar code on each case on a pallet and each case must be identified the pallet may hay have to be unstacked to read the bar codes of all the cases Another disadvantage is that the data in a bar code is static Thus if the data changes a new bar code must be printed and the old bar code must be rendered unreadable Additionally bar codes are susceptible to damage from harsh conditions and could be rendered unreadable or separated from the product 5 Radio Frequency Identi cation Radio Frequency Identi cation RFID is an AIDC technology that is being used increas ingly in supply chains because it can effectively overcome some of the disadvantages of bar coding RFID is a system in which data is stored on a machinereadable tag and is transmitted to the reader by radio waves Therefore no lineofsight is required to read the data stored in RFID tags is required to read bar codes In addition RFID tags can be built to be more resistant to the elements and can be enclosed inside protective packaging and so can be used in harsh conditions in which bar codes would be less effective RFID is gaining in prominence due to some recent requirements set by major cus tomers For example VValMart is requiring its top 100 suppliers to put RFID tags on all their pallets by the end of the year and is requiring the same of all its suppliers by 2006 In addition VValMart has strict requirements on the capabilities these RFID tags must have For example they require that the tags should be readable when on con veyors moving fast 540 feet per minute These types of requirements will push the development of RFID technologies Similarly the United States Department of Defense is requiring its suppliers to put RFID tags on its products and is even requiring that the tags be put on individual cases or items in some cases 51 RFID System Components An RFID system consists of the transponders or tags that are placed on the items and the antenna and transceiver devices used to read the data RFID tags can be classified active or passive and read write or readonly The difference between active and passive tags is that active tags have their own power source whereas passive tags get all their power from the radio waves transmitted to them Active tags use battery power to transmit and receive data and can store fairly substantial amounts of data much 1 MB Because they have their own power source they have a longer read range than passive tags The disadvantage of active tags is that they are larger and more expensive and have a limited lifespan based on the battery life although lifetimes can be long 10 years Passive tags have shorter read ranges and require a more powerful reader The advan tage of passive tags however is that they are lighter less expensive and have a virtually unlimited lifetime If made cheap enough there is speculation that passive tags could eventually replace bar codes on products An example of a passive tag is the antitheft hard plastic tags used in retail stores These have a small RFID chip in them that can be read by transceivers at store exits to detect if an item is being taken out of the store without being paid for With read write tags it is possible to write new data onto a tag well read the data on the tag Readonly tags can only have data written to them once after which the data can only be read Typically read write tags are active whereas readonly tags are passive Figauo S An RFID Antenna nether hey errrpenent er an REID system is the antenna whieh is what aetuaiiy transrm gtradi w 390 to the tag or fromthe tag in the ease ofan ye ta antennae e me in many di mom shapes a t s an tgtxamphgt is in tmro 5 and ean use many di mom frequenei andLVJi a yhawhmjtodmngo ithatinterfereneewith it i he ayei ed haye dif mh transrrritting threugh metaIIie ehjeets The iinaI eerrrpenent er an temi the tra gtiyer ereentreIIerwhieh w at tahes signaIs fmm the antenna and transmits it te a eerrrputer 0139th the transeeiyer and the antenna are huruiIed tegether singIe item 52 Applications of RFID A appIieatiens in many industries and the nurrrher er appIieatiens is gmwing Iewing are seme exarrrpIes i re an n 1 39 RI ID tags on Iai and inelallod anwnnav by tmrk and w mark of vhmo mi ram aw vhi 39 Mo huts te heep eh raeiIitates impmvod iieet uti tien quot 39 The feedanrin v v v REID fer aii metiie t39 shy 2007 te eemhat eeunterreit drug 39 new We haye ahead rrrentiened that REID tags are used fer eIeetrenie suryei Ianee er pmde te preyent thert REID tags ean he piaeeti in ears te reeerd when a eth se that the teii ean he tieiueteti fmm the tiriyers gtr haying to stop to pay the to 0 Aniamica Tall Calleriian ear ras es threugh a th he aeeeunt rather than the dIi Cani allsdArrenn 0f Permittel REID tags e Ihe pl ed in persenneI name tags te re rietaee te seeure and h Idol h at 39 wad to Flexible Manufacturing 81152611 REID tags en pmdu s ean he ea 39 identify speeiiie pmdu yariants fer autemat preees eentreI 53 Item level RFID As RFID tags become cheaper it may become costeffective to place RFID tags on every item for items that are not too cheap The implications for a retailer in this case are huge It would then be possible to know exactly how many of each product are on the shelf at any time allowing for improved control In addition this technology could eliminate the need for scanning every item when a customer checks out Instead the customer could just push their cart through the RFID reader and the total charge could be instantly calculated There are a couple challenges that need to be overcome before RFID will become prevalent at the item level First RFID tags still are not cheap enough to be placed on the majority of products Second there is a disconnect between who bene ts from itemlevel RFID tags retailers and who has to pay to put them on manufacturers Therefore before RFID will be implemented at the item level in large scale a mechanism has to be created to allow the manufacturers to share the bene ts Finally there are people who are concerned with privacy issues with putting RFID tags on all items we buy People may be unhappy with the prospect that companies can keep track of everything they own and buy These same types of issues came up with the introduction of bar codes and the concerns generally were proven to be unfounded or at least consumers were willing to accept them to achieve the increased convenience offered by bar codes The same may occur with RFID technology but it will require careful attention to consumer desires such the option to disable an RFID chip after a product is purchased and education of consumers such informing them that it would not be possible to read an RFID chip on a product in their house from the street 54 Advantages and Disadvantages One Of the principle advantages of RFID over bar coding is that there is no line of sight required to read an RFID tag In addition active RFID tags have the capability to be read write so that the data stored can be changed over time This capability allows tags to be used a sort of moving database RFID tags also have the advantage of being more suitable for harsh conditions since they can be placed inside protective packaging and still be read The principle disadvantage of RFID tags is their cost Even the cheaper passive tags are still signi cantly more expensive than bar codes and until this cost can be brought down substantially there will still be a large role for bar codes to play in supply chain automatic identi cation and data collection Another disadvantage of RFID tags is the challenge of gaining consumer acceptance and overcoming the privacy concerns consumers may have ISyE 3103 Minimum Spanning Tree Models First7 we start with some technical information Recall the de nition of a network model G N7 A Suppose there are n nodes Path A path P in G is a sequence of nodes connected by edges in the network In our study of Minimum Cost Path problems7 we identi ed methods for determining the minimum cost paths in G from a given starting node 5 to all other nodes in the network Cycle A cycle is a set of edges that forms a closed loop in G you can begin walking at some node7 follow only edges in the cycle regardless of their direction7 and then return to that node Thus7 a cycle G is a sequence of nodes7 connected by edges7 that are unique except that the rst and last nodes in the sequence are the same Trees A tree T in G is a collection of edges such that all n nodes are connected7 and no cycles exist All nodes connected implies the existence of a path between all pairs of nodes on T An equivalent de nition of a tree is a set of n 7 1 edges such that all nodes are connected An important property of a tree is that it de nes7 for each pair of nodes7 a unique path between them Minimum spanning tree A minimum spanning tree T in a network where each edge m has a cost 017 is a tree such that the total cost sum of all the arcs in the tree is minimized Question ls the minimum spanning tree the same as the shortest path tree Answer No In the shortest path tree7 the length of the path from some origin node to each other node is minimized In the minimum spanning tree7 the total cost of all the arcs in the tree is minimized This is not the same thing Finding the minimum spanning tree Two algorithms that you can use Both of them are quite fast7 and easy to understand Kruskal7s algorithm Initialization TREE Q Iterations 1 Sort the arcs in order of increasing Ci 2 For each edge in the order from step 1 a Add i7j to TREE if so doing does not create a cycle b If number of edges in TREE n 7 17 STOP At the end7 T H TREE Basically7 Kruskal7s algorithm looks at the lowest cost edges rst and tries to include them in the tree7 as long as doing so does not create a cycle which would prevent a tree from being formed Prim7s algorithm Initialization TREE 0 LIST 1 ln English7 the set LIST contains node 17 while the set TREE is empty Iterations Do until number of edges in TREE n 7 1 1 Find the least cost edge from a node in LIST to a node not in LIST7 say i7j where i is in LIST andj is not 2 Add i7j to TREE 3 Add j to LIST At the end7 T TREE Prim7s algorithm works by keeping a tree on a subset of the nodes and in each iteration expanding the tree to include another node at minimum cost ISyE 3103 Notes Vehicle Routing De nition Suppose a eet of vehicles is based at a depot referred to as node 0 Each vehicle in the eet can transport a maximum of Q units weight volume pallets items etc Suppose further that a set of 71 customers nodes 1 through 71 are dispersed in a region near the depot Each customer 239 demands that a quantity q measured in the same units as Q be picked up or delivered and that this quantity may not be split between vehicles Travel between locations 239 andj incurs some cost eij Then the vehicle routing problem VRP is to nd a set of vehicle tours each beginning and ending at the depot such that each customers demand is fully served no vehicle violates its capacity and the total travel cost of all vehicles combined is minimized A combination of TSP and Bin Packing The standard vehicle routing problem can be thought of as a combination of the bin packing problem and the traveling salesman problem First it should be clear that if trucks were very large for example so large that a single truck could carry the quantities demanded by all customers eg Q 00 the VRP reduces to a traveling salesman problem The solution to the VRP would simply be a TSP tour through all customers and the depot Thus since the TSP is a special case of the VRP the VRP is at least as hard to solve as the TSP The bin packing problem is also a special case of the VRP To see why this is true suppose that the costs eij on all arcs between customer locations were zero and the costs on arcs between customes and the depot had a cost of In this formulation the optimal solution to the VRP uses as few vehicles bins as possible in order to minimize the amount of travel in and out of the depot and the solution to the problem is the minimum number of bins required Of course this is exactly the objective of the bin packing problem Heuristics for the VRP Since VRP is at least as hard as TSP and bin packing no one to date has been able to develop an ef cient optimal algorithm for the VRP Therefore we will again focus our attention on heuristic algorithms that lead to reasonably good solutions In general however the heuristics that have been developed for VRP do not result in solutions of comparable quality to the TSP heuristics I ClarkeWright Savings Heuristic The Clarke Wright method begins with a poor initial solution in which each vehicle visits a single customer Tours are then combined as long as total cost savings are produced Suppose the depot is node 0 1 For each node 2 E N construct a tour T beginning at the depot traveling to node 2 and returning to the depot Let S be the set of tours E0 Calculate the savings SM co 070 7 07 for all pairs of nodes 2j 9 Sort the savings in nonincreasing order 4 Walk down the savings combination list and nd the next feasible combination pair 2j such that a 2 and j are on different tours and 2 is the last node on its tour Tk and j is the rst node on its tour Tl b ZkeTiUTj 9k 3 Q C 52739 Z 0 Add the combined tour T to S and remove T and Repeat this step as long as feasible combinations remain in the savings list Note that ifthe costs 07 satisfy the triangle inequality for example ifthey were generated by nding the min cost paths between all pairs of nodes then the third condition SM 2 0 would always hold and so need not be checked II Cluster rst Routesecond Heuristics Often in practical vehicle routing problems the subproblem of determining which cus tomers to group together in a cluster served by a single vehicle is relatively more im portant than routing considerations Since effective clustering can lead to reduced eet sizes through better packing problems in which dispatch or xed vehicle costs are high may include packing as a primary concern However it can be shown that by focusing on clustering before routing even in the traditional vehicle routing problem focused on distance based costs can result in good heuristic solution methods Sweep Heuristic In the sweep heuristic nodes must have geographic positions Without loss of generality suppose that the depot is given cartesian coordinates 00 and suppose each customer 2 has polar coordinates n 19 relative to the depot Here suppose 0 S 0 lt 27139 is measured clockwise from the positive x axis H Choose a start ray 139 with a polar angle 0 E0 For each customer calculate A as the relative angle between I39 and the customer location measured clockwise 9 Sort the customers in order of non decreasing Ala Suppose the order created is To 2391723927 7Z39n39 Create customer clusters by running the next t bin packing heuristic with lot sizes q and vehicle capacity Q on the customer order de ned by TO 7 9 Create nal VRP tours by generating a separate TSP tour for each customer cluster and the depot Basically the rst three steps create an ordering of the customers by 77sweeping a ray from the depot and putting the customers in the order in which the ray passes over the customers III Improvement Heuristics Given an initial solution to the Vehicle Routing Problem we can try to improve it in much the same way we tried to improve solutions for the traveling salesman problem Any improvement heuristic is de ned by the neighborhood of a solution which is searched to nd an improving solution We discuss this concept with two examples TSP 20PT The TSP 2 OPT neighborhood corresponds to simply trying to improve each tour within the vehicle routing problem solution in the same way a tour is improved by the 2 OPT heuristic for the traveling salesman problem In this case the neighborhood of a solution that is searched is the solutions that can be obtained by removing 2 edges and inserting 2 different edges to create a new tour InsertSwap In this neighborhood VRP solutions can be modi ed by moving customers between tours in addition to improving the tours themselves Speci cally a customer can be removed from a tour and inserted in a different tour in the best possible place as long as the new total load on the tour in which the customer is added does not exceed the capacity That is customer 2 can be removed from its current tour T and inserted into tour as long as ZkeTj qk q S Q In addition a pair of customers 2 and j can be swapped between two tours as long as the loads in the resulting tours do not exceed capacity that is ZkeTi qk qj 7 21 S Q and ZkeTi qk q 7 qj S Q Thus the improvement 200000 180000 160000 140000 120000 100000 80000 60000 IHI WHlu 2002 2003 2004 2005 OFFERTORY Dependent Variable OFFERTORY Method Least Squares Date 022005 Time 2250 Sample 2001 07 200501 Included observations 43 OFFERTORY 01 02TIME 03DEOEMBER 04 FIVEWEEKS Coefficient Std Error tStatistic Prob 01 8718724 3009023 2897526 00000 02 6777826 1178071 0575333 05684 03 5473738 5298224 1033127 00000 04 2377941 3116701 7629672 00000 Rsquared 0864393 Mean dependent var 1019159 Adjusted Rsquared 0853962 SD dependent var 2480117 SE of regression 9477752 Akaike info criterion 2123969 Sum squared resid 350E09 Sohwarz criterion 2140352 Log likelihood 4526533 DurbinWatson stat 1406046 Method Least Squares Sample 2001 07 200501 Included observations 43 Dependent Variable OFFERTORY Date 022005 Time 2252 OFFERTORY 01 C2DECEMBER C3FVEWEEKS Coefficient Std Error tStatistic Prob C1 8588178 1959652 4382502 00000 C2 5473738 5253731 1041876 00000 03 2352598 3059506 7689471 00000 Rsquared 0863242 Mean dependent var 1019159 Adjusted Rsquared 0856404 SD dependent var 2480117 SE of regression 9398161 Akaike info criterion 2120163 Sum squared resid 353E09 Schwarz criterion 2132450 Log likelihood 4528350 DurbinWatson stat 1389115 Dependent Variable OFFERTORY Method Least Squares Date 022005 Time 2258 Sampleadjusted 200108 200501 OFFERTORY1 Included observations 42 after adjusting endpoints OFFERTORY 01 02DEOEMBER 03FIVEWEEKS 04 Coefficient Std Error tStatistic Prob 01 6362151 5970 778 1065548 00000 02 5315912 4521819 1175614 00000 03 2736420 2784044 9828940 00000 04 0206708 0053222 3883850 00004 Rsquared 0905236 Mean dependent var 1019839 Adjusted Rsquared 0897755 SD dependent var 2509775 SE of regression 8025194 Akaike info criterion 2090895 Sum squared resid 245E09 Schwarz criterion 2107444 Log likelihood 4350880 DurbinWatson stat 1784591 ISyE 3103 Single Vehicle Routing the Traveling Salesman Problem Let7s consider the routing of a single vehicle that must make an optimal circuit of a set of locations Optimality will be de ned according to a single summation cost criterion Complete Undirected Network with AInequality To do so in most applications7 the rst step is to develop a complete undirected network satisfying the A inequality G N7 A7 where N is limited to the set of locations through which we would like to build the circuit In a complete network7 an arc exists connecting each node to every other node A complete undirected network with n nodes always contains 0n2 arcs Furthermore7 suppose that the network satis es the A inequality with respect to a set of arc costs cij cji De nition 1 A inequality on Complete Networks A complete network G N7 A satis es the A inequality with respect to arc costs cij i for all i7j7k E N the following relationship holds cm 3 CH cjk As an aside7 there is also a notion of a A inequality for networks that are not complete De nition 2 Triangle Inequality on Arbitrary Networks A network G N7 A satis es the A inequality i for all arcs i7 k E A and intermediate nodesj E N the following relationship holds cm 3 G Ca where G represents the minimum path cost from nodei to node j A network satis es this assumption if the arc from i to j always has no greater cost than a path through a different node7 say k Generating Complete Undirected Network with AInequality Many transportation problems are associated with a fundamental underlying infrastruc ture network G NZA which is not complete7 nor does it satisfy the A inequality For example7 G may be a network of road segments However7 such a network may can be converted to a CUNDl through the use of a minimum cost path procedure Suppose N C N is the set of nodes of interest in a routing problem We can construct a CUNDl G N7 A where the arc set A includes an arc from each node in N to every other node in N7 and the cost on arc i7j is the cost of the minimum cost path from i7j in G Clearly7 in cases where the cost of the path from i to j differs from the cost from j to i7 this procedure will not work however7 this assumption is frequently valid Also7 there must exist some path between all nodes in N Traveling salesman tours and subtours Let7s now de ne the traveling salesman problem on some CUNDl G N7A7 where lNl n7 with arc costs cij cji TSP tour a visitation order or sequence of all the nodes in N T i1i2 ini1 where ik E N and unique Subtour a sequence of nodes with a common start and end node such that not all nodes in N are visited i1i2 iqi1 ik E N and unique q a positive integer lt 71 Tour costs and optimal Traveling salesman tours Tour cost the cost of a tour is simply the sum of all of the arc segments traversed in the tour CT Emmi Chili Optimal traveling salesman tour the traveling salesman TSP tour that requires the minimum total cost TSP argminTeaCT The problem of determining the optimal TSP tour in a network is in general a very dif cult problem and much more dif cult than nding a minimum cost path or tree on a network It is in the problem type NP hard which essentially means that no one has discovered an ef cient optimal algorithm to solve all instances of the problem In fact the TSP problem is perhaps the most studied of all operations research problems An enumeration algorithm One inef cient way to determine an optimal TSP tour is to simply enumerate each possible tour and pick the one with minimum total cost How many tours in a network with n nodes Why From a start node one can go to n 1 nodes next Then a choice of n 2 nodes and so on We divide by 2 since tours since in an undirected network half of these tours are just the reverse of other tours So the enumerative method is an 0711 algorithm optimal but not ef cient Be quite con dent that an inef cient algorithm will not be aided by improvements in computation speed for large problem instances Consider the following chart 77 6 Since there are only about 315 million seconds in a year let7s consider the performance of the worlds fastest computer performing TSP enumeration on a problem with 100 nodes Currently the Earth Simulator performs a peak of 41000 giga ops billion operations per second this performance is not sustainable but suppose it was The Earth Simulator would require 9815 million years to complete 2 100 operations and 72266 136 years to complete 1001 operations Heuristic algorithms A heuristic or heuristic algorithm provides feasible solution to an optimization problem which may or may not be optimal Good heuristics give solutions that are close to the optimal solution and usually are ef cient in terms of theoretical or practical running time A desirable property of a heuristic is that the worst case quality of the solution provided can be guaranteed For example some heuristics guarantee that the solution they identify is at worst a optimal that is if the optimal cost is 0 the heuristic nds a solution no greater than aC for minimization problems Importance of Lower Bounds for Hard Minimization Problems When solving hard minimization problems like TSP problems we usually cannot know the cost of the optimal solution for a given instance Even if we were handed the optimal solution it is a dif cult problem to recognize it as such So how do we know if the cost of a feasible solution developed by a heuristic for a given instance is close to the optimal solution cost Suppose that TH is some feasible tour identi ed by a heuristic Clearly we know that CTH 2 CTSP But how close it Often we can compare our heuristic solution cost instead to an easily identi able lower bound on the optimal cost Suppose QTSP is a lower bound for the TSP cost for a given problem Then CTSP 2 QTSP If the bound is close to the optimal solution tight then comparing CTH to QTSP is a good proxy And if a heuristic solution is 04 percent higher than a lower bound it is clearly no greater than 04 higher than the true optimal cost Developing good lower bounds for hard minimization problems is often nearly as hard as developing the optimal solution However any reasonable lower bound is often a good start A simple lower bound for the TSP Often we generate lower bounds using a decomposition strategy For example suppose a feasible solution to a problem can be decomposed into two components If these two components are optimized separately the resulting solution may not be feasible for the original problem but the resulting cost is a lower bound on the optimal cost of the original problem Consider any feasible solution to the TSP that is a tour visiting all nodes in G Suppose TOUR is a set containing all of the arcs used in the tour clearly lTOURl 71 If one arc 27 from the tour is removed the remaining structure is a TREE on G all nodes are connected and the TREE contains 71 7 1 arcs ln set terminology we could write this decomposition as TOUR TREE Z39jlz39j E A TREE The cost of a tour could then be written as follows CTOUR CTREE c Now lets minimize the decomposition Clearly the minimum cost tree in a network is given by the MST Therefore a lower bound on the optimal TSP cost is the following CTSP 2 CMST c where 02 is the cost of the minimum cost arc not in MST Heuristics for the TSP I Construction Heuristics 1 An aapproximation heuristic MST 2 approximation Steps H Generate a minimum spanning tree MST of the nodes N P Let LIST contain two copies of each arc in the minimum spanning tree MST 3 Generate a WALK of nodes of G using each arc in LIST exactly once 111112 112n111 Note that 1 are not unique 4 Create a heuristic tour TH by following the nodes in the order speci ed by WALK but skipping repeat visits to any node the taking shortcuts77 process a Let tz39 0 for all t E N TH 0 b for t 1 to 2n 71 i if tv 0 then TH TH 1 andt1 1 5 TH lt TH 11 In this method recognize that WALK does not t with our de nition of a tour since it may contain nodes that are visited more than once So we simply eliminate repeat visits in our WALK to identify TH sometimes referred to as an embedded tour Generating a walk of the nodes Generating the walk of the nodes above is always possible since the arcs in LIST form what is known as an Eulerian graph Walks in such graphs can be identi ed using a simple recursive procedure Pick an arbitrary node 01 as a starting point and create a walk of some but possibly not all of the nodes WALK1 iii102030201 Now remove the arcs you just used from LIST and examine the remaining structure You now may have additional disconnected walks that may need to be attached to nodes in the main walk For example perhaps you nd a new walk attached to 113 U314151413 Again re move these arcs from LIST Then you update WALK2 1111120304v5v4113112111 Keep proceeding recursively in this fashion until no arcs are left in LIST For example in Figure 1 suppose a TSP tour is started at node 1 One example of a WALK that could be generated would be WALK 1213431 This tour contains unnecessary return visits to nodes and has a total cost of 12 2 gtk 3 2 1 Applying the shortcut procedure a tour would begin at 1 and move to 2 The walk speci es a return to 1 so we look ahead to the next unvisited node which is 3 The shortest path from 2 to 3 is along arc 23 so we add this arc to the tour T is now T 12 23 Next WALK tells us to visit node 4 and since it has not yet been visited we move along the MST T 1 2 23 34 Next the WALK speci es a Figure 1 The dark black lines represent the minimum spanning tree return to 3 Since it has already been visited7 we move ahead to the next unvisited node Since all nodes have been visited7 we return to the start node 1 along the shortest path7 which happens to be arc 471 The nal tour is T 1727271 0737474717 with a cost of 10 Proof of the 2approximation The MST 2 approximation heuristic will generate a TSP tour with a cost no greater than double the optimal cost for networks satisfying the triangle inequality This is not good7 but at least its a guarantee Proof First7 we know that the heuristic tour we generated has a cost less than twice the min imum spanning tree7 since we started with a walk with cost exactly equal to 20MST and then reduced its cost by taking shortcuts due to the A inequality CTH 20MST Now7 suppose that you were to remove a single arc from the optimal traveling salesman tour the result is a tree Let7s call it TSPTREE lt7s clear that the minimum spanning tree cost is always no greater than the cost of any TSPTREE CMST CTSPTREE and of course7 the cost of any TSPTREE is no greater than the cost of the optimal TSP tour for problems with nonnegative arc costs CTSPTREE CTSP The result now follows CTH 20MST 20TSPTREE 20TSP 2 NearestNeighbor heuristic The nearest neighbor heuristic is a greedy local search method for TSP which maintains at each step a current path Starting at an arbitrary starting node it scans neighbors77 of either one or both current path endpoints and adds the closest neighbor to the tour The last step of the method connects the remaining two endpoints together Initialization Given an undirected network G N A with costs 0 associated with each ij E A Alternative 1 P ij where arc ij has minimum cost among all arcs Alternative 2 Choose an arbitrary start node i and nd j E N such that 07 is minimized Let P ij Steps while lPl lt n 1 Let s beginP and t endP the nodes at the beginning and end of the current path 2 Choose the node k E N P to enter the path Alternative 1 Let k be such that ctk is minimized P P Alternative 2 Let k be such that cm or CM is minimized The new path P is either P or P respectively end Let T P beginP Tour Generation The nodes in T now de ne a TSP tour when followed in order This heuristic is simple to understand without resorting to precise pseudocode At each step the current tour T contains two endpoints that is nodes connected to only one arc in the tour At each step of the algorithm the arc with minimum cost connecting an endpoint to a node not yet visited by the tour is added to the tour If no unvisited nodes remain a connection is formed between to the two endpoints to complete the tour 3 Nearest insertion heuristic Initialization Given an undirected network G N A with costs 0 associated with each ij E A where 0 satis es the A inequality Find the arc ij with minimum cost in A Let T ij i Steps while lTl lt n 1 1 Find the node j T that is closest to a node currently in T That is7 nd j Ti 6 T such that CM is minimized 2 Find the insertion location for node j into the existing tour To do so7 nd the arc 716 in the current tour with the minimum insertion cost 01 ojk 7 0 Insert j between l and k in T end The nearest insertion heuristic is a 2 7 optimal heuristic 4 Farthest insertion heuristic Initialization Given an undirected network G N7A7 with costs ch associated with each i7j 6 A7 where C satis es the A inequality Find the arc i7j with maximum cost in A Let T i7j7 i Steps while lTl lt n 1 1 Let 0T be miniET C for all nodes j T The node j to be inserted into the tour is one with maximum CAT 2 Find the insertion location for node j into the existing tour To do so7 nd the arc 716 in the current tour with the minimum insertion cost 01 ojk 7 0 Insert j between l and k in T end In English7 Step 1 nds the node j not on the tour for which the minimum distance to a vertex on the tour is maximum7 and adds that node to the current tour 5 Cheapest insertion heuristic Initialization Given an undirected network G N7A7 with costs ch associated with each i7j 6 A7 where C satis es the A inequality Alternative 1 Find the arc i7j with maximum cost in A Let T i7j7i Alternative 2 Use some procedure to develop an initial subtour7 T Frequently7 convex hulls or close approximations are used Steps while lTl lt n 1 1 Let C T be clj cinema 7 0mm for all nodes j T 2 Let j and 6 be the indices of the minimum cost 0 Insert node j after node 6 in T end In this heuristic7 we simply calculate an insertion cost matricc at each step representing the cost of inserting node j T after node Z 6 T We choose the minimum cost insertion at each iteration II Improvement Heuristics Given that a tour T has already been created via some method7 it may be possible to improve the tour with an improvement heuristic One often employed improvement heuristic is called A opt A A opt heuristic is based on the concept of x optimality7 which is a local neighborhood condition Essentially7 a tour is said to A optimal if there is no way to replace A arcs in T with A arcs not in T to create a new feasible tour with lower cost De nition 3 A optimality Given a CUNDI G N7 A and a tour Ti let be the set of arcs de ned by the nodes in 1117112 11215 7 viklwn MHz1 Then tour T1 is A optimal if and only if there does not eccist two sets of arcs X E ATZ Y E A such that Z le lYl A 239 ZijeX Cij Elma Cij gt 0 3 The set Y X allows a new feasible TSP tour sequence Ti These ideas motivate the following generic heuristic Note that technically7 the A inequality is not necessary for the validity of this heuristic A opt heuristic Initialization Given some initial traveling salesman tour T0 k 0 Iterations 1 Identify a feasible A exchange with positive savings That is7 nd two sets X E ATk and Y E AATk such that le lYl A 0ij CH 7 Zawey cij gt 07 and that the set of arcs Tk Y X admits a feasible tour sequence If no sets can be identi ed7 STOP Tk is A optimal 2 Let Tki l be the new tour sequence generated from X and Y 3 Repeat from 1 Figure 2 The dark black lines represent the TSP tour Note that in this case7 67 but 4 of these choices leave one node no longer adjacent to any arc in the tour The removal of arcs 17 2 and 13 is such an example Analysis How many options for removing A arcs in Tk and replacing them with A new arcs exist In a network with n nodes7 each tour contains 71 arcs Thus7 there are ways of removing A arcs from a tour lf removing a set of A arcs results in exactly z nodes that are no longer adjacent to any arc in the tour7 the number of new ways to reconnect the nodes is A i 12Hw i 1 The two most commonly employed heuristics are 2 opt and 3 opt Let7s analyze how many new tours are created in each iteration in these cases 2 0pt In this case7 there are ways of removing 2 arcs Additionally7 in n of these cases7 one node is left no longer adjacent to any arc In these 71 cases7 there is no new way to connect the nodes 2 71122 1 1 7 1 1120 7 1 0 1n the remaining cases7 there is exactly one new way to reconnect the nodes 2 7 1122 1 71 1121 71 1 Therefore7 the total number of possible 2 opt exchanges is n 2 71 3 0pt In this case7 there are ways of removing 3 arcs 1n n of these cases7 two nodes are left no longer adjacent to any arc In these 71 cases7 there is exactly one new way to connect the nodes 3 71123 1 2 71 2120171 1 ln nn 74 cases7 one node is left no longer adjacent to an arc In these cases7 there are 3 71123 1 171 2121171 3 new ways to reconnect 1n the remaining cases7 there are 371123 1171 2122171 7 new ways to reconnect Therefore7 the total number of new tours to be examined at each iteration is n 7 7n7nn74 3nn74n Using these equations for a network 50 nodes7 the 2 opt heuristic would examine at most 1175 exchanges each iteration while 3 opt would examine no more than 127700 exchanges each iteration Implementation Issues ISyE 3103 Supply Chain Modeling Transportation and Logistics Spring 2006 Regression Models with Indicator Variables 1 Categorical Variables One of the advantages regression based forecasting models have over time series extrapolation mod els ie moving average exponential smoothing etc is that regression models can include other explanatory variables that are not necessarily related to time It seems logical that demand and other dependent variables could be a function of factors such as advertising expenditures and price in addition to time series elements Some of these factors could be categorical in nature as opposed to quantitative Examples of categorical variables include gender color region of the country and the political party currently in power As we will see categorical variables are also useful in modeling seasonal effects in regression models Regression models require that all of the variables included both independent and dependent be quantitative in nature Consequently we must devise a method of translating these categories into numbers We will de ne the levels of a categorical variable as the number of values that variable can assume It is not suf cient for us to haphazardly assign the levels to an integer or any other value in order to convert them Creating integer values necessarily implies some kind of ordering on the levels which does not make any sense in the context of a categorical variable Consider the following example Suppose that we wanted to model the starting salary for Georgia Tech ISyE graduates and we thought that an important factor might be the color of the graduates hair For simplicity let us assume that there are three hair colors light dark and red If we were to create an integer variable called COLOR where COLOR0 denotes light hair COLOR1 denotes red hair and COLOR2 denotes dark hair we would be imposing an arti cial ordering on the levels of the COLOR variable This ordering renders the regression coef cient meaningless since we would be implying that dark hair is two 77colors77 higher or lower than light hair 2 Using Indicator Variables In order to incorporate categorical variables into a regression model we must create indicator vari ables1 that either take on a value of 0 or 1 To represent a categorical variable that has 0 levels we require c 7 1 indicator variables If we created 0 indicator variables along with a constant term 30 in the regression model we would get an error from our statistical software program because the data matrix or more accurately XTX is singular You must choose3 one of the levels to be the base case and then each of the other levels has a corresponding indicator variable that is equal to 1 if the observation exhibits that level and 0 otherwise Continuing our hair color example from above suppose we denote light hair as the base case We must then create indicator variables4 RED and DARK to represent individuals with those particular 1lndicator variables are often called dummy variables77 or binary variables77 2Recall that a singular matrix has no inverse and we must be able to invert that matrix in order to use leastsquares regression 3The speci c choice of the base level does not matter Any of the levels is as good a base as any of the others 4Note that these variables must be created No data set that you receive will include all of these 0 s and 1 s Once you choose an indicator variable mechanism to represent a categorical variable you must go through the data and determine the appropriate values of each indicator variable for each data observation ISyE 3103 Spring 2006 Regression Models with Indicator Variables 2 hair colors If we list a given observation s indicator variable values as an ordered pair RED DARK a red haired person would be denoted by 10 a dark haired person by 0 1 and a light haired person by 00 If we wanted to include a second categorical variable in a regression model we would still require the number of indicator variables equal to the number of levels for the new categorical variable minus one The de nition of the base case must be extended to include the chosen base level for the second categorical variable To illustrate this concept in the context of our previous example suppose we thought that the gender of the graduate was an important factor in his or her starting salary Obviously this variable has two levels male and female Let us select the female level as our base case Consequently we will create one indicator variable MALE that is equal to 1 if the person is male and zero otherwise The base case of the model now corresponds to a light haired female graduate There are six possible types of graduates since we have two genders and three hair colors We now con rm that these three indicator variables RED DARK MALE are suf cient to characterize the six types of graduates 3 Interpreting Regression Coef cients for Indicator Variables Regression coef cients true 3 parameters typically represent the change in the dependent vari able as the corresponding independent variable increases by one unit Estimated coef cients statistics represent the change in the expected value of the dependent variable as the independent variable increases by one These interpretations must be modi ed for indicator variables since they are binary and we have a base case Regression coef cients for indicator variables signify the change in the dependent variable as our corresponding categorical variable changes from the base level to the level represented by that coe icient s indicator variable Suppose that we have the following estimated regression model SALARY Bo lcPA BZRED BgDARK BiMALE where GPA is a quantitative variable5 representing the graduates nal Georgia Tech grade point average Recall that we de ned our base graduate as a light haired female Consequently the estimated salary for any light haired female graduate is SALARY 30 BleA We can interpret 32 as the change in expected salary for a red haired female compared with a light haired female when the two graduates have the same nal grade point average Similarly 33 represents the change in expected salary for a dark haired female over that of a light haired 5We are allowed to use quantitative independent Variables along with indicator Variables in regression models This will enable us to build models of trend and seasonality ISyE 3103 Spring 2006 Regression Models with Indicator Variables Table 1 Data for example problem ISyE 3103 Spring 2006 Regression Models with Indicator Variables 4 Table 2 First two weeks of data with indicator variable values female with the same GPA 34 corresponds to the change in expected salary for a light haired male compared with a light haired female for graduates with the same GPA We can also determine the change in expected salary when both categorical variables shift from the base levels For example the change in expected salary for a red haired male compared with a light haired female with the same GPA equals 32 34 The interpretation of 31 is free from these complications since GPA is a quantitative variable It simply represents the change in expected salary for a given type of graduate as the graduates nal grade point average increases by one point 4 Time Series Example The Belgian Trucking Company6 needs to determine the number of refrigerated7 trucks to satisfy the transportation demand between Antwerp and Brussels on a daily basis The demand for refrig erated trucks is dependent on the daily temperature because more refrigerated vans are needed when the outside temperature increases and it also appears that there are trend and daily sea sonality elements present in the data Six weeks7 worth of data are provided in Table 1 Since the data exhibits daily seasonality within each week we need to create appropriate indicator variables to model this seasonality in the regression model There are ve workdays in each week so we need four indicator variables Let us choose Friday as our base day and create variables MONTUEWED and THU Table 2 contains the rst two weeks of data observations including the indicator variable values The subsequent weeks of data are modi ed in the same fashion to obtain the data set on which we will t the regression model Regressing demand on all of the independent variables 2 quantitative and 4 indicator we obtain the following estimated regression function DEMAAND 725510474TME70849TEMP5476MON711538TUE717811WED722143THU 6This example is adapted from Ghiani Laporte and Musmanno s Introduction to Logistics Systems Planning and Control 2004 pg72 published by John Wiley amp Sons 7These are also known as reefer trucks lSyE 3103 and lSyE 6203 Transportation and Supply Chain Systems Automatic Identi cation and Data Collection Technologies 1 Introduction Item identification and data collection are extremely important in supply chain systems Many different models are used to optimize and control various portions of a supply chain All these models depend on having quality data inputs without the data the models are useless Anyone who has ever done any work in industry can tell a story of a problem they have had with data when working on a problem Manual collection of data can be slow and hence costly and more importantly is highly prone to errors For example if part numbers are manually input by a keyboard the error rate is approximately 1 in 300 However if the same data is collected with bar codes the error rate is approximately 1 in 3 million a huge difference Thus we turn our attention to automatic identification and data collection AIDC technologies that can be used to collect the required data accurately and at a reasonable cost After data has been collected with these technologies it must be stored and processed by information systems typically a database this subject is covered elsewhere We mentioned that models require quality data to be useful What exactly is meant by quality data Some characteristics of quality data are the following 0 Accuracy The data must be correct 0 Timely The data must be available when it is needed for making decisions 0 Effective The data must be relevant for the decisions being made For exam ple data about the exact specifications of a product is probably not necessary for making decisions about which mode the product should be shipped by c Reliable The data must satisfy the above qualities consistently Data that is occasionally of poor quality won t be trusted and hence is less likely to be used even if it is usually good 2 Types of AIDC Technologies Below we list some of the many different types of AIDC technologies 0 Bar coding The is the most prevalent form of AIDC and it will be discussed more extensively later in this document Radio Frequency Identi cation With this technology identi cation and data cap ture is done via radio waves Optical Character Recognition This technology can read the same printed words and symbols that we read and convert them into electronic format This technology is heavily used by the United States Postal Service for reading addresses IlIagnetic Ink Character Recognition This technology is heavily used in the banking industry for example by encoding the check and bank routing number on checks in magnetic ink The data can then be read in a similar to optical character recognition Magnetic stripes Data is stored in a magnetic stripe such as on the back of a credit card Smart cards Data is stored in a small chip embedded in a card such American Express cards One advantage over magnetic stripes is that more data can be stored in the chip Biometrics This includes technologies that can identify a person by looking at their ngerprints or eye This document will focus on bar coding and radio frequency identi cation RFID since they are the most widely used AIDC technologies in supply chain systems 3 Uses of AIDC AIDC technologies are used in a wide range of industries In this section we describe some examples Retail Bar codes are on essentially every product we buy By one estimate the retail industry does 35 million bar code scans per minute Manufacturing Bar codes and increasingly RFID are used extensively in the manufacturing industry to track inventory and work in progress and to assist in quality assurance Distribution AIDC technologies are used in distribution systems to automatically record incoming and outgoing shipments Healthcare This is an industry that has been slower to adopt AIDC technologies in all areas but there is great potential For example consider a nurse administering medicine Before administering he scans the patient tag his own id and the medicine If he is attempting to administer the wrong medicine or medicing that should not be taken with other medications the patient is taking a warning goes off Bar codes have even been used to keep track of bees in experiments Little bar codes have been placed on the bottoms of the bees for identi cation purposes 4 Bar Coding We now turn to talking speci cally about bar coding the most prevalent type of AIDC technology A bar code is de ned a spacial representation of encoded characters 41 Bar Code System Steps There are a number of steps that typically must be followed when implementing a bar code system H Coding requirement The rst step is to determine what data needs to be stored on the bar code For example are we storing part numbers lot numbers etc 3 Machine readable language A standard format for the bar code that can be read by a machine must be decided upon This is referred to in the bar coding terminology symbology S Bar code printing The bar codes must be printed onto labels or directly onto the items they will be identifying 3 Bar code veri cation Quality control measures must be taken to ensure the bar codes can be read reliably C Bar code scanning This is the step where data is actually captured 333 Transmit data After being captured the data must be transmitted to an informa tion system gt1 Use the data This step is almost too obvious to mention but it s too important not to mention If there is no use for the data the bar code system is just a waste of resources 513 cm Slop 09 I I muel Gum Zone Dimenslon 10 mm a m 1 we myan 4 2 qvmbulugy and Dam gumm a 1m mmmm 1m r mum w r mm mucwm NullVow a W m mama w mm we ummmm m mm Wm mum mucwm a w mo Ath mde m Mum wwwmch 0 mm mm um m m m We mmm m manqqu mm mum on m 5 tut100mb mamm um w W m new m mime om chockwwumu u o ummm mukmwuwonmrw Amuwhomw mu m M a m Figure 2 The top bar code is a twodimensional stacked bar code and the next one down is a matrix bar code Data structures are used for both bar coding and RF lDA The Global Trade ltem Number GTlN is an umbrella group under which all different types of data structures now l39alL The GTlN allows for 14 digits but the specilic data structures that fall under GTE may not use all 14 digits The most common example of a speci c data structure is the UPC which is on most of the products you purchase The data structure that is becoming standard for use in RF lD chips is known as EPCT The ET C structure consists of a header plus three sets of data The header includes information such as the EPC version number so that changes to the EPC structure itself can be managed The lirst set of data is a code for the EPC manager such as the manager of the product The second set of data indicates the object clas which specilies the exact type of product eg Diet Coke 330 ml can The linal data set stores a serial number which is specilic to the specilic iteml 43 Bar Code Readers Bar code readers can be handheld or handsl39reel Hands l39ree scanners are more ef cient when it is easier to bring the bar code to the scanner than it is to bring a handheld reader to the bar code Hands l39ree laser quotanners are often used in checkout lines in grocery stores We discuss three of the most common types ol39handheld bar code readers belowi Figure 4 A Charged Couple Device Wands Wands are penlike readers with a laser at the tip see gure 3 A bar code is read by a wand by moving the wand over the bar code The advantages of wands are that they are lightweight inexpensive and rugged In addition they require less power than other types of readers and hence could be good for mobile use in which the reader must be powered by a battery One disadvantage of a wand is that there is relatively more training required for people to use them In addition because wands have to be moved across the bar code they are less efficient and because they come in contact with the code during the scan they can eventually damage the bar codes if they are read repeatedly Charged Couple Devices CCD CCDs work by flooding the entire bar code with light An example of a GOD is shown in gure 4 CCDs are moderately costly and are to use In addition they are rugged because they do not have any moving parts to break Other advantages of CCDs is that they are lightweight and typically produce decoded output The primary disadvantage of CCDs is their limited depth of eld The eld of depth of a reader is the distance from the bar code which the reader must be in order to successfully read the code Laser The most commonly used handheld bar code reader is the laser an example is shown in gure 5 Because they are so common lasers have the advantage of being widely accepted Figure 5 A Laser Bar Code Scanner Figure 6 These bar codes can dissolve in water by users The other primary advantage of lasers is that they have a wider depth of eld than the other handheld readers One disadvantage of lasers is that they have moving parts mirrors to direct laser beams and hence can breakdown easier In addition they have higher power requirements than the other types of readers and are more expensive 44 Bar Code Labels It is often more convenient to print bar codes on a label which is subsequently placed on a product than to put the bar code directly on a product There are a huge variety of different types of bar code labels that can be useful for widely different applications Bar code labels characteristics include cost texture ease of application resistance to the elements tendency to peel life eXpectancy and resistance to scratching and tearing There are even bar code labels that are made that are designed to dissolve in water see gure 6 Bar code labels can be made from a variety of materials including paper vinyl and polystyrene When choosing the type of bar code label to use it is important to nd the bar code label that meets the speci c needs of the application they will be used for 45 Bar Code Printing The rst major decision to make with bar code printing is whether to have the printing done onsite or offsite With onsite printing also known as imprint or ondemand printing there is a large initial investment that must be made to purchase the printers w ammo 1mm wa ma mam w aumuo m mu m m M 11 Vow I M1 o4 mwmnw n w oVrA ltd1Lol lt m Vmowm Jomm m mm a m mm 1 Km L0 mm m m mm m md woman m m MAM am cm W w a mm mewwww L0 Mable L0 um um m ury w u mwm nmww 1 um mm W nx a u ML Mauro1mmMuomucu r Yo rwdo a m m uumuwul m m WWW we am mum w Ld M WHRmrmuwmrmu p L mwmw mqu Mawmmmoomam wmuqumxo of mm mm 11 m 1mm gown w m V W cm am mm m MW Mme Wm M rm 1 mumm ww r mmmwowmoka w wVwoowm m mm 11 m r mu KW1101 mm l ltumoltql L mm we of u q mm MaIL mm mm 1qu o m m wwwk mm mm m x m armm mwmuw m w v 1 mm Mquot u ww Wm mm mmmmoi m mm mm mmuocwImuwcoi m a Mm LNN LNNM mu ltmmm wmamomWmwwmmw M w Curls Vuriiimtiuu m we mmuow 1 1 00 w mm1W w LNIm WW mo1a u m 14 m V x m mumwmuw am1mm r mm mm wva m mam um um WW 1 mm m mmuo mm m nmm 01me m lm mm 1 L0 uwwwwouon w mm Mkltme ham u mm mm mow L m m Wm M tomc m wquo mm mm m be effectively lost Companies take the quality of bar codes on their products seriously For example VValmart has been known to fine its suppliers 50000 for having poor bar codes on the cases they supply Bar code verification involves more than just scanning the bar code after printing to see if it scans Separate machines are used for verification which measure various characteristics of the printed bar codes to judge whether the bar code can be read reliably by different types of readers and whether it is likely to continue to be readable even after slight degradation At a minimum verification should be done at the beginning sometime at the middle and at the end of the printing process In addition any time something is done to the bar code such being laminated or varnished verification should be done again Some major users of bar codes such the Department of Defense have specific guidelines on how bar code verification should be done 47 Costs of Bar Coding The average bar coding implementation can cost between 50 and 250 thousand dollars However companies have reported that the average payback on this investment is typi cally quite short averaging about 5 months When considering the costs of a bar coding implementation it is important to compare it to the costs of not implementing bar cod ing and the data errors that can result For example there are costs associated if you ship the wrong item to a customer Imagine the potential costs if a company installs the wrong part on an aircraft Some costs of potential data errors cannot even be measured for example if the wrong medicine is administered to a patient leading to a fatal reaction Considering the potential costs of data errors bar coding will generally be considered a bargain 48 Advantages and Disadvantages Two advantages of bar coding are that it is relatively inexpensive and widely used and accepted in industry In addition bar coding is based on an open system Thus the standards for symbologies and data structures are not owned by a single company and are open knowledge so that no royalties have to paid for the use of a specific bar coding method In addition the prevalence of established standards for bar codes facilitates the use of bar codes that can be used throughout the supply chain by different companies A primary disadvantage of bar codes is that the symbol must be visible to be read For example if there is a bar code on each case on a pallet and each case must be identified the pallet may hay have to be unstacked to read the bar codes of all the cases Another disadvantage is that the data in a bar code is static Thus if the data changes a new bar code must be printed and the old bar code must be rendered unreadable Additionally bar codes are susceptible to damage from harsh conditions and could be rendered unreadable or separated from the product 5 Radio Frequency Identi cation Radio Frequency Identi cation RFID is an AIDC technology that is being used increas ingly in supply chains because it can effectively overcome some of the disadvantages of bar coding RFID is a system in which data is stored on a machinereadable tag and is transmitted to the reader by radio waves Therefore no lineofsight is required to read the data stored in RFID tags is required to read bar codes In addition RFID tags can be built to be more resistant to the elements and can be enclosed inside protective packaging and so can be used in harsh conditions in which bar codes would be less effective RFID is gaining in prominence due to some recent requirements set by major cus tomers For example VValMart is requiring its top 100 suppliers to put RFID tags on all their pallets by the end of the year and is requiring the same of all its suppliers by 2006 In addition VValMart has strict requirements on the capabilities these RFID tags must have For example they require that the tags should be readable when on con veyors moving fast 540 feet per minute These types of requirements will push the development of RFID technologies Similarly the United States Department of Defense is requiring its suppliers to put RFID tags on its products and is even requiring that the tags be put on individual cases or items in some cases 51 RFID System Components An RFID system consists of the transponders or tags that are placed on the items and the antenna and transceiver devices used to read the data RFID tags can be classified active or passive and read write or readonly The difference between active and passive tags is that active tags have their own power source whereas passive tags get all their power from the radio waves transmitted to them Active tags use battery power to transmit and receive data and can store fairly substantial amounts of data much 1 MB Because they have their own power source they have a longer read range than passive tags The disadvantage of active tags is that they are larger and more expensive and have a limited lifespan based on the battery life although lifetimes can be long 10 years Passive tags have shorter read ranges and require a more powerful reader The advan tage of passive tags however is that they are lighter less expensive and have a virtually unlimited lifetime If made cheap enough there is speculation that passive tags could eventually replace bar codes on products An example of a passive tag is the antitheft hard plastic tags used in retail stores These have a small RFID chip in them that can be read by transceivers at store exits to detect if an item is being taken out of the store without being paid for With read write tags it is possible to write new data onto a tag well read the data on the tag Readonly tags can only have data written to them once after which the data can only be read Typically read write tags are active whereas readonly tags are passive Figauo S An RFID Antenna nether hey errrpenent er an REID system is the antenna whieh is what aetuaiiy transrm gtradi w 390 to the tag or fromthe tag in the ease ofan ye ta antennae e me in many di mom shapes a t s an tgtxamphgt is in tmro 5 and ean use many di mom frequenei andLVJi a yhawhmjtodmngo ithatinterfereneewith it i he ayei ed haye dif mh transrrritting threugh metaIIie ehjeets The iinaI eerrrpenent er an temi the tra gtiyer ereentreIIerwhieh w at tahes signaIs fmm the antenna and transmits it te a eerrrputer 0139th the transeeiyer and the antenna are huruiIed tegether singIe item 52 Applications of RFID A appIieatiens in many industries and the nurrrher er appIieatiens is gmwing Iewing are seme exarrrpIes i re an n 1 39 RI ID tags on Iai and inelallod anwnnav by tmrk and w mark of vhmo mi ram aw vhi 39 Mo huts te heep eh raeiIitates impmvod iieet uti tien quot 39 The feedanrin v v v REID fer aii metiie t39 shy 2007 te eemhat eeunterreit drug 39 new We haye ahead rrrentiened that REID tags are used fer eIeetrenie suryei Ianee er pmde te preyent thert REID tags ean he piaeeti in ears te reeerd when a eth se that the teii ean he tieiueteti fmm the tiriyers gtr haying to stop to pay the to 0 Aniamica Tall Calleriian ear ras es threugh a th he aeeeunt rather than the dIi Cani allsdArrenn 0f Permittel REID tags e Ihe pl ed in persenneI name tags te re rietaee te seeure and h Idol h at 39 wad to Flexible Manufacturing 81152611 REID tags en pmdu s ean he ea 39 identify speeiiie pmdu yariants fer autemat preees eentreI 53 Item level RFID As RFID tags become cheaper it may become costeffective to place RFID tags on every item for items that are not too cheap The implications for a retailer in this case are huge It would then be possible to know exactly how many of each product are on the shelf at any time allowing for improved control In addition this technology could eliminate the need for scanning every item when a customer checks out Instead the customer could just push their cart through the RFID reader and the total charge could be instantly calculated There are a couple challenges that need to be overcome before RFID will become prevalent at the item level First RFID tags still are not cheap enough to be placed on the majority of products Second there is a disconnect between who bene ts from itemlevel RFID tags retailers and who has to pay to put them on manufacturers Therefore before RFID will be implemented at the item level in large scale a mechanism has to be created to allow the manufacturers to share the bene ts Finally there are people who are concerned with privacy issues with putting RFID tags on all items we buy People may be unhappy with the prospect that companies can keep track of everything they own and buy These same types of issues came up with the introduction of bar codes and the concerns generally were proven to be unfounded or at least consumers were willing to accept them to achieve the increased convenience offered by bar codes The same may occur with RFID technology but it will require careful attention to consumer desires such the option to disable an RFID chip after a product is purchased and education of consumers such informing them that it would not be possible to read an RFID chip on a product in their house from the street 54 Advantages and Disadvantages One Of the principle advantages of RFID over bar coding is that there is no line of sight required to read an RFID tag In addition active RFID tags have the capability to be read write so that the data stored can be changed over time This capability allows tags to be used a sort of moving database RFID tags also have the advantage of being more suitable for harsh conditions since they can be placed inside protective packaging and still be read The principle disadvantage of RFID tags is their cost Even the cheaper passive tags are still signi cantly more expensive than bar codes and until this cost can be brought down substantially there will still be a large role for bar codes to play in supply chain automatic identi cation and data collection Another disadvantage of RFID tags is the challenge of gaining consumer acceptance and overcoming the privacy concerns consumers may have

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.