TASTE:: a two-phase heuristic to solve a routing problem with simultaneous delivery and pick-up

The reverse logistics problem of the simultaneous distribution of commodities and the collection of reusable empty packages with a single depot and a single vehicle with limited capacity is addressed in this paper. Commodities to be distributed are loaded at the depot and the empty packages are transported back to the depot. This is called the traveling salesman problem with simultaneous delivery and pick-up (TSDP), a variant of the classical traveling salesman problem (TSP), where nodes require both delivery and pick-up. The objective is to minimize the total distance traveled by servicing of the all customers. We develop a mathematical programming model and a two-phase heuristic to solve the TSDP. In the first phase, we use an agglomerative procedure to find an initial solution. In the second phase, we develop an enhanced version of simulated annealing (SA) to search for the best solution. We tested the heuristic on standard, derived, and randomly generated data-sets and obtained encouraging results.