1987 03 Spring 1987 SOUTHERN METHODIST UNIV Analysis of Trucks Heuristics Compared to LP Model in GAMS Mike Feather Martin Ozinga Analysis of TRUCKS Heuristic Compared to LP Model in GAMS S S DEPARTMENT OF OPERATIONS RESEARCH AND ENGINEERING MANAGEMENT SCHOOL OF ENGINEERING AND APPLIED SCIENCE DALLAS TEXAS 75275 Analysis of TRUCKS Heuristic Compared to LP Model in GAMS by Mike Feather Martin Ozinga for OREM 4390 Senior Design May 8 1987 Acknowledgments We gratefully acknowledge the help of Lee Hill and Mark Hellwig of STSC and Dr Dick Barr for the completion I of this project 1 Summary We did a comparison of the TRUCKS software package I 1 I to solve a routing problem that minimized distance with a model on GAMS that achieves the same goal We allowed the TRUCKS package to operate only under the constraint of minimum distance and did the same with our GAMS model Out of the three small sample problems we ran we achieved I the exact same solution on both systems Thus the heuristic on TRUCKS achieved the optimal solution that the GAMS model did 2 Table of Contents Summary 2 3 4 6 7 I Background Technical Description of Model I I I Analysis Conclusion Appendix GAMS Model Matrix 2 1 Solution Background After meeting with Lee Hill who works for STSC s logistics software division we decided to attempt a comparison of TRUCKS a heuristic routing and scheduling software package to an optimizing program written in GAMS The purpose was to determine how accurate the TRUCKS routing solution was to the optimizer s The TRUCKS package can be applied to various trucking operations Presently this package is available commercially and is used by Frito Lay Safeway and McDonald s It sells for approximately 180 000 GAMS is a General Algebraic Modeling System developed by World Bank to solve problems that incorporated algebraic modeling This system can substantially improve the quality and productivity of a model by use of a high level compact language for large and complex models To compare the router of TRUCKS to GAMS we first had to eliminate virtually all the constraints TRUCKS takes into account so that we could have a clean comparison with as few variables as possible This meant eliminating time windows and truck capacities and making sure only one truck and one route were used to make the comparison as equal as possible to our GAMS program 3 Technical Description of Model The mathematical GAMS model involves the objective function n n DARC 1 3 1 1 j 1 X 1 3 where DARC equals the arc distance between each city rode and X equals the decision variable to use that arc The constraints for the objective function consist of n 1 1 where j 1 to n X 1 where i 1 to n X i 1 n j 1 1 3 This insures that every city is visited 2 X 1 3 X 3 1 This keeps the model from staying at a city and not leaving 3 u 1 u nx n 1 3 1 3 where i j 2 to n This keeps the model from subtouring M equals the set of usually positive numbers and makes the route visit every node and return To turn the TRUCKS package into a traveling salesman problem we loosened all the constraints so that they played 4 1 no role in routing To do this we made the truck capacity large enough to ensure delivery to all stops without missing any Also we made the delivery time windows open twenty four hours This gave TRUCKS a choice of stops based solely on distance and not time We also set the 1 maximum number of trucks equal to one to ensure that only one route would be made 5 Analysis After routing the TRUCKS with the eliminated conI I I straints we came up with a route covering 1 080 miles Our GAMS program resulted in the same solution as the TRUCKS route These results show that in the simplest routing problem TRUCKS can find an optimal solution We ran I I U two other samples with different data but the same basic numbers of cities to be visited These results were the same distance for GAMS and TRUCKS of 2 762 for sample 1 and 987 for sample 2 The same route for each sample was chosen by both GAMS and TRUCKS 6 Conclusion While our limited model shows that the TRUCKS router I I I I I I I I can find an optimal solution to run such a route would not be helpful in a real world situation The limitations of our model are obvious In a real world situation time windows would have to be observed as well as truck capacities Also TRUCKS has the ability to divide the route into more routes and use more than one truck as where ours does not have these capabilities To make our model more complete we needed to use the mixed integer program part of GAMS This would have enabled us to use more than one truck or more than one route thus enhancing our program greatly 4 44 4 44 44 4444 44 4 44 4 4444 4 44 44 44 4444 4444 44 44 Originating Link Id SMUVM1 Originating Userid E4AI0005 Distribution Code BlN712 4494 4 44 44 44 Spool file number 2455 File Size Recs 00000503 4444 9 4 94 File name and type SAM Origin Time Date 5 07 87 94 4 4444 44 44 4444 4444 9 4444 0 LISTING 9 94 18 40 32 C D T 94 4 a 1 SU41 GENERAL ALGEBRA COMPILATION I C MODELING SYSTEM 1 MODEL OF TRAVELING SALESMAN PROBLEM 2 3 SETS I NODESI A B C D E F G 4 5 ALIAS I J 6 7 SCALAR NCITY NUMBER OF CITIES 7 8 9 PARAMETER DARC I J ARC DISTANCES 10 C D 11 A B 329 C E 12 A 0 433 402 C F 13 A D A E C G 14 501 A F D E 459 15 402 D F 16 A G 17 B 0 D 0 105 E F 18 B D 105 172 B E E G 19 B F 140 F G 20 21 B G 102 22 23 24 DISTANCE TOTAL FOR PATH VARIABLES DTOTAL 25 X I J DECISION TO USE THIS PATH 26 TOUR BREAKING VARIABLE 27 U I POSITIVE VARIABLE X U 28 29 SUMATION FOR I 30 EQUATIONS ISUMX I JSUMX J SUMATION FOR J 31 SUB I J SUBTOUR 32 SELF I NO SELF TOURS 33 TOTAL TOTAL DISTANCE 34 35 SUM J X I J E 1 ISUMX I 36 SUM I X I J E 1 JSUMX J 37 38 39 SUB I J ORD I CT 1 AND ORD J CT 1 40 U I U J NCITY X I J L NCITY 1 41 42 SELF I X I I E 0 43 44 45 DTOTAL E SUM I J DARC I J X I J TOTAL 46 47 48 49 MODEL SAM ALL 50 51 52 SAM …