The problem of decreasing truck transportation costs for Mexican firms is of great interest and a challenge due to the currently deficient supply structure. This work deals with the case of leading Mexican tobacco manufacturer that requires a reduction of its outbound transportation cost under a decliningmarket scenario. The approach applied to achieve the objective includes the elimination of important transportation wastes through mathematical modeling techniques. Truck fill loss and distance travelled in excess are identified as the main wastes existent in the transportation of finished product from the manufacturing plant, located in Monterrey, to three regional warehousing hubs, and then, from these to 70 distribution centers located throughout the country. The application of location and/or routing models imbedded into a decision analysis scheme and supported by a GIS system is carried out to obtain the solution to several scenarios developed by the management of the company. Results and advances of their implementation are provided.