Development of an Optimized Routing Scheme for a Capacitated Vehicle Model

Development of an Optimized Routing Scheme for a Capacitated Vehicle Model.

ABSTRACT

This presents the of an optimized routing for a capacitated model using Firefly (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 increases 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 (pick up 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. The simulation was carried out using MATLAB R2015b and performance was evaluated on the two scenarios using total route distance covered.

The simulated results show a significant improvement occurred in the traveled 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 central and random depot placement.

This informs that the developed scheme has significantly reduced the total traveled 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
ACKNOWLEDGMENT 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
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
5.5 Recommendations for Further Work 54
REFERENCES 56

INTRODUCTION

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 on 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).

REFERENCES

Agatz, N., Campbell, A., Fleischmann, M., & Savelsbergh, M. (2011). Time slot management in attended home delivery. Transportation Science, 45(3), 435-449.
Al Mamun, M. A., Hannan, M., Hussain, A., & Basri, H. (2016). Theoretical model and implementation of a real time intelligent bin status monitoring system using rule based decision algorithms. Expert Systems with Applications, 48, 76-88.
Archetti, C., Fernández, E., & Huerta-Muñoz, D. L. (2017). The flexible periodic vehicle routing problem. Computers & Operations Research, 85, 58-70.
Arora, S., & Singh, S. (2013). The Firefly optimization algorithm: convergence analysis and parameter selection. International Journal of Computer Applications, 69(3).
Augerat, P., Belenguer, J. M., Benavent, E., Corberán, A., Naddef, D., & Rinaldi, G. (1998). Computational results with a branch-and-cut code for the capacitated vehicle routing problem.
Bianchessi, N., Drexl, M., & Irnich, S. (2017). The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints.