||A Tabu Search Solution Algorithm for Autonomous Truck-Drone Delivery
||Department of Transportation & Communication Management Science
Unmanned Aerial Vehicle
Traveling Salesman Problem
Flying Sidekick Traveling Salesman Problem
Between August 6, 2009, and August 10, 2009, the deadly typhoon Morakot has hit Taiwan which brought the rainfall and the worst flooding across the country. Due to the devasting flooding incident, 681 people were dead and 18 went missing. Furthermore, the flooding washed away buildings, roads, bridges, and destroyed the only way back and forth of several mountain areas. Once the villages and towns lose the important traffic, air-delivery becomes the only choice to obtain supplies. However, the shortness of the air-delivery made the villages face tough trials. In such an emergency, the most concerned in this research is delivering numerous supplies quickly, properly, and accurately to meet everyone who is in urgent need.
In recent years, most logistics service providers are desired to seek innovative delivery options to fight with time pressure and labor shortages. In that case, autonomous vehicles seem to be the most appropriate solution to solve the problem. In Singapore, Jurong Island has applied autonomous trucks because of the shortage of labor. In America, autonomous trucks are the only solution in increasing efficiency to fight against the increasing volume of freights. According to National Development Council in Taiwan, the total population from 2020 to 2065 will decrease from 23 million to 17 million. The shortage of labor will bother Taiwan. The autonomous truck can redeem the shortage of labor and increase the efficiency in transportation and safety by automotive control. All the strengths can be achieved by autonomous vehicles, that is why this research focuses on ITS technologies such as an autonomous truck.
The objective of this research aims to develop a model for delivering relief resources in an emergency using Intelligent Transportation System (ITS) such as autonomous vehicles and unmanned aerial vehicles (UAVs). This research focuses on the routing problem in emergency logistics. Logistics has been mostly utilized in the commercial field. However, logistics is also an important tool to transport relief resources when a disaster occurs.
Once the emergency occurs, autonomous vehicles can prevent the labor shortage. In limited time, UAVs are useful to do humanitarian logistics and the most important for those injuries is to deliver relief resources fast and moderately. By optimizing the route and distributing the resource moderately, relief transporting by autonomous vehicles can efficiently transport to injuries from the disaster. Despite the autonomous trucks are mostly utilize in delivering cargos, the development of the intelligent transportation system is the trends sweeping across the whole world. Thus, this research is desired to adopt autonomous trucks cooperating with two UAVs to transport supplies when an emergency occurs. To enhance the efficiency in delivering supplies, this research aims to develop a model for traveling salesman problem with two drones based on tabu search algorithm. Finally, the results are expected to present optimal routes for an autonomous truck and UAVs and be compared with a standard commercial solver, GUROBI. This research is contributed to providing some ideals for delivering relief resources in an emergency adopting the autonomous truck cooperating with two UAVs.
List of Table vi
List of Figure vii
CHAPTER 1 INTRODUCTION 1
1.1 Research Motivation and Background 1
1.2 Research Objectives 3
1.3 Research Flow Chart 3
CHAPTER 2 LITERATURE REVIEW 6
2.1 Autonomous Vehicles 6
2.2 Unmanned Aerial Vehicle (UAV) 8
2.2.1 Current States of Unmanned Aerial vehicles 8
2.2.2 Developments of Unmanned Aerial vehicles 9
2.3 Traveling Salesman Problem 10
2.3.1 Traveling Salesman Problem (TSP) 10
2.3.2 The Flying Sidekick Traveling Salesman Problem (FSTSP) 11
2.4 Vehicle Routing Problem 14
2.4.1 The Introduction of Vehicle Routing Problem 14
2.4.2 The extended problem of VRP 15
2.5 Tabu Search Method 25
2.6 Summary 28
CHAPTER 3 RESEARCH METHODOLOGY 29
3.1 Conceptual Framework 29
3.2 Problem Statement and Research Assumptions 30
3.3 Research Framework 34
3.4 Mathematical Formulation 36
3.5 Solution Algorithm 49
CHAPTER 4 NUMERICAL ANALYSIS 52
4.1 The Structure of Mathematical Model 52
4.2 The Structure of Heuristic Approach 53
4.2.1 Tabu Search Solution Algorithm 53
4.2.2 Heuristic Flowchart 57
4.3 Test Network Development 59
4.3.1 Test Network I 59
4.3.2 Test Network II 62
4.4 Results of Test Networks 64
4.4.1 Results of Test Network I Solving by GUROBI 64
4.4.2 Results of Test Network I Solving by Tabu Search Algorithm 68
4.4.3 Results of Test Network II Solving by GUROBI 70
4.4.4 Results of Test Network II Solving by Tabu Search Algorithm 72
4.5 Summary 74
CHAPTER 5 EMPIRICAL STUDY 76
5.1 Experimental Design and Setup 76
5.1.1 Experimental Design 76
5.1.2 Experimental Setup 79
5.2 Empirical Experiments 80
5.2.1 Empirical Instance with 20 Nodes 80
5.2.2 Empirical Instance with 30 Nodes 82
5.2.3 Empirical Instance with 40 Nodes 83
5.3 Results of Experimental Network 84
5.4 Summary 90
CHAPTER 6 CONCLUSIONS AND SUGGESTIONS 91
6.1 Conclusions 91
6.2 Suggestions 92
Agatz, N., Bouman, P., & Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4), 965-981.
Archetti, C., Fernández, E., & Huerta-Muñoz, D. L. (2017). The flexible periodic vehicle routing problem. Computers & Operations Research, 85, 58-70.
Belgin, O., Karaoglan, I., & Altiparmak, F. (2018). Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers & Industrial Engineering, 115, 1-16.
Bortfeldt, A., Hahn, T., Männel, D., & Mönch, L. (2015). Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints. European Journal of Operational Research, 243(1), 82-96.
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313.
Burer, S., & Letchford, A. N. (2012). Non-convex mixed-integer nonlinear programming: A survey. Surveys in Operations Research and Management Science, 17(2), 97-106.
Campbell, A. M., & Wilson, J. H. (2014). Forty years of periodic vehicle routing. Networks, 63(1), 2-15.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
de Freitas, J. C., & Penna, P. H. V. (2018). A Randomized Variable Neighborhood Descent Heuristic to Solve the Flying Sidekick Traveling Salesman Problem. Electronic Notes in Discrete Mathematics, 66, 95-102.
Desrochers, M., & Laporte, G. (1991). Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Operations Research Letters, 10(1), 27-36.
Erdoğan, S., & Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 48(1), 100-114.
Estrada, M. A. R., & Ndoma, A. (2019). The uses of unmanned aerial vehicles–UAV’s-(or drones) in social logistic: Natural disasters response and humanitarian relief aid. Procedia Computer Science, 149, 375-383.
García-Nájera, A., Bullinaria, J. A., & Gutiérrez-Andrade, M. A. (2015). An evolutionary approach for multi-objective vehicle routing problems with backhauls. Computers & Industrial Engineering, 81, 90-108.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533-549.
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
Goel, A., & Gruhn, V. (2008). A general vehicle routing problem. European Journal of Operational Research, 191(3), 650-660.
Gribkovskaia, I., Laporte, G., & Shyshou, A. (2008). The single vehicle routing problem with deliveries and selective pickups. Computers & Operations Research, 35(9), 2908-2924.
Ha, Q. M., Deville, Y., Pham, Q. D., & Ha, M. H. (2018). On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 86, 597-621.
Huang, Y., Zhao, L., Van Woensel, T., & Gross, J.-P. (2017). Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B: Methodological, 95, 169-195.
Joerss, M., Schröder, J., Neuhaus, F., Klink, C., & Mann, F. (2016). Parcel delivery: The future of last mile. McKinsey & Company.
Khademi, N., Balaei, B., Shahri, M., Mirzaei, M., Sarrafi, B., Zahabiun, M., & Mohaymany, A. S. (2015). Transportation network vulnerability analysis for the case of a catastrophic earthquake. International journal of disaster risk reduction, 12, 234-254.
Koç, Ç., & Laporte, G. (2018). Vehicle routing with backhauls: Review and research perspectives. Computers & Operations Research, 91, 79-91.
Lahyani, R., Coelho, L. C., & Renaud, J. (2018). Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem. OR Spectrum, 40(1), 125-157.
Lahyani, R., Khemakhem, M., & Semet, F. (2015). Rich vehicle routing problems: From a taxonomy to a definition. European Journal of Operational Research, 241(1), 1-14.
Li, H., Lv, T., & Lu, Y. (2016). The combination truck routing problem: a survey. Procedia engineering, 137, 639-648.
Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. (2014). Survey of green vehicle routing problem: past and future trends. Expert systems with applications, 41(4), 1118-1138.
Maden, W., Eglese, R., & Black, D. (2010). Vehicle routing and scheduling with time-varying data: A case study. Journal of the Operational Research Society, 61(3), 515-522.
Marinakis, Y., & Marinaki, M. (2014). A bumble bees mating optimization algorithm for the open vehicle routing problem. Swarm and Evolutionary Computation, 15, 80-94.
Montoya-Torres, J. R., Franco, J. L., Isaza, S. N., Jiménez, H. F., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115-129.
Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109.
Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013). A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1), 1-11.
Rosenfeld, A. (2019). Are drivers ready for traffic enforcement drones? Accident Analysis & Prevention, 122, 199-206.
Wang, X., Poikonen, S., & Golden, B. (2017). The vehicle routing problem with drones: several worst-case results. Optimization Letters, 11(4), 679-697.
Watkins, S., Burry, J., Mohamed, A., Marino, M., Prudden, S., Fisher, A., . . . Clothier, R. (2019). Ten questions concerning the use of drones in urban environments. Building and Environment, 106458.
Yurek, E. E., & Ozmutlu, H. C. (2018). A decomposition-based iterative optimization algorithm for traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 91, 249-262.