An iterative biased‐randomized heuristic for the fleet size and mix vehicle‐routing problem with backhauls

• Author: Javier Belloso,Javier Faulin,Angel A. Juan
• Published date: 01 January 2019
• Date: 01 January 2019
• DOI: http://doi.org/10.1111/itor.12379

Intl. Trans. in Op. Res. 26 (2019) 289–301

DOI: 10.1111/itor.12379

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

An iterative biased-randomized heuristic for the fleet size and

mix vehicle-routing problem with backhauls

Javier Bellosoa, Angel A. Juanband Javier Faulina

aDepartment of Statistics and Operations Research, Public University of Navarre,31006, Pamplona, Spain

bDepartment of Computer Science, Multimedia, and Telecommunication – IN3, Open University of Catalonia, 08018,

Barcelona, Spain

E-mail: javier.belloso@unavarra.es [Belloso]; ajuanp@uoc.edu [Juan]; javier.faulin@unavarra.es [Faulin]

Received 4 March 2016; receivedin revised form 7 November 2016; accepted 8 November 2016

Abstract

This paper analyzes the fleet mixed vehicle-routing problem with backhauls, a rich and realistic variant

of the popular vehicle-routing problem in which both delivery and pick-up customers are served from a

central depot using a heterogeneous and configurable fleet of vehicles. After a literature review on the issue

and a detailed description of the problem, a solution based on a multistart biased-randomized heuristic is

proposed. Our algorithm uses an iterative method that relies on solving a series of smaller instances of the

homogeneous-fleet version of the problem and then using these subsolutions as partial solutions for the

original heterogeneous instance.In order to better guide the exploration of the solutions space, the algorithm

employs several biased-randomized processes: a first one for selecting a vehicle type; a second one for sorting

the savings list; and a third one to define the number of routes that must be selected from the homogenous-

fleet subsolution. The computational experiments show that our approach is competitive and able to provide

20 new best-known solutions for a 36-instance benchmark recently proposed in the literature.

Keywords:vehicle-routing problem with backhauls; heuristics; biased randomization; multistart algorithms; fleet size and

mix vehicle-routing problem

1. Introduction

Road transportation is the predominant way of transporting goods in many world regions. This

explains the relevance of rich and real-life vehicle-routing problems (VRPs), since efficient route

planning can significantly reduce transportation costs and offer a better service to customers

(Caceres et al., 2014). This paper analyzes the fleet mixed vehicle-routing problem with backhauls

(FSMVRPB), in which both delivery and pick-up customers are served froma central depot using a

heterogeneous and configurable fleet of vehicles. This rich and realistic variantcombines the aspects

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.