A Review on

Metaheuristic Algorithm in Multi Depot Vehicle Routing Problem

Mohd Shahizan Othman *,a, sherylaidah binti samsuddinb, Lizawati Mi Yusuf c

Faculty

of Computing, Universiti Teknologi Malaysia, 81310, UTM Johor Bahru, Johor,

Malaysia

a,*[email protected], b [email protected], c [email protected],

Abstract – In recent years, VRP has attracted high

attention in real life problem. VRP has many variants and MDVRP is a part of

it. MDVRP is arises with rapid development in logistic and transportation.

Hence, to solve the problem, there is a need to apply metaheuristic in order to

get a better result. This reviewed paper has discussed about Metaheuristic and

hybrid algorithm in MDVRP. Based on the previous work, it showed that mostly

hybrid algorithm in metaheuristic algorithm did help in give good solution for

MDVRP.

Keywords: Metaheuristic, Multi depot, VRP, MDVRP

1.0 INTRODUCTION

In recent years, Logistics and transportation cost became

rising and critical issue in all the fields. The most challenging strategy is

to optimize product distribution from suppliers to users following satisfying

constraints. Goods transportation processed has undergone drastic increased

because of increasing in community of users and growing number of on-line

shopping stores. VRP is one of the most

studied problem in field of logistic and transportation (Allahyari, Salari, & Vigo, 2015)

VRP is evolution from the classic

Traveling Salesman Problem (TSP). In TSP, The number of vehicle used to handle

a group of customer with the optimal design of routes can be one or more than

that. The difference between TSP and VRP is the TSP aim to find a shortest path

where the vehicle must visit and return to the city where it started whereas

VRP aim to minimize the total cost for serving customers. Nonetheless, Laporte

(2007) highlighted that the VRP is practically more challenging to solve

compare to a TSP (Annouch, Bouyahyaoui, Bellabdaoui, & Mohammed,

2015).

The VRP was first presented by Dantzig and Ramser in 1959 (Calvete et al, 2004). The VRP plays an important

role in reducing the costs of transportation in logistic distribution and

considered as one of the most important combinatorial optimization problems.

Based on definition about VRP, we can conclude that there are four elements or

components that involve in VRP which are vehicle, customer, depot and goods (Dondo & Cerdá, 2007; Goksal, Karaoglan, &

Altiparmak, 2013; Student & Sharma, 2015). Generally, in distribution

and pickup of goods, VRP will determined a minimum-cost set of routes.

Many variants of VRP are studied to address the

variety of conditions in real world applications such as the capacitated VRP

(CVRP), the VRP with time windows (VRPTW), the heterogeneous fleet VRP (HVRP),

the VRP with pickup and delivery (VRPPD), and multiple depots VRP (MDVRP) (Goksal et al., 2013). The MDVRP is said to be more

demanding and sophisticated compared to VRP. MDVRP is the extended version of

VRP where more than one depot are used. The variants of multi-depots known to

be NP-hard problems because it have many constraints which consume a high

computational time to find optimal solutions for large problems.

There are three solution methods to solved problems

in MDVRP which are exact, heuristics and metaheuristic method. This paper

provided a review about the metaheuristic algorithms for solving multi-depot

vehicle routing problem (MDVRP) and hybrid algorithm in MDVRP.

2.0 MULTI DEPOT IN VRP

The VRP and its variants is said to be NP-hard problem. MDVRP is one of

the variant where it is one of the most widely used variations in VRP problem (Karakati? & Podgorelec, 2015) and main optimization

problems in the logistics field. Compared with VRP that has single-depot, MDVRP

is said to be more practical and challenging in real life problem because it

involved more than one depot. It is a challenging task for decision makers to

find out which user are served by which depots without exceeding the capacity

constraints since there are a more depots involved (Calvet, Ferrer, Gomes, Juan, & Masip, 2016). Same like VRP, MDVRP also

have many variants. Among others are time windows, heteregenous fleet,

capacitated, periodic, pick-up and delivery, split delivery and etc.

•

Time Windows –

Related to every customer where it define a time interval in which the

