Selective multi-depot vehicle routing problem with pricing

Firms in the durable goods industry occasionally launch trade-in or buyback campaigns to induce replacement purchases by customers. As a result of this, used products (cores) quickly accumulate at the dealers during the campaign periods. We study the reverse logistics problem of such a firm that aims to collect cores from its dealers. Having already established a number of collection centers where inspection of the cores can be performed, the firm's objective is to optimize the routes of a homogeneous fleet of capacitated vehicles each of which will depart from a collection center, visit a number of dealers to pick up cores, and return to the same center. We assume that dealers do not give their cores back free of charge, but they have a reservation price. Therefore, the cores accumulating at a dealer can only be taken back if the acquisition price announced by the firm exceeds the dealer's reservation price. However, the firm is not obliged to visit all dealers; vehicles are dispatched to a dealer only if it is profitable to do so. The problem we focus on becomes an extension of the classical multi-depot vehicle routing problem (MDVRP) in which each visit to a dealer is associated with a gross profit and an acquisition price to be paid to take the cores back. We formulate two mixed-integer linear programming (MILP) models for this problem which we refer to as the selective MDVRP with pricing. Since the problem NP-hard, we propose a Tabu Search based heuristic method to solve medium and large-sized instances. The performance of the heuristic is quite promising in comparison with solving the MILP models by a state-of-the-art commercial solver. (C) 2010 Elsevier Ltd. All rights reserved.