A multilevel evaluation method for heuristics with an application to the VRPTW

• Author: K. Sörensen,J. Corstjens,B. Depaire,A. Caris
• Published date: 01 January 2020
• Date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12631

Intl. Trans. in Op. Res. 27 (2020) 168–196

DOI: 10.1111/itor.12631

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A multilevel evaluation method for heuristics with

an application to the VRPTW

J. Corstjensa, B. Depaireb,A.Caris

aand K. S¨

orensenc

aResearch Group Logistics, UHasselt, Agoralaan, Diepenbeek 3590, Belgium

bResearch Group Business Informatics,UHasselt, Agoralaan, Diepenbeek 3590, Belgium

cDepartment of Engineering Management, Universiteit Antwerpen,Prinsstraat, Antwerpen 2000, Belgium

E-mail: jeroen.corstjens@uhasselt.be [Corstjens]; benoit.depaire@uhasselt.be[Depaire]; an.caris@uhasselt.be [Caris];

kenneth.sorensen@uantwerpen.be [S¨

orensen]

Received 27 October 2017; accepted 2 January 2019

Abstract

The field of combinatorial optimization has inspired the development of a largenumber of heuristic solution

procedures. These methods are commonly assessed using a competitive evaluation methodology that may

give an indication of which algorithm has a better performance. A next step in the experimental analysis is to

uncover “why”one algorithm performs better. Which elements are responsible forgood or bad performance?

How does the performance of elements vary across the design space? What is the influence of the specific

problem instance that is being solved? We focus on gaining a better understanding of heuristic algorithm

performance and demonstrate thatthe application of a proper statistical methodology can provideresearchers

insight into how performance is affected by the different algorithm parameters and components. As an

example, we apply a multilevel statistical analysis to a large neighborhood search algorithm for the vehicle

routing problem with time windows.

Keywords: algorithm performance; statistical evaluation; understanding; vehicle routing problem with time windows;

large neighborhood search; metaheuristics

1. Introduction

The field of combinatorial optimization has inspired the developmentof a large number of heuristic

algorithms that are able to produce good solutions in a reasonable time. They range from standard

construction and improvement algorithms to powerful metaheuristic frameworks. The former two

also constitute an important component in all metaheuristic frameworks (Br¨

aysy and Gendreau,

2005).

The most common approach to evaluate heuristics for an optimization problem is by studying

their performance on a set of standard benchmark problems. This type of evaluation results in a

C

2019 The Authors.

International Transactionsin Operational Research C

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

J. Corstjenset al. / Intl. Trans. in Op. Res. 27 (2020) 168–196 169

competition among state-of-the-art methods in the literature. A newly developedheuristic algorithm

is considered “better” than the existing ones,if it outperforms them on the standard set of benchmark

problems. This kind of experimental evaluation has been useful to know which algorithms work

well on which applications. It is one type of knowledge acquisition. This research argues to go a

step further and acquire another type of knowledge that focuses on understanding why heuristic

algorithms or configurations of a single algorithm perform differently. An experimental evaluation

focused on gaining insight into how things work and why they work well has been acknowledged

as important but has received little attention (Hooker, 1995; Cuervo et al., 2014; S¨

orensen, 2015).

This research aims to fill this gap by focusing on evaluating heuristic algorithms with the aim of

understanding how the reported performance valuesare obtained rather than on developing the best

performing algorithm. Therefore, we propose a general statistical evaluation framework to set up

and analyze the results of an experimental study investigating the relationships between algorithm

performance, algorithm parameters, and problem instance characteristics. The methodology has

a statistical foundation since statistical tests offer a means of learning (Bartz-Beielstein, 2006)

with the interest being to draw conclusions that are valid beyond the specific problem instances

and parameter values chosen (Rardin and Uzsoy, 2001). We wish to identify how the algorithm

parameters impact algorithm performance,positively or negatively, and how these effectsvary across

different parts of the problem space. The objective is to expose patterns in the performance data

to establish which (combinations of) elements work well under which conditions. These patterns

can then be further investigated by formulating falsifiable hypotheses in consecutive studies and the

ultimate goal is the production of insights that increases our knowledge of heuristic algorithms.

In this paper, the contribution is threefold. First, the methodological framework is presented and

discussed. Second, the frameworkis applied to produce falsifiable hypotheses thatare to be validated

in consecutive iterations of the experimental study (e.g., in Corstjens et al., 2019). Third, the

framework is demonstrated to the domain of vehicle routing problems (VRPs). These are an

extensively studied class of combinatorial optimisation problems, with a wide spectrum of real-

life applications. Understanding how a VRP influences heuristic algorithm behavior is therefore

relevant knowledge to acquire.

The paper is structured as follows. In Section 2, previous research efforts targeted at providing

some explanation for performance results are reviewed. This is followed by a brief introduction

to the hypothetico-deductive method in Section 3, which forms the foundation our evaluation

methodology is built on. In Section 4, we introduce our methodology followed by an illustration

in Section 5 on the large neighbourhood search (LNS) and vehicle routing problem with time

windows (VRPTW), where we first elaborate on the problem instances generated (Section 5.2) and

the heuristic algorithm used to solve these instances (Section 5.3). The results of the statistical

analysis and the insights obtained are discussed in Section 5.5. A conclusion is finally given in

Section 6.

2. Related work

The surgence of automated algorithm configurators over the last decade, often inspired byconcepts

from machine learning, have gained a lot of popularity by introducing more formal procedures

to determine parameter settings rather than the tedious and error-prone trial-and-error approach

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation of OperationalResearch Societies