【正文】 would like to find a vehicle route that minimizes the total of routing penalty costs. A possible solution approach is to enumerate all possible vehicle routes and find the optimal one. This approach is prohibitive even when only the travel cost is considered. The putation time is further increased by the simulation time needed to search for a weight vector that prioritizes stops or even to estimate the expected cost of a given pickup policy. For this reason, a heuristic approach is proposed that can produce a good solution in a reasonable time. The TSP has received a great deal of attention from researchers over the years and many heuristics have been proposed in the literature. The algorithm implemented here is a posite algorithm that first finds a feasible vehicle tour from the Arbitrary Insertion Procedure of Golden and Stewart using only the travel cost. In the second stage, a ―tour improvement‖ procedure is successively used to find better routes that account for both the travel cost as well as the penalty cost of the returning materials left at stop locations. One of the better known procedures of this type is the edge exchange algorithms .The edge exchange procedures are referred to as ropt, where r edges in a feasible vehicle tour are exchanged for redges not in that tour as long as the result remains a feasible vehicle tour and the travel cost is reduced. As r increases, the quality of the heuristic solution improves but at the expense of increasing the putational time. The 2opt and 3opt algorithms are monly used in practice. Oropt , which is a modification of the 3opt procedure, is used in this study to 7 improve the initial vehicle route. Oropt is known to work reasonably well while it requires only a small percentage of the exchanges that would be considered by a regular 3opt algorithm. The Oropt algorithm used here is described as follows. Stop with equal service priorities For this case, as discussed in front. the optimal pickup policy for a given vehicle route is to pickup as much as possible of returning materials at each vehicle stop along the route. However, for each of the four possible routes for each exchange in the Oropt algorithm, simulation is needed to estimate the expected penalty cost of postponing pickups. In this section, the effectiveness of some heuristic procedures devised to reduce the putational effort without significantly degrading the solution quality is explored. Stop with unequal service priorities For the general case of stops with unequal priorities, the stops have a different penalty cost for postponing a returning item for one period. As discussed in front ,for a given route, the weighted leveling policy provides an efficient heuristic rule for making the returns decision. Computational results in Alshamrani et al. showed that this policy, on an average, results in a penalty cost that is within 8% of the lower bound. Thus, to evaluate a new route in the Oropt algorithm, the weighted leveling heuristic is used. However, this requires an expensive simulationbased search to determine the weights for each stop. This makes the rudimentary algorithm putationally prohibitive as each exchange requires evaluating four routes. As was proposed in Section for the case where all stops have the same penalty cost ai , evaluating only one direction rather than both directions for each exchange was also considered for this general case. An extensive putational study showed that using only one direction reduces the putational effort by about 50% without degrading the solution quality. However, the putational effort required is still impractical—a problem with 10 stops on average may need about 10 h of putational time on a Ghz, Pentium 4 PC to determine the best route and the stop weights needed for the returns strategy. 5. Conclusion Reverse logistics involves many problems in the supply chain whose importance has been heightened by increasing concerns about the environment, customer service, and cost reduction. One of the reverse logistics problems is managing the return of materials generated from deliveries made on a delivery route. Determining how much of the returning materials should be picked up at each stop along a delivery route has been the focus of this research. 8 The pickup strategy was formulated for a planning horizon. Previous research by these authors developed pickup strategies when the route was known and fixed. It produced some interesting, practical rules. However in this research, the putationally more difficult problem of developing the delivery route while simultaneously determining the best pickup strategy over a planning horizon was tackled. The stop volumes along a route were known only probabilistically. This integrated and dynamic planning problem is putationally intense, so for practical reasons a heuristic procedure was developed involving a weighted leveling policy for returns decisions. The proposed algorithm is a modified Oropt procedure. However, it is observed that a simple minded application of the Oropt procedure will be putationally prohibitive, even for problems with less than 10 stops. In this paper, several heuristic rules and strategies are proposed that makes the algorithm putationally viable without degrading solution quality. For this case, as discussed the optimal pickup policy for a given vehicle route is to pickup as much as possible of returning materials at each vehicle stop along the route. However, for each of the four possible routes for each exchange in the Oropt algorithm, simulation is needed to estimate the expected penalty cost of postponing pickups. In this section, the effectiveness of some heuristic procedures devised to reduce the putational effort without significantly degrading the solution quality is explored.