Premium
Traveling salesman problems with profits and stochastic customers
Author(s) -
Zhang Mengying,
Qin Jin,
Yu Yugang,
Liang Liang
Publication year - 2018
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12310
Subject(s) - travelling salesman problem , traveling purchaser problem , mathematical optimization , bottleneck traveling salesman problem , computer science , 2 opt , profit (economics) , class (philosophy) , vertex (graph theory) , operations research , graph , mathematics , economics , artificial intelligence , microeconomics , theoretical computer science
In this paper, we introduce a class of new selection and routing problems, and name it as the traveling salesman problem with profits and stochastic customers (TSPPSC), which is an extension of the traveling salesman problem with profits (TSPP). The class of new problems is put forward to address how to deal with stochastic customer presence under the environment in which an associated profit is obtained once a customer is visited. It is defined on a complete graph in which profits are associated with the vertices and travel costs are associated with the edges. Each vertex (customer) has a probability of requiring a visit. The objective is the simultaneous optimization of the expected collected profits and expected travel costs. According to the way the two objectives (profits and travel costs) are addressed, TSPPSC is categorized into three subproblems. Mathematical formulations are provided for these problems and a genetic algorithm is proposed to solve one of these subproblems. Computational experiments conducted on several sets of instances show a good performance of the proposed algorithm.