The probabilistic profitable tour problem

Mengying Zhang, John Wang, Hongwei Liu

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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
Volume13
Issue number3
DOIs
StatePublished - 1 Jul 2017

Fingerprint

Profitability
Costs
Tailings
Genetic algorithms
Industry
Experiments
Profit
Travel cost

Keywords

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

Cite this

Zhang, Mengying ; Wang, John ; Liu, Hongwei. / The probabilistic profitable tour problem. In: International Journal of Enterprise Information Systems. 2017 ; Vol. 13, No. 3. pp. 51-64.
@article{48b3355336034ea3968ade45f7b4dd3f,
title = "The probabilistic profitable tour problem",
abstract = "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.",
keywords = "Customer, Genetic Algorithm, Profitable Tour Problem, Stochastic Routing",
author = "Mengying Zhang and John Wang and Hongwei Liu",
year = "2017",
month = "7",
day = "1",
doi = "10.4018/IJEIS.2017070104",
language = "English",
volume = "13",
pages = "51--64",
journal = "International Journal of Enterprise Information Systems",
issn = "1548-1115",
publisher = "IGI Publishing",
number = "3",

}

The probabilistic profitable tour problem. / Zhang, Mengying; Wang, John; Liu, Hongwei.

In: International Journal of Enterprise Information Systems, Vol. 13, No. 3, 01.07.2017, p. 51-64.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - The probabilistic profitable tour problem

AU - Zhang, Mengying

AU - Wang, John

AU - Liu, Hongwei

PY - 2017/7/1

Y1 - 2017/7/1

N2 - 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.

AB - 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.

KW - Customer

KW - Genetic Algorithm

KW - Profitable Tour Problem

KW - Stochastic Routing

UR - http://www.scopus.com/inward/record.url?scp=85022197126&partnerID=8YFLogxK

U2 - 10.4018/IJEIS.2017070104

DO - 10.4018/IJEIS.2017070104

M3 - Article

VL - 13

SP - 51

EP - 64

JO - International Journal of Enterprise Information Systems

JF - International Journal of Enterprise Information Systems

SN - 1548-1115

IS - 3

ER -