Computational Intelligence - November 2014 - 20
II. Literature Review
y
Back
Ht
O
Front
Wt
Rear Door
x
Lt
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.
20
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 fixed cost of vehicles
and was first proposed by [4], the HFVRP-V only considers
the unit travel cost [5], and HFVRP-FV considers both the
fixed 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
fleet fixes 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 first 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
Computational Intelligence - November 2014 - Cover1
Computational Intelligence - November 2014 - Cover2
Computational Intelligence - November 2014 - 1
Computational Intelligence - November 2014 - 2
Computational Intelligence - November 2014 - 3
Computational Intelligence - November 2014 - 4
Computational Intelligence - November 2014 - 5
Computational Intelligence - November 2014 - 6
Computational Intelligence - November 2014 - 7
Computational Intelligence - November 2014 - 8
Computational Intelligence - November 2014 - 9
Computational Intelligence - November 2014 - 10
Computational Intelligence - November 2014 - 11
Computational Intelligence - November 2014 - 12
Computational Intelligence - November 2014 - 13
Computational Intelligence - November 2014 - 14
Computational Intelligence - November 2014 - 15
Computational Intelligence - November 2014 - 16
Computational Intelligence - November 2014 - 17
Computational Intelligence - November 2014 - 18
Computational Intelligence - November 2014 - 19
Computational Intelligence - November 2014 - 20
Computational Intelligence - November 2014 - 21
Computational Intelligence - November 2014 - 22
Computational Intelligence - November 2014 - 23
Computational Intelligence - November 2014 - 24
Computational Intelligence - November 2014 - 25
Computational Intelligence - November 2014 - 26
Computational Intelligence - November 2014 - 27
Computational Intelligence - November 2014 - 28
Computational Intelligence - November 2014 - 29
Computational Intelligence - November 2014 - 30
Computational Intelligence - November 2014 - 31
Computational Intelligence - November 2014 - 32
Computational Intelligence - November 2014 - 33
Computational Intelligence - November 2014 - 34
Computational Intelligence - November 2014 - 35
Computational Intelligence - November 2014 - 36
Computational Intelligence - November 2014 - 37
Computational Intelligence - November 2014 - 38
Computational Intelligence - November 2014 - 39
Computational Intelligence - November 2014 - 40
Computational Intelligence - November 2014 - 41
Computational Intelligence - November 2014 - 42
Computational Intelligence - November 2014 - 43
Computational Intelligence - November 2014 - 44
Computational Intelligence - November 2014 - 45
Computational Intelligence - November 2014 - 46
Computational Intelligence - November 2014 - 47
Computational Intelligence - November 2014 - 48
Computational Intelligence - November 2014 - 49
Computational Intelligence - November 2014 - 50
Computational Intelligence - November 2014 - 51
Computational Intelligence - November 2014 - 52
Computational Intelligence - November 2014 - 53
Computational Intelligence - November 2014 - 54
Computational Intelligence - November 2014 - 55
Computational Intelligence - November 2014 - 56
Computational Intelligence - November 2014 - 57
Computational Intelligence - November 2014 - 58
Computational Intelligence - November 2014 - 59
Computational Intelligence - November 2014 - 60
Computational Intelligence - November 2014 - 61
Computational Intelligence - November 2014 - 62
Computational Intelligence - November 2014 - 63
Computational Intelligence - November 2014 - 64
Computational Intelligence - November 2014 - 65
Computational Intelligence - November 2014 - 66
Computational Intelligence - November 2014 - 67
Computational Intelligence - November 2014 - 68
Computational Intelligence - November 2014 - 69
Computational Intelligence - November 2014 - 70
Computational Intelligence - November 2014 - 71
Computational Intelligence - November 2014 - 72
Computational Intelligence - November 2014 - 73
Computational Intelligence - November 2014 - 74
Computational Intelligence - November 2014 - 75
Computational Intelligence - November 2014 - 76
Computational Intelligence - November 2014 - 77
Computational Intelligence - November 2014 - 78
Computational Intelligence - November 2014 - 79
Computational Intelligence - November 2014 - 80
Computational Intelligence - November 2014 - Cover3
Computational Intelligence - November 2014 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com