Phát Triển Thuật Toán Giải Quyết Vấn Đề Lập Lịch Vận Tải Hành Khách và Hàng Hóa

Tài liệu nghiên cứ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ổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên

• Tác giả: Nguyen Van Son
• Người hướng dẫn: Ph. Pham Quang Dung
• Trường học: Hanoi University of Science and Technology
• Chuyên ngành: Computer Science
• Đề tài: Development of Algorithms for Solving Routing Problems in the People and Parcel Transportation
• Loại tài liệu: doctoral dissertation
• Năm xuất bản: 2023
• Địa điểm: Hanoi

Tóm tắt

I. Tổng Quan Về Thuật Toán Giải Bài Toán Lập Lịch Vận Tải

Ngành vận tải đóng vai trò quan trọng trong sự phát triển kinh tế và kết nối giữa các khu vực. Trong bối cảnh toàn cầu hóa, việc tăng cường hợp tác kinh tế gắn liền với sự di chuyển của người và hàng hóa. Nhiều mô hình vận tải hành khách và vận tải hàng hóa đã được xây dựng, bao gồm dịch vụ công cộng với tuyến cố định, dịch vụ taxi, vận tải container, và dịch vụ vận tải hàng hóa từ kho trung tâm đến khách hàng. Tại Việt Nam, số lượng phương tiện đã tăng lên đáng kể, kéo theo sự gia tăng về số lượng hành khách và hàng hóa được vận chuyển. Tuy nhiên, chi phí vận tải chiếm một phần đáng kể trong tổng chi phí sản phẩm, và các thành phố đang đối mặt với các vấn đề như ùn tắc giao thông, ô nhiễm, và tai nạn. Do đó, cần thiết kế các tuyến đường vận tải hiệu quả để tiết kiệm chi phí, đáp ứng nhu cầu của người dân, và giảm thiểu các vấn đề nêu trên.

1.1. Tầm quan trọng của tối ưu hóa lịch trình vận tải

Việc tối ưu hóa vận tải giúp tiết kiệm chi phí, tăng lợi nhuận cho doanh nghiệp, đáp ứng nhu cầu của khách hàng và giảm thiểu các vấn đề giao thông đô thị. Theo [2], chi phí vận tải chiếm khoảng 20% tổng chi phí sản phẩm. Do đó, việc tìm ra các giải pháp tối ưu hóa là vô cùng quan trọng. Các thuật toán hiệu quả có thể giúp các công ty logistics và chuỗi cung ứng giảm đáng kể thời gian vận tải và chi phí vận chuyển.

1.2. Bài toán lập lịch vận tải VRP và các biến thể

Bài toán lập lịch vận tải (VRP) tìm kiếm giải pháp tối ưu cho các tuyến đường của phương tiện. Các biến thể như CVRP, PDVRPTW là những mô hình đơn giản, thường không phản ánh đầy đủ thực tế. Các yếu tố và ràng buộc khác nhau cần được thêm vào để nắm bắt các vấn đề thực tế hơn, dẫn đến các bài toán Rich VRP (RVRP). VRP là một bài toán NP-khó, thu hút sự chú ý của nhiều nhà khoa học máy tính do tác động của nó đối với xã hội và nền kinh tế.

II. Thách Thức và Vấn Đề Trong Lập Lịch Vận Tải Hiện Nay

Các hệ thống vận tải hiện đại đối mặt với nhiều thách thức, bao gồm sự gia tăng về số lượng phương tiện, ùn tắc giao thông, ô nhiễm môi trường, và yêu cầu ngày càng cao về hiệu quả và tối ưu hóa chi phí. Việc lập lịch vận tải hành khách và vận tải hàng hóa hiệu quả đòi hỏi phải xem xét nhiều yếu tố, như thời gian vận tải, chi phí vận chuyển, lịch trình vận tải, và điều phối vận tải. Các phương pháp truyền thống thường không đáp ứng được yêu cầu của các bài toán phức tạp, đòi hỏi các thuật toán vận tải tiên tiến và các kỹ thuật tối ưu hóa hiện đại.

2.1. Sự phức tạp của bài toán lập lịch vận tải thực tế

Các bài toán VRP thuần túy như CVRP, MMVRP, PDVRPTW thường quá đơn giản so với thực tế. Nhiều yếu tố và ràng buộc cần được thêm vào để mô tả chính xác hơn các vấn đề thực tế, dẫn đến các bài toán Rich VRP (RVRP). Ví dụ, vận tải các loại sản phẩm khác nhau như dầu, sữa, thực phẩm đông lạnh, hoặc giao các gói hàng thương mại điện tử đòi hỏi các phương pháp tiếp cận khác nhau.

2.2. Yêu cầu về tính linh hoạt và khả năng thích ứng

Các hệ thống vận tải cần có khả năng thích ứng với các thay đổi đột ngột, như sự cố giao thông, yêu cầu mới của khách hàng, hoặc sự thay đổi về lịch trình vận tải. Các giải thuật lập lịch cần phải linh hoạt và có khả năng tái tối ưu hóa nhanh chóng để đảm bảo hiệu quả và giảm thiểu rủi ro trong vận tải.

2.3. Bài toán cân bằng tải và tối ưu hóa nguồn lực

Một trong những mục tiêu quan trọng của các bài toán lập lịch là cân bằng tải, đảm bảo sự hài lòng của nhân viên, giảm thiểu thời gian làm thêm và giảm tắc nghẽn trong việc sử dụng tài nguyên. Do giới hạn về năng lực, số lượng xe cố định và ràng buộc về thời gian, các xe phải giao hàng từ nhiều trung tâm phân phối đến khách hàng và thực hiện nhiều chuyến đi. Tuy nhiên, một số chuyến đi của xe được lên kế hoạch chở quá ít hàng hóa do thời gian eo hẹp.

III. Phương Pháp Tiếp Cận Mới Thuật Toán Tối Ưu Hóa Vận Tải

Để giải quyết các thách thức trong lập lịch vận tải, cần phát triển các thuật toán tiên tiến và các phương pháp tối ưu hóa hiệu quả. Các thuật toán này cần có khả năng xử lý các bài toán phức tạp, xem xét nhiều yếu tố và ràng buộc, và đưa ra các giải pháp tối ưu trong thời gian ngắn. Một số phương pháp tiếp cận mới bao gồm sử dụng thuật toán di truyền, thuật toán tìm kiếm lân cận, và quy hoạch động.

3.1. Ứng dụng thuật toán di truyền trong lập lịch vận tải

Thuật toán di truyền là một phương pháp tối ưu hóa dựa trên quá trình tiến hóa tự nhiên. Trong lập lịch vận tải, thuật toán di truyền có thể được sử dụng để tìm kiếm các giải pháp tốt nhất bằng cách tạo ra các quần thể các lịch trình, đánh giá chất lượng của chúng, và lai tạo các lịch trình tốt để tạo ra các lịch trình mới.

3.2. Sử dụng thuật toán tìm kiếm lân cận để tối ưu hóa lịch trình

Thuật toán tìm kiếm lân cận là một phương pháp tối ưu hóa cục bộ, trong đó thuật toán bắt đầu với một giải pháp ban đầu và sau đó tìm kiếm các giải pháp tốt hơn trong vùng lân cận của giải pháp đó. Các thuật toán tìm kiếm lân cận có thể được sử dụng để cải thiện các lịch trình hiện có bằng cách thực hiện các thay đổi nhỏ, như thay đổi thứ tự các điểm dừng hoặc thay đổi tuyến đường của phương tiện.

3.3. Quy hoạch động và ứng dụng trong bài toán vận tải

Quy hoạch động là một phương pháp giải quyết các bài toán tối ưu hóa bằng cách chia bài toán thành các bài toán con nhỏ hơn và giải quyết chúng một cách đệ quy. Trong lập lịch vận tải, quy hoạch động có thể được sử dụng để tìm kiếm các tuyến đường ngắn nhất hoặc các lịch trình hiệu quả nhất bằng cách xem xét tất cả các khả năng có thể.

IV. Ứng Dụng Thực Tế và Kết Quả Nghiên Cứu Về Thuật Toán Vận Tải

