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, May, 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 scienti c 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 signi cant 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, May, 2023 Ph.
Student NGUYEN VAN SON 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 28 2.2 Problem description and formulation .2 Notations and de nitions .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 .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 e ciency between construction heuristics .4 Experiment 3: The e ciency of the A-ALNS algorithm .2 The e ciency of removal and insertion operators .3 Robustness of the A-ALNS strategy .5 Experiment 4: Sensitivity analysis for the lower-bound capacity constraint. 69 3 MODELLING AND SOLVING A NEW VARIANT OF DYNAMIC VEHICLE ROUTING PROBLEM 71 3.2 Taxi-Share Routing Model .3 Online Taxi-Share Routing Problem Based on Predicted Information .1 Taxi Demand Prediction .1 Learning method with equal length subintervals .2 Learning framework with an adaptive binning method 78 3.2 Online Routing Algorithm .2 Possible Positions for Insertion .3 Route Re-optimization .7 Prediction-Based Idle Taxi Direction. 91 CONCLUSIONS 92 PUBLICATIONS 94 Bibliography 95 v ABBREVIATIONS No.
Abbreviation Meaning 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 MILP Mixed-Integer Linear Programming 25 MTVRP Multi-Trip Vehicle Routing Problem 26 NHPP NonHomogeneous Poisson Process 27 NP Non-deterministic Polynomial-time 28 OP Optimization Problem 29 PDVRPTW Pickup-and-Delivery Vehicle Routing Problem with Time Window vi 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 vii LIST OF TABLES 2 A summary of the related papers.1 Sets and parameters .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 56 2.6 Travel time matrix of instances RG−1−2−2−2−6 and RG−2−2−2−2−6 56 2.7 Comparison solutions of the MILP model with the found optimal solutions.8 Comparison between MILP model and the A-ALNS algorithm.9 Comparison between MILP model and construction algorithms.10 The e ciency comparison between construction algorithms.11 Results of parameter tuning .12 The comparison of solution approaches .2 Taxi fare rate for calculating the pro t 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 rst scenario.5 The routing results of four algorithms in the second scenario.6 The e ciency of the algorithm based on the predicted information .7 The pro t of scheduling algorithm using our proposed learning method. 91 viii LIST OF FIGURES 1.1 An example of the CVRP problem.2 Rich vehicle routing problem.3 A classi cation 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 MILP model on random generated instances.4 Results of solving the MILP model on real small instances.5 Solution visualization of instance E21 -1-2-4-6-5.6 The e ciency 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-o point to the parking locations.2 The proposed learning framework.3 The exchange operator.4 The accumulated pro t of four scheduling algorithms .5 The percentage of failure requests. 90 ix 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 intensi cation 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 xed 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 O ce [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 speci ed 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 tra c 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 e cient transport routing for people and parcels.
A good transport routing aims to save costs, thus bringing better pro ts to companies while meeting people's demands, signi cantly increasing the e ciency of transportation systems and possibly reducing the above pointed out issues. The routing problem that nds 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 dierent factors and constraints generally need to be added to capture real-world problems more fully, 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 dierent 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 1 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 extend the existing VRPs more exibly and realistically. It is crucial that new variants are formulated and solution algorithms are developed to solve them as e ciently as possible. According to surveys from the literature as well as actual operations from transport companies, the routing operation is usually classi ed 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 im- portant objectives of routing problems is to balance the workload allocation in order to ensure acceptance of operational plans, maintain employee satisfaction and morale, reduce overtime, and to reduce bottlenecks in resource utilization. Due to the limited capacity, the xed eet size, and time window constraints, vehicles must deliver prod- uct units from multiple distribution centers to customers and operate multiple trips.