Metaheuristics based on decision hierarchies for the traveling purchaser problem

• Published date: 01 July 2018
• Author: Raquel Bernardino,Ana Paias
• Date: 01 July 2018
• DOI: http://doi.org/10.1111/itor.12330

Intl. Trans. in Op. Res. 25 (2018) 1269–1295

DOI: 10.1111/itor.12330

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Metaheuristics based on decision hierarchies for the traveling

purchaser problem

Raquel Bernardinoaand Ana Paiasb

aDEIO, Faculdade de Ciˆ

encias, Universidade de Lisboa, Lisboa, Portugal

bCentro de Matem´

atica, Aplicac¸˜

oes Fundamentais e Investigac¸ ˜

ao Operacional, Faculdade de Ciˆ

encias,

Universidade de Lisboa, Lisboa, Portugal

E-mail: raquelbernardino@live.com.pt [Bernardino]; ampaias@fc.ul.pt [Paias]

Received 1 March 2016; receivedin revised form 21 June 2016; accepted 21 June 2016

Abstract

In this paper we address the traveling purchaser problem, an NP-hard problem that generalizes the traveling

salesman problem. We present several metaheuristics that combine genetic algorithms and local search. The

genetic algorithms are induced by different hierarchic orderings of the decision making regarding the route

and the acquisition of the items. Computational experimentswere carried out with benchmark instances and

the results show that the proposed metaheuristics are a suitable tool to solve high-dimensioned instances for

which the exact methods do not provide solutions within a reasonable CPU time. For several instances, best

new upper bounds for the optimum value of the objective function were obtained.

Keywords: traveling purchaser problem; genetic algorithms; local search; metaheuristics; biased random key genetic

algorithm

1. Introduction

Consider a depot, a set of markets, and a list of items to be purchased. Additionally, assume that

the cost of purchasing an item at each market where it is available and the cost of traveling between

each pair of markets and between each market and the depot are known. The traveling purchaser

problem (TPP) consists in finding a route that satisfies the following criteria:

rstarts and ends at the depot;

rcontains a subset of markets, which covers the list of items;

rminimizes the total cost, which is the sum of the traveling cost and the purchasing cost.

Apart from the most common application of the TPP in vehicle routing, there are several other

applications such as warehousing problems or production scheduling problems (see, e.g., Singh and

van Oudheusden, 1997; Gouveia et al., 2011).

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.

1270 R. Bernardino and A. Paias/ Intl. Trans. in Op. Res. 25 (2018) 1269–1295

The above definition of the TPP was firstly introduced in Ramesh (1981). The author assumed

that if an item is available in one market then the quantity available of that item is enough to

fulfill the demand. Consequently, visiting a single market is sufficient to purchase a given item. This

version is called the uncapacitated TPP (UTPP). In the capacitated TPP (CTPP) one wants to buy

several copies of each product and the quantity available in each market may be lower than the

demand, meaning that it might be necessary to visit more than one market to purchasea given item.

The TPP can be modeled using a simple graph G=(M,A),whereM={1,...,m}is the set

of markets and Ais the set of arcs, and considering a set of items K={1,...,n}. The depot will

correspond to market 1. For simplicity we assume that Gis a complete graph, that is, A={(i,j):

i,j∈M∧i= j}. However, if that is not the case, we can either consider that Aonly includes the

arcs corresponding to existing connections or transform the graph into a complete graph by adding

arcs with infinite costs. For each arc in Alet cij be the cost of traveling from market ito the market

jand let dki, with k∈Kand i∈M, be the cost of purchasing the item kin the market i. We assume

that the purchasing costs are strictly positive.

The TPP is NP-hard because it is a generalization of the traveling salesman problem (TSP), which

is known to be NP-hard. In fact, let us assume that each market only sells one type of items. The

solution of this particular TPP will be a hamiltonian cycle. So, if the distance costs are modified

in order to incorporate the purchase cost, we obtain the TSP. The TPP can also be reduced to

the uncapacitated facility location problem if we consider that the traveling cost associated with

markets iand jis the average cost of opening both facilities iand j, and the cost of purchasing an

item kin a market iis the cost of assigning the costumer kto the facility i. Finally, the UTPP can

be transformed in the generalized TSP (GTSP). In order to do this one needs to replicate each of

the markets as many times as the number of items that are sold in that market, that is, if a market

isells kitems we will have knodes representing market i. The GTSP is obtained by defining as

many clusters as the number of items and the cluster associatedwith item kcontains all the markets

that sell it. If the triangle inequality holds one will never buy the same item in more than one

market.

As mentioned above, the objective function is the sum of two components, one associated with

the route and another with the item acquisition. In order to minimize the route cost it is desirable to

have a small route, however to minimize the purchase cost it might be better to visit several markets

in order to buy the items where their price is the lowest. For this reason the TPP may be seen as a

biobjective problem (Riera-Ledesma and Salazar-Gonz´

alez, 2005a).

We can find in the literature variants of the TPP with additional constraints. In Gouveia et al.

(2011) the authors consider that there exists a limit in the number of markets that can be visited and

a limit in the number of items that can be bought in each market. In Mansini and Tocchella (2009),

it is considered that the purchase cost cannot be greater than a predefinedvalue. In this specific case

the objective function only considers the route cost since the purchase cost is addressed as a budget

constraint.

Another variant is the multi-vehicle TPP that generalizes the problem by considering several

routes. An example of such variant applied to school bus routing can be found in Riera-Ledesma

and Salazar-Gonz´

alez (2012). In this particular case there are several vehicles and one wants to

determine several routes that, once again, are a cover for a list of items. The markets represent bus

stops and the items are students that need to be transported to school. In each bus stop there are

several students and each student can go to several bus stops. The route cost is the distance between

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation of OperationalResearch Societies