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
- Xem thêm -