# The Probabilistic Profitable Tour Problem

Mengying Zhang (School of Business, Anhui University, Anhui, China), John Wang (Department of Information Management and Business Analytics, Montclair State University, Montclair, NJ, USA) and Hongwei Liu (School of Business, Anhui University, Anhui, China)
DOI: 10.4018/IJEIS.2017070104
Available
\$37.50
No Current Special Offers

## 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.
Article Preview
Top

## 1. Introduction

The probabilistic profitable tour problem (PPTP) is defined on a fully connected graph , where denotes the set of vertices with associated profits and denotes the set of edges with associated travel costs. Each vertex has a probability of requiring a visit. 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 of this problem is to find a subset of vertices (customers) and an a priori tour through those vertices that maximizes the difference between the expected profits and the expected travel costs.

The study of this problem is motivated by the situation where a set of customers is given with a probability of requiring service every day and only a subset of them has to be selected and served. Nowadays customers are increasingly interested in purchasing products online instead of through traditional retail outlets, and each customer has a probability of purchasing products online every day. Once a carrier provides transportation service for a customer who shops online, he will receive a value of profit. At the meantime, he should pay for the corresponding travel cost. Some e-commerce platforms, such as JINGDONG in China, provide transportation services partially by themselves and outsource some of them. In this case, the e-commerce companies need to determine, among the set of potential customers, the customers to be served by themselves and the delivery routes, and then outsource the service of the rest customers to third party logistics companies.

Since each customer arises on a stochastic basis, it is desirable to design the tour through an a priori optimization (Bertsimas et al., 1990). In the a priori optimization, an ordering of all possible customers that a particular driver may need to visit is constructed first, once the information of customer presence is revealed, the driver then skips those customers on the tour who do not require a service. A priori tours can be easily implementable and are an alternative to the high cost of re-optimization. In addition, a priori tours offer both drivers and customers consistency and help to improve driver efficiency as the driver becomes familiar with the tour (Campbell and Thomas, 2008; Muscatello et al., 2016; Wang and Wu, 2014).

If there is only one vehicle involved, the problem can be viewed as an instance of the PPTP. To the best of our knowledge, the two most common features of numerous variants of TSP are that the presence of the customer is deterministic and that no profit is associated with each customer (Bellmore and Nemhauser, 1968; Gutin and Punnen, 2002). Previous studies have not addressed how to deal with stochastic customer presence under the environment in which an associated profit is obtained once a customer is visited. Thus, our research focuses on the probabilistic profitable tour problem in which the customer presence is stochastic. The PPTP can be considered an extension of the profitable tour problem (PTP) (Dell'Amico et al., 1995). In the PTP, it is assumed that each customer has a deterministic service request and the objective is to maximize the difference between the total profits and the total costs. In the PPTP, the PTP is extended to the case where each customer has a probability to request a delivery.

In this paper, we restrict our attention to the homogeneous PPTP, a problem where each vertex has the same visiting probability. We present an integer non-linear formulation for this problem and develop a genetic algorithm to solve it. Experiments were conducted on several sets of instances to assess the efficiency of the proposed approach in this paper. The computational results indicate that the proposed genetic algorithm is a promising tool to handle the PPTP.

## Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 18: 4 Issues (2022): Forthcoming, Available for Pre-Order
Volume 17: 4 Issues (2021): 2 Released, 2 Forthcoming
Volume 16: 4 Issues (2020)
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing