SOLVING VEHICLE ROUTING PROBLEM

(1)

SOLVING VEHICLE ROUTING PROBLEM

USING ANT COLONY OPTIMIZATION (ACO) ALGORITHM

WONG HAW NGIE

UNIVERSITI SAINS MALAYSIA

2017

(2)

SOLVING VEHICLE ROUTING PROBLEM

USING ANT COLONY OPTIMIZATION (ACO) ALGORITHM

by

WONG HAW NGIE

Thesis submitted in partial fulfilment of the requirements for the degree of Bachelor of Engineering (Mechatronic Engineering)

UNIVERSITI SAINS MALAYSIA

2017

(3)

ii

ACKNOWLEDGEMENT

This thesis is dedicated to everyone who helped me to complete this thesis without much troubles. I would like to acknowledge some individuals and parties who had given me this opportunity to gain invaluable experience during my final year project.

I would like to express my deepest gratitude and appreciation to my supervisor of the project, Dr. Wan Amir Fuad Wajdi bin Othman for his supervision, constant support and the valuable time given throughout this project. Without his help and supervision, it is impossible for me to complete my final year project. The guidance and insightful suggestions are much appreciated.

My special thanks reached out to my beloved parents as well as my siblings for the emotional and eternal moral supports throughout my years of studies.

Last but not least, applauds and appreciations are dedicated to my fellow course mates and friends for their help and moral support during my final year project.

(4)

iii

Bidang kejuruteraan biasanya memerlukan rekabentuk yang paling baik untuk membawa prestasi optimum. Oleh itu, pengoptimuman memainkan peranan yang penting dalam bidang ini. Masalah penghalaan kenderaan (VRP) adalah satu masalah yang penting dalam bidang pengedaran dan logistic dari sekurang-kurangnya awal tahun 1960.

Oleh itu, kajian ini adalah tentang kegunaan algoritma pengoptimuman koloni semut (ACO) untuk menyelesaikan masalah penghalaan kenderaan. Pertama, kajian ini membina model bagi masalah ini untuk diselesaikan dalam kajian ini. Seterusnya, kajian ini memberi perhatian kepada algoritma pengoptimuman koloni semut. Fungsi objektif bagi algoritma ini dikaji dan diguna dalam kajian. Keberkesanan algoritma bertambah dengan pengurangan kriteria berhenti. Parameter kawalan dikaji untuk mencari nilai terbaik bagi setiap parameter kawalan. Selepas nilai terbaik bagi setiap parameter dikenalpasti, penilaian bagi prestasi ACO bagi VRP dijalankan. Prestasi yang baik bagi algoritma menonjolkan kepentingan parameter iaitu: bilangan semut (nAnt), alpha (α), beta (β) dan rho (ρ). Alpha mewakili kepentingan relative jejak, beta mewakili kepentingan penglihatan and rho mewakili the parameter mentadbir pereputan pheromone. Laluan bagi lelaran yang berbeza dibandingkan supaya prestasi algoritma dianalisis. Set terbaik bagi parameter kawalan adalah 20 semut, α = 1, β = 1 and ρ = 0.05.

Kos purata dan sisihan piawai dari 20 pelaksanaan algoritma dengan set terbaik bagi parameter kawalan juga dinilai, 1057.839 km and 25.913 km masing-masing. Akhir sekali, satu kesimpulan dibuat untuk meringkaskan pencapaian kajian ini.

(12)

xi ABSTRACT

Engineering field usually requires to have the best design for an optimum performance, thus optimization plays an important part in this field. The vehicle routing problem (VRP) has been an important problem in the field of distribution and logistics since at least the early 1960s. Hence, this study was about the application of ant colony optimization (ACO) algorithm to solve vehicle routing problem (VRP). Firstly, this study constructed the model of the problem to be solved through this research. The study was then focused on the Ant Colony Optimization (ACO). The objective function of the algorithm was studied and applied to VRP. The effectiveness of the algorithm was increased with the minimization of stopping criteria. The control parameters were studied to find the best value for each control parameter. After the control parameters were identified, the evaluation of the performance of ACO on VRP was made. The good performance of the algorithm reflected on the importance of its parameters, which were number of ants (nAnt), alpha (α), beta (β) and rho (ρ). Alpha represents the relative importance of trail, beta represents the importance of visibility and rho represents the parameter governing pheromone decay. The route results of different iterations were compared to analyse the performance of the algorithm. The best set of control parameters obtained is with 20 ants, α = 1, β = 1 and ρ = 0.05. The average cost and standard deviation from the 20 runtimes with best set of control parameters were also evaluated, with 1057.839 km and 25.913 km respectively. Last but not least, a conclusion was made to summarize the achievement of the study.

(13)

1

CHAPTER 1 INTRODUCTION

1.1 Research Background

The study is about solving vehicle routing problem (VRP) using ant colony optimization (ACO) algorithm. This is a software-based project. VRP generalises the well-known travelling salesman problem (TSP).The study can be divided into two parts, vehicle routing problem (VRP) and ant colony optimization (ACO) algorithm.

The vehicle routing problem (VRP) has been an important problem in the field of distribution and logistics since at least the early 1960s. VRP research accelerated during the 1990s. Researchers could develop and implement more complex search algorithms due to the improvement of microcomputer capability and availability. During this era the term meta-heuristics was introduced to name a number of search algorithms for solving these VRPs as well as other combinatorial optimization problems[1]. VRP applications are studied with meta-heuristics such as: simulated annealing, deterministic annealing[2], Tabu search[3], genetic algorithms[4], ant systems[5], and neural networks[6, 7].

The technical definition of vehicle routing problem (VRP) states that m vehicles initially located at a depot are to deliver discrete quantities of goods to n customers. The aim of a VRP is to determine the optimal route used by a group of vehicles when serving a group of users. The objective of VRP is to minimize the overall transportation cost. The solution of the classical VRP is a set of routes which all begin and end in the depot, and which satisfies the constraint that all the customers are served only once. The transportation cost can be improved by reducing the total travelled distance and by reducing the number of the required vehicles.

(14)

2

The VRP in real life may have several classes of additional constraints, such as limit on the capacity of the vehicles, time windows for the customer to be served, limits on the time a driver can work, limits on the lengths of the routes, etc.[8]. Figure 1-1 shows several types of VRP while the abbreviations are shown in list of symbols and abbreviations (Refer page ix).

Two important classes of population-based optimization algorithms are evolutionary algorithms and swarm intelligence-based algorithms [9]. In this research, swarm intelligence-based algorithms is chosen to be applied on VRP. Swarm intelligence- based algorithms is obtained by studying collective intelligence which exist in nature such a cockroach, fish, ant, bee, birds and so on. The pattern of their survival can be presented with algorithm.

When the task is about the optimization within complex domains of data or information, the solutions are methods representing successful animal and micro- organism team behaviour, such as swarm or flocking intelligence (birds flocks or fish schools inspired Particle Swarm Optimization), artificial immune systems (that mimic the

VRP

VRP B VRPP

D DCVR

P VRPT

W

VRPS D

VRPS C

VRPS T SVR

P MDVR

P

SDVR P

PVRP CVRP

Figure 1-1 Different type of vehicle routing problem

(15)

3

biological one), ant colonies (ants foraging behaviours gave rise to Ant Colony Optimization), or optimized performance of bees.

The study is focused on the general vehicle routing problem (VRP). There are many other methods regarding VRP as discussed earlier in this section while this project is focusing on ant colony optimization (ACO) algorithm.

1.2 Problem Statement

The vehicle routing problem (VRP), a well-known combinatorial optimization problem, holds a central place in logistics management. Due to the fundamental interest as difficult combinatorial optimization problem and to the importance of applications in terms of economic, VRP has received a lot of attention and many algorithms, both exact and heuristics have been developed since then to solve general problem and real world cases[8]. Many meta-heuristic approaches like Simulated Annealing (SA), Genetic Algorithms (GA) and Tabu Search (TS), have been proposed to solve VRP. However, those approaches have some weaknesses such as getting trapped to local optima and slower execution time. These meta-heuristic approaches are not very accurate and they do not always return the optimal solution. Swarm algorithm such as ant colony algorithm[8], honey bee mating optimization algorithm, hybrid ant colony optimization algorithm[10], cuckoo search algorithms[11], bird swarm algorithm[12] and cockroach swarm optimization[13] has been applied to various combinatorial optimization problems, including traveling salesman problem and quadratic assignment problem. In this research, ant colony optimization (ACO) algorithm is proposed and will be applied to an established set of vehicle routing problem (VRP). The procedure simulates the decision- making processes of ant colonies as they forage for food and is similar to other adaptive

(16)

4

learning and artificial intelligence techniques such as Tabu Search, Simulated Annealing and Genetic Algorithms.

1.3 Objective

The main aim of this study is to apply ant colony optimization (ACO) algorithm for optimising or solving vehicle routing problem (VRP). With this as the aim, the following objectives are to be achieved from this study:

1. To apply ACO algorithm to solve VRP using MATLAB.

2. To analyse the control parameters of ACO algorithm for optimal result.

3. To analyse the performance of the ACO algorithm in solving VRP.

1.4 Project Scope

In order to study the ant colony optimization (ACO) algorithm and the performance in this study, various control parameters are reviewed as follows:

1. Limited to 1 vehicle only.

2. Number of iterations ranged from 100 to 500.

3. Number of ants ranged from 1 to 30.

4. Value of alpha (α) ranged from 0.5 to 5.

5. Value of beta (β) ranged from 0.5 to 5.

6.

Value of rho (ρ) ranged from 0.01 to 0.99.

The theory and formulas of the algorithm are studied. Every steps of the algorithm are studied. The performance of algorithm is evaluated. Comparison and contrast is made before the most suitable control parameters are chosen. The relationship between

(17)

5

formulas of the algorithm and the performance of the algorithm is reviewed in this study.

Final conclusion of the overall performance of the algorithm is made.

1.5 Thesis Organization

The thesis consists of five main chapters which includes Introduction, Literature Review, Methodology, Results and Discussion and lastly Conclusion and Future Work.

Chapter 1 presents a research overview of ant colony optimization (ACO) algorithm and vehicle routing problem (VRP). The background of VRP and the ant colony optimization (ACO) algorithm are discussed in general. Research objectives are also stated.

Chapter 2 presents literature reviews which summarize the past efforts that have been done on proposing algorithm for VRP. Several sub-sections discuss about the concept of optimization, overview of VRP, overview of swarm algorithm and ACO.

Chapter 3 presents about the methodology, design and implementation of ant colony optimization (ACO) algorithm in solving VRP. The flow of study, testing and evaluation of ACO algorithm is included in this chapter. The procedures to create basic design using MATLAB are also included.

Chapter 4 presents the results of the research. The discussion are made based on the result obtained. The result and findings are presented by tables and figures.

Chapter 5 presents conclusion that can be drawn through the results and finding obtained in the project. Suggestion on future work and improvement is also made in this chapter.

(18)

6

CHAPTER 2 LITERATURE REVIEW

2.1 Introduction

In this chapter, several research papers related to basic concept of optimization, vehicle routing problem (VRP) and ant colony optimization (ACO) algorithm are reviewed. A brief overview of solving vehicle routing problem (VRP) using ant colony optimization (ACO) algorithm by other researcher are also presented in this chapter.

2.2 Concept of Optimization

Optimization is the process of making something better. In other words, optimization is the process of adjusting the inputs to or characteristics of a device, mathematical process, or experiment to find the minimum or maximum output or result.

The input consists of several variables. The process or function is known as the cost function, objective function, or fitness function while the output is known as the cost or fitness[14]. Optimization problems are of high importance both for the industrial world as well as for the scientific world. There are many different optimization problems, which are either continuous, discrete, linear, nonlinear, non-smooth or non-convex. The continuously differentiable problems can be tackled by the traditional methods, such as gradient-based methods. If the problems are very complex, such as non-convex or non- differentiable, they may not be efficiently solved by some traditional methods[12].

Examples of practical optimization problems include train scheduling, time tabling, shape optimization, telecommunication network design, or problems from computational biology. The research community has simplified many of these problems in order to obtain scientific test cases such as the well-known traveling salesman problem (TSP)[15].

(19)

7

There are two main intelligent approaches to solve optimization problems: evolutionary based optimization algorithms and swarm intelligence optimization methods. These optimization algorithms have been successfully applied to constrained optimization problems and multimodal optimization problems[16].

2.3 Overview of Vehicle Routing Problem

Vehicle routing problems (VRPs) are an extension of the classic travelling salesman problem (TSP). In this problem, one or more vehicles travel around a network, leaving from and returning to a depot node. The customers are located on the network and each customer must be visited by exactly one vehicle once. Customers are usually located at network nodes. The objective of the VRP is to find the vehicle routing(s) of minimum cost or in other word, to minimize the total route length[17]. It is described as finding the minimum distance or cost of the combined routes of a number of vehicles m that must service a number of customer n[18]. Figure 2-1 shows a typical vehicle routing problem, where m = 4, n = 15, while m is the number of vehicles and n is the number of customers.

Depot Route 1

11

13 1

10

12 2 Route 3

14 9

6

8 Route 2

3 4

5

7 Route 4 Customers

Figure 2-1 Vehicle Routing Problem

(20)

8

Mathematically, the system of the VRP is described as a weighted graph 𝐺 = (𝑉, 𝐴, 𝑑) where the vertices are represented by 𝑉 = {𝑣₀, 𝑣₁, … , 𝑣_𝑛} and the arcs are represented by 𝐴 = {(𝑣_𝑖, 𝑣_𝑗) ∶ 𝑖 ≠ 𝑗}. A central depot where each vehicle begins its route is located at 𝑣₀ and each of the other vehicles represents the n customers[18]. The distance connected with each arc are represented by the variable 𝑑_𝑖𝑗, which are associated with each arc (𝑣_𝑖, 𝑣_𝑗), represent the distance (or the travel time or the travel cost) between 𝑣_𝑖 and 𝑣_𝑗[19]. The VRP is solved under a few constraints as follows:

1. Each customer is visited only once by a single vehicle.

2. Each vehicle must start and end its route at the depot, 𝑣₀.

3. For each vehicle route, total route length does not exceed maximum route length, 𝐿_𝑚, which includes a service distance δ for each customer on the route.

4. VRP studied here is symmetrical where 𝑑_𝑖𝑗 = 𝑑_𝑗𝑖 for all 𝑖 and 𝑗.

2.4 Overview of Swarm Intelligence

Swarm intelligence studies the collective behaviour of the unsophisticated agents such as social insects that interact locally through their environment. Swarm intelligence has a few advantages such as speed, scalability, adaptation, modularity, parallelism, autonomy, and fault tolerance. Swarm intelligence is a research field which aims to model the collective intelligence which exists in nature in different species e.g. insect, fish, cat, ants, etc. Real-world optimization problems are very difficult and have high degrees of uncertainty. Swarm intelligence based optimization algorithms are proved to be outperforming conventional optimization algorithms, especially when the complexity of the problem increases. In addition, swarm intelligence based optimization algorithms are easy to implement and can be combined with other algorithms. There are several hybrid

(21)

9

algorithm where two swarm algorithms are combined or one swarm algorithm with other algorithms. For example, a hybrid algorithm is done by combining glow-worm swarm optimization and complete 2-opt algorithm[20]. Despite higher optimization performance of swarm intelligence based optimization algorithms, several of the algorithms suffer from some limitations and are not appropriate for all optimization algorithms.

2.4.1 Ant colony optimization (ACO) algorithms

Ant colony optimization (ACO) metaheuristic, a novel population-based approach was proposed by Dorigo et al. to solve several discrete optimization problems[21]. ACO is one of the techniques for approximate optimization. The inspiring source of ACO algorithms are real ant colonies. ACO algorithm mimics the way real ants find the shortest route between the food source and their nest. The ants’ foraging behaviour is the main idea of the algorithms. The indirect communication between the ants is the core of this behaviour. The communication between ants is done by depositing a chemical substance called pheromone. As an ant travels, it deposits a constant amount of pheromone that other ants can follow. However, the continuous random selection of paths by individual ants helps the colony to discover alternate routes when they meet a new decision point.

The ants can choose to follow the pheromone trail which will reinforce the path and increase the probability of the next ant following the trail, or they can select a new path.

Pheromone trails enables them to find short paths between their nests and food sources.

The path with higher concentration of pheromone is more likely to be chosen and thus reinforced. More and more ants are soon attracted to the path and hence the optimal route from the nest to food source and back is very quickly established. In the meantime, the pheromone intensity of the other paths that are not chosen is decreased through evaporation. The unchosen paths become difficult to detect and thus further decreases

(22)

10

their use. This phenomena is called stigmergy, which is defined as a mechanism of indirect coordination, through the environment, between agents or action. The principle of stigmergy is that the trace left in the environment by an action stimulates the performance of a next action, by the same or a different agent [22]. This characteristics of real ant colonies are exploited in ACO algorithms in order to solve VRP.

Figure 2-2 shows how real ants find the shortest path. In Figure 2-2(A), the ants arrive at a decision point. In Figure 2-2(B), some ants choose the upper path and some the lower path (the choice is random). In Figure 2-2(C), given the ants move at approximately a constant speed, the ants who choose the lower path which is shorter reach the opposite decision point faster than those which chose the upper path which is longer.

The ants then go back to the starting point using the same path and thus reinforce the pheromone of the route. In Figure 2-2(D), pheromone accumulates at a higher rate on the shorter path which is represented by number of dashed lines in the figure.

Figure 2-2 How real ants find the shortest path.

(23)

11 2.5 Chapter Summary

Based on the literature review above, it can be summarised that engineering problems requires optimization to obtain desired results. An engineering problem is optimized by applying suitable solution. The solution is applied to the problem and then evaluated with the aim to achieve particular objectives and expectations. In this context, with the presence of a designed problem and fitness as performance index, the performance of the system to be optimized can be evaluated. The problem in this study is vehicle routing problem (VRP). Optimization algorithm is used to determine the best and optimal solution. Optimization algorithm used in this study is ant colony optimization (ACO) algorithm. The concepts and idealisation of the algorithm were explained in detail.

(24)

12 CHAPTER 3 METHODOLOGY

This chapter describes the methodology in conducting the application of swarm algorithm on vehicle routing problem (VRP). The swarm algorithm used in the study is ant colony optimization (ACO) algorithm. It first presents a block diagram for simple visual of the methodology. Then, the variables and specific parameters set in the algorithm as well as the procedures to create basic design using MATLAB is included in this section. The methods to evaluate the performance are explained in detail in this chapter.

3.2 Proposed Work

The project will be carried out by applying ant colony optimization (ACO) algorithm to solve vehicle routing problem (VRP). Figure 3-1 shows the flow chart of the proposed work.

(25)

13

Figure 3-1 Flow chart of the methodology ACO parameters declaration

Start

End

ACO parameters initialization Route construction from depot by using

transition probability

Update the best cost solution

Update the best cost solution Calculate the cost value for the routes

Update pheromone trail intensity Update pheromone trail evaporation

Terminating criteria satisfied?

Plot optimum solution (best solution tour model) and the cost per iteration

graph

Yes No

Problem definition

(26)

14 3.2.1 Vehicle Routing Problem (VRP)

The formulas required for solving the VRP is searched and used in MATLAB.

Problem definition of VRP are as follows:

Minimize

∑ ∑ 𝐶_𝑖𝑗𝑥_𝑖𝑗

𝑗∈𝑉 𝑖∈𝑉

(3.1)

Subject to

∑ 𝑥_𝑖𝑗 = 1

𝑖∈𝑉

, ∀𝑗 ∈ 𝑉\{0} (3.2)

∑ 𝑥_𝑖𝑗 = 1

𝑗∈𝑉

, ∀𝑖 ∈ 𝑉\{0} (3.3)

∑ 𝑥_𝑖0 = 𝐾

𝑖∈𝑉

(3.4)

∑ 𝑥_0𝑗 = 𝐾

𝑗∈𝑉

(3.5)

𝑥_𝑖𝑗 ∈ {0,1} ∀ 𝑖, 𝑗 ∈ 𝑉 (3.6)

Where 𝐶_𝑖𝑗 = the cost incurred on customer 𝑖 to customer 𝑗, 𝑥_𝑖𝑗 = the arc from customer 𝑖 to customer 𝑗,

𝑥_𝑖0 = the arc from customer 𝑖 to depot, 𝑥_0𝑗 = the arc from depot to customer 𝑗, 𝐾 = number of vehicles, and

𝑉 = vehicle capacity.

(27)

15

Equation 3.1 is the objective function of the vehicle routing problem.

Equations 3.2 and 3.3 state that exactly one arc enters and exactly one leaves each vertex associated with a customer, respectively.

Equations 3.4 and 3.5 specify that the number of vehicles leaving the depot is the same as the number entering.

Equation 3.6 is the capacity cut constraints, which impose that the routes must be connected and that the demand on each route must not exceed the vehicle capacity.

3.2.2 Ant Colony Optimization (ACO) Algorithms

ACO algorithm are divided into two main phases, which are ants’ route construction and the pheromone update[17]. In the first phase, which is tour construction phase, 𝑀 ants concurrently chosen in the network of 𝑁 customer nodes (plus the depot node). At each construction step, ant 𝑘 currently at node 𝑖 applies a probabilistic random proportional rule to decide which node to go to next. It selects the move to expend its tour by taking into account the following two values, heuristic function 𝜂_𝑖𝑗 and the level of pheromone on the arc (𝑖, 𝑗), denoted 𝜏_𝑖𝑗. The 𝜂_𝑖𝑗 represents the attractiveness of the move, usually calculated as the inverse of the distance/cost on the arc from the node 𝑖 to node 𝑗.

The 𝜏_𝑖𝑗 indicates how useful it has been in the past to traverse this particular arc.

Probabilistic random proportional rule are shown below:

𝑝_𝑖𝑛^𝑘 = (𝜏_𝑖𝑛)^𝛼(𝜂_𝑖𝑛)^𝛽

∑_𝑙∈𝑁 (𝜏_𝑖𝑙)^𝛼(𝜂_𝑖𝑙)^𝛽

𝑖𝑘

(3.7)

Where 𝑁_𝑖^𝑘 = the feasible neighbourhood (i.e. the nodes which are directly accessible from node 𝑖 and not previously visited),

(28)

16 𝛼 𝑎𝑛𝑑 𝛽 = heuristic parameters,

𝛼 = relative importance of trail, 𝛼 ≥ 0, and

𝛽 = relative importance of visibility, 𝛽 ≥ 0.

Equation 3.7 is the probabilistic random proportional rule that calculate the probability that the ant 𝑘 chooses to go to node 𝑛 next.

For first phase, which is during route construction, ant 𝑘 located at node 𝑖 moves to node 𝑛 chosen according to the Equation 3.7. Then, after ant 𝑘 moves to the next node, the new node become the node 𝑖 while another new node 𝑛 is chosen again according to the probabilistic random proportional rule. This phase is repeated with the condition that the same node cannot be chosen twice, which means that every node will only undergoes this phase once.

For second phase, pheromone updates of ACO is very critical to achieve optimum solution. The pheromone updating formula was meant to stimulate the change in the amount of pheromone due to both the accumulation of new pheromone deposited by ants on the visited edges and the pheromone evaporation[23]. ACO algorithm uses two types of pheromone updates, namely global pheromone update and local pheromone update.

The local pheromone update is performed every time an ant transverses an arc (𝑖, 𝑗) by using Equation 3.8.

𝜏_𝑖𝑗 ← (1 − 𝜌)𝜏_𝑖𝑗+ 𝜌𝜏₀ 𝑓𝑜𝑟 (0 < 𝜌 < 1) (3.8)

Where 𝜏₀ = (𝑁𝐿^𝑛𝑛)⁻¹,

𝜏₀ = the initial pheromone value, and

(29)

17

𝐿^𝑛𝑛 = the length of the nearest neighbour tour (a tour in which each move is to the nearest unvisited node; this is used as a baseline tour length).

The global pheromone update is only carried out by the ant that produced the best tour so far and is implemented by Equation (3.9) for each arc of the tour.

𝜏_𝑖𝑗 ← (1 − 𝜌)𝜏_𝑖𝑗 + 𝜌∆𝜏_𝑖𝑗^𝑏𝑠, ∀(𝑖, 𝑗) ∈ 𝑇^𝑏𝑠 (3.9)

∆𝜏_𝑖𝑗^𝑏𝑠 = (𝐿^𝑏𝑠)⁻¹ = 𝑄

𝐿^𝑏𝑠 (3.10)

Where 𝜌 = parameter governing pheromone decay, Q = constant, and

𝑇^𝑏𝑠 = the best found tour so far with 𝐿^𝑏𝑠 as its length.

(30)

18 3.2.3 Settings of ACO Algorithm

The algorithm owns specialised control parameters that can be set based on the optimization problem. Table 3.1 shows the control parameters of the algorithm. The MATLAB coding for ACO algorithm is shown in Appendix A.

Table 3.1 Symbols Set in the Algorithm

Description Symbols

Maximum number of iterations MaxIt

Number of decision variables nVar

Number of ants (population size) nAnt

Initial pheromone tau0

Pheromone exponential weight alpha

Heuristic exponential weight beta

Evaporation rate rho

Heuristic information matrix eta

Pheromone matrix tau

Probability P

Current position of ant i

Next position of ant j

Since the optimization problem involved in this study consists of four different control parameters that can affect the output of the algorithm, the algorithm will be evaluated according to the different combinations of these parameters. Table 3.2 shows the setting for these control parameters that are used to evaluate the performance and output of the algorithm.

(31)

19

Table 3.2 Settings of Control Parameters

Parameters Settings

nAnt 5, 20, 30

alpha (α) 0.5, 1, 5

beta (β) 0.5, 1, 5

rho (ρ) 0.05, 0.5, 0.99

3.3 Comparative Study on Cost Function and Stopping Criteria

The objective function was in the main loop of the main program which was saved as aco.m file (see Appendix A.1). To decide the stopping criteria, the algorithm was executed at maximum of 500 iterations at first. Then, to determine the termination condition, one-third or two-third of the iterations executed were taken as the maximum iterations for the algorithm or in other words, when a steady cost value was obtained.

After the suitable stopping criteria was selected, several sets of control parameters were selected. The algorithm was executed with the selected set of control parameters.

The data output of the algorithm was extracted and compared. The number of runtimes was one of the stopping criteria in this algorithm. The algorithms were executed with 20 runtimes for each set of control parameters. Each runtime was an independent experiment which did not affect the other experiments. Results obtained from the 20 runtimes were tabulated and compared to check the robustness of the algorithm. The comparison and analysis of the different sets of control parameters can lead to the best set of control parameters among all. The data of the cost values were saved in .xlsx file format for

(32)

20

further analysis while the graph solutions were saved in .eps file format for analysis and comparison as well.

The maximum, minimum and average data from the 20 runtimes were retrieved from the data and analysed. For every iteration, both maximum and minimum cost value were identified and tabulated for comparison. The solutions were evaluated and ranked.

The process continued until reached termination conditions, which was the last iteration.

The last iteration of each runtime gave the optimum or minimum cost value. Then, the average cost value was calculated by summing up the values of cost values from runtime 1 to runtime 20 and divided by the total number of runtimes which was 20 runtimes. The average cost values was tabulated.

Theoretically, the cost values were significantly reduced through iterations and finally converged to a final best value. As the algorithm found the final best value, the cost value was the optimal solution and will be constant throughout the rest of the iterations. The solutions can be said to be improving in each iteration. To visualise the convergence of cost values, the graph of average cost function against number of iterations was plotted. Besides, error bars were plotted in both graph to indicate the variability of data.

The plots were compared for ACO algorithms with different set of control parameters. The results of the algorithm were compared in terms of computational time, cost function values and converges. The combination of different control parameters were tested to find the best combination of the control parameters.

(33)

21 3.4 Chapter Summary

In short, this chapter focus on the methods used to evaluate and compare the performance of ACO with different control parameters. Before comparison was made, the objective function of this research was defined. The objective function was defined such that it consists of four control parameters that can affect the result of the algorithm.

The control parameters were number of ants, alpha (α), beta (β) and rho (ρ). The stopping criteria was decided before moving on to the experiments with the control parameters.

The stopping criteria of the experiment was the number of iterations for the algorithm.

Based on these factors, the experiment on each set of control parameters was repeated for 20 times with the stopping criteria obtained. Comparison and analysis was made based on the elapsed time, best cost value and the number of iteration where the algorithm reach optimal result. The best set of control parameters was chosen and used to evaluate the performance of ACO algorithm. The maximum, minimum, average and standard deviation of cost value were then plotted on graph to compare the performance of the ACO algorithm. Comparison and analysis were made based on the average and standard deviation of cost value.

(34)

22

CHAPTER 4 RESULTS AND DISCUSSIONS

The chapter presents the experimental results obtained using methods in previous chapter. The different sets of control parameters were applied to the algorithm. The average and standard deviation of the cost values of the system were analysed. The comparison was made based on the analyses.

4.2 The Construction of the Vehicle Routing Problem (VRP)

In ant colony optimization (ACO) algorithm, the VRP was represented by using a graph while the customers were represented by using the nodes on the graph. The range of graph was set to be from 0 to 100 for both x-axis and y-axis. See Appendix A.2 for the MATLAB coding for this function. There were two options in the function, which were either the usage of the fixed coordinates or the usage of randomly generated coordinates.

In order to evaluate the performance of the algorithm, the fixed coordinates were used in the algorithm. The number of the nodes (aka the customers) were set to 100. Table 4.1 shows the fixed coordinates that were used for the rest of the study.

The first node (50, 50) was the depot. The vehicle routing started and ended here.

(35)

23

Table 4.1 Fixed Coordinates of the Customers

No. Coordinates No. Coordinates No. Coordinates

X Y X Y X Y

1 50 50 35 22 51 69 8 44

2 91 3 36 13 97 70 22 43

3 12 85 37 11 18 71 17 90

4 92 94 38 42 21 72 57 18

5 63 68 39 44 42 73 59 10

6 9 76 40 41 48 74 24 73

7 28 75 41 71 25 75 76 30

8 55 39 42 29 91 76 36 2

9 96 66 43 17 68 77 40 3

10 97 17 44 47 14 78 84 91

11 15 71 45 44 13 79 23 88

12 98 3 46 92 68 80 25 54

13 96 27 47 47 53 81 22 97

14 49 4 48 58 89 82 93 15

15 80 9 49 74 15 83 50 20

16 14 83 50 88 0 84 68 57

17 42 70 51 78 76 85 62 20

18 92 32 52 8 19 86 20 29

19 80 95 53 99 5 87 23 11

20 96 3 54 60 35 88 57 82

21 56 75 55 42 32 89 6 42

22 15 11 56 67 11 90 48 81

23 29 32 57 56 98 91 28 100

24 43 2 58 72 59 92 13 64

25 95 24 59 59 49 93 29 18

26 74 50 60 79 48 94 83 28

27 84 72 61 88 23 95 76 93

28 33 66 62 89 77 96 37 89

29 50 44 63 80 66 97 18 87

30 87 78 64 44 94 98 40 37

31 66 37 65 62 99 99 87 61

32 80 40 66 50 66 100 2 65

33 84 16 67 22 62

34 98 64 68 74 67

(36)

24

Figure 4-1 The coordinates of the customers

4.3 Selection of the Stopping Criteria

The stopping criteria of the algorithm was the number of iteration. In order to determine the suitable number of iteration, the algorithm was first executed with 500 iterations. Table 4.2 shows the parameters used for the evaluation.

Table 4.2 Control Parameters used to determine the Stopping Criteria

alpha 1

beta 1

rho 0.05

nAnt 20

*nAnt = number of ants

(37)

25

The optimum result was obtained and reviewed to determine the termination condition. Figure 4-2 shows the result for 500 iterations. The graph indicated that the algorithm achieved the optimum result around 100-150 iterations.

Figure 4-2 Graph of minimum cost per iteration with 500 iterations

Then, one-third or two-third of the iterations executed were taken as the maximum iterations for the algorithm or in other words, when a steady cost value was obtained.

Thus, stopping criteria of the algorithm was then set to 150 iterations. The result was then obtained and reviewed again. Figure 4-3 shows the second result with 150 iterations.

(38)

26

Figure 4-3 Graph of minimum cost per iteration with 150 iterations

Finally, the stopping criteria of the algorithm for the rest of the thesis was set to be 150 iterations as it was good enough to obtain the optimum result required without wasting too much execution time and accumulate too much excessive data to be reviewed.

4.4 Selection of Best Set of Control Parameters

The algorithm will be executed with different set of control parameters. Table 4- 3 shows the control parameters that will be considered. Meanwhile, the stopping criteria (number of iterations) was set to be constant as discussed in previous session. It was represented with ‘MaxIt’ in MATLAB coding as shown in Appendix A. MaxIt = 150 was set for every execution of the algorithm.

(39)

27

Table 4.3 The Combination of Control Parameters to be evaluated

Case nAnt alpha (α) beta (β) rho (ρ)

1(a) 5 1 1 0.05

1(b) 20 1 1 0.05

1(c) 30 1 1 0.05

2(a) 20 1 1 0.05

2(b) 20 1 1 0.5

2(c) 20 1 1 0.99

3(a) 20 1 1 0.05

3(b) 20 1 0.5 0.05

3(c) 20 1 5 0.05

3(d) 20 0.5 1 0.05

3(e) 20 5 1 0.05

*nAnt = number of ants

4.4.1 Control Parameter 1: The number of ants (nAnt)

The ants in the ant colony algorithm (ACO) algorithm represented the vehicle in the vehicle routing problem (VRP). The number of ant was one of the control parameters that affect the performance of the algorithm. According to Table 4.3, the number of ants was set to 5, 20 and 30. The algorithm was executed 20 times each with different number of ants. Table 4.4 shows the performance of the algorithm based on the different number of ants.

(40)

28

Table 4.4 Output of the ACO Algorithm with Different Number of Ants (nAnt) Case 1(a) : nAnt = 5 Case 1(b) : nAnt = 20 Case 1(c) : nAnt = 30 Run-

time

Elapsed Time (s)

Best Cost

Value Iter

Elapsed Time (s)

Best Cost

Value Iter

Elapsed Time (s)

Best Cost

Value Iter 1 11.672 1201.85 95 17.698 1067.81 40 27.124 1027.25 105 2 12.286 1114.22 137 18.190 1017.02 101 19.409 1069.17 84 3 12.601 1157.52 68 18.001 1064.97 90 20.171 1017.27 112 4 13.910 1111.54 147 17.791 1086.11 55 19.341 1044.95 50 5 12.323 1039.72 145 17.230 1074.24 70 18.911 1039.76 139 6 12.891 1087.53 127 17.309 1073.59 89 21.937 1028.47 121 7 12.055 1133.27 97 17.036 1033.89 113 19.718 1040.09 110 8 13.636 1152.65 142 15.933 1081.97 80 20.024 1041.71 107 9 12.466 1104.66 91 17.813 1054.48 122 19.416 1059.47 80 10 13.584 1106.31 111 17.289 1018.97 63 19.563 1063.58 115 11 14.346 1167.72 85 17.476 1029.08 147 19.657 1006.28 88 12 17.983 1167.90 85 21.309 1062.87 123 19.191 1049.22 122 13 15.154 1132.96 85 18.142 1036.60 131 20.825 1052.84 137 14 14.669 1187.82 65 18.950 1045.76 112 19.236 1059.60 83 15 13.382 1144.61 58 15.751 1045.96 108 19.327 1050.55 89 16 13.101 1187.00 77 16.461 1028.47 95 18.930 989.17 122 17 13.879 1178.62 121 17.647 1082.52 94 19.362 1048.01 71 18 13.896 1115.28 138 16.414 1017.82 132 18.893 1026.99 109 19 15.286 1082.52 93 16.827 1087.53 122 19.078 995.62 101 20 12.107 1135.86 86 17.194 1066.91 84 18.857 1034.44 130 Average 13.561 1135.48 102 17.523 1053.83 98 19.948 1037.22 103

*Iter = number of iteration where the algorithm reach optimal result.

From Table 4.4, the performance of the algorithm was the best when the number of ants was set to be 20 (Case 1(b)). The number of iteration required to obtain the optimal result was shortest and was within two-third of the stopping criteria. The result was more accurate as compared to Case 1(a) and Case 1(c). The constant best cost value after the optimal result was obtained and became the proof that there was no further best cost value.

The best cost value for each case was almost the same and thus it did not affect the choice too much. The average elapsed time for the algorithm was not considered here as the number of iteration required to obtain the optimal result was more important.

(41)

29

One of the best cost per iteration graph was shown for each case. Figure 4-4 shows one of the results for Case 1(a), where nAnt = 5. Runtime 9 was chosen as the best cost value was minimum among 20 runtimes. Figure 4-5 shows one of the results for Case 1(b), where nAnt = 20. Runtime 16 was chosen as elapsed time, number of iteration where the algorithm reach optimal result and the best cost value were all below average. Figure 4-6 shows one of the results for Case 1(c), where nAnt = 30. Runtime 19 was chosen as the best cost value was minimum among 20 runtimes. The performance of the cases were similar but Case 1(b) was chosen as the best parameter for the number of ants (nAnt).

Figure 4-4 Case 1(a) Runtime 9: nAnt = 5, α = 1, β = 1, ρ = 0.05

(42)

30

Figure 4-5 Case 1(b) Runtime 16: nAnt = 20, α = 1, β = 1, ρ = 0.05

Figure 4-6 Case 1(c) Runtime 19: nAnt = 30, α = 1, β = 1, ρ = 0.05

(43)

31 4.4.2 Control Parameter 2: rho (ρ)

The parameter rho (ρ) was used in most of the formulas in the ACO algorithm as mentioned in section 3.2.2. The parameter was limited at range of (0 < 𝜌 < 1). According to Table 4-3, rho was set to 0.05, 0.50 and 0.99. The algorithm was executed 20 times each with different value of rho. Table 4.5 shows the performance of the algorithm based on the different value of rho.

Table 4.5 Output of the ACO algorithm with Different Value of Rho Case 2(a) : rho = 0.05 Case 2(b) : rho = 0.50 Case 2(c) : rho = 0.99 Run-

time

Elapsed Time (s)

Best Cost

Value Iter

Elapsed Time (s)

Best Cost

Value Iter

Elapsed Time (s)

Best Cost

Value Iter 1 20.428 1068.36 148 23.796 1005.61 46 23.083 852.93 87 2 18.062 1046.09 131 17.513 1009.63 109 16.943 1000.17 57 3 16.463 1021.17 139 17.076 891.07 103 18.279 973.87 20 4 15.832 1111.42 90 18.531 911.72 125 16.350 1001.83 46 5 16.733 1008.09 135 17.901 883.15 138 18.537 1014.78 106 6 15.915 1012.28 130 17.554 918.76 34 16.586 977.34 99 7 16.321 1059.96 144 17.207 995.60 56 17.302 1012.08 60 8 19.215 1090.79 90 16.088 991.76 81 17.666 1022.99 42 9 17.415 1057.52 78 16.836 987.64 50 16.799 988.60 73 10 16.700 1068.80 88 16.554 899.42 122 17.114 952.48 35 11 17.101 1068.80 65 16.873 928.27 146 17.159 986.78 33 12 17.104 1014.61 123 16.328 1002.42 62 16.565 994.97 104 13 17.426 1075.39 76 17.939 913.17 128 18.264 992.95 73 14 17.093 1067.26 119 29.404 972.47 72 20.291 961.27 65 15 17.305 1088.04 95 17.085 936.22 95 17.458 971.88 99 16 15.850 1095.32 86 16.097 927.73 73 17.602 997.67 67 17 17.377 1001.57 87 15.610 1012.08 41 16.444 964.85 95 18 17.017 1056.95 112 17.306 948.62 81 16.380 951.30 60 19 16.065 1063.38 95 17.243 955.96 80 19.020 959.15 97 20 18.244 1071.75 107 17.708 961.73 128 17.974 987.48 45 Average 17.183 1057.38 106 18.033 952.65 88 17.791 978.27 68

(44)

32

From Table 4.5, the performance of the algorithm was the best when the value of rho was set to be 0.05 (Case 2(a)). The average time elapsed for the algorithm was shortest among Case 2. The number of iteration required to obtain the optimal result was in the acceptable range which was around two-third of the stopping criteria. Furthermore, the result was more accurate as compared to the other two value of rho as the range of result obtained was smaller and more precise. Table 4.6 shows the comparison of data obtained in Case 2.

Table 4.6 The Comparison of Data in Case 2

Maximum Iter Minimum Iter Range

Case 2(a) 148 65 83

Case 2(b) 146 34 112

Case 2(c) 106 20 86

The constant best cost value after the optimal result was obtained became the proof that there was no further best cost value. The best cost value for each case were almost the same and thus it did not affect the choice too much.

One of the best cost per iteration graph was shown for each case. Figure 4-7 shows one of the results for Case 2(a), where rho = 0.05. Runtime 17 was chosen as the best cost value was minimum among 20 runtimes. Figure 4-8 shows one of the results for Case 2(b), where rho = 0.50. Runtime 5 was chosen as the best cost value was minimum among 20 runtimes. Figure 4-9 shows one of the results for Case 2(c), where rho = 0.99. Runtime 16 was chosen as elapsed time, number of iteration where the algorithm reach optimal result and the best cost value were all below average. The performance of the cases were similar but Case 2(a) was chosen as the best parameter for the rho.

(45)

33

Figure 4-7 Case 2(a) Runtime 17: nAnt = 20, α = 1, β = 1, ρ = 0.05

Figure 4-8 Case 2(b) Runtime 5: nAnt = 20, α = 1, β = 1, ρ = 0.50

(46)

34

Figure 4-9 Case 2(c) Runtime 16: nAnt = 20, α = 1, β = 1, ρ = 0.99

SOLVING VEHICLE ROUTING PROBLEM

SOLVING VEHICLE ROUTING PROBLEM

USING ANT COLONY OPTIMIZATION (ACO) ALGORITHM

WONG HAW NGIE

UNIVERSITI SAINS MALAYSIA

2017

SOLVING VEHICLE ROUTING PROBLEM

USING ANT COLONY OPTIMIZATION (ACO) ALGORITHM

by

WONG HAW NGIE

Thesis submitted in partial fulfilment of the requirements for the degree of Bachelor of Engineering (Mechatronic Engineering)

UNIVERSITI SAINS MALAYSIA

2017

Table of Contents

CHAPTER 1 INTRODUCTION

6.

CHAPTER 2

LITERATURE REVIEW

CHAPTER 4

RESULTS AND DISCUSSIONS