Elsevier

Applied Soft Computing

Volume 52, March 2017, Pages 657-672
Applied Soft Computing

Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem

https://doi.org/10.1016/j.asoc.2016.10.006Get rights and content

Highlights

  • A new metaheuristic, symbiotic organism search (SOS), is applied to the capacitated vehicle routing problem (CVRP).

  • Two solution representations, SR-1 and SR-2, are implemented and compared.

  • Two new interaction strategies, competition and amensalism, are proposed to improve SOS.

  • The performance of SOS is evaluated using two sets of classical benchmark problems.

  • The results indicate that the proposed SOS performs well in solving CVRP.

Abstract

This paper presents the symbiotic organisms search (SOS) heuristic for solving the capacitated vehicle routing problem (CVRP), which is a well-known discrete optimization problem. The objective of CVRP is to decide the routes for a set of vehicles to serve a set of demand points while minimizing the total routing cost. SOS is a simple and powerful metaheuristic that simulates the symbiotic interaction strategies adopted by an organism for surviving in an ecosystem. As SOS is originally developed for solving continuous optimization problems, we therefore apply two solution representations, SR-1 and SR-2, to transform SOS into an applicable solution approach for CVRP and then apply a local search strategy to improve the solution quality of SOS. The original SOS uses three interaction strategies, mutualism, commensalism, and parasitism, to improve a candidate solution. In this improved version, we propose two new interaction strategies, namely competition and amensalism. We develop six versions of SOS for solving CVRP. The first version, SOSCanonical, utilizes a commonly used continuous to discrete solution representation transformation procedure. The second version is an improvement of canonical SOS with a local search strategy, denoted as SOSBasic. The third and fourth versions use SR-1 and SR-2 with a local search strategy, denoted as SOSSR-1 and SOSSR-2. The fifth and sixth versions, denoted as ISOSSR-1 and ISOSSR-2, improve the implementation of SOSSR-1 and SOSSR-2 by adding the newly proposed competition and amensalism interaction strategies. The performances of SOSCanonical, SOSBasic, SOSSR-1, and SOSSR-2 are evaluated on two sets of benchmark problems. First, the results of the four versions of SOS are compared, showing that the preferable result was obtained from SOSSR-1 and SOSSR-2. The performances of SOSSR-1, SOSSR-2, ISOSSR-1, and ISOSSR-2 are then compared, presenting that ISOSSR-1 and ISOSSR-2 offer a better performance. Next, the ISOSSR-1 and ISOSSR-2 results are compared to the best-known solutions. The results show that ISOSSR-1 and ISOSSR-2 produce good VRP solutions under a reasonable computational time, indicating that each of them is a good alternative algorithm for solving the capacitated vehicle routing problem.

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):iV,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)

  • C. Prins

    A simple and effective evolutionary algorithm for the vehicle routing problem

    Comput. Oper. Res.

    (2004)
  • S. Mazzeo et al.

    An ant colony algorithm for the capacitated vehicle routing

    Electron. Notes Discrete Math.

    (2004)
  • B. Yu et al.

    An improved ant colony optimization for vehicle routing problem

    Eur. J. Oper. Res.

    (2009)
  • M. Reimann et al.

    D-ants: savings based ants divide and conquer the vehicle routing problem

    Comput. Oper. Res.

    (2004)
  • W.Y. Szeto et al.

    An artificial bee colony algorithm for the capacitated vehicle routing problem

    Eur. J. Oper. Res.

    (2011)
  • T.J. Ai et al.

    Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem

    Comput. Ind. Eng.

    (2009)
  • M.-Y. Cheng et al.

    Symbiotic organisms search: a new metaheuristic optimization algorithm

    Comput. Struct.

    (2014)
  • H. Kamankesh et al.

    Optimal scheduling of renewable micro-grids considering plug-in hybrid electric vehicle charging demand

    Energy

    (2016)
  • M. Abdullahi et al.

    Symbiotic Organism Search optimization based task scheduling in cloud computing environment

    Future Gener. Comput. Syst.

    (2016)
  • D.-H. Tran et al.

    A novel multiple objective symbiotic organisms search (MOSOS) for time–cost–labor utilization tradeoff problem

    Knowl. Based Syst.

    (2016)
  • F.P. Goksal et al.

    A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery

    Comput. Ind. Eng.

    (2013)
  • V.F. Yu et al.

    Open vehicle routing problem with cross-docking

    Comput. Ind. Eng.

    (2016)
  • J. Brandão

    A tabu search algorithm for the open vehicle routing problem

    Eur. J. Oper. Res.

    (2004)
  • A. Yurtkuran et al.

    A new hybrid electromagnetism-like algorithm for capacitated vehicle routing problems

    Expert Syst. Appl.

    (2010)
  • E. Teymourian et al.

    Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem

    Inf. Sci.

    (2016)
  • Cited by (0)

    View full text