An evolutionary algorithm for the multi‐objective pick‐up and delivery pollution‐routing problem

• Author: Lorena Pradenas Rojas,Mauricio Bravo,Victor Parada
• DOI: http://doi.org/10.1111/itor.12376
• Date: 01 January 2019
• Published date: 01 January 2019

Intl. Trans. in Op. Res. 26 (2019) 302–317

DOI: 10.1111/itor.12376

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

An evolutionary algorithm for the multi-objective pick-up

and delivery pollution-routing problem

Mauricio Bravoa, Lorena Pradenas Rojasaand Victor Paradab

aIngenier´

ıa Industrial, Universidad de Concepci´

on, Concepci´

on, Chile

bIngenier´

ıa Inform´

atica, Universidad de Santiago de Chile, Santiago,Chile

Received 26 April 2015; received in revised form 7 November 2016; accepted 8 November 2016

Abstract

The design of sustainable logistics solutions poses new challenges for the study of vehicle-routing problems.

The design of efficient systems for transporting products via a heterogeneous fleet of vehicles must consider

the minimization of cost, emissions of greenhouse gases, and the ability to serve every customer within an

available time slot. This phenomenon gives rise to a multi-objective problem that considers the emission

of greenhouse gases, the total traveling time, and the number of customers served. The proposed model is

approached with an ε-constraint technique that allows small instances to be solved and an evolutionary

algorithm is proposed to deal with complex instances.Results for small instances show that all the points that

approach the Pareto frontier found by the evolutionary algorithm are nondominated by any solution found

by the multi-objective model. For complex instances, nondominatedsolutions that serve most of the requests

are found with low computational requirements.

Keywords: multi-objective pick-up and delivery problem; pollution-routing problem; green logistics; routing carbon

footprint

1. Introduction

Designing efficient transport networks should not only take into account the minimization of cost

but also the emissions of greenhouse gases as well as the quality of service providedto customers. In

2014, 80.0% of greenhouse gases was CO2emanated fromfossil fuel use; the activities with the great-

est influence on total emissions were energy supply, industry, and transport (IPCC, 2014). Due to the

emission of gases, transport has a dangerous impact on the environment, including toxic effects on

the ecosystem and, in particular,on humans (Ohnishi et al., 2008). Thus, particular emphasis should

be given to the design of transport systems that specify routesto be followed by vehicles of a particu-

lar company to transport goods between their origins and destinations. Consequently, several design

objectives should be considered:the minimization of emissions, the minimization of operational cost,

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

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

USA.

M. Bravo et al. / Intl. Trans.in Op. Res. 26 (2019) 302–317 303

and high-quality transport service.Thus, attractive routes forall stakeholders in the problem must be

generated.

Energy and pollution considerations have defined a turning point in the study of the extended

family of vehicle-routing problems (VRP). Such considerations give rise to optimization problems

that present a computational difficulty even in their simplest variants (Toth and Vigo, 2014). When

considering the fuel consumption in regard to such problems, a trade-off between load and con-

sumption for each type of vehicle in the fleet must be established so that routing does not affect

the quality of service. This situation gives rise to the pollution-routing problem (PRP). Kara et al.

(2007) establish an approximation for such a relationship by studying an energy-minimizing VRP

that considers not only the distance traveled by vehicles but also their fuel consumption. Addition-

ally, Xiao et al. (2012) studied a routing model in which fuel consumption is a goal that considers

a linear relationship between load and fuel consumption. In both cases, a homogenous fleet was

considered. In a study by Suzuki (2011), a routing model that also considers the use of fuel as a

means of decreasing greenhouse gases was proposed. In addition to the influence of vehicle load,

a speed factor was included without the explicit consideration of service quality. Also, it has been

found that an effective way to minimize emissions in freight transport is the pooling of resources

(Pan et al., 2013; Sanchez et al., 2016). Also, a heuristic that optimizes speed and time of departure

of the vehicle from the depot allows generating routes that minimize travel and emission costs by

determining the starting time, and the optimal speed for each arc while satisfying the time window

for each customer (Kramer et al., 2015a, 2015b). A linear integer programming model that also

considered time windows and the amount of pollution produced was used to determine that the

cost of fuel consumption does not necessarily decrease by solely minimizing distance when only

one type of customer is considered (Bektas¸ and Laporte, 2011). Such a result may be different if the

minimization of driving time is taken into account. This issue was included as an objective in an

extension of the problem studied by Demir et al. (2014). Because both objectives conflict with each

other, they are considered separately.

A more complex routingwas studied by Pradenas et al. (2013), who considered backhauls and time

windows and attempted to minimize energy consumption when different transportation companies

work together to decrease their emissions. Despite the computational difficulty encounteredin PRP,

the results obtained for differentvariants clearly show that vehicle routings thatare more complex in

nature and which in turn represent appropriately certain real situations are numerically affordable.

A particular case arises in logistics networks that consider pickup and delivery, quality of service,

and time windows. In this paper, a multi-objective pick-up and delivery VRP with time windows

that we name the multi-objective pick-up and delivery PRP (MO-PRP) is considered. One solution

to this problem defines a set of routes that a fleet of vehicles must meet to satisfy a set of product

pick-up and delivery orders for a given planning period, considering multiple objectives. As each

vehicle has different characteristics, a heterogeneous fleet case is studied. In addition, each vehicle

starts its route at a depot and mustvisit customers to meet a set of requests during the given planning

period.

A multi-objective model is proposed to solve the MO-PRP. The objectives considered are the

following: the emission of greenhouse gases measured in terms of fuel consumption; total traveling

time of the vehicles of the fleet; and number of customers served, which is utilized as an indicator

of the quality of service of the routing. The proposed mathematical programming model can solve

small instances. To evaluate larger instances, an evolutionaryalgorithm is designed and numerically

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies