The probabilistic profitable tour problem

Mengying Zhang, John Wang, Hongwei Liu

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


A new routing problem is introduced and named as the probabilistic profitable tour problem in this paper. The problem is defined on a complete graph where profits are associated with the vertices and travel costs are associated with the edges. Each vertex (customer) has a probability of requiring a visit on a given day. The tour starts and ends at a fixed vertex, and each vertex can never be visited more than one time. Once a vertex is visited, an associated profit is collected and the corresponding travel cost occurs. The objective is to find a subset of vertices and an a priori tour through those vertices that maximizes the difference between the expected profits and the expected travel costs. The problem is confronted by some big e-tailing companies who need to determine, among the set of all potential customers, the customers to be served by themselves and outsource the unselected customers. The problem under study is shown to be NP-hard in this paper. The authors provide a non-linear mathematical formulation for it. Consequently, a genetic algorithm is developed to solve this problem. The computational experiments carried out on small-and moderate-size instances show a good performance of the proposed algorithm.

Original languageEnglish
Pages (from-to)51-64
Number of pages14
JournalInternational Journal of Enterprise Information Systems
Issue number3
StatePublished - 1 Jul 2017


  • Customer
  • Genetic Algorithm
  • Profitable Tour Problem
  • Stochastic Routing


Dive into the research topics of 'The probabilistic profitable tour problem'. Together they form a unique fingerprint.

Cite this