A nonlinear optimization model for the balanced vehicle routing problem with loading constraints

• DOI: http://doi.org/10.1111/itor.12570
• Author: Carlos A. Vega‐Mejía,Sardar M. N. Islam,Jairo R. Montoya‐Torres
• Published date: 01 May 2019
• Date: 01 May 2019

Intl. Trans. in Op. Res. 26 (2019) 794–835

DOI: 10.1111/itor.12570

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A nonlinear optimization model for the balanced vehicle

routing problem with loading constraints

Carlos A. Vega-Mej´

ıaa,b , Jairo R. Montoya-Torrescand Sardar M. N. Islama

aInstitute of Sustainable Industries & Liveable Cities, VictoriaUniversity, P.O. Box14425, Melbourne, Victoria, 8001,

Australia

bOperations & Supply Chain Management Research Group, Universidad de La Sabana, Campus del Puente del Com´

un,

km 7 Autopista Norte de Bogot´

a D.C., Ch´

ıa (Cundinamarca), Colombia

cGrupo de Investigaci´

on en Sistemas Log´

ısticos, Faculty of Engineering, Universidad de La Sabana, Campus del Puente del

Com´

un, km 7 Autopista Norte de Bogot´

a D.C., Ch´

ıa (Cundinamarca), Colombia

E-mail: carlos.vegamejia@live.vu.edu.au [Vega-Mej´

ıa]; jairo.montoya@unisabana.edu.co[Montoya-Torres];

sardar.islam@vu.edu.au [Islam]

Received 11 August2016; received in revised form 25 May 2018; accepted 5 June 2018

Abstract

The vehicle routing problemwith loading constraints (VRPLC) is related to real-life transportation problems

and integrates twoof the most important activities in distribution logistics: packing of items inside vehicles and

planning of delivery routes.In spite of its relevance, literature on VRPLCs is still limited. The majority of the

solution approaches have concentrated on heuristic solution methods, and few have presented mathematical

optimization models to help characterize the problem. Furthermore, few studies have considered several

practical loading and routing constraints that could be used to approximate the problem toward more

realistic situations. To help fill this gap in the literature, this article extends an existing VRPLC optimization

model to a nonlinear optimization model that considers weight-bearing strength of three-dimensional items,

vehicle weight capacity, weight distribution inside vehicles, delivery time windows, and a balanced fleet of

vehicles. The model is solved by applying a simple procedure that isolates the nonlinearity of the model.

Computational experiments show that the new proposed model gives a more streamlined formulation than

the model it extended on, and that the addition of practical loading constraints can improve the solutions of

the original model by reducing the measure of tardiness due to latedeliveries and by producing cargo patterns

with better weight distribution.

Keywords: vehicleloading problem with loading constraints; nonlinear mixed integer program; weight-bearing strength;

weight capacity; weight distribution; time windows; balanced vehicles

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.

C. A. Vega-Mej´

ıa et al. / Intl. Trans. in Op. Res. 26 (2019) 794–835 795

1. Introduction

The packing of items in a vehicle and the subsequent delivery route planning are two of the

most important operations in distribution management (Ruan et al., 2013). The simultaneous

determination of both the optimal routes and packing patterns of vehicles can be carried out by

modeling and solving a problem known as the vehicle routing problem with loading constraints

(VRPLC) (Zachariadis et al., 2013), which is a combination of two well-known problems: the

container loading problem (CLP) and the vehicle routing problem (VRP) (Iori and Martello, 2010).

The problems that comprise the VRPLC (VRP and CLP) have been intensively studied in the

past, as can be concluded from the analyses of the review works by Bortfeldt and W¨

ascher (2013)

and Lin et al. (2014), but which were often studied individually. However, focusing on individual

subproblems may neglect structural dependencies betweenthe two distribution operations and lead

to suboptimal solutions (Schmid et al., 2013), or worse, to unfeasible solutions when looking at the

integrated problem (Junqueira et al., 2013).

In spite of the relevance and connection to real transportation situations of VRPLCs, literature

on the topic is still limited (Ruan et al., 2013). This could also be supported by the fact that research

in VRPLCs is “fairly” recent. For instance, one of the first studies to address the VRPLC is that of

Gendreau et al. (2006), in which the authors considered severaloperational considerations (e.g., item

fragility, vertical load stability, and multidropsituations). Given that VRPLCs are NP-hard (Iori and

Martello, 2010), the majority of the solution approaches have concentrated on heuristic methods,

and not much attention has been directed toward mathematical models to characterize the problem,

