A critical analysis of the “improved Clarke and Wright savings algorithm”

• Published date: 01 January 2019
• Author: Kenneth Sörensen,Florian Arnold,Daniel Palhazi Cuervo
• Date: 01 January 2019
• DOI: http://doi.org/10.1111/itor.12443

Intl. Trans. in Op. Res. 26 (2019) 54–63

DOI: 10.1111/itor.12443

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A critical analysis of the “improved Clarke and Wright savings

algorithm”

Kenneth S¨

orensen, Florian Arnold and Daniel Palhazi Cuervo

ANT/OR – Operations Research Group, Department of Engineering Management,University of Antwerp, Belgium

E-mail: kenneth.sorensen@uantwerpen.be [S¨

orensen]; florian.arnold@uantwerpen.be [Arnold];

daniel.palhazicuervo@uantwerpen.be [Palhazi Cuervo]

Received 16 February2017; accepted 23 June 2017

Abstract

In their paper “An improvedClarke and Wrightsavings algorithm for the capacitatedvehicle routing problem,”

published in ScienceAsia (38, 3, 307–318, 2012), Pichpibul and Kawtummachaideveloped a simple stochastic

extension of the well-known Clarke and Wright savingsheuristic for the capacitated vehicle routing problem.

Notwithstanding the simplicity of the heuristic, which they call the “improved Clarke and Wright savings

algorithm” (ICW), the reported results are among the best heuristics everdeveloped for this problem. Through

a careful reimplementation, we demonstrate that the results published in the paper could not have been

produced by the ICW heuristic. Studying the reasons how this paper could have passed the peer review

process to be published in an ISI-ranked journal, we have to conclude that the necessary conditions for a

thorough examination of a typical paperin the field of optimization are generally lacking. We investigate how

this can be improved and come to the conclusion that disclosing source code to reviewers should become a

prerequisite for publication.

Keywords:optimization; combinatorial optimization; heuristics

1. Introduction

The capacitated vehicle routing problem (CVRP) is defined on a complete, undirected graph with

n+1 nodes, one node representing the depot and the nremaining nodes a set of customers with

known demand. The cost of traveling between any pair of customers, or between any customer and

the depot, is also given in a distance matrix, as is the (uniform) capacity of a fleet of vehicles. The

objective of the CVRP is to define a set of routes with minimal total cost such that each vehicle

performs at most one route, the total demand in each route does not exceed the vehicle capacity,

and all customers are visited exactly once.

The CVRP is among the most studied problems in the field of Operations Research, and a very

large number of algorithms have been developed to solve it (see, e.g., Toth and Vigo, 2014, for

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.