The traveling purchaser problem with fast service option


KÜÇÜKOĞLU İ.

COMPUTERS & OPERATIONS RESEARCH, vol.141, 2022 (Peer-Reviewed Journal) identifier identifier

  • Publication Type: Article / Article
  • Volume: 141
  • Publication Date: 2022
  • Doi Number: 10.1016/j.cor.2022.105700
  • Journal Name: COMPUTERS & OPERATIONS RESEARCH
  • Journal Indexes: Science Citation Index Expanded, Scopus, PASCAL, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Keywords: Combinatorial optimization, Traveling purchaser problem, Meta-heuristics, Adaptive large neighborhood search, LARGE NEIGHBORHOOD SEARCH, VEHICLE-ROUTING PROBLEM, CUT ALGORITHM, FORMULATION, HEURISTICS

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.