customer should be provided (Calvete et al., 2004).

•

Heteregenous Fleet – To minimize the transportation cost, the

number and the type of vehicle used must be determined and which customer must

be serviced by which vehicle also what sequence to follow should be specified (Dondo & Cerdá, 2007).

•

Capacitated – The capacity of each vehicle is

specified.

•

Periodic – each depot has different period (Crainic et al, 2012).

•

Pick-up and Delivery – Every location have goods for pickup and

delivery along with multiple delivery locations that have possibility not the

depots (Kachitvichyanukul et al, 2015).

•

Split Delivery – Within the set of customer

nodes, the optimal location of the depot specified (Ray. et al.,

2014).

VRP

VRPTW

VRPB

VRPPD

PVRP

VRPSPD

MDVRP

CVRP

MDVRPTW

SDMVRP

MDVRPPD

PMDVRP

HFMDVRP

CMDVRP

Figure 1 : Different variants of VRP

and MDVRP (Montoya et al, 2015)

Basically, MDVRP aims to minimize the

total delivery distance or time spent in serving all customers. To get the

customer satisfaction, the delivery time should be not take time too long.

Besides that, MDVRP also aims to minimize the number of vehicles needed. If the

number of vehicle reduced, then it also reduced the total operation cost. No

matter which type of objectives is defined, the ultimate goal of the MDVRP is

to increase the efficiency of the delivery.

Sequencing each

route in every depots

Appoint customer

in each depot to routes

Appoint customer

to depot

Scheduling

Routing

Grouping

Figure

1. The hierarchy of decision in the MDVRP

To solved MDVRP, three types of possible solution applied

which are exact method, heuristic and metaheuristic method. Exact method

introduced based on branch and cut and only can solve a small instances problem

(Mingozzi, Giorgi, & Baldacci, 1999). It only can solve instances

with 25 up to 50 customers. Example of exact method are Branch-and-cut

algorithms, branch and price algorithm, column generation and integer

programming (Azi, Gendreau, & Potvin, 2010; Ma et al., 2017). Reeves stated that heuristic

is a technique that seek near-optimal solutions at a reasonable computational

cost but it does not guarantee optimality 15. The heuristic method is more

flexible and can solved more instances than the exact method (Pop et al, 2011). Example of heuristic method

are Nearest Neighbour and a Clarke-Wright based heuristic (El-Sherbeny, 2010). For metaheuristic, it is

effective techniques applicable to a problems involving large instances.

Metaheuristic and heuristics can solve larger problem but metaheuristic give

more deep search of the objective space compare to traditional heuristics.

During search process, it allow fewer and even unreasonable intermediate

solutions. That is why it rarely stranded in local optimum 18. Example of

metaheuristic are Ant Colony Optimization (ACO), Genetic Algorithm (GA), Simulated

Annealing (SA) and Tabu search (TS) etc. (Montoya-Torres et al., 2015).

3.0 SOLUTION METHOD IN MDVRP

Nowadays, most of the MDVRP problem is solved by using three approach

which are exact methods, heuristic and metaheuristic methods. What

distinguishes between these three methods is the former guarantee the

optimality of the solution found, while the closing usually provide a

high-quality solution faster. For exact method, usually it applied in solving

small instances problem such as work on (Contardo & Martinelli, 2014b) where it involved only 23

instances (Contardo & Martinelli, 2014a) and work on Baldacci et al,

(2009) solving for 20 up to 50 instances (Baldacci & Mingozzi, 2009). Moreover, since MDVRPs are

NP hard, exact methods are not suitable to get optimal solutions. That is why

heuristic algorithms have been selected to solve the MDVRPs at a faster rate

thus giving computationally effective solutions. However, metaheuristic method

have received high attention among researchers (Montoya-Torres et al., 2015) and it can solve more larger

instances than heuristic and exact method. That is why many researchers applied

metaheuristic algorithm for solving MDVRP.

3.1 Metaheuristics algorithm

A repetitive generation process that leads a subordinate

heuristic by bringing together various concept for exploiting and exploring the

search space is defined as metaheuristic (Osman & Laporte, 1996). They are constructed

for optimization problem in which the optimization methods and classical

heuristic failed to be efficient and effective (Osman & Laporte, 1996). In higher-level frameworks,

fundamental heuristic will be integrate in metaheuristic. User have a broad and

continually growing number of metaheuristics at their disposal. There are four

componnets in metaheuristic which are initial space solution, search engines,

learning and guidance method and management of information structures (Osman, 2001). Almost all

metaheuristics share the following characteristics; they are nature inspired,

they make use of stochastic components, they do not use the gradient or Hessian

matrix of the objective function, they have several parameters that need to be

fitted to the problem at hand.

There are two basic components in any

metaheuristic algorithm which are diversification and intensification. This two

components are very important because the behaviour metaheuristic is determined

by them (Blum & Roli, 2003). Diversification is to produce various solution to make it

able to explore the search space on the global scale, Whereas intensification

is to give focal point on the search in a local area by exploiting the

information that are current better solution establish in this area. This is an

integration with the collection of the better solution. The collection of the

best guarantee that the solution will converge to the optimality. Furthermore,

the diversification through randomisation prevent the solution being trapped at

local optima, at the same time the diversity of the solution will increases.

Usually, the global optimality is feasible through good integration of these

two elements (Yang, 2011).

The

advantages of metaheuristis are metaheuristics give decision

makers with powerful tools that acquire great features solutions, in a

reasonable computational effort (Osman, 2001).

Table 1 shows variants

in MDVRP and its solution method using metaheuristic algorithm which have been

used by other researchers in solving NP-hard combinatorial problems. From Table 1 below, it shows that most

widely studied variant is time windows. It can be concluded that time window is

one of the challenging and practical problem in logistic management.

Furthermore, from table 1, it also shows that

mostly researchers choose to combined metaheuristics algorithm with other

metaheuristic algorithm or another word known as hybrid metaheuristic method in

order to solved multi-depot vehicle routing problem. It shows that hybrid

metaheuristic algorithms strategy in solving multi depot vehicle routing

problem has been used many times as it can figure out high dimensional problems

quickly in order to get a better solution.

Table 1 : Variants in MDVRP and

its solution method using metaheuristic algorithm

REFERENCES

VARIANTS

SOLUTION

(G. Wang & Lin, 2017)

–

Hybrid mosquito-host seeking

algorithm

(Shimizu, Sakaguchi, & Yoo, 2016)

MD VRP + simultaneous pickup and delivery

Weber basis saving method +

modified TB

(Shimizu et al., 2016)

SPD

Hybrid method

(Li, Li, & Pardalos, 2016)

TW

Hybrid GA

(Yalian, 2016)

–

Improved ACO

(Kachitvichyanukul et al., 2015)

PDP

PSO + multiple social learning

(Xu, Jiang, & Branch, 2014)

HVR

Improved variable neighbourhood

search algorithm

(Contardo & Martinelli, 2014b)

–

Exact algorithm

(Liu & Yu, 2013)

–

ACO + GA

(T. J. Wang & Wu, 2013)

–

Cloud adaptive PSO

(Ala?a & Dridi, 2013)

TW

GA

(Dharmapriya, Siyambalapitiya, & Kulatunga,

2012)

TWSD

SA + TB

(Vidal, Crainic, Gendreau, Lahrichi, & Rei,

2012)

MDPVRP

Hybrid GA

(Zhen & Zhang, 2009)

TW

Hybrid algorithm

(Wen & Meng, 2008)

TW

Improved PSO

3.2

classification of metaheuristics

Metaheuristic approaches can be classified into several

condition regarding how memory is exploited and the search path followed by

them.

a) Trajectory

methods vs discontinuous method

In different metaheuristics, one of

important thing is whether they pursue one single search trajectory corresponding to a closed walk on the neighborhood graph or

whether larger jumps in the neighborhood graph are allowed. Local search algorithms that

carry out more complex transition which are consist of simpler moves also known

as trajectory method. Usually, these method allow not efficient solutions to be

able to escape from local minima

b) Population

