INTEGRATED MATHEMATICAL MODEL BASED ON A HEURISTIC METHOD FOR
LOADING AND ROUTING OF VEHICLES: APPLICATION IN A TOBACCO COMPANY
Jorge Israel Frómeta
Moya
University of Oriente (UO), Cuba
E-mail: jorgef@uo.edu.cu
Daniel René Tasé
Velázquez
Methodist University of Piracicaba (UNIMEP),
Brazil
E-mail: dtasev88@gmail.com
Lorena Hernández
Mastrapa
Methodist University of Piracicaba (UNIMEP),
Brazil
E-mail: lorenahmastrapa@gmail.com
Yosvany Orlando Lao
León
University of Holguín (UHO), Cuba
E-mail: ylaol1986@gmail.com
Submission: 12/18/2019
Accept: 01/07/2020
ABSTRACT
The
vehicle-routing problem (VRP) combined with freight-loading problem is a
complex and relatively recent issue studied by the scientific literature. This
paper presents the formulation of a mathematical model and a procedure to solve
this problem in a Cuban tobacco company aiming to determine the quantity of
merchandise to be loaded on vehicles and the best route to be taken. For this
purpose, a decomposition’s heuristic method was used and it was integrated with
multiobjective programming by-goals and mixed binary quadratic programming.
This approach allowed simplifying the problem and offering a satisfactory
solution based on the demand fulfillment, the vehicles’ rational use and for
searching the local optimums of the traffic load indicator. The model was
tested in a case study and its feasibility evaluated based on a real
operational situation in a tobacco company. Although the results of the
application of the developed model does not imply reaching the optimal solution
to the problem studied, it represents an opportunity for company’s performance
improvement and it could be adapted and applied to other institutions dedicated
to the same activities.
Keywords: Vehicle-routing problem; Freight-loading problem; Heuristic methods; Goals-based programming; Quadratic programming
1.
INTRODUCTION
The vehicle-routing problem (VRP) has been extensively investigated over more than 50 years, from the approach of the “Traveling Salesman Problem” (TSP) (DANTZIG et al., 1954). The VRP is an important issue and recent studies have being developed. Smiti et al. (2020) studied the Cumulative Capable Vehicle Routing Problem (CCVRP), that is a relatively new version of the classic CVRP and is equivalent to a capacity constrained itinerant repairer problem and a homogeneous vehicle fleet, which aims to minimize the total uptime arrival to customers.
In
previous literature review (MASTRAPA et al., 2018a), it was identified that in
cases of emergency (humanitarian logistics), the VRP is mostly focused on
minimizing the sum of arrival times. One the biggest challenge is responding to
the demand (any kind) with minimal operating costs in addition to social costs,
as in humanitarian logistics the main goal is to provide the highest service
level in the shortest time possible, which often require very high operating
and social costs.
However,
the study of the approach that integrates the VRP with vehicles freight loading
is more recent (BORTFELDT;
WÄSCHER, 2013; IORI; MARTELLO, 2016). The
objective of this approach aims to find the best vehicle routing programming,
given the constraints that impose the limited capacity of the vehicles
regarding the merchandise to be loaded. In these cases, the tools contemplated
within the Operational Research discipline have been fundamental, as part of
the mathematical modeling of these problems for their solution (MEDINA et al. 2011).
Most
of the cases that integrate these two approaches belongs to the kind of
problems with solutions that present strongly undetermined polynomial time
(strongly NP-hard), so they are a challenge for achieving an optimal solution (IORI; MARTELLO, 2016).
This is the case of the VRP, which is well-known as an NP-hard problem (PIQUERAS, 2002; LÜER et al., 2009; MEDINA et al.
2011; CHOWMALI; SUKTO,
2020),
and it is a famous problem in operations research and combinatorial
optimization (CHOKANAT et al., 2019; WICHAPA; KHOKHAJAIKIAT, 2018). The
vehicles freight distribution problem with loading constraints is also considered as NP-hard
problem (PACE et
al., 2015). That is why it is not feasible to search for
exact mathematical methods to solve these problems, although the use of such
methods is not ruled out (IORI; MARTELLO, 2016).
Some
alternatives were proposed for solving these combined problems. One of them
includes the approach of Tarantilis et al. (2009). They used up to six
heuristics to solve the VPR with Simultaneous Pick-ups and Deliveries and
Two-Dimensional Loading Constraints (2L-SPD), primarily to reduce the
computational cost involved in this kind of complex mathematical models, and
find the optimal solutions in reasonable times. However, the methodology used
did not allow a deeper study of the operational objectives related to a problem
of this type, restricting the modeling to a single objective for this approach,
due to its multidimensional nature, it could be more flexible.
Fuellerer
et al. (2009) used the ant colony metaheuristics method for solving a Logistics
distribution problem classified as Vehicle Routing Problem and Two-Dimensional
Loading Constraints (2L-VRP). These authors demonstrated that the use of this
technique allows the successful combination of two approaches with completely
different measurement criteria, being superior to other algorithms studied (IORI; MARTELLO, 2016).
However, the methodology used lacks a more targeted approach to the
decision-making process, perhaps due to the very nature and complexity of the
metaheuristic method used.
Duhamel
et al (2010) made another interesting proposal as they used heuristics
decomposition for routing as well as metaheuristics for designing a
set of trips minimizing the total transportation cost with a homogenous fleet of
vehicles based on a depot node, as a solution of a Capacitated Vehicle Routing
Problem and Two-Dimensional Loading
Constraints (2L-CVRP). These authors demonstrated that the use of this
approach implies a high efficiency for solving this kind of problems, and
presents a better computational performance compared to other algorithms
compared in their research. However, the methodology used lacks a completely
comprehensive approach to a problem of a composite nature, giving greater
attention on solving the CVRP and Two-Dimensional Loading Problem in a
separately manner, rather than in its integrated configuration, and the
approaches that emerge from that interrelation.
Corstjens et al. (2020) propose a statistical methodology to understand the performance of an heuristic algorithm to investigate the correlations between algorithm performance and algorithm parameters and correlations between the latter and the instance characteristics of the problem. They see this as a next step in experimental research on combinatorial optimization problems to gain a deeper understanding and insight into the effects of heuristic parameters and components on algorithm performance. The methodology is able to identify which algorithm parameters significantly affect the solution quality of a heuristic method and how the characteristics of the problem instance influence these effects. However, the current methodology considers single-goal optimization, but optimization problems, such as vehicle routing, typically consider multiple objectives.
Mastrapa (2017) and Mastrapa et al. (2018b) in their study addresses the Problem of Design of Urban Public Transport Networks (PDRTPU). They focused on the improvement of a heuristic algorithm based on minimum path methods aiming to obtain a solution that meets the users demand, minimizing the number of transshipments, with a significantly smaller number of lines than the one found in the original application of Aquino (1980).
Chowmali and Sukto (2020) investigated a solution method for the cluster-based multi-compartment vehicle routing problem (MCVRP) in which a variant of FJA (Fisher and Jaikumar algorithm) was considered to cluster the nodes, and the TSP model was employed to find the ideal routes of individual vehicles. The numerical results showed the effectiveness of the proposed heuristic. They recomended as further research, the application of the proposed heuristic to be tested with more cases of MCVRP to further increase the validity of the search results.
Tobacco
companies in the eastern region of Cuba find vehicular routing combined with
the freight loading among their most pressing problems in their logistics
management. Currently, a company in that branch is looking forward a new way to
improve the physical distribution of their merchandise, specifically, physical
distribution of raw material; among the various problems they have had, it is
included:
•
Failure to meet delivery
deadlines of raw material: There has been a production delay of hand-twisted tobacco due to insufficient
delivery of raw material to the Production Base, despite being stocked in the
Company warehouses;
•
Absence of a
methodological planning tool for physical distribution: The collaborator in
charge of the physical distribution planning process does not use methodological tools (computational software, mathematical
algorithms, etc.), but instead performs it empirically, without taking full
account about aspects such as the travel distance, the vehicle capacity
constraints, freight-loading and unloading volume, etc.
Therefore,
the aim of this paper is to propose an integrated mathematical model for
freight loading and vehicle routing as a tool to improve the process of
physical distribution of raw materials in a Cuban tobacco company. The proposed
methodology in this paper based on a heuristic algorithm can be framed within
the "tailored algorithms" classification, as it is designed for a
very specific situation. This gives it the advantage of greater flexibility in
modeling the characteristics of a problem that are not incorporated in the
theoretical schemes of the reviewed literature, such as the use of the load
traffic indicator for objectives modeling; or consideration in the freight sub
problem of both volume and weight restrictions.
In
addition, regarding the other approaches analyzed in the literature, the
algorithm configured for the method proposed have a lower focus on the
computational cost of the proposal and greater focus on the decision-making
process within the problem described. This presents an advantage in practical
terms for implementation and development of the proposal over others in
literature, for specific problems such as the studied in this paper.
This work is organized in fourth sections. The introduction, which contextualize and presents the paper research interest and main objective; the methodology is discussed in the next section; results and discussion, as the third one, includes the structured model flow and the procedure configured, main data used and main results on the research context; and final considerations as conclusions are settled at the last one.
2.
METHODOLOGY
The
main stages for the implementation of operational research principles for the
resolution of a problem can be summarized as follow (HILLIER; LIEBERMAN, 2004;
ORTIZ-TRIANA; CAICEDO-ROLÓN, 2014): (i)
the problem definition; (ii) the model configuration; (iii) the model’s
solution; (iv) the model’s validation, and; (v) the implementation of the
solution.
In
this paper is used this procedure, specifically the first four stages, as a
methodological guide in order to fulfill the objective proposed. For
configuring the model, a heuristic method of decomposition of the problem with
cascade solution is used, which is based on the principle “divide and conquer”.
This principle allows fragmenting the problem into smaller ones, so, when
solving them all, a solution is obtained for the global problem (PIQUERAS, 2002).
The
solution of some sub-problems constitutes relevant data of the following ones.
This approach is combined with multi-objective programming by-goals for
vehicles freight loading and with an exact method of optimization named mixed binary quadratic programming
of vehicle routes by stages, as well as, linking algorithms between the
different stages as the problem is divided.
The
problem of mixed binary quadratic programming modeled according to its standard
form contains a quadratic objective function and linear constraints (NGUYEN et al., 2016).
The traffic load indicator is used as a solution criteria, which is “the
magnitude of the work in the freight’s transport combining the freight and the
distance which the products and goods are transported” (ONEI, 2015). Although
this is one of the most difficult problems in combinatorial optimization,
usually with solutions in undetermined polynomial time (NP-hard) (BURKARD et al., 2012),
some cases are relatively simple (ADAMS; WADDELL, 2014; LAURENT; SEMINAROTI, 2015).
The case study of this paper is one of them.
3. RESULTS AND DISCUSSIONS
In this section are presented the results obtained after the
implementation of the four stages defined in previous section for solving the
problem studied.
Stage I. Problem’s
definition
The
problem is defined as follow: Insufficiencies of the physical distribution
of raw materials process in a tobacco company that affect the efficiency and
effectiveness of the operational (production) process.
The
precepts that serve as the basis for the mathematical model configuration were
established as follows:
•
There is only one origin,
with availability of the products demanded by the destinations, this
availability is known at all times;
•
There are destinations
whose demand for goods is known;
•
There are vehicles (one
fleet), heterogeneous, limited and with constrained capacity;
•
There are no established priorities
between destinations or between goods;
•
The capacities of the
vehicles are known based on the goods’ characteristics;
•
Within the cost system,
the unit transportation costs (variable or fixed) are not identified, and they
are assumed proportional to the distance traveled, and independent of the type
of vehicle or destination;
•
There are no time
constraints;
•
It is considered that in
all destinations the merchandise will be accepted (no returns are
contemplated).
Stage II. Mathematical
model configuration
The
formulated mathematical model and the procedure for solving the problems
studied imply the development and application of a heuristic method of
decomposition. The flow chart that summarizes the algorithm that supports the
model is shown in Figure 1.
The
following guidelines were settled for configuring the mathematical model:
Model subscripts definition
Stages (n): Ordinal identification
of the subproblems sequence in chronological order about the freight to be
loaded and distributed by the vehicles, and the programming of each vehicle’s
visit to the destinations as part of the distribution’s vehicular routing (n =
1,2, ..., N).
i: Nominal
identification of the vehicles available for distribution (i = 1,2,…, I).
j: Nominal
identification of destinations with demand for goods (j = 1,2,…, J).
k: Nominal
identification of the goods to be distributed (k = 1,2, ..., K).
Model Parameters
: Availability of merchandise k in the warehouse (origin) at the
beginning of the problem.
: Demand for merchandise k at destination j at the beginning of the problem.
: Capacity coefficient of the
merchandise k in the vehicle i regardless of the stage in which it is
located.
: Distance traveled by the vehicle i to the destination j.
: Weight of each unit of merchandise
k expressed in kilograms (kg).
: Physical position of the
destinations within the independent model of the Stage (1, 2…, P)/
.
: Physical position of the vehicle i in Stage n within the model (0, 1, 2…, P)/
0 = physical position of the warehouse.
Definition of model
decision variables
: Quantity of merchandise k to be loaded on vehicle i in Stage (n).
: Quantity of merchandise k to be transported on the vehicle i to unload at destination j in Stage (n).
: Binary variables that model
whether or not the destination j is
visited by the vehicle i (0 = not
visited; 1 = visited) in Stage (n)
Figure 1: Model
and procedure stages for freight planning and vehicular routing
Planning of the first
freight load on the vehicles (submodel of multiobjective programming by-goals)
- Stage (n=1)
Taking into account the
characteristics of this first problem based on the structure given by which the
model is decomposed, this sub-model makes use of the standard formulation of
multi-objective programming by goals. The strict total demand fulfillment of
the destinations for each merchandise to be loaded on the vehicles constitutes
the modeled goals. This is because differentiating cost or performance criteria
between vehicles are not available.
Step 1. Definition of
submodel parameters
: Availability of merchandise k in the warehouse (origin) in Stage (n
= 1).
(1)
: Demand for merchandise k at destination j in Stage (n = 1).
(2)
: Capacity coefficient of the
merchandise k in the vehicle i regardless of the Stage in which it is
located.
Step 2. Definition of
submodel variables
: Decision variables that reflect the
quantity of merchandise k to be
loaded on the vehicle i in Stage
(n=1).
: Underachievement variables or negative deviation that expresses the
breach of the goals regarding the demand of the merchandise k in the destinations determined for the
Stage (n=1).
: Overachievement variables or positive deviation that expresses the
over-compliance of the goals regarding the demand of the merchandise k in the destinations determined for the
Stage (n=1).
Step 3. Formulation of
the mathematical submodel
(3)
(4)
(5)
(6)
(7)
The objective function (OF) represented by Eq. 3 minimizes positive and
negative deviations, which will result in strict demand satisfaction. Eq. 4
models the restrictions that guarantee in order to load any quantity of
merchandise into vehicles it must be available in the warehouse. The
restriction formulated in Eq. 5 expresses that vehicles cannot be loaded over
its capacity. These restrictions will depend on the volumetric capacity of the
vehicles and the freight dimensions. Eq. 6 constitutes the goal, modeling the
possible deviations of the freight volume on vehicles regarding the total
demand. Eq. 7 express the restrictions of non-negativity of both the decision
variables and the variables of underachievement and overachievement of the
goals.
Step 4. Resolution of
the mathematical submodel
The formulated mathematical model is solved.
Programming of first
visit of vehicles to destinations for freight distribution (mixed binary
quadratic programming submodel) - Stage (n=2)
In this stage, the first visit of vehicles fleet to the destinations is
scheduled as part of the routing to distribute the previously loaded freight.
This link between Stages already raised previously, favors that the results of
the previous Stage constitute parameters of the present.
Step 1. Definition of
submodel parameters
: Demand for merchandise k at destination j in Stage (n=2).
Demand for merchandise k at destination j in
Stage (n=2) is the same that the demand at the beginning of the problem
(8)
: Quantity of the merchandise k planned to be loaded in the vehicle i in Stage (n=2).
Quantity of merchandise k planned to be loaded on vehicle i in Stage (n=2) is the same that the quantity at the beginning of
the problem (9)
: Distance traveled by the vehicle i from the physical position of the
Warehouse (p=0) to destination j.
Step 2. Definition of
submodel decision variables
: Quantity of merchandise k to be transported in the vehicle i for unloading at destination j in the Stage (n=2).
: Binary variables that model
whether it is decided to visit or not the destination j by the vehicle i (0 =
if not visited; 1 = if visited) in Stage (n=2).
Step 3. Formulation of
the mathematical submodel
(10)
(11)
(12)
(13)
(14)
(15)
The OF in Eq. 10, links the binary variables with the quantity of
merchandise to be unloaded on a destination in a directly proportional way, and
inversely proportional with the distance that it is from the origin, which
means that it is sought to maximize freight traffic generated by the routing
process. The absence of relevant information to apply reliable criteria in
terms of economics, such as, transportation costs, has an alternative by using
the traffic load indicator compared to not presenting any.
The restrictions represented by Eq. 11 aims to not exceeding the demand
for each merchandise in each destination. Eq. 12 models the restrictions
implying that in each destination, a quantity of the merchandise is unloaded
from each vehicle being less than or equal to the available by the vehicle
capacity. Eq. 13 is responsible for modeling that each vehicle can only visit
one destination, as defined by the Stage. The Eq. 14 represent the decision
variables constraint of non-negativity, and the Eq. 15 the binary constraint
for the other variables.
Step 4. Resolution of
the mathematical submodel
The formulated mathematical model is solved.
Step 5. Transition
algorithm between Stages
To determine the transition between submodels within the stages of the
global mathematical model, the following Algorithm 1 (pseudocodes) is followed.
Algorithm 1: Determine
the transition between stages
|
If //// It implies that the entire
volume of merchandise distributed by the vehicles up to the stage (n=1+m) has
not completed the demand for all destinations, therefore the distribution
must continue. If //// It implies that the entire volume of merchandise distributed by
the vehicles up to the stage (n=1+m) is less than the total load they possess
at this stage, so they can continue distributing. Initiate Stage (n=2+m): New programming of vehicle visits to
destinations for distribution. Else Initiate Stage (n=2+m): New planning of freight loading on vehicles. EndIf Else End of the procedure EndIf EndAlgorithm |
Regarding the transition algorithm between Stages that is applied, each
Stage (n=2+m) can generate two types of submodels until the solution for
general mathematical model is obtained. In this case, m is a positive integer variable beginning in one (1) that indicate
the subsequent stages after the first two stages of loading and routing. These
stages are explained below.
New planning of the freight load on vehicles
(sub-model of multi-objective programming by-goals) - Stage (n=2+m)
Step 1. Definition of submodel parameters
:
Availability of merchandise k in the
warehouse (origin) in Stage (n=2+m).
:
Availability of merchandise k at the
warehouse (origin) in Stage (n=2+m) that is equal to the availability at the beginning of the problem minus the sum of all
deliveries of merchandise k in
previous stages (16)
: Demand
for merchandise k at destination j in Stage (n=2+m).
: Demand for
merchandise k at destination j in Stage (n=2+m) that is equal to the demand at the beginning of the problem minus
the sum of all deliveries of merchandise k
at destination j in previous stages (17)
: Capacity
coefficient of the merchandise k in
the vehicle i regardless of the stage
in which it is located.
Step 2. Definition of submodel variables
: Decision
variables that reflect the quantity of merchandise k to be loaded on the vehicle i
in Stage (n=2+m).
: Underachievement variables or negative
deviation that expresses the non-fulfillment of the goals regarding the demand
determined for the Stage (n=2+m).
: Overachievement variables or positive
deviation expressing the over-compliance of the goals regarding the demand
determined for the Stage (n=2+m).
Step 3. Formulation of
the mathematical submodel
The sub-model of multi-objective programming
by-goals is formulated according to the Eq. 3 to 7 for this stage.
Step 4. Resolution of
the mathematical submodel
The formulated mathematical model is solved.
New programming of
vehicle visits to destinations for distribution (mixed binary quadratic
programming submodel) - Stage (n=2+m)
Step 1. Definition of
submodel parameters
: Demand for merchandise k at
destination j in Stage (n=2+m).
: Demand for merchandise k at destination j in Stage (n=2+m) that is
equal to the demand at the beginning
of the problem minus the sum of all deliveries of merchandise k at the destination j in previous stages
(18)
: Quantity of merchandise k
loaded on the vehicle i for
distribution in Stage (n=2+m).
: Quantity of merchandise k loaded on vehicle i for distribution in Stage (n=2+m) that is equal to the demand at
the beginning of the problem minus the sum of all deliveries of merchandise k in previous stages (19)
: Physical position of vehicle i in Stage (n=2+m). The Algorithm 2
(pseudocode) is used for its determination.
Algorithm 2:
Determine the physical position of each vehicle in Stage (2+m): New programming
of vehicle visits to destinations for freight distribution.
|
///////// Performed for
each vehicle “i” at this stage and for each destination “j" at a
previous stage If Stage (1 + m) =
“Schedule of vehicles visit to destinations for distribution”, then //// It implies that in the previous stage the transportation
of goods was programmed Consult //// denotes whether the vehicle “i” was assigned or
not to transport goods to destination “j” in the previous stage If //// It implies that the vehicle “i” is at the
beginning of the current stage on the position of the destination “j” that
was assigned to transport goods in the previous stage] Else EndIf Else //// It implies that the vehicle returns to the
origin to be loaded EndAlgorithm |
: Distance to be traveled by the
vehicle i from its physical position
in this stage to the destination j.
Step 2. Definition of
submodel variables
: Decision variable that reflects
the quantity of the merchandise k to
be transported on the vehicle i for
unloading at destination j in the
Stage (n=2+m).
: Binary variable that models
whether or not to visit the destination j
by the vehicle i (0 = if not visited;
1 = if visited) in Stage (n=2+m).
Step 3. Formulation of
the mathematical submodel
The mixed binary quadratic programming submodel is formulated according
to Eq. (10) to (15), for the present stage.
Step 4. Resolution of
the mathematical submodel
The formulated mathematical model is solved.
Step 5. Transition
algorithm between Stages
Proceed as indicated in Algorithm 1.
Stage III. Model solution and validation. Case
study results
The feasibility of the
proposed model is evaluated through a case study based on a real situation on
the planning of raw material distribution in a Cuban tobacco company.
It is needed to transport four kinds of raw
materials to four destinations (Production and Exportation facilities). The
demand of each facilities (Destination 1, 2, 3 and Exportation 4), for a
period, is known as presented in Table 1.
Table 1: Demand for raw
material in destinations
|
|
Demand ( |
|||
|
Freight (k) Destination
(j) |
Raw material 1 (Gut) |
Raw material 2 (Leaves) |
Raw material 3 (Cloak) |
Raw material 4 (Cape) |
|
Destination 1 |
17
boxes |
8
bales |
11
bales |
16
boxes |
|
Destination 2 |
16
boxes |
8
bales |
11
bales |
15
boxes |
|
Destination 3 |
11
boxes |
5
bales |
7
bales |
11
boxes |
|
Exportation 4 |
2 boxes |
1
bale |
1
bale |
2
boxes |
|
Total demand |
46
boxes |
22
bales |
30
bales |
44
boxes |
The distribution is carried out from the raw material warehouse (Origin),
where there is a certain availability of the merchandise to be distributed. Each
raw material has a known unit weight according to their packaging as presented
in Table 2.
Table 2: Availability of goods
in the warehouse and their unit mass
|
Freight
(k) |
Availability
in Warehouse ( |
Unit
weight ( |
|
Raw material 1 (Gut) |
123 boxes |
25 kg/box |
|
Raw material 2 (Leaves) |
130 bales |
26,68 kg/bale |
|
Raw material 3 (Cloak) |
125 bales |
25 kg/bale |
|
Raw material 4 (Cape) |
121 bales |
21 kg/box |
Table 3 shows the load capacity of three vehicles that are available for transportation.
Only the volumetric capacity is taken into account depending on the packaging
of the merchandise to be loaded, since all products are classified as light
according to their consistency.
Table 3: Volumetric and load capacity
of vehicles
|
Vehicle (i) |
Volumetric
capacity (m3) |
Volumetric capacity
depending on the merchandise to be loaded ( |
|||
|
Raw material 1 (Gut) |
Raw material 2 (Leaves) |
Raw material 3 (Cloak) |
Raw material 4 (Cape) |
||
|
Truck Kamaz |
24 m³ |
95 boxes |
131 bales |
115 bales |
83 boxes |
|
Truck Howo |
20 m³ |
75 boxes |
109 bales |
96 bales |
69 boxes |
|
Truck KingLion |
10 m³ |
39 boxes |
54 bales |
48 bales |
34 boxes |
Table 4 shows the travel distances to distribute the freight, from the origin
to destinations, as well as the distances between destinations.
Table 4: Matrix of distances
|
Distances to be traveled by vehicles between
physical positions ( |
||||
|
Destinations
(j) Physical position (p) |
Destination 1 |
Destination 2 |
Destination 3 |
Exportation 4 |
|
Origin
(Warehouse) |
34.5 km |
51.6 km |
8.6 km |
4.1 km |
|
Destination
1 |
- |
20.8 km |
34.1 km |
33.8 km |
|
Destination
2 |
20.8 km |
- |
51.2 km |
52.8 km |
|
Destination
3 |
34.1 km |
51.2 km |
- |
11.5 km |
|
Exportation
facility 4 |
33.8 km |
52.8 km |
11.5 km |
- |
The generic VRP treated in the literature are classified in NP-hard, so
issues concerning to the type of software and hardware used to solve them is
very relevant due to the implications of the computational effort required. The
solution to the problem studied is simplified by means of the application of a
heuristic method, and it was possible to solve it using the WinQSB 2.0 software
on a Corei5 PC with 4 GB of RAM memory in a relatively short time. From the
application of the formulated mathematical model were obtained, with its
solution procedure, the following results.
Table 5 presents the quantity of freight loaded out on the vehicles in a
first stage. As shown (Table 5), was only needed to use two of the three
vehicles available to fully satisfy the demand of the destinations, which
implies that only one stage is necessary for planning the vehicle loading.
Table 5: First freight load to
be transported - Stage (n=1)
|
Vehicles |
Amount of freight to be loaded |
|||
|
Raw material 1 (Gut) |
Raw material 2 (Leaves) |
Raw material 3 (Cloak) |
Raw material 4
(Cape) |
|
|
Kamaz |
46 boxes |
22 bales |
30 bales |
6
boxes |
|
Howo |
- |
- |
- |
38
boxes |
As shown in Table 6, the first trip of the loaded fleet is scheduled as
part of the vehicle routing to distribute the freight. This allows meeting the
demand of the Destination 1, at the same time that it generates optimal traffic
load for this Stage, starting from the Warehouse that constitutes the origin.
Table 6: First trip of freight
distribution’s routing - Stage (n=2)
|
Vehicles |
Destination 1 Traffic load generated: 18.11 kg/km |
|||
|
Amount of freight to be distributed |
||||
|
Raw material 1 (Gut) |
Raw material 2 (Leaves) |
Raw material 3 (Cloak) |
Raw material 4 (Cape) |
|
|
Kamaz |
17 boxes |
8 bales |
11 bales |
4 boxes |
|
Howo |
- |
- |
- |
12 boxes |
The programming of the second trip of the loaded fleet is carried out in Stage
3, based on the fact that the vehicles have as initial physical position
(Destination 1) and the freight’s availability to be distributed has decreased
due to the first delivery, but it is adjusted to the destinations demand. This
satisfies the demand of Destination 2. Based on the conditions described above,
optimal traffic load is obtained for this Stage, as shown in Table 7.
Table 7. Second trip for
freight distribution’s routing - Stage (n=3)
|
Destination
visited: Destination 2 Traffic load generated: 28.92 kg/km |
||||
|
Vehicles |
Amount of freight to be distributed |
|||
|
Raw material 1 (Gut) |
Raw material 2 (Leaves) |
Raw material 3 (Cloak) |
Raw material 4 (Cape) |
|
|
Kamaz |
16 boxes |
8 bales |
11 bales |
- |
|
Howo |
- |
- |
- |
15 boxes |
The third trip
of the fleet is scheduled in Stage 4, having as initial physical position
(Origin) for both vehicles the Destination 2 already visited, with the
freight’s availability to be distributed adjusted according to the deliveries
already made. The destination that is obtained to be visited is Destination 3
in order to meet its demand and an optimal traffic load value for the
conditions of this stage is obtained. The results are shown in Table 8.
Table 8: Third trip for
freight distribution’s routing - Stage (n=4)
|
Destination
visited: Destination 3 Traffic load generated: 7.95 kg/km |
||||
|
Vehicles |
Amount of freight to be distributed |
|||
|
Raw material 1 (Gut) |
Raw material 2 (Leaves) |
Raw material 3 (Cloak) |
Raw material 4 (Cape) |
|
|
Kamaz |
11 boxes |
5 bales |
7 bales |
- |
|
Howo |
- |
- |
- |
11 boxes |
In Stage 5,
the visit to the last destination (Exportation facility) is scheduled,
satisfying its demand. Only a vehicle is used as shown in Table 9. This concludes
the procedure according to that is established in the algorithm.
Table 9: Four trip for freight
distribution’s routing - Stage (n=5)
|
Destination
visited: Exportation facility Traffic load generated: 12.49 kg/km |
||||
|
Vehicles |
Amount of freight to be distributed |
|||
|
Raw material 1 (Gut) |
Raw material 2 (Leaves) |
Raw material 3 (Cloak) |
Raw material 4 (Cape) |
|
|
Kamaz |
2 boxes |
1 bale |
1 bale |
2 boxes |
The mathematical
model configured for vehicle loading and routing is viable for the company
studied. The model allowed the scheduling of vehicles load and routing for a
specific case study (Tobacco Company) based on the reality of its operational
management. This model responds in its configuration to a heuristic method.
This method is also known as tailored algorithms, not being usable for others
problems (TELFAR, 1994).
With this model, a local optimum of the problem studied is defined at
each stage in which it is segmented. However, the solution obtained does not
guarantee the global optimum given the “myopia” of the proposed procedure,
which does not follow the principle of optimality typical of dynamic
programming that states that an optimal policy for the remaining stages is
independent of the policy adopted in previous stages (DELGADO et al., 2015).
The technique used avoids exploring all possible sequences by solving
the subproblems to facilitate the solution of the biggest one. This procedure
is justified based on the cost in time and other computational resources that
would imply developing a procedure to find an optimal solution that, on the
other hand, given the case studied in this paper, will not represent an
important benefit.
The formulated model used as an operational procedure for loading and
vehicular routing for distribution of raw materials in the tobacco company
(case study) has the potential to contribute for achieving a more rational use
of the available fleet. In the case study analyzed in this paper, only two of
the three vehicles available were used for distributing the freight, and in the
last stage, only one of them was needed. Likewise, the value of the total
traffic load indicator, obtained for vehicular routing is 5.27 kg/km traveled,
while they oscillate between 2.75 kg/km and 10 kg/km at each stage. These
values are higher than the average values that were reported by these vehicles
monthly, ranging between 1.27 kg/km and 1.59 kg/km.
4.
FINAL REMARKS
An
integrated heuristic mathematical model for freight loading and vehicle routing
was configured in this paper. The model was applied for evaluate the
characteristics of the physical distribution of raw materials process and its
feasibility was evaluated through a case study based on a real and timely
problem situation in a Cuban tobacco company concluding the following:
a)
The four stages developed
and applied in the case study presented high reliability on the study of a real
problem;
b)
The model results allowed
scheduling the freight loading and the vehicular routing with reliable
performance;
c)
The heuristic method used
is an interesting alternative to solve complex load and vehicle routing
problems, even if it does not involve reaching the optimal solution;
d)
The proposed mathematical
model, as part of the operational management of the merchandise distribution in
the company studied represents an opportunity for production processes
improvement;
e)
Despite dealing with
complex integrated problems, the proposed method is simple and easy to implement
and replicate in others manufacturing companies.
REFERENCES
ADAMS, W.; WADDELL, L. (2014) Linear programming insights into solvable
cases of the quadratic assignment problem. Discrete Optimization, v. 14, p. 46-60. http://doi.org/10.1016/j.disopt.2014.07.001
AQUINO, W. J. S. (1980) Uma abordagem do problema de definição de rede
interurbana de rotas de ônibus. Dissertação em opção ao título de mestre em
Engenharia de Produção. Coordenação do Programa de Pós-Graduação de Engenharia.
Universidade Federal do Rio de Janeiro, Rio de Janeiro, Outubro, p.1-88.
BORTFELDT, A.; WÄSCHER, G. (2013) Constraints in container loading–A
state-of-the-art review. European
Journal of Operational Research, v. 229, n. 1, p. 1-20. http://doi.org/10.1016/j.ejor.2012.12.006
BURKARD, R.; DELL'AMICO, M.; MARTELLO, S. (2012|) Assignment problems (Revised reprint). SIAM - Society of Industrial
and Applied Mathematics, 393 p., ISBN 978-1-611972-22-1.
CHOKANAT, P.; PITAKASO, R.; SETHANAN, K. (2019) Methodology to Solve a
Special Case of the Vehicle Routing Problem: A Case Study in the Raw Milk
Transportation System. AgriEngineering,
v. 1, n. 1, p. 75-93. http://doi.org/10.3390/agriengineering1010006
CHOWMALI, W.; SUKTO, S. (2020) A novel two-phase approach for solving
the multi-compartment vehicle routing problem with a heterogeneous fleet of
vehicles: a case study on fuel delivery. Decision
Science Letters, v. 9, n. 1, p. 77–90. http://doi.org/10.5267/j.dsl.2019.7.003
CORSTJENS,
J.; DEPAIRE, B.; CARIS, A.; SORENSEN, K. (2019) A multilevel evaluation method
for heuristics with an application to the VRPTW. International Transactions in Operational Research, v. 27, p.
168–196. http://doi.org/10.1111/itor.12631
DANTZIG, G. B.; FULKERSON, D. R.;
JOHNSON, S. M. (1954) Solution of a Large-Scale Traveling Salesman Problem. Operations Research,
n. 2, p. 393–410. http://doi.org/10.1287/opre.2.4.393
DELGADO, J. A. C.; AVALOS, L. C. M.; DELGADO, E.
R.; PUYCÁN, L. A. L. (2015) Optimización de programas matemáticos con
programación dinámica. Revista Ciencia & Desarrollo, n. 19, p. 77-83. http://doi.org/10.33326/26176033.2015.19.491
DUHAMEL, C.; LACOMME, P.; QUILLIOT, A.; TOUSSAINT, H. (2010) A
multi-start evolutionary local search for the two-dimensional loading
capacitated vehicle routing problem. Computers
& Operations Research, v. 38, n. 3, p. 617-640. http://doi.org/10.1016/j.cor.2010.08.017
FUELLERER, G.; DOERNER, K. F.; HARTL, R. F.; IORI, M. (2009) Ant colony
optimization for the two-dimensional loading vehicle routing problem. Computers & Operations Research, v.
36, n. 3, p. 655-673. http://doi.org/10.1016/j.cor.2007.10.021
HILLIER, F. S.; LIEBERMAN, G. J. (2004) Introduction to Operations Research. Ed. 8, McGraw-Hill, p. 1088.
ISBN 0-07-252744-7
IORI, M.; MARTELLO, S. (2016) An annotated bibliography of combined
routing and loading problems. Yugoslav
Journal of Operations Research, v. 23, n. 3, p. 311-326. http://doi.org/10.2298/YJOR130315032I
LAURENT, M.; SEMINAROTI, M. (2015) The quadratic assignment problem is
easy for Robinsonian matrices with Toeplitz structure. Operations Research Letters, v. 43, n. 1, p. 103-109. http://doi.org/10.1016/j.orl.2014.12.009
LÜER, A.; BENAVENTE, M.; BUSTOS, J.; VENEGAS, B. (2009) El problema de
rutas de vehículos: extensiones y métodos de resolución, estado del arte. Proceedings of 3er Encuentro
de Informática y Gestión (EIG 2009), Universidad de la Frontera, Temuco, Chile.
Available at: http://www.semanticscholar.org/paper/El-Problema-de-Rutas-de-Veh%C3%ADculos%3A-Extensiones-y-de-L%C3%BCer-Benavente/e47e71d4f7470d69dd987190286cfd48eeabae61
MASTRAPA,
L. H. (2017) Melhorias em um método
heurístico para a solução do Problema de Desenho de Rede de Transporte Público
Urbano. Dissertação de Mestrado-Departamento de Engenharia Industrial.
Pontifícia Universidade Católica do Rio de Janeiro, Rio de Janeiro, Agosto, p.
1-114. https://doi.org/10.17771/PUCRio.acad.31654
MASTRAPA, L. H.; LEAL, J. E.; ASSUMPÇÃO, M.
R. P. (2018b) Melhorias em um método heurístico para a solução do problema de
desenho de rede de transporte público urbano. In: XXXVIII Encontro Nacional de Engenharia de Produção ENEGEP 2018,
Maceió, Alagoas, Brasil. Available at: http://www.abepro.org.br/biblioteca/TN_WPG_263_509_36318.pdf
MASTRAPA, L. H.; VELÁZQUEZ, D. R. T.;
OLIVEIRA, E. D.; GENNARO, C. K.; BELEM, M. J. X. (2018a) Análise dos modelos
matemáticos para o transporte de ajuda humanitária em situações de desastres.
In: VIII Congresso Brasileiro de Engenharia
de Produção CONBREPRO 2018, Ponta Grossa, Paraná, Brasil. Available at: http://aprepro.org.br/conbrepro/2018/anais.php
MEDINA, L. B. R.; LA ROTTA, E. C. G.; CASTRO, J. A. O. (2011) Una revisión
al estado del arte del problema de ruteo de vehículos: Evolución histórica y
métodos de solución. Ingeniería, v.
16, n. 2, p. 35-55. Available at: http://dialnet.unirioja.es/servlet/articulo?codigo=4797255
NGUYEN, B.; MORELL, C.; DE BAETS, B. (2016) Un método eficiente para
resolver un problema de programación cuadrática derivado del aprendizaje de
funciones de distancia. Investigación
Operacional, v. 37, n. 2, p. 124-136. Available at: http://go.gale.com/ps/anonymous?id=GALE%7CA458262039&sid=googleScholar&v=2.1&it=r&linkaccess=abs&issn=02574306&p=AONE&sw=w
ONEI - Oficina Nacional de Estadística e Información (2015) Anuario Estadístico de Cuba. La Habana,
Cuba, Edición 2016.
ORTIZ-TRIANA, V. K.; CAICEDO-ROLÓN, Á. J. (2014) Programación óptima de la producción
en una pequeña empresa de calzado - en Colombia. Ingeniería Industrial, v. 35, n. 2, p. 114-130. Available
at: http://scielo.sld.cu/scielo.php?script=sci_arttext&pid=S1815-59362014000200002
PACE, S.; TURKY, A.; MOSER, I.; ALETI, A. (2015) Distributing fibre
boards: a practical application of the heterogeneous fleet vehicle routing
problem with time windows and three-dimensional loading constraints. Procedia Computer Science, v. 51, p. 2257-2266. http://doi.org/10.1016/j.procs.2015.05.382
PIQUERAS, V. Y. (2002) Optimización heurística económica aplicada a las
redes de transporte del tipo VRPTW. [Doctoral Thesis, p. 351], Universidad
Politécnica de Valencia, 2002. http://doi.org/10.4995/Thesis/10251/2664
SMITI, M.; DHIAF, M. M.; JARBOUI, B.; HANAFI, S. (2020). Skewed general
variable neighborhood search for the cumulative capacitated vehicle routing
problem. International Transactions in
Operational Research, n. 27, p. 651–664. http://doi.org/10.1111/itor.12513
TARANTILIS, C. D.; ZACHARIADIS, E. E.; KIRANOUDIS, C. T. (2009) A hybrid
metaheuristic algorithm for the integrated vehicle routing and
three-dimensional container-loading problem. IEEE Transactions on Intelligent Transportation Systems, v. 10, n.
2, p. 255-271. http://doi.org/10.1109/TITS.2009.2020187
TELFAR, G. (1994) Generally
Applicable Heuristics for Global Optimization: An Investigation of
Algorithm Performance for the Euclidean Traveling Salesman Problem. Reading
paper - Master of Science in Statistics and Operations Research, p. 150,
Victoria University of Wellington.
WICHAPA,
N.; KHOKHAJAIKIAT, P. (2018) Solving a multi-objective location routing problem
for infectious waste disposal using hybrid goal programming and hybrid genetic
algorithm. International Journal of
Industrial Engineering Computations, v. 9, n. 1, p. 75-98. http://doi.org/10.5267/j.ijiec.2017.4.003