Nghiên cứu thuật toán tối ưu hóa vận tải người và hàng hóa của Nguyễn Văn Sơn

MINISTRY OF EDUCATION AND TRAINING HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY NGUYEN VAN SON DEVELOPMENT OF ALGORITHMS FOR SOLVING ROUTING PROBLEMS IN THE PEOPLE AND PARCEL TRANSPORTATION DOCTORAL DISSERTATION OF COMPUTER SCIENCE Hanoi−2023 MINISTRY OF EDUCATION AND TRAINING HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY NGUYEN VAN SON DEVELOPMENT OF ALGORITHMS FOR SOLVING ROUTING PROBLEMS IN THE PEOPLE AND PARCEL TRANSPORTATION Major: Computer Science Code: 9480101 DOCTORAL DISSERTATION OF COMPUTER SCIENCE SUPERVISORS: 1. Pham Quang Dung 2. Nguyen Xuan Hoai Hanoi−2023 DECLARATION OF AUTHORSHIP I declare that my thesis titled "Development of algorithms for solving routing prob- lems in the people and parcel transportation" has been entirely composed by myself, supervised by my cosupervisors, Ph. Pham Quang Dung and Assoc.

Nguyen Xuan Hoai. I assure some statements as follows: • This work was done as a part of requirements for the degree of PhD at Hanoi University of Science and Technology. • This thesis has not previously been submitted for any degree. • The results in my thesis is my own independent work, except where works in the collaboration have been included.

Other appropriate acknowledgements are given within this thesis by explicit references. Hanoi, February, 2023 Ph. Student NGUYEN VAN SON SUPERVISORS Ph. Pham Quang Dung Assoc.

Nguyen Xuan Hoai i ACKNOWLEDGEMENT My thesis has been realized during my doctoral course at the School of Information Communication and Technology (SoICT), Hanoi University of Science and Technology (HUST). HUST is a really special place where I have accumulated immense knowledge in my PhD process. A PhD process is not a one-man process. Therefore, I am heartily thankful to my supervisors, Ph.

Pham Quang Dung and Assoc. Nguyen Xuan Hoai, whose encouragement, guidance and support from start to end enabled me to develop my research skills and understanding of the subject. I have learned the countless amount of things from them. This thesis would not have been possible without their precious support.

I would like to thank Prof. Luc De Raedt and all members of Faculty of Computer Science, KU Leuven, Belgium for supporting me a lot in the research process. A special thanks goes to Assoc. Mahito Sugiyama at National Institute of Informatics, Japan for valuable guidance helps me obtain many scientific experiences during the internship periods of the PhD.

Many thanks go also to Ph.D Anton Dries, Ph.D Behrouz Babaki, Ph.D Bui Quoc Trung, Msc. Nguyen Thanh Hoang, Msc. Phan Anh Tu for a positive research-partnership during many months made this research significant as well as realistic. I would like to thank Executive Board and all members of Computer Science De- partment, SoICT as well as HUST for the frequent support in my PhD course.

I thank my colleagues at Academy of Cryptography Techniques for their help. Last but not the least, I would like to thank my family: my parents, my wife and my friends, who support me spiritually throughout my life. They were always there cheering me up and stood by me through the good and bad times. Hanoi, February, 2023 Ph.