which in turn, could aid in the design of alternative solution procedures. The objectiveof this article

is, therefore, to present an optimization model for the VRPLC for the transportation of three-

dimensional (3D) items, including several practicalloading and routing constraints. This model will

be aimed at covering some of the gaps when dealing with the mathematical representation of the

VRPLC, and atthe same time extending previously presented models. By including practical loading

constraints as defined in the work by Bischoffand Ratcliff (1995) that havenot been simultaneously

considered before (i.e., container weight limit, weight-bearing strength, weight distribution), and

additional routing conditions (i.e., time windows, balanced vehicle fleet), it is expected that this

new model would serve as a more precise approximation of real life situations in distribution

operations.

The remainder of this article is organized as follows. Section 2 provides a brief description

of some optimization models proposed for different versions of the VRPLC. Section 3 presents

the proposed nonlinear multiobjective model to solve the VRPLC with the mentioned practi-

cal loading and routing constraints. Section 4 presents the methodology employed to solve some

of the tested instances and to compare the results of the models. Section 5 presents the results

obtained for the model by means of a simple solution procedure, considering some problem

instances available in the literature. Finally, Section 6 provides some concluding remarks and

proposes some of the possible research directions for continuing and extending the proposed

model.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies

796 C. A. Vega-Mej´

ıa et al. / Intl. Trans. in Op. Res. 26 (2019) 794–835

2. Background

2.1. Previous studies

In spite of the variety of mathematical models available for VRP (Lin et al., 2014), and the ac-

knowledgment that models for CLP are scarce (Bortfeldt and W¨

ascher, 2013), the development of

mathematical models to aid the characterization of the VRPLC has not been extensively explored,

thus existing models are still limited in number. Instead, efforts have been directed toward the

development of heuristic methods to solve the problem, of which Junqueira and Morabito (2015)

presented a review of algorithms and solution strategies commonly employed. However, in this

section, we part from the perspective of heuristic approaches and focus on some of the existing

mathematical models for VRPLCs. These are presented briefly to give a general notion of what is

currently available in the literature on the VRPLC. These studies considered that all vehiclesdepart

from a single central depot, and either considered the packing of 2D or 3D objects of different

sizes (i.e., heterogeneous cargo), depending on the capacity of the items to bear weight on top of

them. From the perspective of packing problems, dealing with 2D objects could be referred to as

the pallet loading problem (PLP), while dealing with 3D items can be regarded as the CLP. A

formal classification of these packing problems can also be perfor med by considering the typology

proposed by W¨

ascher et al. (2007). According to this typology, these problems could be categorized

as 2D or 3D single stock size cutting stock problem or single bin size bin packing problem. When

considering 3D items, constraints to define stability, weight-bearing strength, and fragility of items

can be introduced to give a representation closer to reality. The 2D case has no need for these

constraints, since it is assumed that no item can be placed on top of another. This might appear as a

trivial difference when addressing VRPLCs, but the fact is that solving the 3D case is more difficult

than the 2D version of the problem (Lacomme et al., 2013).

This does not mean that all existing studies that combined routing and packing decisions deal

exclusively with 2D or 3D items. Some recent studies considered that the containers of the vehicles

have multiple stacks or slots in which the items fit perfectly, and without overlapping with other

items (e.g., Cˆ

ot´

e et al., 2012; Iori and Riera-Ledesma, 2015; Veenstra et al., 2017). Studies such

as these could be referred to as 1D VRPLCs or special cases of capacitated VRPs. Regardless, the

use of 1D items clearly reduces the complexity of the problem, but ultimately fails to consider the

impact of the geometric attributes of the items. Hence, our review will concentrate on 2D and 3D

versions of the VRPLC.

Regarding the 2D approaches, Iori et al. (2007) proposed a linear program (LP) to minimize the

distribution costs of a VRPLC, considering a fleet of identical vehicles (i.e., homogeneous vehicles).

As practical constraints, Iori et al. (2007) considered the weight limit of the container and “last

in–first out” (LIFO) conditions. The latter established that the items should be stored inside the

vehicle container in the reverse order of the delivery route in order to ease the unloading of items

from the vehicle at each stop, thus preventing the need to rearrange the cargo pattern inside the

container. The model was solved by relaxing the subtour elimination constraints of the routing

problem, which were only applied if a generated delivery route contained subtours. Subsequently,

the loading arrangements were validated for each route. However, the model by Iori et al. (2007)

does not present the loading constraints explicitly and limits its inclusion to the definition of clients’

sets that shorten the formulation. This summarized version of the model may impose additional

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies