A matheuristic for the MinMax capacitated open vehicle routing problem

• Author: Ana Dolores López‐Sánchez,Jens Lysgaard,Alfredo G. Hernández‐Díaz
• DOI: http://doi.org/10.1111/itor.12581
• Published date: 01 January 2020
• Date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 394–417

DOI: 10.1111/itor.12581

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A matheuristic for the MinMax capacitated open vehicle

routing problem

Jens Lysgaarda, Ana Dolores L´

opez-S´

anchezband Alfredo G. Hern´

andez-D´

ıazb

aDepartment of Economics and Business Economics, Aarhus University, FuglesangsAll ´

e 4, DK-8210 Aarhus V, Denmark

bDepartment of Economics, QuantitativeMethods and Economic History, Pablo de Olavide University, Ctra. Utrera,Km 1,

41013 Seville, Spain

E-mail: lys@econ.au.dk [Lysgaard]; adlopsan@upo.es [L´

opez-S´

anchez]; agarher@upo.es [Hern´

andez-D´

ıaz]

Received 30 October 2016; receivedin revised form 18 July 2018; accepted 18 July 2018

Abstract

In this paper,the MinMax-COVRP (where COVRPis capacitated open vehicle routing problem) is considered

as a variation of the COVRP where the objective is to minimize the duration of the longest route. For the

purpose of producing high-quality solutions, elements from the fields of mathematical programming and

metaheuristics are combined, resulting in a matheuristic for solving the MinMax-COVRP. The matheuristic

benefits from the diversificationproduced by a metaheuristic and the intensification from mixed-integer linear

programming (MILP). The initial solution provided by a multistart heuristic is used to seed and acceleratethe

MILP in which a local branching frameworkand the separation of k-path inequalities are suitably combined.

Computational experience shows promising results not only improving the initial solution provided by the

multistart algorithm, but also ensuring optimality for most of the small- and medium-sized instances.

Keywords:vehicle routing problem; matheuristic; COVRP; MinMax objective

1. Introduction

The classical capacitated vehicle routing problem (CVRP), as introduced by Dantzig and Ramser

(1959), is concerned with the determination of routes for a fleet of vehicles in order to serve given

demands by a set of customers, so that the total distance traveled is minimized. All vehicles are

available at a depot and have limited capacity. In the CVRP, all routes are closed in the sense that

they all must begin and end at the depot. The capacitated open vehicle routing problem (COVRP),

introduced by Sariklis and Powell (2000), is a variation of the CVRP obtained by requiring open

routes, that is, each route must begin at the depot and end at a customer (or vice versa).

The MinSum objective of minimizing total distance, as used in both CVRP and COVRP, may be

viewed as a measure of the total cost incurred by the owner of the vehicle fleet as a consequence of

the planned routes.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 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. Lysgaard et al. / Intl. Trans. in Op. Res.27 (2020) 394–417 395

Depending on the specific problem context, however, it may be more relevant to consider the

customers’ perspective when measuring the quality of a solution. For example, Campbell et al.

(2008) presented alternative objectives, including the possibility of letting the quality of a solution

be given by the duration of the longest route, that is, a MinMax objective. Also in the application

considered by L´

opez-S´

anchez et al. (2014), the duration of the longest route wasused as the measure

of quality of a solution. They named this variant as balanced open vehicle routing problem since

minimizing the maximum route duration can also be viewed as a measure of route balancing. In

this paper, we consider the same type of problem as that considered by L´

opez-S´

anchez et al. (2014),

and from now on we will name it the MinMax-COVRP.

While the MinMax objective serves as an alternative to the traditional MinSum objective, we

find it appropriate to emphasize that, in general, a broader spectrum of possible objective functions

may come into consideration. In particular, whereas the MinMax objective may reflect a purpose

of route balancing, as in L´

opez-S´

anchez et al. (2014), alternative approaches for balancing could

also be considered. For an extensive coverage of alternative objectives, in relation to balancing as

well as other aspects, we refer to the survey in Jozefowiez et al. (2008).

In terms of practical problem domains,alternative objectives naturally come into considerationin

routing of buses, as considered in L´

opez-S´

anchez et al. (2014) and in several of the articles referred

to in Section 2. Some papers focus on the routing part as wedo in this paper, whereas other authors

include the routing, planning, and scheduling parts, as it is done by Kinable et al. (2014) who

resolve a public school bus transportation problem. However, also in other areas than bus routing

it is natural to consider alternative objectives. Indeed, the problem domain of humanitarian relief

is another important area involving a variety of alternative objectives, and we refer to Huang et al.

(2012) for a detailed analysis of alternative objectives related to that particular application area.

Matheuristics represent combinations of heuristics and exact optimization methods, where the

diversification ability of heuristics and the intensification ability of mathematical programming are

combined. Matheuristics have been applied to a variety of optimization problems. For instance,

in the routing area an interesting real-world multitrip vehicle routing problem with time windows

(VRPTW), pickup and deliveries,and heterogeneous fleet is solved using a matheuristic by Boschetti

and Maniezzo (2015). Moreover, in the location field Stefanello et al. (2015) solve the well-known

capacitated p-median problemby reducing mathematical models obtained by a heuristic elimination

of variables. To solve the problem considered in this paper, wepropose a matheuristic that combines

the heuristic from L´

opez-S´

anchez et al. (2014) and the local branching framework introduced by

Fischetti and Lodi (2003). Depending on its parameter settings, the resulting algorithm may be

exact or heuristic. Indeed, the proposed matheuristic is obtained by truncating the tree search in

local branching, which otherwise would correspond to complete implicit enumeration and, hence,

to an exact algorithm.

The MinMax-COVRP is strongly NP-hard as it reduces to the Hamiltonian path problem if the

vehicle fleet contains only a single vehicle. This problem complexity generally serves as motivation

for the use of heuristics. However, we find it interesting to investigate the potential of combining

heuristic and exact approaches to this problem, supporting the emerging role of matheuristics.

Indeed, our purpose is to propose a matheuristic and analyze its potential with respect to producing

optimal or near-optimal solutions in reasonable time.

The paper is organized as follows. Section 2 describes related literature. Section 3 describes

and models the MinMax-COVRP. Section 4 presents the proposed matheuristic algorithm. Then,

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies