Dr Pepper bottles soft drinks that it distributes to retail outlets from ten warehouses in USA. A single bottling plant is located in Seattle. The product is shipped from the plant to the warehouses via trucks each of which possibly travels more than one warehouse in a trip. Dr Pepper outsources the transportation of the products to a third-party trucking company, DHL. DHL charges a fix fee of $500 plus a variable free of $0.80 per miles per a trip of a truck. For instance; if the length of a trucks trip is 600 miles, then DHL charges 500 + 600*0.80 = $980 to Dr Pepper. The capacity of each truck is 36 pallets but transportation fee does not change if the all capacity is used or not. In a particular day the demands of the warehouses are as listed in the following table. Use Savings method to find the number of routes (trucks) needed, warehouses on the routes, and the sequence the truck should serve the warehouses based on the real distance matrix given below (assume the warehouses are located at about the center of city zones). Calculate total cost of the route plan.

Warehouse location Demand (pallets)
New York	12
Chicago	10
Boston	9
Houston	6
Washington	16
Denver	14
Detroit	8
Austin	6
Nashville	7
Atlanta	9
Total	97

	Seattle (Plant)	New York	Chicago	Boston	Houston	Washington	Denver	Detroit	Austin	Nashville	Atlanta
Seattle (Plant)	0	233	424	151	422	324	411	540	336	500	647
New York	233	0	544	384	655	453	579	318	258	620	414
Chicago	424	544	0	537	705	718	444	618	322	311	906
Boston	151	384	537	0	271	243	325	691	487	544	745
Houston	422	655	705	271	0	320	326	962	747	549	1016
Washington	324	453	718	243	320	0	564	771	660	783	734
Denver	411	579	444	325	326	56	0	848	550	225	993
Detroit	540	318	618	691	962	771	848	0	304	853	453
Austin	336	258	322	487	747	660	550	304	0	555	592
Nashville	500	620	311	544	549	783	225	853	555	0	1034
Atlanta	647	414	906	745	1016	734	993	453	592	1034	0