The traveling purchaser problem with fast service option

Abstract

The traveling purchaser problem (TPP) is a generalization of the well-known traveling salesman problem, in which a list of products with different quantities has to be purchased from a subset of markets selling various products with different prices. The aim of the problem is to minimize total traveling and purchasing costs while satisfying the products demand in a unique tour. This study introduces a new variant of the TPP, in which the tour has to be completed within a duration time limit by taking into account the traveling and purchasing times of the purchaser. For the purchasing operations, two types of service options are allowed for the purchaser: standard and fast service. The fast service option of a market gives opportunities to the purchaser to complete the purchasing process in a shorter time with an additional cost. This problem is called the traveling purchaser problem with fast service option (TPP-FSO). In addition to presenting a new TPP variant to the literature, this paper proposes an adaptive large neighborhood search (ALNS) algorithm for the TPP-FSO. The proposed ALNS is enriched by a local search procedure, which consists of a set of route-change-based and procurement-changebased heuristics. To evaluate the performance of the ALNS on TPP-FSO, different-sized benchmark problems are generated by using a well-known TPP benchmark problem set. The results of the computations demonstrate the efficiency of the proposed algorithm by introducing better results in shorter computational times.