Tài liệu Luận án nghiên cứu và phát triển các thuật toán giải quyết các bài toán tối ưu trong giao thông vận tải người và hàng hóa.

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. Ph.D. Pham Quang Dung 2. Assoc. Prof. Nguyen Xuan Hoai Hanoi−2023 DECLARATION OF AUTHORSHIP I declare that my thesis titled "Development of algorithms for solving routing problems in the people and parcel transportation" has been entirely composed by myself, supervised by my cosupervisors, Ph.D. Pham Quang Dung and Assoc. Prof. 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.D. Student NGUYEN VAN SON SUPERVISORS Ph.D. Pham Quang Dung Assoc. Prof. 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.D. Pham Quang Dung and Assoc. Prof. 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. Prof. 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 Department, 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.D. Student ii CONTENTS CONTENTS vi SYMBOLS vi LIST OF TABLES viii LIST OF FIGURES ix INTRODUCTION 1 1 BACKGROUND 10 1.1 Optimization Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Vehicle Routing Problem and Extensions . . . . . . . . . . . . . . . . . 1.2.1 Capacitated Vehicle Routing Problem . . . . . . . . . . . . . . . 11 11 1.3 1.2.2 Pickup-and-Delivery Vehicle Routing Problem with Time Windows 12 1.2.3 People and Parcel Sharing Taxi Routing Problem . . . . . . . . 14 1.2.4 1.2.5 Rich Vehicle Routing Problem . . . . . . . . . . . . . . . . . . . Static Routing Scenario . . . . . . . . . . . . . . . . . . . . . . 16 17 1.2.6 Dynamic Routing Scenario . . . . . . . . . . . . . . . . . . . . . 18 Solution Methodologies for VRP problems . . . . . . . . . . . . . . . . 18 1.3.1 1.3.2 Exact Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . Incomplete Methods . . . . . . . . . . . . . . . . . . . . . . . . 19 21 1.3.2.1 Classic Heuristics . . . . . . . . . . . . . . . . . . . . . 21 1.3.2.2 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . 23 2 MODELLING AND SOLVING A NEW VARIANT OF STATIC VEHICLE ROUTING PROBLEM 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 27 2.2 Problem description and formulation . . . . . . . . . . . . . . . . . . . 29 2.2.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.2 2.2.3 Notations and definitions . . . . . . . . . . . . . . . . . . . . . . Model formulation . . . . . . . . . . . . . . . . . . . . . . . . . 31 33 The solution methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.1 Notations for heuristic algorithms and solution evaluation . . . . 36 2.3.2 Analysis of the challenges of the new capacity constraints in the MTDLC-VR problem . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3 iii 2.4 2.3.2.1 A review of construction heuristics . . . . . . . . . . . 2.3.2.2 The challenges of the capacity constraints on construc- 2.3.2.3 tion heuristics . . . . . . . . . . . . . . . . . . . . . . . Splitting procedure . . . . . . . . . . . . . . . . . . . . 39 40 2.3.3 Adapted construction algorithms with splitting procedure . . . . 43 2.3.4 An adapted ALNS with splitting procedure . . . . . . . . . . . . 47 2.3.4.1 2.3.4.2 Outline of A-ALNS algorithm . . . . . . . . . . . . . . Choosing the operators . . . . . . . . . . . . . . . . . . 48 49 2.3.4.3 Removal operators . . . . . . . . . . . . . . . . . . . . 50 2.3.4.4 Insertion operators . . . . . . . . . . . . . . . . . . . . 51 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Instances and setting . . . . . . . . . . . . . . . . . . . . . . . . 53 53 2.4.2 Experiment 1: Mathematical formulation validation . . . . . . . 56 2.4.3 Experiment 2: Comparison the efficiency between construction 2.4.4 heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Experiment 3: The efficiency of the A-ALNS algorithm . . . . . 59 62 2.4.4.1 Parameter tuning . . . . . . . . . . . . . . . . . . . . . 62 2.4.4.2 The efficiency of removal and insertion operators . . . 63 2.4.4.3 Robustness of the A-ALNS strategy . . . . . . . . . . Experiment 4: Sensitivity analysis for the lower-bound capacity 64 constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.4.5 2.5 37 3 MODELLING AND SOLVING A NEW VARIANT OF DYNAMIC VEHICLE ROUTING PROBLEM 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 70 3.2 Taxi-Share Routing Model . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.2.1 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . 72 3.2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . Online Taxi-Share Routing Problem Based on Predicted Information . 72 75 3.3.1 Taxi Demand Prediction . . . . . . . . . . . . . . . . . . . . . . 75 3.3.1.1 Learning method with equal length subintervals . . . . 75 3.3.1.2 Learning framework with an adaptive binning method Online Routing Algorithm . . . . . . . . . . . . . . . . . . . . . 76 81 3.3.2.1 Route representation . . . . . . . . . . . . . . . . . . . 81 3.3.2.2 Possible Positions for Insertion . . . . . . . . . . . . . 82 3.3.2.3 3.3.2.4 Route Re-optimization . . . . . . . . . . . . . . . . . . Route Establishment . . . . . . . . . . . . . . . . . . . 83 83 3.3.2.5 Request Insertion . . . . . . . . . . . . . . . . . . . . . 83 3.3 3.3.2 iv 3.3.2.6 Improvement Operator . . . . . . . . . . . . . . . . . . 84 3.3.2.7 Prediction-Based Idle Taxi Direction . . . . . . . . . . 84 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3.1 Data Description . . . . . . . . . . . . . . . . . . . . . 85 85 3.3.3.2 Simulation design . . . . . . . . . . . . . . . . . . . . . 86 3.3.3.3 Experimental results . . . . . . . . . . . . . . . . . . . 87 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.3.3 3.4 CONCLUSIONS 93 PUBLICATIONS 95 Bibliography 97 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 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 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. . . . . . . . . . . . . . . . . . . . . . 5 2.1 Sets and parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.2 Modeling variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Parameters of instance E21 − 1 − 2 − 4 − 6 − 5 . . . . . . . . . . . . . . 54 2.4 2.5 Travel time matrix of instance E21 − 1 − 2 − 4 − 6 − 5 . . . . . . . . . 55 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. . . . . . . . . . . . . . . . . 57 2.8 2.9 Comparison between MILP model and the A-ALNS algorithm. . . . . . Comparison between MIP model and construction algorithms. . . . . . 58 59 2.10 The efficiency comparison between construction algorithms. . . . . . . . 61 2.11 Results of parameter tuning . . . . . . . . . . . . . . . . . . . . . . . . 63 2.12 The results of the A-ALNS algorithm . . . . . . . . . . . . . . . . . . . 66 3.1 Parameter Setting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3.2 Taxi fare rate for calculating the profit introduced in [14]. . . . . . . . 87 3.3 3.4 The number of taxi requests need to be served in two scenarios. . . . . The routing results of four algorithms in the first scenario. . . . . . . . 87 88 3.5 The routing results of four algorithms in the second scenario. . . . . . 89 3.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 viii LIST OF FIGURES 1.1 1.2 An example of the CVRP problem. . . . . . . . . . . . . . . . . . . . . Rich vehicle routing problem. . . . . . . . . . . . . . . . . . . . . . . . 12 17 1.3 A classification of the VRP methods. . . . . . . . . . . . . . . . . . . . 19 1.4 An illustration of search space for a minimization problem. . . . . . . . 22 1.5 1.6 Illustration of one-point move . . . . . . . . . . . . . . . . . . . . . . . Illustration of two-point move . . . . . . . . . . . . . . . . . . . . . . . 23 24 1.7 Illustration of two-opt move . . . . . . . . . . . . . . . . . . . . . . . . 24 1.8 Illustration of or-opt move . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.9 Illustration of three-opt move . . . . . . . . . . . . . . . . . . . . . . . 1.10 Illustration of three-point move . . . . . . . . . . . . . . . . . . . . . . 24 24 1.11 Illustration of cross-exchange move . . . . . . . . . . . . . . . . . . . . 24 2.1 An example of node transfers to satisfy the capacity constraints, where the lower and the upper boundaries are 70 and 110, respectively. . . . . 28 2.2 An example of vehicle itineraries in the MTDLC-VR problem. . . . . . 30 2.3 Results of solving the MIP model on random generated instances. . . . 58 2.4 2.5 Results of solving the MIP model on real small instances. . . . . . . . . Solution visualization of instance E21 -1-2-4-6-5. . . . . . . . . . . . . . 58 59 2.6 The efficiency of operators . . . . . . . . . . . . . . . . . . . . . . . . . 64 2.7 The number of requests removed from the solution for violating the lower-bound capacity constraints. . . . . . . . . . . . . . . . . . . . . . 3.1 68 An example of candidate taxi routes from the last drop-off point to the parking locations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Overfitting in piecewise-polynomial regression on the San Francisco taxi request data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.3 The proposed learning framework. . . . . . . . . . . . . . . . . . . . . . 79 3.4 The exchange operator. . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.5 3.6 The accumulated profit of four scheduling algorithms . . . . . . . . . . The percentage of failure requests. . . . . . . . . . . . . . . . . . . . . . 90 91 3.2 ix INTRODUCTION As an important component of the economy, the transportation sector plays an important role in economic development and connectivity between regions. The connectivity 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 transport 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 bigger 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 Vehicle 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, leading to problems usually called Rich VRP (RVRP) problems. Therefore, thousands of papers in world literature have been devoted to this problem. For example, transportation 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 applications. 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 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 satisfaction 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. Therefore, this thesis proposes a new variant of the static VRP problem taking into account most of the well-studied features. Specifically, it is a new constraint on the lower bound of the capacity of vehicles that has not been investigated in the literature. This dissertation formulates the considered problem as a mixed-integer linear programming (MILP) problem, analyzes the challenges of the lower-bound capacity constraints and proposes an adaptive large neighborhood search (ALNS) framework for solving it. For the dynamic VRP problem, a new people transport model is studied that is an extension of the share-a-ride problem proposed by [14]. In the considered model, people and parcels can share a ride and information about future requests is predicted. A new mathematical model and a new anticipatory algorithm for scheduling taxis exploiting the predicted future requests are proposed in this dissertation. Related works Authors in [15] were the first scientists who introduced the Truck Dispatching Problem, modelling how a fleet of homogeneous trucks could serve the demand for oil of a number of gas stations from a central hub and with a minimum travel distance. This problem became known as the VRP problem, one of the most widely studied topics in the field of Operations Research [12, 16]. Since then, several variants of the problem have been put forward, including CVRP, PDVRPTW, VRP with multiple depots (MDVRP) and VRP with multiple trips (MTVRP). The most classical VRP is CVRP, where each customer has a given demand that has to be satisfied, and the total demand of the customers served in the same route does not exceed the upper-bound vehicle capacity. The number of solution methods introduced in the academic literature (for old as well as 2 new variants of the VRP) has grown rapidly over the past decades [7, 17, 18]. Moreover, the performance of current computers has increased significantly. Therefore, we can solve larger instances of the VRP, which promotes the progression in the research field and the development of efficient algorithms for the VRP. VRPTW is a well-known simple extension of VRP that extends the CVRP by adding time windows to a depot and customers. General and state-of-the-art surveys on this problem class are provided in [19]. In [20], the authors implemented the Priority-based Heuristic Algorithm for solving perishable food products delivery problems to maximize customer satisfaction. In their model, customer satisfaction includes the freshness of delivered food. Thus, the time window constraint of each customer demand is relatively tight. Especially, the works in [21] investigated VRP with multiple prioritized time windows for distributing confectionery and chocolate products in Iran. Due to the complexity of their problem, a binary artificial bee colony algorithm tuned via the Taguchi method is developed to solve it. Then, [22] reviewed VRPTW applications related to freight transportation that most logistics and distribution companies face in their daily operations. The MDVRP arises as a generalization of VRP, where vehicles depart from and return to multiple depot locations. [23] surveyed several studies on the MDVRP based on either complete or incomplete methods. In terms of complete algorithms, [24] presented a branch-and-cut-and-price algorithm to find the optimal solution of a variation of VRP in which vehicles have different capacities and fixed costs, located at different depots. An exact method-based heuristic is proposed by [25] to solve the MDVRP problem in which each subproblem becomes a single depot VRP and evolves independently in its domain space. In [26], four fuzzy simulation-based heuristic algorithms are also designed to search the exact solution of the MDVRP for hazardous materials transportation. Regarding incomplete algorithms, [27] and [28] proposed variants of the Variable Neighborhood Search algorithm for solving the MDVRP problem. In [28], the authors considered a multi-depot multi-compartment vehicle routing problem, where the cargo space of each vehicle has multiple separate compartments to transport different products simultaneously. In the context of our problem, these compartments of vehicles are adjustable. Therefore, we only consider constraints on the total available cargo space on each vehicle. Recently, many heuristic methods have been developed in the context of the MDVRP, including the genetic algorithm [29], the local search algorithm [30], and a variable tabu neighborhood search [31]. In [31], their algorithms can be implemented to solve the Multi-Depot Open Vehicle Routing Problem (MDOVRP), which is a generalization of the MDVRP. [32] also considered the MDOVRP and developed a general multiple variable neighborhood search hybridized with a tabu search strategy for solving it. However, the complex objectives and constraints often lead to various solution spaces. These challenges lead to considerable research efforts in em3 bedding learning mechanisms for more efficient neighborhood search through adaptive neighborhood selection. In [33], the authors proposed a hybrid ALNS algorithm that is competitive compared with the algorithm in [32]. Their algorithm combines the ALNS strategy with three insertion, five removal heuristics, and four post-optimization local search procedures. In the MDOVRP model, vehicles do not return to their starting point after serving the last customer. In our model, although a vehicle can also visit different depots on different trips, it must return to a parking area after serving the last customer. The ALNS algorithm is also adapted for dealing with large problem instances. Furthermore, the advanced extension of the problem by combining MDVRP with MTVRP is studied in this thesis. The MTVRP was first proposed by [34], where a vehicle makes several journeys during a day. [35] proposed a mathematical programming model based on a set covering formulation for MTVRP. Recently, a branch-and-price algorithm in [36], and the first exact solution framework based on a novel structure-based formulation in [37] were presented to solve the MTVRP. For incomplete algorithms, it is common to solve the MTVRP by combining VRP and packing procedure [38, 39, 40]. The authors in [38] studied the one vehicle version with multi-trip in a route (a trip is called leg by the authors) and considered the capacity of the vehicle as an output (i.e., the vehicle capacity is not fixed). That is, their model proposed an approach to select the best capacity and the best route, in order to minimize the acquisition cost function and the distance traveled. In [39], the authors proposed an adapted ALNS algorithm that iteratively modifies a CVRP solution and applies bin packing techniques to assign the created routes to available vehicles. Their model assumed that the serving time at the depot was fixed. In contrast, the loading time-dependent at the depot is considered in works of [41] which designs routes to replenish stocks for a cafe company around Singapore. They also developed a hybrid ALNS algorithm that employs two-variable neighborhood descend operators. However, both of those papers considered only one single depot. A survey on the MTVRP can be found in [42]. A combination of the above problems has more practical applications. Recently, more attention has been focused on the multi-trip multi-depot VRP with specific combinations of real-life constraints. They also apply their model to transportation problems for different kinds of commodities. For example, [43] proposed three metaheuristics to solve the multi-trip multi-depot heterogeneous Dial-a-Ride problem. Two-hybrid bee algorithms and an ALNS are presented. These methods are highly effective and efficient. [44] also considered a multi-trip multi-depot VRP problem in which vehicles must pick up meals from multiple suppliers and deliver them to customers. Their problem under logistics resource sharing is solved by two popular algorithms: local search and ALNS. In the ALNS algorithm, the authors proposed a supplier-oriented removal operator and three rules to choose a specific range of insertion for each insertion op4 erator. Their results show that the sharing service has a significant advantage over the exclusive service. In addition, [8] first proposed a multi-trip multi-depot VRPTW with release dates. Their problem originates from the e-commerce package delivery in China. In their model, each trip starts and ends at the same depot. The release date introduced in their paper is when the package requested by a customer in the distribution center can be delivered by a vehicle. Therefore, they considered the practices that vehicles can only deliver available packages that have been released. It is solved by a hybrid particle swarm optimization algorithm and a hybrid genetic algorithm. A summary of the assumptions of related papers is presented in Table 2. Table 2: A summary of the related papers. Ref. [43] [28] [44] [37] [8] [41] This work Multitrip Multidepot √ √ √ √ √ √ √ √ √ Trip limitation √ Constraints No sta- Servicert at dependdepot ent time √ √ √ √ √ √ √ √ √ √ Time window √ √ √ √ √ √ √ Lowerbound capacity Solution methods ComIncomplete plete √ √ √ √ √ √ √ √ √ The difference of our study is exploring logistics services and combining real-world constraints in product delivery, where product companies want to maximize the number of served customers and minimize the number of vehicles related to their availability. In our model, there are three types of points with different accessibility: points visited one time in one-way direction (parking areas), points visited many times (distribution centers), and points visited at most once (customers). Besides, the existence of service sharing leads to the objective function of minimizing outsourcing costs. The loading time at distribution centers and the unloading time at customers are depended on the product type and the product quantity. Moreover, in the context of the MTDLC-VR problem, dairy products are always available at distribution centers. Managers are often concerned with occupancy product rates in vehicles. Thus, new lower-bound capacity constraints are added to our model. To the best of our knowledge, no work has been conducted to address this problem. Most of the above studies deal with the VRP problem in the static scenario, where all data is known in advance. In the dynamic scenario of VRP problems, new requests can be revealed online during the plan execution. Therefore, routes must be dynamically updated while executing the current simulation [45]. A neighborhood search heuristics to optimize the routes of vehicles for dynamic PDVRPTW problems is proposed by 5 [46]. The taxi routing problem can be seen as the specific practical application of PDVRPTW problems in the dynamic scenario, firstly introduced by [13] as a Dial-ARide problem (DARP). Authors in [14] described a SARP problem and solved it in both static and dynamic scenarios. In that paper, the authors explained the conceptual and mathematical model of the DARP problem, where the same taxi network serves people and parcels. There are new variants of this model and some heuristic algorithms that have been proposed by [9, 10] to solve this problem. As DARPs are NP-hard, they are usually solved by heuristic approaches [47, 48, 49]. Although the integration of logistics and transportation into multiple modes of transportation with ridesharing has received much attention, the number of studies remains limited [50, 51]. Even fewer studies have sought an efficient solution to the SARP of people and goods over relatively short transportation distances [52, 53]. A smart taxi-routing system based on a histori- cal data analysis can improve the operational efficiency of drivers and optimize the overall travel efficiency. However, it appears that most researches have opti- mized only the total route distance of all current events on the schedules [9, 54]. In the dynamic scenario, one of the novel components is the dispatch system with unknown requests, which aims to suggest more efficient routes for drivers as well as to serve more than requests by using the learned arrival rate of taxi requests. Applying the learned information to the routing problem, this thesis attempts to maximize the overall travel efficiency while minimizing the idle time of a driver. Motivation The optimization of transportation has become a great issue in recent years. The routing problem is a new challenge for the transportation sector: improve productivity and reduce costs by increasing the number of served clients, reducing the time and cost of transportation to achieve good human resources planning and efficient operation. The research on the VRP is beneficial not only to transportation companies but also to society. With economic development, parcel distribution is one of the most significant static VRP models. Complete models and appropriate algorithms need to be developed for the product distribution problem of the company in Vietnam as well as similar problems around the world. This motivated us to fill a gap in the literature on some VRP problems by combining real-world factors to extend these problems more flexibly and realistically. For people transportation models, one of the most preferred transportation modes for people in urban areas is taxi services due to its convenience, flexibility, and innovative operation strategies, e.g., integration of passenger and parcel transportation on each taxi aims to discount the passenger. Smart ridesharing services can be realized through the convergence of location-based devices, geographic information systems, 6 global positioning systems, and wireless communication. In addition, they enable the deployment of intelligent routing services. The motivation is to consider the share-aride taxi routing problem based on predictive information in online scenarios. A smart routing system based on historical data analysis can improve the operational efficiency of drivers and optimize overall travel efficiency. Methodology The methodology of this dissertation are as follows: • Theoretical study of variants of the VRP problem as optimal problems. • Analyzing the related works to the considered problems. • Designing the practical and useful models of the VRP problem. • Proposing efficient metaheuristic algorithms to solve the investigated VRP models. Scope of Research VRP problems are complex NP-hard problems that include many subproblems and variants. Therefore, the scope of my thesis is to investigate two practical transportation problems typical for two types of VRP problems, static and dynamic VRP problems. In the class of static VRP problems, the parcel distribution problem is studied. The problem considers specific combinations of real-life constraints to tackle real problems in one of the biggest dairy companies in Vietnam. In the class of dynamic VRP problems, the dynamic taxi scheduling problem with predictive information is investigated. This problem is extended from the novel share-a-ride VRP problem proposed by [9, 14] in which people and parcel requests are scheduled on the same taxi network. The considered problems are known as the N P -hard problems. Moreover, the combination of real-life constraints makes the problem more challenging. Therefore, the thesis mainly focuses on heuristic/metaheuristic algorithms for solving the proposed problems. Contributions The three main contributions of the thesis are as follows: • With the goal of developing parcel transportation models to cover real-life problems, the thesis has defined a novel product transportation problem for real-world applications taking into account most of the well-studied features, especially with a new constraint on the lower bound of the capacity of vehicles which has not been investigated in the literature. The thesis formulates the considered problem as a MILP model and proposes some efficient metaheuristic algorithms to solve it. Experiments are performed in various scenarios to examine the efficiency of 7 algorithms. The quality of solutions and computation time are compared with existing methods and some insights are presented on each algorithm’s use in different instances. • For people transportation models, a new variant of the share-a-ride taxi transportation routing model in the dynamic scenario is developed in this thesis. In this model, people and parcels are served in the same taxi network in which the routing system needs to recommend the best route to the driver of a taxi without load so that the chance of receiving a new transportation demand is high when the taxi is still available. We propose a new efficient algorithm for routing taxis and exploiting the predicted future requests. Our model alleviates the deficiencies of the models in [9, 14] by considering the best route for the taxi driver without load. The algorithm is experimented on real data sets in San Francisco city and compared with the methods for DSARP in [14] under the same parameter settings. • This thesis proposed an adaptive and data-driven binning method for learning the non-homogeneous Poison process (NHPP) to predict future transport requests that help minimize the vehicle’s idle distance. The experimental results prove that applying improvement of traveling direction in routing based on the demand prediction leads to flexible movement and overall traveling efficiency. This study linked transportation problems with machine learning which is expected to cope with traditional traffic problems. Organization of the Dissertation This dissertation is organized as follows. • Chapter 1 provides some background about VRP problems such as Optimization Problems, CVRP, PDVRPTW, SARP, RVRP problems and state-of-the-art approaches for solving them. • Chapter 2 is the first of two chapters that detail the research on the RVRP problems carried out in this thesis. The product distribution problem is discussed in this chapter and an adapted ALNS algorithm is proposed for solving the problem. A strategy including generating initial solutions and subsequently applying an adaptive large neighborhood search (A-ALNS) to improve the quality of solutions is also proposed. The performance of the proposed A-ALNS algorithm is compared with that of other heuristics by conducting extensive numerical experiments to evaluate the applicability of the proposed algorithm in real-world applications. • Chapter 3 starts the investigation of the people and parcel share-a-ride taxi transportation problem in the dynamic scenario, which is the more realistic variant of 8 the dynamic VRP problem. The considered problem is an extension of the work in Li et al. 2014 and Nguyen et al. 2015. A data-driven learning method is developed to predict the new transport requests and an efficient algorithm is proposed for routing taxis and exploiting the predicted future requests. • To conclude, Chapter Conclusion and Future works summaries the research that has been undertaken in this thesis and outlines avenues for further research. 9