Traveling salesperson problem with unique pricing and stochastic thresholds. (November 2022)

• Record Type: Journal Article
• Authors: Afsar, Hasan Murat
• Is Part Of: Computers & industrial engineering. Volume 173(2022)
• Publication Date: 2022-11
• Subjects: Traveling Salesperson Problem -- Unique Pricing -- Random thresholds -- Chance-constrained model -- Logic Based Benders Decomposition; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108696
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: In this variant of traveling salesperson person problem, only the customers who accept to pay a unique service fee are serviced. Each customer has a random price acceptance threshold and accepts to pay any fee lower than this threshold. To address this issue, a chance-constrained stochastic model is developed and two exact methods, one based on a Branch & Cut scheme, and the other on Logic Based Benders Decomposition, are built. Numerical tests show that, on small instances both methods are efficient but on larger instances with 100 customers, Logic Based Benders Decomposition dominates clearly the Branch & Cut method. Highlights: A new version of Traveling Salesperson Problem with stochastic price acceptance, is studied. The problem is modeled with the help of chance-constraints, linearized by discretization. Two exact methods, (Branch & Cut and Logic Based Benders decomposition) are proposed. Especially the second method is very efficient on the instances with 100 customers.