A model‐based heuristic to the vehicle routing and loading problem

• DOI: http://doi.org/10.1111/itor.12586
• Date: 01 May 2019
• Author: Ana Moura
• Published date: 01 May 2019

Intl. Trans. in Op. Res. 26 (2019) 888–907

DOI: 10.1111/itor.12586

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A model-based heuristic to the vehicle routing

and loading problem

Ana Moura

Department of Economics, Management and Industrial Engineering, University of Aveiro, Campus Universit´

ario de

Santiago, Aveiro 3810-193, Portugal

E-mail: ana.moura@ua.pt [Moura]

Received 31 March 2017; receivedin revised form 31 January 2018; accepted 21 July 2018

Abstract

In this paper a model-based heuristic approach fora typical distribution problem is presented. In order to be

cost-effective, the distribution process for manycustomers, each of them with orders of considerable volume,

should be dealt with like a combination of two well-known problems: the vehicle routing problem (VRP)

and the container loading problem (CLP). This paper studies a particular integration of these two problems

called the vehicle routing and loading problem (VRLP). The VRLP is an operational problem that must

be solved daily by many production and distribution companies. Like the two original problems (VRP and

3D-CLP), the VRLP is NP-hard. In this work, regardless of the complexity of this problem, a mixed integer

linear programming (MILP) model thatcharacteriz es the VRLP with time windowsis presented and it is also

used to solve the problem optimally. Then, a model-based heuristic that improves the computational time,

when bigger instances need to be solved, is also presented. In order to prove the viability of the approach

and the developed MILP model, tests with the benchmark instances of the VRLP were made and the results

compared with other published works. Despite the long computational time needed to solve bigger instances,

the VRLP model could be used to compute optimal solutions or at least good lower bounds,in order to have

a base of comparison when nonexact methods are applied to the VRLP.

Keywords:vehicle routing problem; container loading problem; mixed integer linear programming;model-based heuristic

1. Introduction

The vehicle routing and loading problem(VRLP) arises in real-world distribution operations.Goods

must be delivered while taking two distribution logistic operations into consideration. On one hand,

an effective distribution must be achieved in order to reduce the distribution costs,but on the other,

the quality of the packing and transport is crucial to meet the customers’ needs. So, the packing

and transport process are an interdependent process.

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.

A. Moura / Intl. Trans.in Op. Res. 26 (2019) 888–907 889

The VRLP is an integration of the vehicle routing problem with time windows (VRPTW) and the

three-dimensional (3D) packing problems of rectangular pieces. The main goal is that the products

must be delivered to the customers’ locationson time and undamaged, in the quantities ordered, and

the unloading process of the goods must be accomplished easily and in a time-saving manner—in

order to reduce the costs distribution process and the dissatisfaction of the clients. To accomplish

this, the packing and transportation operations must be carried out efficiently and in an integrated

basis. Basically, the objective is to minimize the total transportations costs (or the distances/time

traveled) ensuring that the customers’ demands are satisfied and the vehicle loading capacities in

terms of volume and weight are not exceeded.

The VRLP must take into account the constraints related to the routing and packing problems.

The basic vehicle routing problems (VRPs) and container loading problems are NP-hard, so the

VRLP is also an NP-hard problem, as a result of this integration. Nevertheless, it is proven in this

work that it is possible to solve it using a mixed integer linear programming (MILP) model.

The highlight of this work is that the VRLP is solved using an exact approach that allows for the

optimal solutions or good upper bonds that could be used to further result comparisons obtained

with other nonexact approaches. The problem formulation presented involves the minimization

of the total travel distance and the spatial allocation of mixed-sized boxes into fixed-dimensional

vehicles, also minimizing the number of vehicles. Furthermore, the model allows all boxes to rotate

in three dimensions and they may also have fixed or limited orientation. The boxes could be loaded

in multiple layers formed by different sized and shaped boxes in order to make the package as tight

as possible (minimizing the volume utilization of the vehicles).

This paper is structured as follows. Section 2 is a review of the relevant literature of VRLP;

Section 3 has a detailed description of the problem followed by the proposed MILP model in

Section 4; Section 5 presents a performance study of the model, using well-known benchmark

instances. A model-based heuristic developed to improve the computational time needed to solve

the VRLP and the related result comparisons with other published approaches are also presented;

finally, Section 6 summarizes the research findings and concludes this paper.

2. Literat ure review

Logistic operations are vital to manufacturing and distribution companies. Managing the distribu-

tion of goods is a vital operation that has a major economic impact. However, client satisfaction

depends mainly on meeting their demands as effectively as possible. This is commonly described as

providing a service to a client. Usually, a service is a mixture of differentdistribution characteristics,

for example, product availability, delivery time, delivery programming, and good conditions after

delivery (Moura and Oliveira, 2009). One of the most important areas in serving clients is the trans-

portation of goods. With an effective distribution, items arrive on time, not damaged and in the

desired quantities. Naturally, these are the three main client demands that have to be achieved. For

that, a high degree of interdependence between the route planning and vehicle loading is needed.

There are onlya few papers dealing with the VRP with 3D loading constraints and the publications

dated back to 2007 with a work presented by Iori et al. (2007) that deals with a 2D packing and

routing problem, where they present an exact branch-and-cut algorithm. Later on, Gendreau et al.

(2008) proposed a metaheuristic solution method for the same problem.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies