A multiobjective GRASP–VND algorithm to solve the waste collection problem

• Author: A.G. Hernández‐Díaz,A.D. López‐Sánchez,F. Gortázar,M.A. Hinojosa
• DOI: http://doi.org/10.1111/itor.12452
• Date: 01 March 2018
• Published date: 01 March 2018

Intl. Trans. in Op. Res. 25 (2018) 545–567

DOI: 10.1111/itor.12452

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A multiobjective GRASP–VND algorithm to solve the waste

collection problem

A.D. L´

opez-S´

ancheza, A.G. Hern´

andez-D´

ıaza,F.Gort

´

azarband M.A. Hinojosaa

aEconomics, Quantitative Methods and Economic History,Pablo de Olavide University, Ctra. Utrera,Km 1, 41013, Seville,

Spain

bRey Juan Carlos University, Tulip´

an s/n, 28933, M´

otoles Madrid, Spain

E-mail: adlopsan@upo.es [L´

opez-S´

anchez]; agarher@upo.es [Hern´

andez-D´

ıaz]; francisco.gortazar@urjc.es [Gort´

azar];

mahinram@upo.es [Hinojosa]

Received 14 October 2016; receivedin revised form 28 April 2017; accepted 24 July 2017

Abstract

In this paper,the waste collection problem (WCP)of a city in the south of Spain is addressed as a multiobjective

routing problemthat considers three objectives.From the company’sperspective, the minimization of the travel

cost is desired as well as that of the total number of vehicles. Additionally, from the employee’s point of view,

a set of balanced routes is also sought. Four variants of a multiobjective hybrid algorithm are proposed.

Specifically, a GRASP (greedy randomized adaptive search procedure) with a VND (variable neighborhood

descent) is combined. The best GRASP–VND algorithm found is applied in order to solve the real-world

WCP of a city in the south of Spain.

Keywords: routing problems; hybrid algorithms; greedy randomized search procedure; variable neighborhood descent;

multiobjective optimization problem;waste collection problem

1. Introduction

The waste collection problem (WCP) is a highly interesting routing problem, and this in turn

presents a very popular optimization problem. Essentially, the WCP involves the collection and

transportation of solid waste by vehicles. Those vehicles collect the solid waste from the streets and

deliver it to the disposal facilities. The objective of the WCP is to design routes for the vehicles in

order to optimize the service. For an extensive review of the literature, see Han and Ponce-Cueto

(2015).

The WCP can usuallybe modeled using a variety of formulations depending on its characteristics.

It is well known that a routing problem may be formulated as a node routing problem, frequently

known as a vehicle routing problem (VRP), an arc routing problem (ARP), or a general routing

problem (GRP), depending on where the demand occurs on the underlying graph. In VRPs, which

C

2017 The Authors.

International Transactionsin Operational Research C

2017 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.

546 A.D. L´

opez-S´

anchez et al. / Intl. Trans. in Op. Res. 25 (2018) 545–567

comprise most traditional routing applications, demands are located at customer sites, represented

by nodes on the graph. However, in ARPs, the service activity involves the traversal or coverage

of an arc since customers are located all along the arc. Several authors deal with a more general

routing problem in which the service activity occurs simultaneously at some of the nodes and along

some of the arcs of the graph. This problem is known in the literature as a GRP.

Routing problems have traditionally been addressed as single-objective problems, even those

problems dealing with real-life situations. Nevertheless, the majority of real-life optimization prob-

lems are of a multiobjective nature, since they usually have several objectives that must be optimized

at the same time and these objectives are possibly in conflict, whereby none of the objectives can

be improved without deteriorating another objective. However, this trend has been changing over

recent years, and the theoretical research and practical applications in the field of routing problems

have developed solution methods to address multiobjective routing problems.

According to Jozefowiez et al. (2008), the objectives taken into account whensolving any multiob-

jective routing problem can be multiple and diverse depending on the characteristics of the routing

problem. The minimization of the total costof the solution generated is the most common objective.

Cost can be expressed in many ways, such as the distance traveled, the time required, the number of

customers visited, and even the economic cost. However, many papers deal with the balance of the

vehicles’ routes, for instance, the makespan (i.e., the minimization of the longest route) is viewed as

a balanced objective and is considered in the studies by Corber´

an et al. (2002), Pacheco and Mart´

ı

(2006), Lacomme et al. (2003), Reiter and Gutjahr (2012), and L´

opez-S´

anchez et al. (2014), among

others. Route balancing could also be introduced by minimizing the difference between the length

of the longest and shortest routes, see Jozefowiez et al. (2007). Further objectives related to routes

exist, such as the minimization of the risk in the case of hazardous transportation problems, see for

instance, Meng et al. (2005) and Xie and Waller (2012). Many papers deal with VRPs with time

windows in which additional objectives are considered. These objectives include the minimization

of the lateness or earliness to the bounds of the windows and/or the numberof violated constraints,

see, forinstance, Bar ´

an and Schaerer (2003), and Castro-Gutierrez et al. (2011). Other objectives are

linked to assigning priority to certain customers in an effortto visit those with the highest priorities,

see Park and Koelling (1986, 1989). Other objectives are focused on customer satisfaction, as in

Sessomboon et al. (1998) and G´

omez et al. (2015), and on factors that improvethe customer–driver

relationship, as in Ribeiroand Ramalhinho-Lourenc¸ o (2001). Moreover,there are objectives related

to the management of the fleet, for example, the minimization of the size, see Corber´

an et al. (2002)

and Pacheco and Mart´

ı (2006); alternatively, it could be interesting to optimize the effectiveness of

the vehicle utilization, see El-Sherbeny (2001) and Sessomboon et al. (1998). Objectives can also

be related to that being transported: consideration of passengers, see Corber´

an et al. (2002) and

Pacheco and Mart´

ı (2006); or the prevention of the deterioration of perishable products, see Park

and Koelling (1986, 1989).

In this paper,a particular multiobjective routing problem will be addressed:a multiobjective WCP

combining closed and open trips in each route. This paper was originally motivated by a real-world

problem proposed by the local authority responsible for the waste collection in a city in the south

of Spain. The WCP will be addressed as a multiobjective routing problem, in which the objectives

are to minimize the distance traveled by all vehicles (perspective of the company), and to minimize

the duration of the longest route, in order to attain a more balanced set of vehicle’s routes (workers’

perspective). In our problem, yet another objectiveis considered, the minimization of the number of

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies