ABSTRACT
This dissertation presents the development of an optimized routing scheme for a capacitated vehicle model using Firefly Algorithm (FFA). The conventional model is a formal description involving mathematical equations formulated to simplify a more complex structure of logistic problems. The logistic problems are generalized as the Vehicle Routing Problem (VRP). When the capacity of the vehicle is considered, the resulting formulation is termed the Capacitated Vehicle Routing Problem (CVRP). In a practical scenario, the complexity of CVRP increases when the number of pickup or drop-off points increase making it difficult to solve using exact methods. Thus, researchers have over the years, proposed computational methods for solving CVRP problems. In this research, two scenarios of CVRP were considered. The solid waste management and supply chain for retail distribution. Thirty-six instances and ten instances in the solid waste management and retail supply chain respectively were used in formulating the optimization model. Certain parameters like number of vehicles, number of customers (pickup or drop off locations), capacity of vehicles, quantity of demand, the number of routes and depot position were considered in formulating the model. Some constraints like a vehicle must begin and end at the depot, all demand must be met, a customer is visited just once by a distinct vehicle each time, the demand on each route must not exceed the vehicle capacity were used to guide the model creation. Also some assumptions were made like observing normal road conditions with traffic, customers availability and a reduction in the total route distance inevitably reduces time and cost. Simulation was carried out using MATLAB R2015b and performance was evaluated on the two scenarios using total route distance covered. The simulated results shows a significant improvement occurred on the travelled distance with a slight percentage difference due to the enormous distance covered. The outcome indicates that the developed model had an overall improvement of 6.03% over the Particle Swarm Optimization (PSO) on the solid waste management and a 7.36% over the Best Known Solution (BKS) for the retail supply chain using the total route cost as performance metrics. For the various depot positions considered which are the Random, Optimized, Centered and Eccentric (ROCE), it is observed that the optimized depot position which is determined by this model had a 25% best result for the Instances of the solid waste management, 44.44% over the eccentric position and 77.78% over the centered and random depot placement. This informs that the developed scheme has significantly reduced the total travelled distance in a search space which can be applied to the logistics industry to save cost and time.
TABLE OF CONTENTS
DECLARATION III
CERTIFICATION IV
DEDICATION V
ACKNOWLEDGEMEN VI
ABSTRACT VIII
LIST OF FIGURES XII
LIST OF TABLES XIII
LIST OF ABBREVIATIONS XIV
CHAPTER ONE: INTRODUCTION
1.1 Background 1
1.2 Significance of Research 3
1.3 Statement of Problem 3
1.4 Aim and Objectives 4
1.5 Methodology 4
1.6 Dissertation Organization 5
CHAPTER TWO: LITERATURE REVIEW
2.1 Introduction 6
2.2 Review of Fundamental Concepts 6
2.2.1 Vehicle Routing Problem 6
2.2.2 Capacitated Vehicle Routing Problem 8
2.2.3 VRP Instances 10
x
2.2.4 Metaheuristic Algorithms 14
2.3 Review of Similar Works 18
CHAPTER THREE: METHODS AND MATERIALS
3.1 Introduction 26
3.2 Materials 26
3.2.1 Computer System 26
3.2.2 MATLAB 27
3.3 Conceptualized Framework for Solid Waste Management 27
3.4 Development of the CVRP Model 28
3.4.1 Depot Positions 30
3.5 CVRP Optimization using Firefly Algorithm 33
CHAPTER FOUR: RESULTS AND DISCUSSIONS
4.1 Introduction 38
4.2 Results of FFA-CVRP Model 38
4.3 Results for Variations in Depot Positions 41
4.3.1 Optimal depot position 42
4.3.2 Depot location percentage improvement 44
4.4 Results of Comparison for the PSO with the FFA Based Technique 46
4.5 Results of Comparison for the ILS-SP, UHGS, BCP with FFA Based Technique 48
CHAPTER FIVE: CONCLUSION, SUMMARY AND RECOMMENDATION
5.1 Summary of findings 52
5.2 Significant Contributions 53
5.3 Conclusion 54
5.4 Limitations 54
xi
5.5 Recommendations for Further Work 54
REFERENCES 56
APPENDIX A 59
APPENDIX B 61
APPENDIX C 65
APPENDIX D 66
xii
CHAPTER ONE
NTRODUCTION
1.1 Background
The rapid advancement in technologies have made logistics to become very important in budgetary considerations for government and its establishments and in revenue generation for private companies. The fact that anybody on the planet can be all around connected has prompted complex transport networks that are exceptionally requesting and are winding up progressively critical. Hence, an effective logistic system can have a tremendous effect to organizations and pertinent business operations. Highlighting the importance of logistics in some sectors like, groceries delivery, online stores delivery of goods, waste management, intra-city public transportation, product price can increase due to an increase in the distribution cost, whereas, vehicle routing has the potential of significant economic savings of up to 30% (Hasle & Kloster, 2007). Thus, the need for vehicle routing becomes necessary.
Vehicle Routing Problem (VRP) is a class of optimization problems that involve optimizing itineraries of a fleet of vehicles to serve a given set of customers (Cattaruzza et al., 2017). This situation represents a large part of the flow of vehicles for various logistic purposes in cities. The framework is used to model an extremely broad range of issues in various applications like, supply chain management, delivery services, public transportation, telecommunications and production planning (Bocewicz et al., 2017). The optimization of vehicle routing can bring about significant economic savings. The interest in VRP is due to its practical and economic importance. However, to solve a VRP is not a simple task as it belongs to the complexity class of decision problems (Kumar & Panneerselvam, 2012).
2
Variants of VRP (Subramanian et al., 2013) include:
1. Capacitated VRP (CVRP)
2. VRP with simultaneous pickup and delivery
3. VRP with mixed pickup and delivery
4. Multi-depot VRP with mixed pickup and delivery
5. VRP with access time windows.
In VRP, the objective can be the minimization of delivery and vehicle costs, optimization of the number of drivers and vehicles, minimizing the time spent during delivery, minimizing the total route cost, etc. (Mahmoudi & Zhou, 2016). The optimization problem may be developed in order to address any one or a combination of the stated objectives considering their constraints. Essential application fields incorporate fuel and diesel conveyance, the arrangement of the soldiers in a frontline, flights of airplanes, conveyance of food and beverage to the restaurants, conveyance of cash to the automated teller machines (ATMs), student and worker services, delivery of items that are purchased by shopping online, transportation and waste management (Kirci, 2016). The focus of this work will be on the CVRP as applied in waste management and supply chain.
In transportation, a CVRP model is an approach that can resolve the improper logistic scheduling in the movement of people that needs a commercial transportation service to ensure all customers are considered and picked up. Also, in supply chain, by taking into cognisance the demand (payload of each customer) and vehicle capacity which are used in planning for payload drop offs and pick up.
In Waste Management, environment quality is the extent to which the condition of an environment relative to the requirements of human need is rapidly deteriorating with
3
concerns to solid waste management, which increases CO2 emissions in the atmosphere and inevitably gives rise to global warming (Budzianowski, 2016). Waste management, has over the years, been modified and improved using various technologies due to increase in solid waste as a result of the growing population (Moh & Manaf, 2014).
1.2 Significance of Research
This research is motivated by the growing concern in getting quality solutions especially for instances of routing models that put into consideration the number of vehicles and cost of the operation. Literature has shown that a better method applied to this routing problem can yield a more optimized solution (Uchoa et al., 2017). For this reason, an algorithm that can be associated with the properties of the CVRP and its attributes will be applied which is the Firefly algorithm (FFA). The main characteristics of the FFA include the fact that, the nodes (fireflies) are more versatile in attractiveness, leading to higher mobility, and a more efficient exploration of the search space i.e. The best route will be more efficiently identified and exploited for vehicles to deliver to customers. Also, the brightness of a node is proportional to the attractiveness i.e. a less bright Firefly will move towards a brighter one through the shortest path. The brightness of every Firefly is determined by the landscape structure of the objective function. Thus, considering the fitness at each stage of motion, for each iteration, the nodes (customers) move to get a better result dropping the previous result to be replaced and this continues until the maximum iteration is reached.
1.3 Statement of Problem
In optimizing route distance to save cost and other resources, first, the necessity to determine the total proximity of all other nodes by locating the best position for a depot which has an effect on the route distance has to be considered. Secondly, the problem of vehicle to route assignment knowing which vehicle to assign to which route, whilst observing the capacity
4
constraints on the model, is a task which needs a solution and such solution will enhance the total route cost. Lastly, a node –to – node travel path which determines the next node for the vehicle to proceed to, such decision has an overall reduced total travelled distance and inevitably will reduce the route cost.
1.4 Aim and Objectives
The aim of this research is to develop an optimized routing scheme for route optimization and depot positioning on a capacitated vehicle model using the Firefly algorithm (FFA).
The objectives for this research are as follows:
1. To develop the CVRP model and objective function considering the Random, Optimized, Centred and Eccentric (ROCE) depot positions.
2. To optimize the developed model in (1) using the FFA and to apply it to instances for solid waste management and supply chain.
3. To validate by comparison with the work of Hannan et al., (2018) and (Uchoa et al., 2017) using total route distance, time and cost as performance metrics.
1.5 Methodology
The methodologies for this research involve the following:
1. Development of the CVRP Model and objective function on various depot positions.
a) Modeling the objective function of the ROCE positions of the depot.
b) Creation of the CVRP model considering all constraints.
2. Application of Firefly algorithm to the developed model in (1) to obtain the optimum of the objective function.
a) Initialize the parameters of Firefly.
b) Development of brightness model.
c) Development of attractiveness model.
5
3. Application of the optimized model in (2) to the instances for solid waste and retail supply chain management.
a) Simulation and performance evaluation.
b) Implement the instances for Solid Waste Management.
c) Implement the instances for Retail supply chain management.
4. Validation by comparing with the work of Hannan et al., (2018) and (Uchoa et al., 2017) using total route distance, time and cost as performance metrics.
1.6 Dissertation Organization
The general introduction has been presented in Chapter One. The rest of the chapters are structured as follows: Detailed review of related literatures and relevant fundamental concept about the capacitated vehicle routing, the algorithm used is explained in Chapter Two. In-depth approach and relevant mathematical models describing the development of the capacitated vehicle routing problem model using the Firefly algorithm were presented in Chapter Three. The analysis, performance and discussion of the result were analysed in Chapter Four. Conclusion and recommendations make up the Chapter Five. Quoted references and Appendices are also provided at the end of this dissertation.
6
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
