A case study of consistent vehicle routing problem with time windows

• Author: Hernán Lespay,Karol Suchan
• DOI: http://doi.org/10.1111/itor.12885
• Date: 01 May 2021
• Published date: 01 May 2021

Intl. Trans. in Op. Res. 28 (2021) 1135–1163

DOI: 10.1111/itor.12885

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A case study of consistent vehicle routing problem

with time windows

Hernán Lespaya,∗and Karol Suchanb,c

aFacultad de Ingeniería y Ciencias, Universidad AdolfoIbáñez, Av. Diagonal las Torres 2640, Santiago 7941169, Chile

bFacultad de Ingeniería y Ciencias, Universidad Diego Portales, Av. EjércitoLibertador 441, Santiago 8370191, Chile

cAGH University of Science and Technology, al. A. Mickiewicza 30, Krakow 30-059, Poland

E-mail: hlespay@alumnos.uai.cl [Lespay]; karol.suchan@mail.udp.cl [Suchan]

Received 5 December 2019; receivedin revised form 16 August 2020; accepted 24 September 2020

Abstract

We develop a heuristic for the consistent vehicle routing problem with time windows (ConVRPTW), which

is motivated by a real-world application at a food company’s distribution center. Besides standard VRPTW

restrictions, ConVRPTW assigns each customer just one driver to fulfill his or her orders during the whole

multiperiod planning horizon. For each driver and period, a route is sought to serve all their customers

with positive demand. Foreach customer, the number of periods between consecutive orders and the ordered

quantities is highly irregular.This causes difficulties in the daily routing, negatively impacting the service level

of the company. Similar problems have been studied as ConVRP, where the numberof drivers is fixed apriori,

and only the total traveltime is minimized. Moreover, the clients present no time window constraints, but the

visits should be scheduled with a small arrival time variation. In our model, the objective is to minimize the

number of drivers. We impose hard time windows but do not consider time consistency in more detail. We

compare solutions given by the heuristic with solutions of a mixed-integer linear programming model on a set

of small artificial instances and solutions used by the food companyon real-world instances. The results show

the effectiveness of the heuristic. For the company, we obtain significant improvements in the routing plans,

with a lower number of vehicles and a higher rate of orders delivered within the prescribed time window.

Keywords:vehicle routing; multiperiod routing; distributionlogistics; service consistency; customer satisfaction; heuristics

1. Introduction

The problem studied in this paper is motivated by a real-world application at a food distribution

company in Chile. This company is one of the leading national producers and marketers of meat

and poultry. The company has 17 distribution centers throughout the national territory. In this

paper, we focus on one of their distribution centers. However, this study can be replicated in each

∗Corresponding author.

© 2020 The Authors.

International Transactionsin Operational Research © 2020 International Federation of OperationalResearch Societies

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

USA.

1136 H. Lespay and K. Suchan / Intl. Trans. in Op. Res. 28 (2021) 1135–1163

distribution center of the company because their operations are quite similar throughout the coun-

try. The company has large sales volumes nationwide, and the costs associated with distribution

activities represent an essential component of their total expenditures. Therefore, a reduction of 5%

or 10% in the routing costs would mean a significant improvement for the company.

The customers of the company correspond to supermarkets, restaurants, wholesalers, and small

convenience stores spread throughoutthe region of Chile. The set of customers changes, on average,

by 10% from one month to another. This customers’ variability is in large part due to the low

frequency and irregularity of orders from small convenience stores, which represent 60% of the

total number of customers.Also, the customers are characterized by high variability of service times

and, even under perfect conditions, the time needed to unload the delivery can differ by about an

hour from one customer to another. Additionally, each customer requires that his or her orders be

delivered within a certain time window.

The company has a fleet of vehicles, which are dispatched from the distribution center to their

respective customers. Each vehicle has a fixed subset of customers assigned to it, and each day the

vehicles serve their corresponding customers.

Due to high variability in the activity of the customers, the quantities they order, and the service

times, the company currently experiences significant problems in the fulfillment process during the

periods of high activity: the customer time windows may not be respectedand, in some cases, the de-

livery even has to be postponed to another day. Consequently, it is vital for the company to develop

a decision support system that would improve the planning and scheduling of the distribution of

products to its customers, seeking the right balance between operational costs and service quality.

1.1. Consistency in vehicle routing

In the standard version of the vehicle routing problem (VRP), we have a set of customers with a

known demand and a set of homogeneous vehicles with a limited capacity based at a depot. The

goal is to determine a set of routes to fulfill all orders at minimum cost. The VRP was introduced

in Dantzig and Ramser (1959), and the objective is oriented to increase the profitability of the com-

panies without considering customer satisfaction, an important concern in competitive markets.

Solving the VRP for each day in an independent way allows companies to minimize operational

costs and efficiently use their vehicle fleet. However, this has some operational disadvantages. Fre-

quent changes in the vehicle’s routes can negatively impact the productivity and job satisfaction

of the drivers. Consequently, due to the growing industry competition, it is crucial to balance the

objective of designing routes of low cost with that of providing high-quality service to increase

customer satisfaction.

In general, customer satisfaction is directly related to providing a consistent service (see Kovacs

et al., 2014a). Service consistency has three different dimensions: (a) time, it refers always to visit a

given customer at roughly the same time; (b) person, it refers always to execute the delivery by the

same driver; and (c) delivery, it refers to minimizing the variability of the quantity delivered when

the supplier decides the quantity delivered (vendor-managed inventory systems). The relevance of

each one of these three dimensions of consistency changes from one market to another.

From the point of view of distribution companies, consistent routes improve driver satisfaction

and productivity because they allow drivers to gain knowledge about the territory where they are

© 2020 The Authors.

International Transactionsin Operational Research © 2020 International Federation of OperationalResearch Societies