Student ii CONTENTS CONTENTS vi SYMBOLS vi LIST OF TABLES viii LIST OF FIGURES ix INTRODUCTION 1 1 BACKGROUND 10 1.2 Vehicle Routing Problem and Extensions.1 Capacitated Vehicle Routing Problem.2 Pickup-and-Delivery Vehicle Routing Problem with Time Windows 12 1.3 People and Parcel Sharing Taxi Routing Problem.4 Rich Vehicle Routing Problem.5 Static Routing Scenario.6 Dynamic Routing Scenario.3 Solution Methodologies for VRP problems.23 2 MODELLING AND SOLVING A NEW VARIANT OF STATIC VE- HICLE ROUTING PROBLEM 27 2.2 Problem description and formulation.2 Notations and definitions.3 The solution methods.1 Notations for heuristic algorithms and solution evaluation.2 Analysis of the challenges of the new capacity constraints in the MTDLC-VR problem 37 iv 2.1 A review of construction heuristics .2 The challenges of the capacity constraints on construc- tion heuristics .3 Adapted construction algorithms with splitting procedure .4 An adapted ALNS with splitting procedure .1 Outline of A-ALNS algorithm .2 Choosing the operators .1 Instances and setting .2 Experiment 1: Mathematical formulation validation .3 Experiment 2: Comparison the efficiency between construction heuristics .4 Experiment 3: The efficiency of the A-ALNS algorithm .2 The efficiency of removal and insertion operators63 .3 Robustness of the A-ALNS strategy .5 Experiment 4: Sensitivity analysis for the lower-bound capacity constraint. 68 3 MODELLING AND SOLVING A NEW VARIANT OF DYNAMIC VEHICLE ROUTING PROBLEM 70 3.2 Taxi-Share Routing Model.3 Online Taxi-Share Routing Problem Based on Predicted Information .1 Taxi Demand Prediction 75 3.1 Learning method with equal length subintervals.2 Learning framework with an adaptive binning method 76 3.2 Online Routing Algorithm.2 Possible Positions for Insertion.3 Route Re-optimization.7 Prediction-Based Idle Taxi Direction.92 CONCLUSIONS 93 PUBLICATIONS 95 Bibliography 97 vii ABBREVIATIONS No. Abbreviatio Meaning n 1 ACS Ant Colony System 2 ALNS Adaptive Large Neighborhood Search 3 BnB Branch-and-Bound 4 BnC Branch-and-Cut 5 BnP Branch-and-Price 6 CDF Cumulative Distribution Function 7 CF-RS Cluster-First Route-Second 8 CP Constraint Programming 9 CVRP Capacitated Vehicle Routing Problem 10 DARP Dial-A-Ride Problem 11 DP Dynamic Programming 12 DVRP Dynamic Vehicle Routing Problem 13 EDF Empirical Distribution Function 14 ERM Empirical Risk Minimization 15 GA Genetic Algorithm 16 GRASP Greedy Randomised Adaptive Search Procedure 17 ICTP Inland Container Transportation Problem 18 KS Kolmogorov-Smirnov 19 LP Linear Programming 20 LS Local Search 21 MDVRP Multi-Depot Vehicle Routing Problem 22 MMCVRP Min-Max Capacitate Vehicle Routing Problem 23 MMVRP MinMax Vehicle Routing Problem 24 MIP Mixed-Integer Programming 25 MTVRP Multi-Trip Vehicle Routing Problem 26 NHPP NonHomogeneous Poisson Process 27 NP Non-deterministic Polynomial-time 28 OP Optimization Problem viii 29 PDVRPTW Pickup-and-Delivery Vehicle Routing Problem with Window Time ix 30 PSO Particle Swarm Optimisation 31 RF-CS Route-First Cluster-Second 32 RVRP Rich Vehicle Routing Problem 33 SA Saving Algorithm 34 SARP Shared-A-Ride Problem 35 SRM Structural Risk Minimization 36 SW Sweep Algorithm 37 TSP Travelling Salesman Problem 38 VRP Vehicle Routing Problem 39 VRPB Vehicle Routing Problem with Backhauls 40 VRPTW Vehicle Routing Problem with Time Windows x LIST OF TABLES 2 A summary of the related papers.1Sets and parameters 32 2.3 Parameters of instance E21 − 1 − 2 − 4 − 6 − 5.4 Travel time matrix of instance E21 − 1 − 2 − 4 − 6 − 5.5 Parameters of instances RG − 1 − 2 − 2 − 2 − 6 and RG − 2 − 2 − 2 − 2 − 6 55 2.6 Travel time matrix of instances RG−1−2−2−2−6 and RG−2−2−2−2−6 56 2.7 The detail of the found optimal solutions.8 Comparison between MILP model and the A-ALNS algorithm.9 Comparison between MIP model and construction algorithms.10 The efficiency comparison between construction algorithms.11 Results of parameter tuning.12 The results of the A-ALNS algorithm.2 Taxi fare rate for calculating the profit introduced in [14].3 The number of taxi requests need to be served in two scenarios.4 The routing results of four algorithms in the first scenario.5 The routing results of four algorithms in the second scenario.6 The efficiency of the algorithm based on the predicted information 90 3.7 The profit of scheduling algorithm using our proposed learning method. 92 xi LIST OF FIGURES 1.1 An example of the CVRP problem.2 Rich vehicle routing problem.3 A classification of the VRP methods.4 An illustration of search space for a minimization problem.5 Illustration of one-point move.6 Illustration of two-point move.7 Illustration of two-opt move.8 Illustration of or-opt move.9 Illustration of three-opt move.10 Illustration of three-point move.11 Illustration of cross-exchange move.1 An example of node transfers to satisfy the capacity constraints, where the lower and the upper boundaries are 70 and 110, respectively.2 An example of vehicle itineraries in the MTDLC-VR problem.3 Results of solving the MIP model on random generated instances.4 Results of solving the MIP model on real small instances.5 Solution visualization of instance E21-1-2-4-6-5.6 The efficiency of operators.7 The number of requests removed from the solution for violating the lower-bound capacity constraints.1 An example of candidate taxi routes from the last drop-off point to the parking locations.2 Overfitting in piecewise-polynomial regression on the San Francisco taxi request data.3 The proposed learning framework.4 The exchange operator.5 The accumulated profit of four scheduling algorithms.6 The percentage of failure requests.91 xii INTRODUCTION As an important component of the economy, the transportation sector plays an important role in economic development and connectivity between regions.

