Traveling salesman problems with profits and stochastic customers

• DOI: http://doi.org/10.1111/itor.12310
• Author: Liang Liang,Jin Qin,Yugang Yu,Mengying Zhang
• Published date: 01 July 2018
• Date: 01 July 2018

Intl. Trans. in Op. Res. 25 (2018) 1297–1313

DOI: 10.1111/itor.12310

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Traveling salesman problems with profits and stochastic

customers

Mengying Zhang, Jin Qin, Yugang Yu and Liang Liang

School of Management, University of Science and Technology of China, Hefei,Anhui 230026, China

E-mail: zmy0908@mail.ustc.edu.cn [Zhang]; qjin@ustc.edu.cn[Qin]; ygyums@gmail.com [Yu];

lliang@ustc.edu.cn [Liang]

Received 11 May2015; received in revised form 19 February 2016; accepted 27 April 2016

Abstract

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 environmentin 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 twoobjectives (profits and travel costs) are addressed, TSPPSC is categorizedinto 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.

Keywords:stochastic routing; profit; stochastic customers; genetic algorithm

1. Introduction

At the present time, customers are increasingly interested in purchasing products online instead

of through traditional retail outlets. The explosive growth of e-commerce has generated significant

volumes of direct-to-customer deliveries,which has caused a number of delivery issues within the last

part of the direct-to-customer delivery chain. This part is called “the last mile logistics,” which can

be considered one of the most expensive and inefficientparts of the supply chain (Boyer et al., 2009).

Some e-commerce platforms, such as Jingdong in China, provide transportation services partially

by themselves and outsource some of them to third-party logistics providers. Once a customer is

served, the transportation service provider will receive a profit associated with the customer and

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1298 M. Zhang et al. / Intl. Trans. in Op. Res. 25 (2018) 1297–1313

pay for the corresponding travel cost. In order to maximize its profits and minimize the travel

costs, these e-commerce platforms need to determine, among the set of potential customers, the

customers to be served by themselves and the delivery routes, and then outsource the services of the

remaining customers to third-party logistics companies. To help such e-commerce platforms make

cost-efficient deliveries, it is important to reexamine the tour design in the last mile logistics.

In the last mile logistics, a set of customers need to be assigned to a particular driver, and each

customer has a probability of purchasing products online every day, accordingly each customer

has a probability of requiring a delivery service on a given day. Since each customer arises on a

stochastic basis, it is desirable to design the tour through an apriorioptimization (Bertsimas et al.,

1990). In the apriorioptimization, an ordering of all possiblecustomers that a particular drivermay

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. Aprioritours can be easily

implemented and are an alternative to the high cost of reoptimization. In addition, aprioritours

offer both drivers and customers consistency, and help to improve driver efficiency as the driver

becomes familiar with the tour (Campbell and Thomas, 2008; Wang and Wu, 2014).

Therefore, the aim of an e-commerce platform is to find aprioritours through a subset of potential

customers with the consideration of simultaneous optimization of the expected collected profit and

expected travelcosts, and then outsource the remaining transportation services. We assume that the

platform will outsource the service to carriers that can satisfythe requests at a lower cost, and issues

concerning the outsourcing are beyond the scope of this paper.

Considering the case of one uncapacitated delivery vehicle, the above situation can be approxi-

mately viewedas an instance of the traveling salesman problem with profitsand stochastic customers

(TSPPSC). The problems are defined on a complete graph G=(V,E), where Vis a set of vertices

representing stochastic customers whose presence is uncertain whereaslocations are known apriori,

which is the same setting as the probabilistic TSP (PTSP) (Jaillet, 1985). In addition, profits are

associated with customers and an associated profit is collected once a customer is visited, which

is different from PTSP. Eis a set of all possible edges associated with travel costs. The tour starts

and ends at a fixed vertex (the depot), and each vertex can never be visited more than once. The

objective is the simultaneous optimization of the expected collected profit and the expected travel

costs.

The main contribution of this paper is to introduce a class of new selection and routing problems

and name it as the TSPPSC. According to the way the two objectives (profits and travel costs) are

addressed, TSPPSC is categorized into three subproblems in this paper: the orienteering problem

(OP) with stochastic customers, prize-collecting TSP (PCTSP) with stochastic customers, and prof-

itable tour problem (PTP) with stochastic customers. Mathematical formulations for these three

types of problems are introduced, and a hybrid genetic algorithm (GA) is developed to solve the OP

with stochastic customers. Experiments were conducted on several sets of instances to assess the ef-

ficiency of the proposed approach. The computational results indicate that the proposed algorithm

is a promising tool to handle the TSPPSC.

The paper is structured as follows. In the following section, we provide an overview of the re-

lated literature. In Section 3, mathematical formulations are presented for three new problems.

Section 4 provides a hybrid GA to solve the OP with stochastic customers. Computational re-

sults are presented in Section 5. The final section contains conclusions and directions for future

research.

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation of OperationalResearch Societies