Computational Intelligence - November 2014 - 20

II. Literature Review
y
Back

Ht
O
Front

Rear Door

z
Figure 1 The 3D coordinate system.

the solution space systematically. When all of the possible
moves of VNS cannot improve the solution, a diversification
procedure is invoked to adjust the search trajectory. We propose two diversification methods and each time one of the
methods is selected probabilistically according to its historical
performance. During the procedure, the program only
searches within the feasible solution space. A candidate solution is accepted as the new solution only when it is determined as feasible in terms of the loading constraints. To speed
up the process, two data structures are creatively used to
reduce the calls to the loading check, which is the most timeconsuming operator. The Trie data structure is used to record
the feasibility information of the routes already visited and
store the times checked by our loading heuristic to help control the computational effort spent on that route. The Fibonacci heap data structure is used to maintain all of the possible
moves of the current solution and the vehicle type assignments, which avoid calling the loading heuristic for unpromising moves. To show the effectiveness of our approach, the proposed AVNS is adapted and extensively tested on the
3L-CVRP and pure HFVRP instances. The results demonstrate that our algorithm outperforms all of the other methods
on the 3L-CVRP, by producing excellent results for all problem instances and even improving some best known results. In
addition, our method produces solutions that are quite close to
the optimal solutions for the HFVRP instances. Last but not
least, we generate many instances for the 3L-HFVRP and provide the results of our algorithm on these instances.
The remainder of this paper is organized as follows. The
next section provides an overview of the relevant literature.
Section III describes the 3L-HFVRP in detail. In Section IV,
the detailed operators of the proposed AVNS are presented.
The loading heuristic to produce the loading plan is discussed
in Section V. The results for the pure HFVRP, 3L-CVRP and
3L-HFVRP are reported in Section VI. Section VII concludes
the paper.

IEEE ComputatIonal IntEllIgEnCE magazInE | novEmbEr 2014

VRP has numerous variants [3]. One of the well studied variants is the HFVRP with an unlimited number of vehicles for
each vehicle type. This HFVRP can be seen as a special case of
the 3L-HFVRP, in which only the weight is considered when
loading freight into the vehicle. There are three variants of the
HFVRP: the HFVRP-F only considers ﬁxed cost of vehicles
and was ﬁrst proposed by [4], the HFVRP-V only considers
the unit travel cost [5], and HFVRP-FV considers both the
ﬁxed and travel costs [6]. Many algorithms have been reported
for this problem, such as tabu search (TS) [7], hybrid evolutionary local search [8], VNS [9], [10], genetic algorithm [11],
memetic algorithm [12], column generation approach [6], and
iterated local search combined with set partitioning formulation [13]. Another well-known variant with a heterogeneous
ﬂeet ﬁxes the number of vehicles of each type. Recently proposed algorithms include the record-to-record travel algorithm [14], multi-start adaptive memory programming [15],
TS [16], and hybrid population heuristic [17].
The loading component of the 3L-HFVRP is closely
related to the single container loading problem (SCLP) which
aims to load boxes into a container so as to maximize its volume utilization. The SCLP is a particularly difficult problem
and has attracted the attention of many researchers. Detailed
description of loading heuristics can be found in [18]-[21].
The routing and loading problems have been studied
widely but independently. The two problems have only been
recently combined. The proposed 3L-HFVRP becomes the
3L-CVRP when the vehicles are homogeneous. The
3L-CVRP was ﬁrst introduced by [22] and solved by invoking a TS to check the loading subproblem. A guided tabu
search (GTS) sharing the advances of TS and guided local
search was proposed and a bundle of loading heuristics was
used to examine the loading constraints by [23]. The savingbased ant colony optimization (ACO), which makes use of
two fast loading heuristics, was developed by [2]. This
method is different from others as it allows infeasible solutions during the search by penalizing violations. Recently, a
two-phase TS incorporating enhanced loading heuristics was
addressed by [24]. Another TS method using the tree search
for loading was reported in [25]. Both algorithms obtained
excellent results and improved several best known solutions.
A hybrid approach combining honey bee mating optimization for routing and six loading heuristics for the loading
aspect was introduced by [26]. In [27], the routing subproblem was solved by a greedy randomized adaptive search procedure combined with the evolutionary local search
(GRASP # ELS) algorithm. The loading component was
examined by relaxing it to a resource constrained project
scheduling problem. However, this method could only consider the 3D and orientation constraints, and additional constraints encountered frequently, such as fragility, stability, and
LIFO constraints, cannot be dealt with.
The 3L-CVRP generalizes the routing and loading problem 2L-CVRP which assumes that the items cannot be

Table of Contents for the Digital Edition of Computational Intelligence - November 2014