Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem
Graphical abstract
Introduction
The capacitated vehicle routing problem (CVRP) was introduced by Dantzig and Ramser [1] and is known an NP-hard problem [2], in which an instance with a large number of customers might not be solved in a reasonable amount of computing time using exact solution methods. Hence, numerous studies have tried to develop heuristic methods to obtain a near optimal solution even though not necessarily guaranteeing an optimal solution. Toth and Vigo [33] classified the heuristic into two major categories: classical heuristic and meta-heuristic.
Classical heuristics were developed mostly between 1960 and 1990, with early attempts to solve CVRP focusing on route construction, route improvement, and two-phase heuristic. These approaches tend to perform a relatively limited investigation of the search space, such as the classical heuristic being used to produce a near optimal solution within a reasonable computational time. The most famous heuristic for CVRP is probably the Clarke and Wright [3] savings algorithm [4], which was followed up by Mole and Jameson [5] who proposed sequential and concurrent route building methods that use a generalized version of that savings algorithm. The route construction heuristic typically starts from one feasible solution and moves to a more efficient solution through the interchange of arcs. Another well-known example of a construction heuristic is the insertion heuristic of Christofides [6]. Some famous heuristics in the route improvement category include the 2-opt, 3-opt, and Lin-Kernighan heuristics, whereas the route improvement heuristic iteratively advances a more feasible solution by replacing a set of arcs or nodes [7]. The sweep algorithm [8] and the Fisher and Jaikumar algorithm [9] are two-phase heuristics, in which the two-phase algorithm normally consists of a clustering phase and a routing phase.
Most research efforts in recent years on VRP have been devoted to developing various metaheuristic algorithms, because they allow for a less preferable solution and sometimes an infeasible move in the course of finding the best solution [10]. Therefore, a metaheuristic explores a much larger solution space compared to a classical heuristic and also offers the capability to get a better result compared to a classical heuristic. A typical implementation of a metaheuristic uses two main principles: local search (or single solution search) and population search. In local search methods, a neighborhood movement at each step from the current solution to another promising solution performs the exploration of the solution space. Simulated annealing (SA) and tabu search (TS) are two algorithms that adopt the local search principle. The implementation of SA for CVRP can be found in Osman [11] and Lin et al. [12], while the effective implementation of TS for CVRP is seen in Taillard [13], Gendreau et al. [14], Derigs and Kaiser [15], and Cordeau et al. [16]. Thereafter, several single solution-based approaches were also proposed and provided promising results, including adaptive memory procedures [17], [18], [19], large neighborhood search [20], [21], active guided evolutionary strategies [22], and variable neighborhood search [7], [23]. For the second principle, the population-based search’s algorithm maintains a solution pool and efficiently creates a new solution by combining and replacing a solution in the solution pool. Some examples of these types of metaheuristics include genetic algorithms [24], [25], ant colony optimization [26], [27], [28], artificial bee colony algorithm [29], honey bees mating optimization [30], particle swarm optimization [31], and hybrid evolutionary search [32]. For a more detailed description, readers can refer to the extensive survey papers of Laporte et al. [4] and Toth and Vigo [33]
Cheng and Prayogo [34] presented a new metaheuristic, called Symbiotic Organisms Search (SOS), which is inspired from the interaction among organisms in an ecosystem and known as symbiotic interaction. This algorithm was initially proposed to solve continuous engineering optimization problems and offers an excellent result and a very promising performance when tested on complex continuous mathematical benchmark problems. Because the SOS algorithm is relatively new, its ability to find a global solution is very interesting and should be further explored and investigated and actually provides a successful result in solving continuous problem. However, it has yet to be tested for a discrete problem such as CVRP. To make SOS applicable to CVRP, a technique that transforms a continuous solution representation into a discrete solution representation is needed. Solution representation is defined as an encoded solution for each particle or candidate solution, while the method to transform it into the problem-specific solution is called a decoding method. In order to improve the performance of SOS, the interaction that defines the main principles of solution space exploration still has some space for research and experiment.
This paper employs SOS to solve CVRP and evaluates the performance of six proposed SOS versions, SOSCanonical, SOSBasic, SOSSR-1, SOSSR-2, ISOSSR-1, and ISOSSR-2, using classical benchmark instances. We adopt three solution representations. The first one is a general solution representation to transform a real-valued solution into a discrete-valued solution, denoted as basic solution representation. The other two are specific solution representations presented by Ai and Kachitvichyanukul [31], which are constructed with an original SOS framework that uses real-valued particle positions instead of a discrete-valued representation. The first solution representation is a commonly used decoding method that transforms real-valued representation into a discrete-valued one by sorting the values of the real-valued solution and taking the index as decoding result. The second solution representation, denoted as solution representation one (SR-1), proposes the basic idea of characterizing the solution as a priority matrix of customer nodes combined with a matrix of vehicle positions. The third solution representation, solution representation two (SR-2), expands the basic idea of SR-1 by accommodating vehicle position and coverage radius in the solution representation, and a local search strategy is then used to improve the solution quality of SOS. This study develops four versions of SOS. The first version represents the canonical version of SOS, SOSCanonical, which only adopts the basic solution representation without applying a local search strategy. The second version, SOSBasic, is the version of SOSCanonical with a local search strategy. The third and fourth versions apply SR-1 and SR-2 with a local search strategy, denoted as SOSSR-1 and SOSSR-2. Furthermore, two new interaction strategies, the so-called competition and amensalism, are developed. These two interaction strategies were implemented on the SOSSR-1 and SOSSR-2 versions, denoted as ISOSSR-1 and ISOSSR-2.
The paper is organized as follows. Section 2 describes the definition of CVRP. Section 3 gives a review of the basic SOS algorithm. Section 4 elaborates the proposed SOS for solving CVRP. Section 5 reports the computational experiment assessing the quality of the SOS algorithms, along with a comparative performance analysis. Finally, Section 6 offers conclusions and suggestions for future research.
Section snippets
Symbiotic organisms search
The SOS algorithm is a population-based evolutionary algorithm influenced by the relationship and interaction in-between living entities in the environment, which is known as a symbiotic relationship. Common symbiotic relationships found in nature are mutualism, commensalism, and parasitism. The advantage of the SOS algorithm compared to other metaheuristics is that the algorithm does not require a specific algorithm parameter, and it reportedly surpasses the performance of several classical
Capacitated vehicle routing problem
The capacitated vehicle routing problem can be defined as follows: the problem consists of determining a set of routes for a homogeneous fleet of m vehicles, so as to meet the demands of n nodes. Let G = (V,A) be a complete graph, where V = {0,….,n} is the vertex set and A = {(i, j):i ∊ V,i≠ j} is the edge set. Vertex i = 1,…., n corresponds to the customer node, and vertex 0 corresponds to the depot. Each customer must be assigned to exactly one vehicle and visited exactly once, whereupon at each
Application of SOS to CVRP
The basic SOS algorithm is capable of solving a continuous mathematical problem with great success [34], but the same condition is not applied for solving CVRP. To use the SOS algorithm for solving a discrete optimization problem, a method is needed to transform the solution representation from a continuous value to a discrete value. Therefore, we propose three solution representations, including a basic solution representation [36], [37] and the two solution representations proposed by Ai and
Computational experiments
The proposed SOS is implemented in Microsoft Visual C + + 2012 and executed on a computer with specifications of Intel i-7 at 3.4 GHz CPU and 16 GB RAM, running on a 64-bit platform under Windows 7 operating system. First, four versions of SOS, i.e. SOSCanonical, SOSBasic, SOSSR-1 and SOSSR-2, are tested on CVRP benchmark instances to understand their performance. Afterwards, SOSSR-1 and SOSSR-2 are applied to the same dataset as detailed in Ai and Kachitvichyanukul [31] in order to evaluate the
Conclusion and future research
In this paper we present a symbiotic organisms search heuristic for the capacitated vehicle routing problem. SOS is a new metaheuristic based on the natural symbiotic relationship of organisms in a natural environment. To solve discrete problems, we adopt the solution representations for PSO, including the basic solution representation and the solution representations SR-1 and SR-2 from Ai and Kachitvichyanukul [31]. This study utilizes these three types of solution representations and a local
Acknowledgement
The authors thank the editors and referees for their helpful comments and suggestions. This research was partially supported by the Ministry of Science and Technology of the Republic of China (Taiwan) under grant NSC 102-2221-E-011-082-MY3. This support is gratefully acknowledged.
References (51)
- et al.
Classical and modern heuristics for the vehicle routing problem
Int. Trans. Oper. Res.
(2000) - et al.
An efficient variable neighborhood search heuristic for very large scale vehicle routing problems
Comput. Oper. Res.
(2007) - et al.
Applying hybrid meta-heuristics for capacitated vehicle routing problem
Expert Syst. Appl.
(2009) - et al.
Applying the attribute based hill climber heuristic to the vehicle routing problem
Eur. J. Oper. Res.
(2007) Solving the vehicle routing problem with adaptive memory programming methodology
Comput. Oper. Res.
(2005)- et al.
A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem
Discrete Optim.
(2006) - et al.
A general heuristic for vehicle routing problems
Comput. Oper. Res.
(2007) - et al.
Active-guided evolution strategies for large-scale capacitated vehicle routing problems
Comput. Oper. Res.
(2007) - et al.
Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem
Expert Syst. Appl.
(2010) - et al.
A genetic algorithm for the vehicle routing problem
Comput. Oper. Res.
(2003)