Article Preview
Top1. 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.