Two- and three-dimensional path optimization for production machinery

Path optimization is desirable in many problem instances occurring in discr ete manufacturing and pick and place technology. The problem may refer to a pplications ranging from two-dimensional movements such as in milling proce sses to three-dimensional movements required in many robotic operations. Th e optimal path can be found using tour construction techniques. sub tour el imination techniques and tour to tour improvement techniques. The limits to which these solution methodologies call be applied are restricted to a cer tain number of nodes. The optimal path for two- and three-dimensional TSP i s determined using a stochastic search procedure based on a tour improvemen t technique. An optimal solution is presented for 500 node TSP in two dimen sions. A procedure for finding optimal path for an even larger number of no des is outlined. The optimal path in three dimensions is also presented usi ng nodes distributed along the periphery of three-dimensional primitives.