based vs single point search

The main point that differentiate

trajectory methods and discontinuous walk method is whether population of

search points or one single search point is used. In second case, at each

iteration of algorithm, only one single solution is employed. to

develop new solution that are predicted to give good fitness, Population-based

meta-heuristic methods will associate a number of solutions in order to achieve

it but at the same time, the good benefits from the old one is still shared. It

is a repetitive procedures that continuously take over solutions with better

ones. (Roeva et al.

2014). The

advantage of population-based algorithm, it give an efficient way for the

exploration of the search space. Yet, the manipulation of population will give

a best final performance.

c) Memory

usage vs. memoryless method

Future search direction very influenced

by the use of search experience (memory, in the widest sense). Usually, short

term memory is used to block revisiting newly found solutions and to prevent

cycling, whereas long term memory is used for intensification and

diversification features

A markov process is performed by memory less algorithm in the process to

complete next process where it is the present state of the search process.

d)

One vs. various neighbourhood

structures

Local search algorithm mostly is a one

single neighborhood structures that describes the type of allowed moves. Certain

initial solution is started by local search algorithm and the process happens

repeatedly to change the current solution to be a good solution. It is known as

neighborhood of the current solution.

e) Dynamic

vs. static objective function

Certain

algorithms customized the evaluation of the single search states when the

algorithm is running. so far, a static objective function is used in introduced

algorithms.

f) Nature-inspired

vs. non-nature inspiration

Most

of metaheuristics algorithm is inspired by naturally from phenomena and these algorithm have been created by

mimicking the most fortunate processes in nature, involving chemical and

physical process, and biological systems (Yang, 2011). Several example are particle swarm

optimization, ant colony optimization, bee colony optimization and firefly

algorithm. From these phenomena, advantages can be taken for algorithmic

approaches to be used as efficient solution of combinatorial optimization

problems.

3.3 hybridization method in

metaheuristic

Metaheuristics is known as a powerful tool to solve any

hard optimisation problems In order to get a better and successful solutions,

various method are hybridized (Piotrowski

& Napiorkowski, 2018). However, to improved

metaheuristic algorithm for a given problem and to make it more powerful, metaheuristic

hybrid optimisation techniques should be applied. With this combination, there

is advantages that can be taken form both algorithms (Beheshti,

Hejazi, & Mirmohammadi, 2014).

Table 2 shows several hybrid algorithm that has been used by researchers

in solving problem in multi depot. It can been seen that genetic algorithm and

local search method mostly used for hybrid algorithm in metaheuristics. It

shows that genetic algorithm and local search is much better for hybridization

process with any other metaheuristic algorithms.

Table 2 : Hybrid algorithm in MDVRP

REFERENCES

VARIANT

ALGORITHM

(G. Wang & Lin, 2017)

MDVRP

MHS

+ 3-opt local optimization

(Shimizu et al., 2016)

Simultaneous pick up and

delivery

modified TB + Weber basis

saving method

(Li et al., 2016)

TW

GA + Adaptive local search

(Allahyari et al., 2015)

Covering tour

GRASP + iterated local search +

SA

(Chaichiratikul, 2013)

Multi depot pick up and

delivery

Memetic algorithm

(Vidal et al., 2012)

Periodic

GA + Adaptive diversity control

(Dharmapriya et al., 2012)

TW and split delivery

SA + TB

(Zhen & Zhang, 2009)

TW

ACO + local search

Time window: TW; Mosquito host seeking: MHS; tabu search:

TB; genetic algorithm: GA; simulated annealing: SA; ant colony algorithm: ACO;

4.0 CONCLUSSION

This paper

is a review about metaheuristic algorithm in MDVRP. The paper has discussed

about MDVRP, solution method in MDVRP, metaheuristic algorithm, classification

of metaheuristic and hybridization method in metaheuristic. From this review

paper, it can be conclude that, metaheuristic algorithm is a better method to

be used in order for solving MDVRP, but, from this review paper also proved

that, hybrid metaheuristic algorithm is more better for solving MDVRP.

5.0 ACKNOWLEDGEMENT