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 is 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.