The con- nectivity is even more so in a global economy where the intensification of economic cooperation is related to the movement of people and freight. Many models of trans- port of people and goods have been built in practice, such as public transportation services with fixed routes (bus, rail, ferry, airline services), taxi services to transport people on call requests, container transportation, freight transportation service from center depots to customers, etc. In Vietnam, according to the preliminary report of the General Statistics Office [1], the number of vehicles has increased to approximately 43 million units, more than 3.3039 billion transported passengers and 1.2 billion tons of transported freight in 2015. Transport typically accounts for about 25 percent of all the energy consumption of an economy [2].

Authors in [2] also specified that transport costs account for 20 percent of the total cost of a product. Cities have now become big- ger and bigger in terms of surface and population. This phenomenon has caused some consequences: severe traffic congestion, noise, pollution, road accidents, etc. Hence, transport systems face requirements to increase their capacity and reduce the costs of movements.

One of the major problems encountered in the urban environment is to design efficient transport routing for people and parcels. A good transport routing aims to save costs, thus bringing better profits to companies while meeting people’s demands, significantly increasing the efficiency of transportation systems and possibly reducing the above pointed out issues. The routing problem that finds the optimal solution for vehicle routes is called a Vehicle Routing Problem (VRP). The pure VRP problems such as Capacitated Ve- hicle Routing Problem (CVRP), Min-Max Vehicle Routing Problem without capacity constraint (MMVRP) and Pickup-and-Delivery Vehicle Routing Problem with Time Window (PDVRPTW) are simple models in the sense that it is usually far from the reality of the people and parcel transportation [3].

In contrast, many different factors and constraints generally need to be added to capture real-world problems more fully, 1 leading to problems usually called Rich VRP (RVRP) problems. Therefore, thousands of papers in world literature have been devoted to this problem. For example, trans- portation of different kinds of products such as oil [4], milk [5], and frozen food [6, 7], or delivery of e-commerce packages [8] is an example of freight transportation service from center depots to customers, Shared-a-Ride Problem (SARP) of taxis [9, 10, 11]. In [3, 12], the authors provided a concise review of existing problem features and ap- plications.

The VRP problem is a well-known NP-hard problem [13]. Solving these 2 problems is very hard and, then, still an active research topic that attracts the attention of many computer scientists due to their impact on society and the economy. Given the practical importance of VRPs, the main objective of this thesis is to ex- tend the existing VRPs more flexibly and realistically. It is crucial that new variants are formulated and solution algorithms are developed to solve them as efficiently as possible.

According to surveys from the literature as well as actual operations from transport companies, the routing operation is usually classified into two scenarios: static and dynamic. Hence, this thesis focuses on real-life problems typical for these types of VRP problems. For the static VRP problem, the authors in [3] declared that one of the most important objectives of routing problems is to balance the workload allocation in order to ensure acceptance of operational plans, maintain employee satis- faction and morale, reduce overtime, and to reduce bottlenecks in resource utilization. Due to the limited capacity, the fixed fleet size, and time window constraints, vehicles must deliver product units from multiple distribution centers to customers and operate multiple trips.

However, some trips of vehicles are scheduled to carry too little cargo in real-world situations due to tight time windows.