Các thuật toán và phương pháp tối ưu hóa vận tải đã được ứng dụng rộng rãi trong thực tế, mang lại nhiều kết quả tích cực. Các ứng dụng bao gồm tối ưu hóa tuyến đường giao hàng, lập lịch cho đội xe, và điều phối các hoạt động vận tải. Các nghiên cứu đã chỉ ra rằng việc sử dụng các thuật toán tiên tiến có thể giúp giảm đáng kể chi phí vận chuyển, thời gian giao hàng, và cải thiện hiệu quả tổng thể của hệ thống vận tải.

4.1. Tối ưu hóa tuyến đường giao hàng và giảm chi phí

Việc tối ưu hóa tuyến đường giao hàng giúp giảm thời gian vận tải, chi phí nhiên liệu, và hao mòn phương tiện. Các thuật toán có thể xem xét nhiều yếu tố, như khoảng cách, tình trạng giao thông, và thời gian giao hàng, để tìm ra các tuyến đường hiệu quả nhất.

4.2. Lập lịch cho đội xe và nâng cao hiệu quả sử dụng

Việc lập lịch cho đội xe giúp đảm bảo rằng các phương tiện được sử dụng một cách hiệu quả nhất, giảm thiểu thời gian chờ đợi và tối đa hóa số lượng hàng hóa hoặc hành khách được vận chuyển. Các thuật toán có thể xem xét nhiều yếu tố, như nhu cầu vận tải, năng lực của phương tiện, và thời gian làm việc của tài xế, để tạo ra các lịch trình tối ưu.

4.3. Điều phối vận tải đa phương thức và tích hợp hệ thống

Vận tải đa phương thức kết hợp nhiều phương thức vận tải khác nhau, như đường bộ, đường sắt, đường thủy, và đường hàng không, để tạo ra các giải pháp vận tải hiệu quả nhất. Việc điều phối vận tải đa phương thức đòi hỏi các thuật toán phức tạp có khả năng xem xét nhiều yếu tố và ràng buộc khác nhau.

V. Kết Luận và Hướng Phát Triển Thuật Toán Lập Lịch Vận Tải

Phát triển các thuật toán giải quyết bài toán lập lịch vận tải là một lĩnh vực nghiên cứu quan trọng, có tiềm năng mang lại nhiều lợi ích cho xã hội và nền kinh tế. Các nghiên cứu trong tương lai cần tập trung vào việc phát triển các thuật toán tiên tiến hơn, có khả năng xử lý các bài toán phức tạp và thích ứng với các thay đổi trong môi trường vận tải. Ngoài ra, cần tăng cường ứng dụng các công nghệ mới, như AI trong vận tải, machine learning trong vận tải, big data trong vận tải, và IoT trong vận tải, để nâng cao hiệu quả và tính bền vững của hệ thống vận tải.

5.1. Tích hợp AI và Machine Learning vào thuật toán vận tải

AI trong vận tải và machine learning trong vận tải có thể được sử dụng để dự đoán nhu cầu vận tải, tối ưu hóa tuyến đường, và điều phối các hoạt động vận tải một cách tự động. Các thuật toán học máy có thể học từ dữ liệu lịch sử và đưa ra các quyết định thông minh để cải thiện hiệu quả của hệ thống vận tải.

5.2. Ứng dụng Big Data và IoT để cải thiện hiệu quả vận tải

Big data trong vận tải và IoT trong vận tải cung cấp một lượng lớn dữ liệu về tình trạng giao thông, vị trí của phương tiện, và nhu cầu vận tải. Dữ liệu này có thể được sử dụng để cải thiện độ chính xác của các thuật toán dự đoán và tối ưu hóa, và để giám sát và điều khiển các hoạt động vận tải một cách hiệu quả hơn.

5.3. Hướng tới vận tải bền vững và thân thiện với môi trường

Các nghiên cứu trong tương lai cần tập trung vào việc phát triển các thuật toán và phương pháp tối ưu hóa vận tải có tính đến các yếu tố môi trường, như giảm thiểu khí thải và sử dụng năng lượng hiệu quả. Vận tải bền vững và vận tải xanh là những mục tiêu quan trọng cần đạt được để bảo vệ môi trường và đảm bảo sự phát triển bền vững của xã hội.

Trích đoạn nội dung tài liệu

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 .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 operators .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 .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 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.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 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 .7 The profit of scheduling algorithm using our proposed learning method. 92 viii 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 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 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, 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 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 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.