The traveling purchaser problem with promotional packages

Abstract

This study introduces a new variant of the traveling purchaser problem (TPP), called the TPP with promotional packages (TPP-PP), in which promotional packages are alternatively available for sale in the markets for a limited time. In TPP-PP, the purchaser has an opportunity to purchase a set of products at a lower cost compared to individual sales of the items in the markets. The TPP-PP provides more realistic product and market selection plans for many real-life applications. The TPP-PP is formulated as a mixed integer linear programming model. To efficiently solve the problem, an adaptive large neighborhood search (ALNS)-based matheuristic algorithm (M-ALNS) is introduced by integrating an exact solver into the ALNS. In each iteration of the M-ALNS, the ALNS procedures are carried out regarding the TPP restrictions. If the corresponding solution is promising, then the exact solver refines the solution by optimizing the procurement plan, including the promotional package sales. In order to analyze the validity of the model formulation and performance of the proposed matheuristic approach, an extensive computational study is performed by using a well-known TPP benchmark problem set. Results show that the TPP-PP model yields cost reductions of up to 2.84%, compared to the classic TPP model. Additionally, the proposed M-ALNS outperforms the GUROBI solver in almost all cases, especially for large-sized instances, achieving over 20% cost reductions. Compared to optimal TPP solutions, the M-ALNS provides savings up to 8.92%. Numerical experiments show that the proposed M-ALNS is capable of finding efficient results for the TPP-PP.