# Solving the vehicle routing problem with deep reinforcement learning

Simone Foà${}^{\text{a},1}$1111 Master of Science in Management engineering.
<EMAIL_ADDRESS>Corrado Coppola<EMAIL_ADDRESS>Giorgio Grani<EMAIL_ADDRESS>Laura Palagi<EMAIL_ADDRESS>Sapienza University of Rome, Dep. of Computer Science, Control and Management
Engineering, Rome, Italy  Sapienza University of Rome, Dep. of Statistical
Science, Rome, Italy

###### Abstract

Recently, the applications of the methodologies of Reinforcement Learning (RL)
to NP-Hard Combinatorial optimization problems has become a popular topic.
This is essentially due to the nature of the traditional combinatorial
algorithms, often based on a trial-and-error process. RL aims at automating
this process. At this regard, this paper focuses on the application of RL for
the Vehicle Routing Problem (VRP), a famous combinatorial problem that belongs
to the class of NP-Hard problems.

In this work, as first, the problem is modeled as a Markov Decision Process
(MDP) and then the PPO method (which belongs to the Actor-Critic class of
Reinforcement learning methods) is applied. In a second phase, the neural
architecture behind the Actor and Critic has been established, choosing to
adopt a neural architecture based on the Convolutional neural networks, both
for the Actor and the Critic. This choice resulted effective to address
problems of different sizes.

Experiments performed on a wide range of instances show that the algorithm has
good generalization capabilities and can reach good solutions in a short time.
Comparisons between the algorithm proposed and the state-of-the-art solver
$OR-TOOLS$ show that the latter still outperforms the Reinforcement learning
algorithm. However, there are future research perspectives, that aim to
upgrade the current performance of the algorithm proposed.

###### keywords:

Vehicle routing problem; Reinforcement learning; Heuristics

##  1  Introduction

The Vehicle Routing problem (VRP) is among the most studied combinatorial
Optimization problems due to its application interest. In its easiest version
it consists, given a set of nodes and a depot, in determining the set of
routes at the minimum cost, where each route must start and end at the depot
and all nodes must be visited. The problem was introduced by Dantzig, George
B. and Ramser, John H. ([6]) in 1959 to address the problem of the optimal
routing of a fleet of gasoline delivery trucks between a bulk terminal and
many service stations. Through the time many versions of the problems have
been introduced (see [2]) and nowadays the so called green vehicle routing
problem (see [13]) is gaining particular importance because of the increased
attention to environmental issues.

The VRP can be seen as an extension of the Travelling Salesman Problem (TSP
[8]) and for this reason, it is proved to be NP-complete ([16]). Hence, the
numerous attempts to solve the problem exactly through mathematical
formulations and using Branch and X methods (branch and bound, branch and cut,
branch and price) do not provide effective results when the dimension of the
instances becomes high. For this reason, much of the research has shifted
toward the development of heuristics (See paragraph 2).

Recently a new approach for combinatorial problems, based on the application
of deep reinforcement learning, is gaining a remarkable attention. This is due
to the ability of RL to learn through trials and errors (and the trial-and-
error process is indeed a typical part of the standard heuristics). The paper
[9] represents a milestone for the application of RL for combinatorial
optimization problems. In this paper, the authors apply a constructive
heuristic for three different combinatorial problems, showing the
effectiveness of the solution proposed across multiple problem configurations.
Regarding the application of reinforcement learning framework for VRP, many
works have been proposed. The paper of Nazari [15] represents a landmark: in
this work, the authors proposed to tackle the problem using a constructive
heuristic based on reinforcement learning and they approximate the policy
using a recurrent neural network (RNN) decoder coupled with an attention
mechanism. At this regard, the work [10] proposed an approach to tackle the
problem based on attention layers as well. Lastly, the paper [14] is among the
few that proposed an improving reinforcement learning heuristic rather than a
constructive one.

In this context, in our work we developed an improving heuristic based on deep
reinforcement learning, which differs from all others because it tackles the
problem in two stages (the first stage is the assignment and the second is the
routing, inspired by the classic heuristic approach Cluster first- Route
second). The RL algorithm proposed aims at learning just an assignment
strategy, while the routing part is performed using a traditional heuristic
that guarantees a good estimate of the optimal solution. The RL algorithm
proposed belongs to the class of the Actor-Critic methods and the neural
architecture used to approximate the policy and the value function is
constituted by Convolutional neural networks (CNN,for a detailed description
see [12]).

This paper is organized as follows: after a brief introduction regarding the
Vehicle routing problem and the basics of Reinforcement learning in section
(2), the section (3) is dedicated to the description of how we modeled the VRP
as a Markov Decision Process. Then, in section (4), we describe in detail the
deep neural networks used. The section (5) is dedicated to the description of
the algorithm, showing the pseudo-code. In section (6) we discuss the
computational experience and finally in section (7) we report the conclusions.

##  2 Preliminaries and notation

In this section, we describe the Vehicle routing problem from a mathematical
optimization point of view and the basics of reinforcement learning (RL),
focusing on one class of methods (The actor critic methods). Among this class
of methods, the Proximal Policy Optimization algorithm (PPO) is discussed.

###  2.1 The vehicle routing problem

The vehicle routing problem is a famous combinatorial optimization
problem,that has a tremendous application interest as it is faced on a daily
basis by thousands of distributors worldwide and has significant economic
relevance. There are many versions of this problem, that try to adapt the
optimization problem to a particular application. However, all the versions
are extensions of the classic VRP. Among all the versions, the most
researched, according to the literature, is the CVRP (Capacitated vehicle
routing problem), which is the main focus of this section.

Figure 1: An example of VRP with $n=16,m=3$

Let $G=(N,A)$ be a complete graph, where $N=\\{0,1,...,n\\}$ is the set of
nodes, while $A=\\{(i,j):i,j\in N,i\neq j\\}$ is the set of arcs. The node 0
represents the depot. Let $V=\\{1,2,...,m\\}$ be the set of vehicles. In
addition,let $F=\\{1,2,...,l\\}$ be the set of features. Each node $i\in
N\setminus 0$ is characterized by a non-negative demand of a feature $f\in F$
$d_{if}$. Each vehicle $v\in V$ is characterized by a specific capacity with
respect to a particular feature $f\in F$ $q_{vf}$. Moreover, a cost is
associated to each arch of the graph $c_{ij}$, $i,j\in N$. In this specific
setting, a symmetric cost structure is assumed, so that $c_{ij}=c_{ji}\forall
i,j\in N$. The problem consists of determining the sets of $m$ routes with the
following properties: (1) each route must start and end at the depot, (2) each
node is visited exactly by one vehicle, (3) the sum of the nodes demands for
each feature, given a single route, cannot exceed the capacity of the vehicle
for that feature, (4) the total routing cost is minimized. The VRP problem is
NP-hard because it includes the Traveling salesman problem (TSP) as a special
case when the number of vehicles $m=1$ and when $q_{v_{f}}=\infty,\forall v\in
V,f\in F$.

Several families of exact algorithms were introduced over time for the VRP.
These are based, first, on the formulation of the problem through a linear
programming formulation and then they typically apply either the Branch and X
methods (Branch and bound, Branch and price, Branch and cut) or the Dynamic
programming. According to in [11],the main formulations are the following:
(1)Two-Index-Vehicle flow formulation,which has the disadvantage of having a
number of constraints exponential with respects to the number of nodes. For
this reason, the exponential constraints are generated dynamically during the
solution process as they are found to be violated. The second formulation is
(2) the set partitioning, which is computationally impractical due to the
large number of variables. For this reason, Column generation is a natural
methodology applied for this type of formulation. Due to the prohibitive
computational effort when the number of nodes becomes large, much of the
research regarding VRP focused on the development of heuristics rather than
exact methods.

Among heuristics, the main distinction is between classical heuristics and
metaheuristics. The former, at each step, proceed from a solution to a better
one in its neighborhood until no further gain is possible. On the other
hand,metaheuristics allow the consideration of non-improving and even
infeasible intermediate solutions. Regarding the classic heuristics, the most
popular is the Clarke and Wright [5] (which is an example of constructive
heuristics i.e. the algorithm starts form an empty solution and construct it
step by step). Its popularity is due to the speed and ease of implementation
rather than its accuracy. Among the classic heuristics, an important class of
methods is constituted by the improving heuristics, which start from a
feasible solution and seek to improve it. Regarding metaheuristics, they can
be classified in (1)local search, (2) population search and (3) learning
mechanism. The following work falls into the latter category.

###  2.2 The reinforcement learning

Reinforcement learning (RL) is a paradigm of machine learning, along with
supervised learning and unsupervised learning. With regard to the other two
paradigms, RL is the most comparable to human learning due to the fact that
the new knowledge is acquired dynamically through a trial-and-error process.
In order to describe effectively the framework of reinforcement learning, the
following elements must be described: the agent, the environment, the state,
the action, the reward. The agent is the decision maker, who is integrated
into an environment. The state represents the encoding of the position in
which the agent is located. Given a state, the agent can perform several
actions, which cause it to change state. The combination of state and action
results in a reward for the agent. In this framework, the goal of the agent is
to take suitable actions in order to maximize the cumulative reward. When a
model for the environment is present (which means the rules that define the
dynamics of states and state-action-reward combinations are known), RL can be
formalized as a Markov Decision Process. In this context, the goal of
maximizing the cumulative reward can be performed, in theory, using the tools
of dynamic programming ([1]). However, in real world applications, the full
tree of possibilities an agent may encounter cannot be inspected since the
size of the tree would be too large to make the computation feasible. Hence,
the goal of RL becomes to maximize the expected total reward, so that this can
be obtained by inference by sampling a portion of the decision space.

From a formal point of view, we define an episode as an instance to be solved
by a RL algorithm. The episode is composed by $T+1$ steps, indexed by
$t=0,1,...T$. To show the dependency upon the steps, we use the notation
$s_{t}$ for the states, $a_{t}$ for the actions, $r_{t}$ for the reward. In
addition, we define S the set of all possible states, A the set of all
possible actions and $\emph{R}:\emph{S}\times\emph{A}\rightarrow\mathbb{R}$ is
a function that maps from states and actions to rewards. Furthermore, the
policy is identified by the function $\pi(a_{t}|s_{t})$, which represents the
probability of taking the action $a_{t}$ when the state $s_{t}$ is observed.

Then,the objective function to be maximized is the following:

$J=\mathbb{E}_{\pi}\left[\sum_{t=1}^{T}\gamma^{t}r_{t}\right]$ (1)

$\mathbb{E}_{\pi}$ is the expectation of the cumulative discounted reward
according to the policy distribution $\pi$ and $\gamma\in(0,1)$ is the
discounted factor for the future rewards. The formulation of the objective
function (1) doesn’t suggest an intuitive algorithmic approach to solve the
problem, therefore many auxiliary functions have been introduced to quantify
the consequences of the actions taken at a given step.

  * 1.

The state-value function. This function represents goodness of a given state
$s_{t}$ (expressed in terms of expected discounted rewards), according to the
current policy $\pi$. It can be written as follows.

$V_{\pi}(s_{t})=\mathbb{E}_{\pi}\left[\sum_{k=0}^{T-t}\gamma^{k}r_{t+k}|S_{t}=s_{t}\right]\
\ $ (2)

  * 2.

The action-value function. This function represents the quality of taking a
certain action $a_{t}$ in a given state $s_{t}$. Even in this case the quality
is expressed as the expected discounted reward, according to the current
policy $\pi$. It can be written as follows.

$Q_{\pi}(s_{t},a_{t})=\mathbb{E}_{\pi}\left[\sum_{k=0}^{T-t}\gamma^{k}r_{t+k}|S_{t}=s_{t},A_{t}=a_{t}\right]$
(3)

  * 3.

The advantage function. It is a function that measures how much is a certain
action $a_{t}$ a good or bad a certain state $s_{t}$. It returns values
greater than $0$ if $Q_{\pi}(s_{t},a_{t})$ is greater than $V_{\pi}(s_{t})$ It
can be written as follows.

$A(s_{t},a_{t})=Q_{\pi}(s_{t},a_{t})-V_{\pi}(s_{t})$ (4)

Over the course of time, several types of RL algorithms have been introduced
and, according to [7], they can be divided into three groups: actor-only,
critic-only and actor critic methods. The actor-only methods typically
parameterize the policy so that classical optimization procedures can be
performed. The drawback of this class of methods is the high variance in the
estimates of the gradient, leading to slow learning. Among this class, the
main two methods are REINFORCE and Policy Gradient Methods. On the other hand,
Critic-only methods, such as Q-learning and SARSA , approximates the state-
action value function and no explicit function for the policy approximation is
present (See [18]). The actor-critic methods, instead,are characterized by
having the agent separated into two decision entities: the actor and the
critic. The critic approximates the state-value function $\hat{V}(s)$, while
the actor improves the estimate of the stochastic policy $\hat{\pi}$ by taking
into account the critic estimation. The Actor and Critic do not share weights:
therefore, we indicate $\theta$ the weights of the Actor Model and $\omega$
the weights of the Critic model. In order to optimize the eq 1, Actor-Critic
methods use the Policy Gradient theorem [18].The theorem, expressed in the
form of log probabilities, states that:

$\displaystyle\nabla_{\theta}J_{\theta}\propto\mathbb{E}_{\pi}\left[\sum_{a_{t}}\log\nabla_{\pi}(a_{t}|s_{t})A_{\omega}(a_{t},s_{t})\right]$
(5)

This result shows how the gradient depends either by the Actor or the Critic
and suggests an algorithmic approach for solving the problem based on gradient
ascent. An abstract representation of a generic Actor-Critic algorithm is
presented in the figure 2.

Figure 2: Actor Critic framework

The actor-critic approach used in this work is an adaptation of the Proximal
Policy Optimization (PPO) algorithm, more specifically the Adaptive KL Penalty
Coefficient version [17]. According to the method, the actor updates its
parameters through the maximization of the following objective function:

$\displaystyle\max_{\theta}\mathbb{E}_{\pi_{\theta}}\left[\frac{\pi_{\theta}({a_{t}}|{s_{t}})}{\pi_{\theta_{old}}(a_{t}|s_{t})}A_{\omega}(a_{t},s_{t})-\beta
KL(\pi(.|s_{t}),\pi_{old}(.|s_{t}))\right]$ (6)

and the parameter $\beta$ is selected as follows:

  * 1.

Compute $d=\mathbb{E}[KL[\pi(.|s_{t}),\pi_{old}(.|s_{t}]]$

  * 2.

Initialize $d_{targ}$ heuristically

  * 3.

Initialize $\beta$ heuristically

  * 4.

If $d<\frac{d_{targ}}{1.5},\beta\leftarrow\frac{\beta}{2}$;  If
$d>d_{targ}\cdot 1.5,\beta\leftarrow 2\cdot\beta$

The parameters of the Critic, instead, are updated minimizing a mean square
error loss function, which is the following:

$\displaystyle\min_{\omega}\mathbb{E}_{t}\left[V_{\omega}(s_{t})-V_{target}\right]^{2}$
(7)

where $V_{target}$ is the sum of the discounted rewards collected. Hence, a
PPO algorithm works as follows: for each iteration, $N$ parallel roll-outs
composed by $T$ steps are performed,collecting $N\cdot T$ samples. These are
used to update the Actor parameters $\theta$ according to (6) and to update
Critic parameters $\omega$ according to (7) .

Initialize $\theta=\theta_{0}$, $\omega=\omega_{0}$, $\beta=\beta_{0}$;

for  _iteration =1, …, $k$_ do

for  _rollout = 1, …, N_ do

Run policy $\pi_{old}$ in environment for $T$ timesteps

Compute the advantage function estimate $\hat{A}_{1}\dots\hat{A}_{T}$

end for

Update the Actor parameter $\theta$ according to (6)

Update the Critic parameter $\omega$ according to (7)

end for

Algorithm 1 Proximal Policy Optimization

##  3 Vehicle routing problem as a Markov decision Process

In this section, we describe the approach used to model the vehicle routing
problem as a Markov Decision Process (MDP). VRP and combinatorial problems in
general, as already mentioned in the paragraph 2, have been historically
addressed using exact algorithms and heuristics.

The approach used in this paper, despite being based on reinforcement
learning, is inspired by two principles typical of the traditional heuristics:
the improving mechanism and the two stage method. Indeed the VRP can be
divided in two stage: the assignment and the routing. The former consists in
assigning the nodes to a specific cluster (or vehicle). The latter, once the
assignment is performed, consists in determining, for each cluster, the
Hamiltonian cycle defined on the subgraph that contains the cluster nodes. The
idea underlying the Markov Decision Process proposed to model the problem is
the following: starting from a feasible solution, the agent picks a node and
assigns it to another feasible cluster. The reward the agent receives is the
difference between the objective function in two successive assignments. In
other words, the goal of the model is for the agent to learn just an
assignment strategy. The routing part, instead, is performed by a traditional
heuristic procedure, which makes a good estimate of the objective function.

Using the notation introduced in the paragraph 2, let $n$ be the number of
nodes, let $m$ be the number of vehicles (clusters), let $l$ be the number of
features. We define $A\in\mathbb{R}$ n×n the adjacency
matrix,$X\in\\{0,1\\}^{l\times n}$the assignment matrix (which is a boolean
matrix where the element $x_{i_{v}}=1$ if and only if the node $i$ is assigned
to the cluster $v$). In addition, let $D\in\mathbb{R}$ l×n the demand matrix
,$Q\in\mathbb{R}$ l×m the capacity matrix. In conclusion $y\in\mathbb{R}$ m is
the vector containing the approximated cost of each cluster. When we mention
the cost of a cluster, we refer to the cost of the optimal solution of a
Travelling Salesman Problem (TSP), having as nodes those of that specific
cluster. However, as already mentioned in the paragraph 2, finding the cost of
a TSP is a NP-Hard problem. For this reason, $y_{v}$, which is the
approximation of the cost of the cluster $v$, is computed using a traditional
approximate heuristic (Christofides [4]), which guarantees a good upper bound
(not worse than $\frac{3}{2}$ the optimal solution) computed efficiently. The
role of the $y$ variable, in fact, is to provide an estimate of the quality of
a given cluster, and so it is not necessary to solve the TSP to the optimum.

After having introduced the basic notation, we can characterize the finite MDP
for the VRP using the tuple
$(\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{P})$, where $\mathcal{S}$ is
the set of states, $\mathcal{A}$ the set of actions,
$\mathcal{R}:\mathcal{S}\times\emph{A}\rightarrow\mathbb{R}$ is the reward
function and $\mathcal{P}:\mathcal{S}\times\emph{A}\rightarrow\mathcal{S}$ the
transition function. The state $s_{t}\in\mathcal{S}$ captures all the relevant
information regarding the current iteration, in order to respect the Markov
Property and to have a fully observable system state. In addition, the state
has the role of providing the agent all the relevant information about the
problem, so that he can learn a strategy based on the peculiar structure of
the problem. In this specific setting, the state $s_{t}$ is a tuple defined as
$s_{t}=(A,X_{t},y_{t},D,Q)$. The adjacency matrix, as well as the demand and
the capacity matrix, are not indexed by the iteration $t$ since their values
are independent of the assignment chosen. Given a state $s_{t}$, the agent
performs the action $a_{t}$, which is made up of two consecutive steps: first,
the agent picks a node other than the depot, then it assigns the chosen node
to a feasible cluster, meaning that the new assignment must satisfy the
capacity constraints. We suppose the agent chooses to move the node $j$ to the
cluster $k$. Then, the next state $s_{t+1}$ is given by the tuple
$s_{t+1}=(A,X_{t+1},y_{t+1},D,Q)$. As we mentioned before, $A,D,Q$ do not vary
from one iteration to the next. Instead $x_{iv}^{t+1}$, which is a generic
element of the assignment matrix is given by:

$x_{iv}^{t+1}=\left\\{\begin{array}[]{cr}x_{iv}^{t}\text{ if }i\neq j\cap
v\neq k\text{ or if }x_{jk}^{t}=1\\\ 1\text{ if }i=j\cap v=k\\\ 0\text{ if
}i=j\cap v\neq k\end{array}\right.$ (8)

Similarly, ${y_{v}}^{t+1}$ is the approximated cost of the optimal solution of
a TSP, having as nodes those of the cluster $v$, related to the assignment
${X}^{t+1}$. In conclusion, the reward $r^{t+1}$ is obtained as the difference
between the approximated cost of the VRP in the successive two states, which
means:

$r^{t+1}=\sum_{v=1}^{m}{y_{v}}^{t+1}-{y_{v}}^{t}$ (9)

##  4 Agents deep models

In this section, we describe the neural network architecture behind the deep
reinforcement learning algorithm proposed. Since the method proposed belongs
to the actor-critic class, two networks need to be specified: the actor for
estimating the policy $\pi_{\theta(s_{t})}$ and the critic for estimating the
state-value function $V_{\omega}(s_{t})$. In this specific setting, the actor
does not perform a single action, but two consequential actions: the choice of
the node and then the choice of the cluster. For this reason, the neural
architecture for estimating the policy $\pi_{\theta}(s_{t})$ is composed by
two different neural networks, that we have named respectively Actor 1 and
Actor 2. Hence, Actor 1 estimates $\pi_{{\theta}_{1}(s_{t})}$, which
represents the probability of choosing every node given the state $s_{t}$.
Once the generic node $i$ is chosen according to $\pi_{{\theta}_{1}(s_{t})}$,
Actor 2 estimates $\pi_{{\theta}_{2}(s_{t}|node=i)}$, which is the probability
of assigning every cluster to the node i. Regarding the weights of the two
networks, we used the notation $\theta_{1}$ for Actor 1 and $\theta_{2}$ for
Actor 2 to emphasize that the two deep neural networks do not share
parameters. The neural architecture proposed has the aim of being flexible to
the size of the VRP instance. In fact, according to the state defined in the
paragraph 3, the size of the matrices $(A,X_{t},y_{t},D,Q)$ varies among
different instances since every problem differs in the number of nodes,
clusters and features. This difficulty is typical of problems whose inputs can
be represented as graphs. In fact, graphs nodes, in contrast to pixel images,
do not have a fixed number of neighboring units nor the spatial order among
them is fixed [19]. For this reason, in recent years, many architecture
belonging to geometric deep leaning [3] and graph convolution neural networks
(GCNN)[19] have been proposed to tackle the peculiarity of the graph
structure. However,the target problem, as mentioned in the paragraph 2, is
characterized by having a complete graph $G$. As a consequence, the adjacency
matrix $A$ is dense and its structure is similar to a pixel image, if $A$ is
appropriately scaled. In this context, a classical Convolutional Neural
Network(CNN) with a flexible padding dimension can be used, and is indeed the
approach followed in this paper.

Figure 3: The Actor Model

The Actor 1 model is composed by a deep Convolutional neural network (CNN),
followed by a Softmax function. The CNN takes as input all the elements of the
state $s_{t}$ apart from the vector $y_{t}$ and it produces as output the
embedded matrix $\bar{H^{t}}\in\mathbb{R}$ m×n, which represents the encoding
of all the relevant information about the problem in a given iteration $t$.
Then, the matrix $\bar{H^{t}}$ is collapsed within a column vector of
dimension $n$ and the Softmax function is applied to obtain
$\pi_{{\theta}_{1}(s_{t})}$. Afterwards, a node is chosen according to
$\pi_{{\theta}_{1}(s_{t})}$. We introduce the incidence vector
${h_{1}}^{t}\in\\{0,1\\}^{n}$, whose elements are all $0$, apart from the one
relative to the node chosen. At this stage the Actor 2, which is composed by a
CNN, followed by a Softmax function as well, takes as input the couple
$(h_{1}^{t},\bar{H^{t}})$. The CNN produces as output another embedded matrix
$\hat{H^{t}}\in\mathbb{R}$ m×n.Then, similarly to Actor 1, the matrix is
collapsed within a columns vector of dimension $m$ and the Softmax function is
applied to obtain $\pi_{{\theta}_{2}(s_{t})}$. At this regard, we point out
that, before applying the Softmax function, a mask is applied to force Actor 2
to choose a feasible cluster. A graphic abstract representation of the Actor
model is reported in figure 3. Lastly, the Critic, figure 4, is composed by a
deep CNN as well. It takes as input the tuple
$(y^{t},\bar{H^{t}},\hat{H^{t}})$, it performs convolution operations, as well
as simple matrix operations. The output of these operations is a matrix, that
is collapsed within a scalar output through simple sum operations. The
complete representation of the neural networks are reported in the appendix.

Figure 4: The Critic Model

##  5 RL Algorithm

In this section we describe in detail the reinforcement learning algorithm
proposed. As already mentioned in the paragraph 2, it is an adaptation of the
Proximal Policy Optimization (PPO) algorithm, more specifically the Adaptive
KL Penalty Coefficient version.

The proposed algorithm is of the improvement type, meaning that the agent has
the goal of improving a starting feasible solution. Therefore, the task the
agent has to perform does not have a terminal state since improving a solution
is a process that lasts until the optimum is found, and it is impossible given
a solution to verify whether it is really the optimum. For this reason, the
task belongs to the so called non episodic or continuous task. However,we can
turn it into an episodic task if we consider an episode as a fixed small
number of steps $T$ in which the agent has to take actions to improve his
current state. In this way, each episode does have a terminal state, which
corresponds to the state $s_{T}$. Differently from the ”real” episodic tasks,
in our case the terminal state does not have a specific meaning within the
problem. Therefore, also the reward $r_{T}$ does not have a particular role if
compared to the rewards to the previous steps. For this decision, the choice
we made is to store, for each roll-out, only the advantage function at the
first step $\hat{A}_{1}$. A detailed description of the algorithm, in term of
pseudo-code is reported below (Algorithm 2).

Choose the hyperparameters ${\text{learning
rate}}_{\text{actor}},{\text{learning
rate}}_{\text{critic}},{epochs}_{actor},{epochs}_{critic}$

Initialize $\theta=\theta_{0}$, $\omega=\omega_{0}$, $\beta=\beta_{0}$

Given a feasible initial solution compute $s_{0}=(A,X_{0},y_{0},D,Q)$

Initialize two empty buffer $B_{iteration},B_{rollout}$

for  _iteration =1, …, $k$_ do

for  _rollout = 1, …, N_ do

Clear buffer $B_{rollout}$

for  _steps = 1, …, T_ do

Run $\pi_{{\theta_{1_{t}}}(s_{t})}$

Choose the node according to $\pi_{{\theta_{1}}(s_{t})}$: so compute the
incidence vector $h_{1_{t}}$

Retrieve the matrix $\bar{H_{t}}$

Run $\pi_{\theta_{2_{t}|{h_{1_{t}}}}}(s_{t})$

Choose the cluster according to $\pi_{{\theta_{2}}(s_{t})}$: so compute
$h_{2_{t}}$

Compute
$\pi(s_{t})=\pi_{\theta_{1_{t}}}(s_{t})\cdot\pi_{\theta_{2_{t}}|h_{1_{t}}}(s_{t})$

Retrieve the matrix $\hat{H_{t}}$

Compute the state-value Function $V_{\omega_{t}}(s_{t})$

Compute the reward $r_{t}$

end for

Compute the advantage function estimate
$\hat{A}_{1}=\sum_{t=1}^{T}\gamma^{t}r_{t}-V_{\omega_{1}}(s_{1})$

Store $\pi(s_{1})$, $\bar{H_{1}}$, $\hat{H_{1}}$, $\hat{A}_{1}$ in the buffer
$B_{rollout}$

end for

Store the content of $B_{rollout}$ in $B_{iteration}$

Update the Actor parameter $\theta_{1}$ and $\theta_{2}$ according to (6),
using data retrieved from $B_{iteration}$

Update the Critic parameter $\omega$ according to (7) using data retrieved
from $B_{iteration}$

Clear buffer $B_{iteration}$

end for

Algorithm 2 Proximal Policy Optimization for VRP

##  6 Computational Experience

In this section we describe the computational experiments performed on VRP
instances. The main goals of the experiments are showing that the algorithm
proposed has learning capabilities (i.e.the agent can learn strategies to
decrease the objective function) and that the model, trained on a training
set, has generalization capabilities on the test set. In addition, we want to
show the comparison between the quality of the performance obtained and the
ones concerning the state of the art solver for Combinatorial optimization
heuristics, which is $OR-TOOLS$ (https://developers.google.com/optimization).
The numerical tests were carried out in two stages.

-During the first stage, we generated training and test instances belonging to three classes with different characteristics to evaluate the behavior of the algorithm in specific situations. During this stage, for each class of instances, we compared the performances of the algorithm proposed with the $OR-TOOLS$ Methaheuristic TABOO SEARCH in terms of value of the objective function returned. We point out that the comparison was performed for different problem dimensions. Hence, for each class of instances and for every dimension, we computed the average of the objective function returned for $10$ instances. In conclusion, the run time of the two algorithms was not a matter of comparison; so we conducted the tests using the same run time for the two algorithms. The three classes of instances are the following:

  * C1

In this class there is only one feature and the capacity of each vehicle
related to that feature is $\infty$. In addition, we suppose the nodes are
uniformly distributed in the two-dimensional space; more specifically we
suppose $x_{i}\sim\mathcal{U}_{[0,100]\times[0,100]}$. The depot is located at
the centre, in the position of coordinates $(50;50)$ (Figure 6(a)). The reason
underlying this class of instances is to show the performances of the
algorithm without the complexity of the capacity constraints.

  * C2

In this class there is only one feature, the capacity of each vehicle is the
same and the nodes are arranged in two separate clusters , with the depot in
the middle between the two (Figure 5(b)).The reason underlying this class of
instances is to verify if the algorithm is able to recognise a specific
pattern and identify a proper assigning strategy.

  * C3

In this class there is only one feature, the capacity of each vehicle is the
same and the nodes are uniformly distributed in the two-dimensional space,i.e.
$x_{i}\sim\mathcal{U}_{[0,100]\times[0,100]}$. The depot is located at the
centre, in the position of coordinates $(50;50)$ (Figure 6(a)).The reason
underlying this class of instances is to verify if the algorithm is able to
identify a proper assigning strategy in a more generic setting.

(a) Uniform configuration

(b) Two clusters configuration

Figure 5: Different types of nodes configuration.

As shown in the table 1, the class of instances in which the algorithm
performs the best is the class C1. In fact, for this class of instances,it
provides a solution, which is only about $20-25\%$ worse than the one provided
by the solver $OR-TOOLS$ with the same run time. Regarding the other two class
of instances, the gap between the algorithms grows in favor of $OR-TOOLS$
solver. However, we want to show that, even if the solution returned is much
worse, the algorithm does learn a strategy (i.e. the objective function
decreases, see figure 6).

Number of nodes | Number of vehicles | Run time | OR-TOOLS | Reinforcement learning
---|---|---|---|---
Between 30 and 40 | Between 3 and 4 | 30 seconds | 501.30 | 629.20
Between 60 and 70 | Between 5 and 6 | 60 seconds | 665.0 | 821.80
(a) Performance on the class of instances C1

Number of nodes | Number of vehicles | Run time | OR-TOOLS | Reinforcement learning
---|---|---|---|---
Between 30 and 40 | Between 3 and 4 | 30 seconds | 313.90 | 878.60
Between 60 and 70 | Between 5 and 6 | 60 seconds | 359.00 | 1410.69
(b) Performance on the class of instances C3

Number of nodes | Number of vehicles | Run time | OR-TOOLS | Reinforcement learning
---|---|---|---|---
Between 30 and 40 | Between 3 and 4 | 30 seconds | 506.20 | 907.30
Between 60 and 70 | Between 5 and 6 | 60 seconds | 719.60 | 1637.40
(c) Performance on the class of instances C3

Table 1: Comparison of the performance with $OR-TOOLS$ solver

(a) Objective function decrease in the case C1

(b) Objective function decrease in the case C3

Figure 6: Decrease of the objective function for different configurations.

-During the second stage, we performed the training and test process on another class of instances, retrieved from the repository $CVRPLIB$, which is the state of the art repository for the Capacitated vehicle routing problem. In fact, it contains instances regarding real distribution problems. Among all the instances present there, we picked 85 of them for the training and 15 for the test. During this stage the goal of the experiments is not to compare the performance of the algorithm proposed with the $OR-TOOLS$ solver, but rather to show that the model proposed has learning capabilities even with real instances. At this regard, we show a figure(See 7) regarding the behavior of the algorithm on the test set, in terms of value of the objective function throughout the iterations.

Figure 7: Objective function decrease in the case of $CVRPLIB$ instances

In conclusion, the computational experience shows that the algorithm does
learn strategies to improve the objective function, but the results produced
are still far from the ones produced by the solver $OR-TOOLS$. However,there
are future research perspectives for the work proposed. These mainly concern
the use of graph neural networks instead of convolutional neural networks and
the possibility of the inclusion of a neural network for estimating the cost
of each TSP.

##  7 Conclusions

In this paper we investigated how to solve the Capacitated Vehicle routing
Problem through Deep Reinforcement learning. Although we applied a different
approach compared to the traditional one, we were inspired by two classic
principles of VRP heuristics: the improving mechanism and the two stage
method. At this regard, the aim of the work was to build an improving
algorithm capable of learning the assignment part of the VRP for a wide class
of instances.

We firstly formulated the CVRP as a Markov Decision Process (MDP), identifying
for the specific problem the tuple
$(\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{P})$. After that, we included
the MDP identified in a RL algorithm. We decided to use, as algorithms, an
adaptation of the PPO method, which belong to the class of Actor-Critic. In a
second phase we addressed the problem of which typology of neural architecture
to use for the Actor and Critic respectively. The neural networks selected
were supposed to have at least two fundamental characteristics: as first, they
were supposed to be flexible to the input dimension. In addition, they were
supposed to take advantage of the particular structure of the input, namely
that of a complete graph. For this reason, the neural architecture chosen is
made of Convolutional deep neural networks with a flexible padding dimension.
In conclusion the last part is about computational results. the primary goal
of this part was to show that an improving deep reinforcement learning
algorithm for the VRP is possible, i.e. the algorithm proposed has learning
capabilities. In addition, we showed the comparison between the results
obtained and the ones obtained through $OR-TOOLS$ solver. The comparison shows
how $OR-TOOLS$ solver still guarantees better results in terms of solution
returned. However, there are future research perspectives for the work
proposed. These mainly concern the inclusion of a neural network for
estimating the cost of each TSP, instead of using the Christofides algorithm
and the use of graph neural networks instead of convolutional neural networks.

## References

  * Bellman, [1966] Bellman, R. (1966).  Dynamic programming.  Science, 153(3731):34–37.
  * Braekers et al., [2016] Braekers, K., Ramaekers, K., and Van Nieuwenhuyse, I. (2016).  The vehicle routing problem: State of the art classification and review.  Computers & Industrial Engineering, 99:300–313.
  * Bronstein et al., [2017] Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., and Vandergheynst, P. (2017).  Geometric deep learning: going beyond euclidean data.  IEEE Signal Processing Magazine, 34(4):18–42.
  * Christofides, [1976] Christofides, N. (1976).  Worst-case analysis of a new heuristic for the travelling salesman problem.  Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group.
  * Clarke and Wright, [1964] Clarke, G. and Wright, J. W. (1964).  Scheduling of vehicles from a central depot to a number of delivery points.  Operations research, 12(4):568–581.
  * Dantzig and Ramser, [1959] Dantzig, G. B. and Ramser, J. H. (1959).  The truck dispatching problem.  Management science, 6(1):80–91.
  * Grondman et al., [2012] Grondman, I., Busoniu, L., Lopes, G. A., and Babuska, R. (2012).  A survey of actor-critic reinforcement learning: Standard and natural policy gradients.  IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(6):1291–1307.
  * Jünger et al., [1995] Jünger, M., Reinelt, G., and Rinaldi, G. (1995).  The traveling salesman problem.  Handbooks in operations research and management science, 7:225–330.
  * Khalil et al., [2017] Khalil, E., Dai, H., Zhang, Y., Dilkina, B., and Song, L. (2017).  Learning combinatorial optimization algorithms over graphs.  Advances in neural information processing systems, 30.
  * Kool et al., [2018] Kool, W., Van Hoof, H., and Welling, M. (2018).  Attention, learn to solve routing problems!  arXiv preprint arXiv:1803.08475.
  * Laporte, [2007] Laporte, G. (2007).  What you should know about the vehicle routing problem.  Naval Research Logistics (NRL), 54(8):811–819.
  * LeCun et al., [2015] LeCun, Y., Bengio, Y., and Hinton, G. (2015).  Deep learning.  nature, 521(7553):436–444.
  * Lin et al., [2014] Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., and Lam, H. (2014).  Survey of green vehicle routing problem: past and future trends.  Expert systems with applications, 41(4):1118–1138.
  * Lu et al., [2019] Lu, H., Zhang, X., and Yang, S. (2019).  A learning-based iterative method for solving vehicle routing problems.  In International conference on learning representations.
  * Nazari et al., [2018] Nazari, M., Oroojlooy, A., Snyder, L., and Takác, M. (2018).  Reinforcement learning for solving the vehicle routing problem.  Advances in neural information processing systems, 31.
  * Papadimitriou and Steiglitz, [1977] Papadimitriou, C. H. and Steiglitz, K. (1977).  On the complexity of local search for the traveling salesman problem.  SIAM Journal on Computing, 6(1):76–83.
  * Schulman et al., [2017] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017).  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347.
  * Sutton and Barto, [2018] Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Zhang et al., [2019] Zhang, S., Tong, H., Xu, J., and Maciejewski, R. (2019).  Graph convolutional networks: a comprehensive review.  Computational Social Networks, 6(1):1–23.

## Appendix

### Hyper-parameters setting

Actor Optimizer | Adam
---|---
Actor Learning Rate | $1\times 10^{-5}$
Critic Optimizer | Adam
Critic Learning Rate | $1\times 10^{-5}$
Number of Kernels of CNN | 27
Number of output channel of CNN | 4

### Detailed neural architectures

Figure 8: The Actor 1 model Figure 9: The Actor 2 Model Figure 10: The Critic
complete model


* [3] J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami, “Internet of Things (IoT): A Vision, Architectural Elements, and Future Directions,” _Future Generation Computer Systems_ , vol. 29, no. 7, pp. 1645 – 1660, 2013\.
  * [4] A. Bouguettaya, Q. Z. Sheng, B. Benatallah, A. G. Neiat, S. Mistry, A. Ghose, S. Nepal, and L. Yao, “An Internet of Things Service Roadmap,” _Communication of the ACM_ , vol. 64, no. 9, p. 86–95, 2021.
  * [5] M. Sheng, Y. Qin, L. Yao, and B. Benatallah, Eds., _Managing the Web of Things: Linking the Real World to the Web_. Morgan Kaufmann, 2017.
  * [6] X. Yang, X. Wang, X. Li, D. Gu, C. Liang, K. Li, G. Zhang, and J. Zhong, “Exploring Emerging IoT Technologies in Smart Health Research: A Knowledge Graph Analysis,” _BMC Medical Informatics and Decision Making_ , vol. 20, p. 260, 2020.
  * [7] Y. A. Qadri, A. Nauman, Y. B. Zikria, A. V. Vasilakos, and S. W. Kim, “The Future of Healthcare Internet of Things: A Survey of Emerging Technologies,” _IEEE Communications Surveys Tutorials_ , vol. 22, no. 2, pp. 1121–1167, 2020.
  * [8] Y. Mehmood, F. Ahmad, I. Yaqoob, A. Adnane, M. Imran, and S. Guizani, “Internet-of-Things-Based Smart Cities: Recent Advances and Challenges,” _IEEE Communications Magazine_ , vol. 55, no. 9, pp. 16–24, 2017.
  * [9] Y. Qian, D. Wu, W. Bao, and P. Lorenz, “The Internet of Things for Smart Cities: Technologies and Applications,” _IEEE Network_ , vol. 33, no. 2, pp. 4–5, 2019.
  * [10] M. Alaa, A. Zaidan, B. Zaidan, M. Talal, and M. Kiah, “A Review of Smart Home Applications Based on Internet of Things,” _Journal of Network and Computer Applications_ , vol. 97, pp. 48–65, 2017.
  * [11] A. Zaidan and B. Zaidan, “A Review on Intelligent Process for Smart Home Applications Based on IoT: Coherent Taxonomy, Motivation, Open Challenges, and Recommendations,” _Artificial Intelligence Review_ , vol. 53, no. 1, pp. 141–165, 2020.
  * [12] P. K. R. Maddikunta, S. Hakak, M. Alazab, S. Bhattacharya, T. R. Gadekallu, W. Z. Khan, and Q. V. Pham, “Unmanned Aerial Vehicles in Smart Agriculture: Applications, Requirements, and Challenges,” _IEEE Sensors Journal_ , vol. 21, no. 16, pp. 17 608–17 619, 2021.
  * [13] M. Pathan, N. Patel, H. Yagnik, and M. Shah, “Artificial Cognition for Applications in Smart Agriculture: A Comprehensive Review,” _Artificial Intelligence in Agriculture_ , vol. 4, pp. 81–95, 2020.
  * [14] Q. Z. Sheng, X. Li, and S. Zeadally, “Enabling Next-Generation RFID Applications: Solutions and Challenges,” _Computer_ , vol. 41, no. 9, pp. 21–28, 2008.
  * [15] W. Abdelghani, C. A. Zayani, I. Amous, and F. Sèdes, “Trust Management in Social Internet of Things: A Survey,” in _16th International Conference on e-Business, e-Services and e-Society_ , 2016, pp. 430–441.
  * [16] M. R. Rashmi and C. V. Raj, “A Review on Trust Models of Social Internet of Things,” in _Emerging Research in Electronics, Computer Science and Technology_. Springer Singapore, 2019, pp. 203–209.
  * [17] F. Amin, A. Ahmad, and G. Sang Choi, “Towards Trust and Friendliness Approaches in the Social Internet of Things,” _Applied Sciences_ , vol. 9, no. 1, p. 166, 2019.
  * [18] R. M.S., S. Pattar, R. Buyya, V. K.R., S. Iyengar, and L. Patnaik, “Social Internet of Things (SIoT): Foundations, Thrust Areas, Systematic Review and Future Directions,” _Computer Communications_ , vol. 139, pp. 32 – 57, 2019\.
  * [19] R. K. Chahal, N. Kumar, and S. Batra, “Trust Management in Social Internet of Things: A Taxonomy, Open Issues, and Challenges,” _Computer Communications_ , vol. 150, pp. 13 – 46, 2020.
  * [20] W. Z. Khan, Q.-u.-A. Arshad, S. Hakak, M. K. Khan, and Saeed-Ur-Rehman, “Trust Management in Social Internet of Things: Architectures, Recent Advancements, and Future Challenges,” _IEEE Internet of Things Journal_ , vol. 8, no. 10, pp. 7768–7788, 2021.
  * [21] “Statista, Internet of Things (IoT) connected devices installed base worldwide from 2015 to 2025,” https://www.statista.com/statistics/471264/iot -number-of-connected-devices-worldwide/, accessed: 2020-04-15.
  * [22] M. Torchia, M. Kumar, and V. Turner, “Worldwide Semiannual Internet of Things Spending Guide,” _International Data Corporation (IDC)_ , 2017.
  * [23] J. Manyika, M. Chui, P. Bisson, J. Woetzel, R. Dobbs, J. Bughin, and D. Aharon, “The Internet of Things: Mapping the value beyond the hype.” McKinsey Global Institute, 2015.
  * [24] S. A. Hamad, Q. Z. Sheng, W. E. Zhang, and S. Nepal, “Realizing an Internet of Secure Things: A Survey on Issues and Enabling Technologies,” _IEEE Communications Surveys Tutorials_ , vol. 22, no. 2, pp. 1372–1391, 2020.
  * [25] R. Van Kranenburg and S. Dodson, _The Internet of Things: A Critique of Ambient Technology and the All-seeing Network of RFID_ , ser. Network notebooks. Institute of Network Cultures, 2008.
  * [26] W. E. Zhang, Q. Z. Sheng, A. Mahmood, D. H. Tran, M. Zaib, S. A. Hamad, A. Aljubairy, A. A. F. Alhazmi, S. Sagar, and C. Ma, “The 10 Research Topics in the Internet of Things,” in _IEEE 6th International Conference on Collaboration and Internet Computing (CIC)_ , 2020, pp. 34–43.
  * [27] S. C. Mukhopadhyay and N. K. Suryadevara, _Internet of Things: Challenges and Opportunities_. Cham: Springer International Publishing, 2014, pp. 1–17.
  * [28] E. Sisinni, A. Saifullah, S. Han, U. Jennehag, and M. Gidlund, “Industrial Internet of Things: Challenges, Opportunities, and Directions,” _IEEE Transactions on Industrial Informatics_ , vol. 14, no. 11, pp. 4724–4734, 2018\.
  * [29] A. R. Khan, Q. F. Hassan, and S. Madani, _Internet of Things: Challenges, Advances, and Applications_. Chapman and Hall/CRC, 01 2018.
  * [30] J. Kleinberg, “Navigation in a Small World,” _Nature_ , vol. 406, p. 845, 2000.
  * [31] J. Kleinberg, “Small-World Phenomena and the Dynamics of Information,” in _Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic_ , ser. NIPS’01, 2001, p. 431–438.
  * [32] M. Kranz, L. Roalter, and F. Michahelles, “Things That Twitter: Social Networks and the Internet of Things,” in _8th International conference on Pervasive Computing (PERCOM)_ , 2010.
  * [33] D. Guinard, M. Fischer, and V. Trifa, “Sharing using Social Networks in a Composable Web of Things,” in _8th IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops)_ , 2010, pp. 702–707.
  * [34] H. Ning and Z. Wang, “Future Internet of Things Architecture: Like Mankind Neural System or Social Organization Framework?” _IEEE Communications Letters_ , vol. 15, no. 4, pp. 461–463, 2011.
  * [35] L. E. Holmquist, F. Mattern, B. Schiele, P. Alahuhta, M. Beigl5, and H.-W. Gellersen, “Smart-Its Friends: A Technique for Users to Easily Establish Connections between Smart Artefacts,” in _3rd International Conference on Ubiquitous Computing (Ubicomp)_ , 2001, pp. 116–122.
  * [36] L. Atzori, A. Iera, and G. Morabito, “SIoT: Giving a Social Structure to the Internet of Things,” _IEEE Communications Letters_ , vol. 15, pp. 1193–1195, 2011.
  * [37] L. Atzori, A. Iera, G. Morabito, and M. Nitti, “The Social Internet of Things (SIoT) – When Social Networks Meet the Internet of Things: Concept, Architecture, and Network Characterization,” _Computer Networks_ , vol. 56, no. 16, pp. 3594 – 3608, Nov 2012.
  * [38] M. Nitti, L. Atzori, and I. Pletikosa, “Network Navigability in the Social Internet of Things,” in _IEEE World Forum on Internet of Things, WF-IoT_ , 2014, pp. 405–410.
  * [39] Z. Cai, Z. He, X. Guan, and Y. Li, “Collective Data-Sanitization for Preventing Sensitive Information Inference Attacks in Social Networks,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 15, no. 4, pp. 577–590, 2018.
  * [40] L. Nie, Y. Wu, X. Wang, L. Guo, G. Wang, X. Gao, and S. Li, “Intrusion Detection for Secure Social Internet of Things Based on Collaborative Edge Computing: A Generative Adversarial Network-Based Approach,” _IEEE Transactions on Computational Social Systems_ , pp. 1–12, 2021.
  * [41] X. Fan, L. Liu, R. Zhang, Q. Jing, and J. bi, “Decentralized Trust Management: Risk Analysis and Trust Aggregation,” _ACM Computing Surveys (CSUR)_ , vol. 53, pp. 1–33, 02 2020.
  * [42] M. N. Ba-hutair, A. Bouguettaya, and A. Ghari Neiat, “Multi-Perspective Trust Management Framework for Crowdsourced IoT Services,” _IEEE Transactions on Services Computing_ , pp. 1–1, 2021.
  * [43] A. I. A. Ahmed, S. H. Ab Hamid, A. Gani, S. khan, and M. K. Khan, “Trust and Reputation for Internet of Things: Fundamentals, Taxonomy, and Open Research Challenges,” _Journal of Network and Computer Applications_ , vol. 145, p. 102409, 2019.
  * [44] G. Fortino, L. Fotia, F. Messina, D. Rosaci, and G. M. L. Sarné, “Trust and Reputation in the Internet of Things: State-of-the-Art and Research Challenges,” _IEEE Access_ , vol. 8, pp. 60 117–60 125, 2020\.
  * [45] A. Sharma, E. S. Pilli, A. P. Mazumdar, and P. Gera, “Towards Trustworthy Internet of Things: A Survey on Trust Management Applications and Schemes,” _Computer Communications_ , vol. 160, pp. 475–493, 2020.
  * [46] P. Mendes and P. P. Mendes, “Social-driven Internet of Connected Objects,” in _Internet Architecture Board (IAB) workshop on Interconnecting Smart Objects with the Internet_ , 2011.
  * [47] O. Voutyras, P. Bourelos, D. Kyriazis, and T. Varvarigou, “An Architecture Supporting Knowledge Flow in Social Internet of Things Systems,” in _IEEE 10th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)_ , 2014, pp. 100–105.
  * [48] A. M. Ortiz, D. Hussein, S. Park, S. Han, and N. Crespi, “The Cluster Between Internet of Things and Social Networks: Review and Research Challenges,” _IEEE Internet of Things Journal_ , vol. 1, pp. 206–215, 06 2014.
  * [49] Y. Li, Y. Huang, M. Zhang, and L. Rajabion, “Service Selection Mechanisms in the Internet of Things (IoT): a Systematic and Comprehensive Study,” _Cluster Computing_ , vol. 23, pp. 1–21, 2020.
  * [50] D. Zhang, L. T. Yang, and H. Huang, “Searching in Internet of Things: Vision and Challenges,” in _IEEE 9th International Symposium on Parallel and Distributed Processing with Applications_ , 2011, pp. 201–206.
  * [51] R. Abdul, A. Paul, J. Gul M, W.-H. Hong, H. Seo _et al._ , “Exploiting Small World Problems in a SIoT Environment,” _Energies_ , vol. 11, no. 8, p. 2089, 2018.
  * [52] F. Amin, R. Abbasi, A. Rehman, and G. S. Choi, “An Advanced Algorithm for Higher Network Navigation in Social Internet of Things Using Small-World Networks,” _Sensors_ , vol. 19, pp. 1–20, 04 2019.
  * [53] M. Nitti, L. Atzori, and I. P. Cvijikj, “Friendship Selection in the Social Internet of Things: Challenges and Possible Strategies,” _IEEE Internet of Things Journal_ , vol. 2, no. 3, pp. 240–247, 2015.
  * [54] M. Nitti, R. Girau, L. Atzori, and S. Member, “Trustworthiness Management in the Social Internet of Things,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 26, no. 5, pp. 1253–1266, 2014.
  * [55] S. Pattar, R. Buyya, K. R. Venugopal, S. S. Iyengar, and L. M. Patnaik, “Searching for the IoT Resources: Fundamentals, Requirements, Comprehensive Review, and Future Directions,” _IEEE Communications Surveys and Tutorials_ , vol. 20, no. 3, pp. 2101–2132, 2018.
  * [56] D. Hussein, S. Han, G. M. Lee, N. Crespi, and E. Bertin, “Towards a Dynamic Discovery of Smart Services in the Social Internet of Things,” _Computers & Electrical Engineering, Elsevier_, vol. 58, pp. 429–443, 2017\.
  * [57] A. Khanfor, H. Ghazzai, Y. Yang, M. R. Haider, and Y. Massoud, “Automated Service Discovery for Social Internet-of-Things Systems,” in _IEEE International Symposium on Circuits and Systems (ISCAS)_ , 2020, pp. 1–5.
  * [58] V. Mohammadi, A. M. Rahmani, A. Darwesh, and A. Sahafi, “Trust-based Friend Selection Algorithm for navigability in social Internet of Things,” _Knowledge-Based Systems_ , vol. 232, p. 107479, 2021.
  * [59] M. Zhang, H. Zhao, R. Zheng, Q. Wu, and W. Wei, “Cognitive Internet of Things: Concepts and Application Example,” _International Journal of Computer Science Issues (IJCSI)_ , vol. 9, no. 6, p. 151, 2012.
  * [60] W. Mardini, Y. Khamayseh, and M. H. Khatatbeh, “Genetic Algorithm for Friendship Selection in Social IoT,” in _International Conference on Engineering MIS (ICEMIS)_ , 2017, pp. 1–4.
  * [61] A. Aljubairy, W. E. Zhang, Q. Z. Sheng, and A. Alhazmi, “Siotpredict: A framework for predicting relationships in the social internet of things,” in _Advanced Information Systems Engineering_ , 2020, pp. 101–116.
  * [62] R. Hardin, “Trust: A Sociological Theory,” _Economics and Philosophy_ , vol. 18, pp. 183–204, 04 2002.
  * [63] B. R. Schlenker, B. Helm, and J. T. Tedeschi, “The Effects of Personality and Situational Variables on Behavioral Trust,” _Journal of personality and social psychology_ , vol. 25, no. 3, p. 419, 1973.
  * [64] R. M. Morgan and S. D. Hunt, “The Commitment-Trust Theory of Relationship Marketing,” _Journal of Marketing_ , vol. 58, no. 3, pp. 20–38, 1994.
  * [65] A. Mahmood, S. A. Siddiqui, W. E. Zhang, and Q. Z. Sheng, “A Hybrid Trust Management Model for Secure and Resource Efficient Vehicular Ad hoc Networks,” in _IEEE 20th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT)_ , 2019, pp. 154–159.
  * [66] A. Mahmood, S. A. Siddiqui, Q. Sheng, W. E. Zhang, H. Suzuki, and W. Ni, “Trust on wheels: Towards secure and resource efficient IoV networks,” _Computing_ , pp. 1–22, 2022.
  * [67] Z. Movahedi, Z. Hosseini, F. Bayan, and G. Pujolle, “Trust-Distortion Resistant Trust Management Frameworks on Mobile Ad Hoc Networks: A Survey,” _IEEE Communications Surveys and Tutorials_ , vol. 18, no. 2, pp. 1287–1309, 2016.
  * [68] R. Hussain, J. Lee, and S. Zeadally, “Trust in VANET: A Survey of Current Solutions and Future Research Opportunities,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 22, no. 5, pp. 2553–2571, 2021.
  * [69] X. Meng and D. Liu, “GeTrust: A Guarantee-Based Trust Model in Chord-Based P2P Networks,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 15, no. 1, pp. 54–68, 2018.
  * [70] S. M. Ghafari, A. Beheshti, A. Joshi, C. Paris, A. Mahmood, S. Yakhchi, and M. A. Orgun, “A Survey on Trust Prediction in Online Social Networks,” _IEEE Access_ , vol. 8, pp. 144 292–144 309, 2020.
  * [71] Y. Cen, J. Zhang, G. Wang, Y. Qian, C. Meng, Z. Dai, H. Yang, and J. Tang, “Trust Relationship Prediction in Alibaba E-Commerce Platform,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 32, no. 5, pp. 1024–1035, 2020.
  * [72] A. Mahmood, Q. Z. Sheng, S. A. Siddiqui, S. Sagar, W. E. Zhang, H. Suzuki, and W. Ni, “When Trust Meets the Internet of Vehicles: Opportunities, Challenges, and Future Prospects,” in _IEEE 7th International Conference on Collaboration and Internet Computing (CIC)_ , 2021, pp. 1–8.
  * [73] W. Li and H. Song, “ART: An Attack-Resistant Trust Management Scheme for Securing Vehicular Ad Hoc Networks,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 17, no. 4, pp. 960–969, 2016.
  * [74] H. Rahimi and H. El Bakkali, “A New Reputation Algorithm for Evaluating Trustworthiness in E-commerce Context,” in _proceeding of National Security Days (JNS3)_ , 2013, pp. 1–6.
  * [75] W. Sherchan, S. Nepal, and C. Paris, “A Survey of Trust in Social Networks,” _ACM Computing Survey_ , vol. 45, no. 4, pp. 1–33, 2013.
  * [76] R. Swedberg, “On the use of definitions in sociology,” _European Journal of Social Theory_ , vol. 23, no. 3, pp. 431–445, 2020.
  * [77] M. Deutsch, “Cooperation and Trust: Some Theoretical Notes,” _Nebraska Symposium on Motivation_ , pp. 275–319, 1962.
  * [78] J. Jalava, “From Norms to Trust: The Luhmannian Connections between Trust and System,” _European Journal of Social Theory_ , vol. 6, no. 2, pp. 173–190, 2003.
  * [79] A. B. Seligman, _The Problem of Trust_. Princeton University Press, 2000.
  * [80] G. R. Henriques, “Psychology Defined,” _Journal of clinical psychology_ , vol. 60, no. 12, pp. 1207–1221, 2004.
  * [81] D. M. Rousseau, S. B. Sitkin, R. S. Burt, and C. Camerer, “Not So Different After All: A Cross-Discipline View Of Trust,” _Academy of Management Review_ , vol. 23, no. 3, pp. 393–404, 1998.
  * [82] A. Jøsang, R. Ismail, and C. Boyd, “”A survey of trust and reputation systems for online service provision,” _Decision Support Systems_ , vol. 43, no. 2, pp. 618 – 644, 2007.
  * [83] R. Backhouse and S. Medema, “On the Definition of Economics,” _Journal of Economic Perspectives_ , vol. 23, pp. 221–33, 01 2009.
  * [84] S. Ba and P. Pavlou, “Evidence OF the Effect of Trust Building Technology in Electronic Markets: Price Premiums and Buyer Behavior,” _Management Information Systems_ , vol. 26, pp. 243–268, 09 2002.
  * [85] J. Riegelsberger, M. A. Sasse, and J. D. McCarthy, “Shiny Happy People Building Trust? Photos on E-Commerce Websites and Consumer Trust,” in _Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems_ , 2003, p. 121–128.
  * [86] K. Arai, “Trust and Trustworthiness in the Economy: How They Function and How They Should Be Promoted,” _Hitotsubashi Journal of Economics_ , vol. 48, 2007.
  * [87] D. Artz and Y. Gil, “A Survey of Trust in Computer Science and the Semantic Web,” _Journal of Web Semantics_ , vol. 5, no. 2, pp. 58 – 71, 2007.
  * [88] _Trust, Computing, and Society_. Cambridge University Press, 2014.
  * [89] W. Harwood, “The Logic of Trust,” Ph.D. dissertation, University of York, 2012\.
  * [90] K. Thompson, “Reflections on Trusting Trust,” _Communications of the ACM_ , vol. 27, no. 8, p. 761–763, 1984.
  * [91] N. B. Truong, T. Um, B. Zhou, and G. M. Lee, “From Personal Experience to Global Reputation for Trust Evaluation in the Social Internet of Things,” in _IEEE Global Communications Conference (GLOBECOM)_ , 2017, pp. 1–7.
  * [92] N. B. Truong, H. Lee, B. Askwith, and G. M. Lee, “Toward a Trust Evaluation Mechanism in the Social Internet of Things,” _Sensors_ , vol. 17, no. 6, 2017.
  * [93] R. Iqbal, T. A. Butt, M. Afzaal, and K. Salah, “Trust Management in Social Internet of Vehicles: Factors, Challenges, Blockchain, and Fog Solutions,” _International Journal of Distributed Sensor Networks_ , vol. 15, no. 1, pp. 1–22, 2019.
  * [94] K. Wang, X. Qi, L. Shu, D. Deng, and J. J. P. C. Rodrigues, “Toward Trustworthy Crowdsourcing in the Social Internet of Things,” _IEEE Wireless Communications_ , vol. 23, no. 5, pp. 30–36, 2016.
  * [95] Y. Chen, M. Zhou, Z. Zheng, and D. Chen, “Time-Aware Smart Object Recommendation in Social Internet of Things,” _IEEE Internet of Things Journal_ , vol. 7, no. 3, pp. 2014–2027, 2020.
  * [96] M. Khani, Y. Wang, M. A. Orgun, and F. Zhu, “Context-Aware Trustworthy Service Evaluation in Social Internet of Things,” in _International Conference on Service-Oriented Computing (ICSOC)_ , 2018, pp. 129–145.
  * [97] N. Truong, H. Lee, B. Askwith, and G. M. Lee, “Toward a Trust Evaluation Mechanism in the Social Internet of Things,” _Sensors_ , vol. 17, p. 1346, 2017.
  * [98] Z. Yan, P. Zhang, and A. V. Vasilakos, “A survey on trust management for Internet of Things,” _Journal of Network and Computer Applications_ , vol. 42, pp. 120–134, 2014.
  * [99] I. P. Stanimirovic, M. L. Zlatanovic, and M. D. Petkovic, “On the Linear Weighted Sum Method for Multi-objective Optimization,” _Facta Acta Universitatis_ , vol. 26, no. 4, pp. 49–63, 2011.
  * [100] I. Y. Kim and O. De Weck, “Adaptive Weighted Sum Method for Multi-objective Optimization: a New Method for Pareto Front Generation,” _Structural and multidisciplinary optimization_ , vol. 31, no. 2, pp. 105–116, 2006.
  * [101] R. T. Marler and J. S. Arora, “The Weighted Sum Method for Multi-objective Optimization: New Insights,” _Structural and multidisciplinary optimization_ , vol. 41, no. 6, pp. 853–862, 2010.
  * [102] L. Liu and R. R. Yager, _Classic Works of the Dempster-Shafer Theory of Belief Functions: An Introduction_. Springer Berlin Heidelberg, 2008, pp. 1–34.
  * [103] K. Sentz and S. Ferson, _Combination of Evidence in Dempster-Shafer Theory_ , 01 2002.
  * [104] M. Beynon, B. Curry, and P. Morgan, “The Dempster–Shafer Theory of Evidence: An Alternative Approach to Multicriteria Decision Modelling,” _Omega_ , vol. 28, no. 1, pp. 37–50, 2000.
  * [105] A. Jøsang and R. Ismail, “The Beta Reputation System,” _In: Proceedings of the 15th Bled Conference on Electronic Commerce_ , 01 2002.
  * [106] K. Weise and W. Woger, “A Bayesian Theory of Measurement Uncertainty,” _Measurement Science and Technology_ , vol. 4, no. 1, p. 1, 1993.
  * [107] J. M. Bernardo and A. F. Smith, _Bayesian Theory_. John Wiley & Sons, 2009, vol. 405.
  * [108] P. N. Mahalle, P. A. Thakre, N. R. Prasad, and R. Prasad, “A Fuzzy Approach to Trust Based Access Control in Internet of Things,” in _International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace and Electronic Systems Technology (Wireless VITAE)_ , 2013, pp. 1–5.
  * [109] L. A. Zadeh, “Fuzzy Sets,” in _Fuzzy sets, fuzzy logic, and fuzzy systems: selected papers by Lotfi A Zadeh_. World Scientific, 1996, pp. 394–432.
  * [110] J. Carbo, J. M. Molina, and J. Davila, “Trust Management Through Fuzzy Reputation,” _International Journal of Cooperative Information Systems_ , vol. 12, no. 01, pp. 135–155, 2003.
  * [111] U. Jayasinghe, G. M. Lee, T. Um, and Q. Shi, “Machine Learning based Trust Computational Model for IoT Services,” _IEEE Transactions on Sustainable Computing_ , vol. 4, no. 1, pp. 39–52, 2019.
  * [112] S. Sagar, A. Mahmood, Q. Z. Sheng, and W. E. Zhang, “Trust Computational Heuristic for Social Internet of Things: A Machine Learning-based Approach,” in _proceeding of IEEE International Conference on Communications (ICC)_ , 2020, pp. 1–6.
  * [113] S. A. Siddiqui, A. Mahmood, W. E. Zhang, and Q. Z. Sheng, “Machine Learning Based Trust Model for Misbehaviour Detection in Internet-of-Vehicles,” in _International Conference on Neural Information Processing (ICONIP)_ , 2019, pp. 512–520.
  * [114] Y. Wang, Y.-C. Lu, I.-R. Chen, J.-H. Cho, A. Swami, and C.-T. Lu, “LogitTrust : A Logit Regression-based Trust Model for Mobile Ad Hoc Networks,” in _6th ASE/IEEE International Conference on Privacy, Security, Risk and Trust_ , 2014.
  * [115] R. Venkataraman, M. Pushpalatha, and T. R. Rao, “Regression-based Trust Model for Mobile Ad Hoc Networks,” _IET Information Security_ , vol. 6, no. 3, pp. 131–140, 2012.
  * [116] U. Jayasinghe, H.-W. Lee, and G. M. Lee, “A Computational Model to Evaluate Honesty in Social Internet of Things,” in _Proceedings of the Symposium on Applied Computing_ , 2017, pp. 1830–1835.
  * [117] I. Chen, F. Bao, and J. Guo, “Trust-Based Service Management for Social Internet of Things Systems,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 13, no. 6, pp. 684–696, 2016.
  * [118] H. Xia, F. Xiao, S. Zhang, C. Hu, and X. Cheng, “Trustworthiness Inference Framework in the Social Internet of Things: A Context-Aware Approach,” in _proceeding of IEEE Conference on Computer Communications (INFOCOM)_ , 2019, pp. 838–846.
  * [119] X. Li, G. Zhu, Y. Gong, and K. Huang, “Wirelessly Powered Data Aggregation for IoT via Over-the-Air Function Computation: Beamforming and Power Control,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 7, pp. 3437–3452, 2019.
  * [120] X. Sun and N. Ansari, “Dynamic Resource Caching in the IoT Application Layer for Smart Cities,” _IEEE Internet of Things Journal_ , vol. 5, no. 2, pp. 606–613, 2018.
  * [121] H. Xiao, N. Sidhu, and B. Christianson, “Guarantor and Reputation Based Trust Model for Social Internet of Things,” in _International Wireless Communications and Mobile Computing Conference (IWCMC)_ , 2015, pp. 600–605.
  * [122] I. Chen, J. Guo, and F. Bao, “Trust Management for SOA-Based IoT and Its Application to Service Composition,” _IEEE Transactions on Services Computing_ , vol. 9, no. 3, pp. 482–495, 2016.
  * [123] C. V. L. Mendoza and J. H. Kleinschmidt, “Mitigating On-Off Attacks in the Internet of Things Using a Distributed Trust Management Scheme,” _International Journal of Distributed Sensor Networks_ , vol. 11, no. 11, pp. 1–8, 2015.
  * [124] Y. B. Saied], A. Olivereau, D. Zeghlache, and M. Laurent, “Trust Management System Design for the Internet of Things: A Context-aware and Multi-service Approach,” _Computers & Security_, vol. 39, pp. 351 – 365, 2013.
  * [125] A. A. Adewuyi, H. Cheng, Q. Shi, J. Cao, A. MacDermott, and X. Wang, “CTRUST: A Dynamic Trust Model for Collaborative Applications in the Internet of Things,” _IEEE Internet of Things Journal_ , vol. 6, no. 3, pp. 5432–5445, 2019.
  * [126] B. Yu and M. P. Singh, “An Evidential Model of Distributed Reputation Management,” in _Proceedings of the 1st ACM International Joint Conference on Autonomous Agents and Multiagent Systems_ , ser. AAMAS ’02, 2002, p. 294–301.
  * [127] F. Bao, I. Chen, and J. Guo, “Scalable, Adaptive and Survivable Trust Management for Community of Interest Based Internet of Things Systems,” in _11th IEEE International Symposium on Autonomous Decentralized Systems (ISADS)_ , 2013, pp. 1–7.
  * [128] S. Sagar, A. Mahmood, J. Kumar, and Q. Z. Sheng, “A Time-Aware Similarity-Based Trust Computational Model for Social Internet of Things,” in _IEEE Global Communications Conference (GlobeCom)_ , 2020, pp. 1–6.
  * [129] Z. Chen, R. Ling, C.-M. Huang, and X. Zhu, “A Scheme of Access Service Recommendation for the Social Internet of Things,” _International Journal of Communication Systems_ , vol. 29, no. 4, pp. 694–706, 2016.
  * [130] I. Garcia-Magarino, S. Sendra, R. Lacuesta, and J. Lloret, “Security in Vehicles with IoT by Prioritization Rules, Vehicle Certificates, and Trust Management,” _IEEE Internet of Things Journal_ , vol. 6, no. 4, pp. 5927–5934, 2019.
  * [131] S. Namal, H. Gamaarachchi, G. MyoungLee, and T. Um, “Autonomic Trust Management in Cloud-based and Highly Dynamic IoT Applications,” in _ITU Kaleidoscope: Trust in the Information Society_ , 2015, pp. 1–8.
  * [132] S. A. Siddiqui, A. Mahmood, Q. Z. Sheng, H. Suzuki, and W. Ni, “A Survey of Trust Management in the Internet of Vehicles,” _Electronics_ , vol. 10, no. 18, p. 2223, 2021.
  * [133] M. Masmoudi, W. Abdelghani, I. Amous, and F. Sèdes, “Deep Learning for Trust-Related Attacks Detection in Social Internet of Things,” in _Advances in E-Business Engineering for Ubiquitous Computing_. Springer International Publishing, 2020, pp. 389–404.
  * [134] C. Marche and M. Nitti, “Trust-Related Attacks and Their Detection: A Trust Management Model for the Social IoT,” _IEEE Transactions on Network and Service Management_ , vol. 18, no. 3, pp. 3297–3308, 2021.
  * [135] A. Chakrabarti, _Managing Trust in the Grid_. Springer Berlin Heidelberg, 2007, pp. 215–246.
  * [136] H. Al-Hamadi and I. R. Chen, “Trust-Based Decision Making for Health IoT Systems,” _IEEE Internet of Things Journal_ , vol. 4, no. 5, pp. 1408–1419, 2017.
  * [137] W. Li, H. Song, and F. Zeng, “Policy-based Secure and Trustworthy Sensing for Internet of Things in Smart Cities,” _IEEE Internet of Things Journal_ , vol. 5, no. 2, pp. 716–723, 2018.
  * [138] V. Mohammadi, A. Rahmani, A. Darwesh, and A. Sahafi, “Trust-based Recommendation Systems in Internet of Things: a Systematic Literature Review,” _Human-centric Computing and Information Sciences_ , vol. 9, pp. 1–61, 2019.
  * [139] A. R. Sfar, E. Natalizio, Y. Challal, and Z. Chtourou, “A Roadmap for Security Challenges in the Internet of Things,” _Digital Communications and Networks_ , vol. 4, no. 2, pp. 118–137, 2018.
  * [140] L. Wei, J. Wu, C. Long, and B. Li, “On Designing Context-Aware Trust Model and Service Delegation for Social Internet of Things,” _IEEE Internet of Things Journal_ , vol. 8, no. 6, pp. 4775–4787, 2021.
  * [141] M. A. Azad, S. Bag, F. Hao, and A. Shalaginov, “Decentralized Self-Enforcing Trust Management System for Social Internet of Things,” _IEEE Internet of Things Journal_ , vol. 7, no. 4, pp. 2690–2703, 2020.
  * [142] N. Truong and G. M. Lee, “A Reputation and Knowledge Based Trust Service Platform for Trustworthy Social Internet of Things,” in _19th International Conference on Innovations in Clouds, Internet and Networks (ICIN)_ , 2016, pp. 1–8.
  * [143] S. Aalibagi, H. Mahyar, A. Movaghar, and H. E. Stanley, “A Matrix Factorization Model for Hellinger-based Trust Management in Social Internet of Things,” _IEEE Transactions on Dependable and Secure Computing_ , pp. 1–1, 2021.
  * [144] S. Sagar, A. Mahmood, M. Zaib, Q. Z. Sheng, and W. E. Zhang, “Towards a Machine Learning-driven Trust Evaluation Model for Social Internet of Things: A Time-aware Approach,” in _17th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services (MobiQuitous)_ , 2020, p. 283–290.
  * [145] O. Ben Abderrahim, M. H. Elhdhili, and L. Saidane, “TMCoI-SIOT: A trust management system based on communities of interest for the social Internet of Things,” in _2017 13th International Wireless Communications and Mobile Computing Conference (IWCMC)_ , 2017, pp. 747–752.
  * [146] P. De Meo, L. Fotia, F. Messina, D. Rosaci, and G. M. Sarne, “Providing Recommendations in Social Networks by Integrating Local and Global Reputation,” _Information Systems_ , vol. 78, pp. 58–67, 2018.
  * [147] B. Jafarian, N. Yazdani, and M. Sayad Haghighi, “Discrimination-aware Trust Management for Social Internet of Things,” _Computer Networks_ , vol. 178, p. 107254, 2020.
  * [148] N. Li, V. Varadharajan, and S. Nepal, “Context-Aware Trust Management System for IoT Applications with Multiple Domains,” in _2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)_ , 2019, pp. 1138–1148.
  * [149] U. Jayasinghe, N. B. Truong, G. M. Lee, and T.-W. Um, “RpR: A Trust Computation Model for Social Internet of Things,” in _IEEE International Conferences on Ubiquitous Intelligence Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People, and Smart World Congress (UIC/ATC/ScalCom/CBDCom/IoP/SmartWorld)_ , 2016, pp. 930–937.
  * [150] J. I. Chen, “Embedding the MRC and SC Schemes into Trust Management Algorithm Applied to IoT Security Protection,” _Wireless Personal Communication_ , vol. 99, no. 1, p. 461–477, 2018.
  * [151] H. Xia, S. Zhang, Y. Li, Z. Pan, X. Peng, and X. Cheng, “An Attack-Resistant Trust Inference Model for Securing Routing in Vehicular Ad Hoc Networks,” _IEEE Transactions on Vehicular Technology_ , vol. 68, no. 7, pp. 7108–7120, 2019.
  * [152] O. Ben Abderrahim, M. H. Elhedhili, and L. Saidane, “CTMS-SIOT: A context-based trust management system for the social Internet of Things,” in _13th International Wireless Communications and Mobile Computing Conference (IWCMC)_ , 2017, pp. 1903–1908.
  * [153] C. Marche, L. Atzori, and M. Nitti, “A Dataset for Performance Analysis of the Social Internet of Things,” in _2018 IEEE 29th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)_ , 2018, pp. 1–5.
  * [154] M. B. Monir, M. H. Abdel Aziz, A. A. Abdel Hamid, and E. M. EI-Horbaty, “Trust Management in Cloud Computing: A Survey,” in _IEEE Seventh International Conference on Intelligent Computing and Information Systems (ICICIS)_ , 2015, pp. 231–242.
  * [155] Q. H. Cao, M. Giyyarpuram, R. Farahbakhsh, and N. Crespi, “Policy-based Usage Control for a Trustworthy Data Sharing Platform in Smart Cities,” _Future Generation Computer Systems_ , vol. 107, pp. 998–1010, 2020.
  * [156] L. Gu, J. Wang, and B. Sun, “Trust management mechanism for Internet of Things,” _China Communications_ , vol. 11, no. 2, pp. 148–156, 2014.
  * [157] T. H. Noor, Q. Z. Sheng, S. Zeadally, and J. Yu, “Trust Management of Services in Cloud Environments: Obstacles and Solutions,” _ACM Computing Survey_ , vol. 46, no. 1, pp. 1–30, 2013.
  * [158] F. Fraile, T. Tagawa, R. Poler, and A. Ortiz, “Trustworthy Industrial IoT Gateways for Interoperability Platforms and Ecosystems,” _IEEE Internet of Things Journal_ , vol. 5, no. 6, pp. 4506–4514, 2018.
  * [159] B. Pourghebleh, K. Wakil, and N. J. Navimipour, “A Comprehensive Study on the Trust Management Techniques in the Internet of Things,” _IEEE Internet of Things Journal_ , vol. 6, no. 6, pp. 9326–9337, 2019.
  * [160] Howe and Jeff, “The Rise of Crowdsourcing,” _Wired_ , vol. 14, pp. 1–4, 2006.
  * [161] K. Habak, M. Ammar, K. A. Harras, and E. Zegura, “Femto Clouds: Leveraging Mobile Devices to Provide Cloud Service at the Edge,” in _IEEE 8th International Conference on Cloud Computing_ , 2015, pp. 9–16.
  * [162] S. D. T. Kelly, N. K. Suryadevara, and S. C. Mukhopadhyay, “Towards the Implementation of IoT for Environmental Condition Monitoring in Homes,” _IEEE Sensors Journal_ , vol. 13, no. 10, pp. 3846–3853, 2013.
  * [163] E. Bulut, S. Hernandez, A. Dhungana, and B. K. Szymanski, “Is Crowdcharging Possible?” in _27th International Conference on Computer Communication and Networks (ICCCN)_ , 2018, pp. 1–9.
  * [164] X. Gan, Y. Li, Y. Huang, L. Fu, and X. Wang, “When Crowdsourcing Meets Social IoT: An Efficient Privacy-Preserving Incentive Mechanism,” _IEEE Internet of Things Journal_ , vol. 6, no. 6, pp. 9707–9721, 2019.
  * [165] C.-H. Liu and C.-F. Chiang, _Social IoT Crowd-Sourcing on Disaster Reduction_. Springer Berlin Heidelberg, 2019, pp. 1–6.
  * [166] A. Khelloufi, H. Ning, S. Dhelim, T. Qiu, J. Ma, R. Huang, and L. Atzori, “A Social-Relationships-Based Service Recommendation System for SIoT Devices,” _IEEE Internet of Things Journal_ , vol. 8, no. 3, pp. 1859–1870, 2021.
  * [167] Q. Z. Sheng, J. Yu, W. E. Zhang, S. Wang, X. Li, and B. Benatallah, “Designing and Building Context-Aware Services: The ContextServ Project,” in _Next-Gen Digital Services. A Retrospective and Roadmap for Service Computing of the Future_. Springer International Publishing, 2021, pp. 138–152.
  * [168] K. Bok, Y. Kim, D. Choi, and J. Yoo, “User Recommendation for Data Sharing in Social Internet of Things,” _Sensors_ , vol. 21, no. 2, p. 462, Jan 2021\.
  * [169] A. Mahmood, W. Zhang, and Q. Sheng, “Software-Defined Heterogeneous Vehicular Networking: The Architectural Design and Open Challenges,” _Future Internet_ , vol. 11, no. 3, p. 70, 2019.
  * [170] Nitti, Michele and Girau, Roberto and Floris, Alessandro and Atzori, Luigi, “On adding the Social Dimension to the Internet of Vehicles: Friendship and Middleware,” in _IEEE international Black Sea Conference on Communications and Networking (BlackSeaCom)_ , 2014, pp. 134–138.
  * [171] T. A. Butt, R. Iqbal, S. C. Shah, and T. Umar, “Social Internet of Vehicles: Architecture and Enabling Technologies,” _Computers & Electrical Engineering_, vol. 69, pp. 68–84, 2018.
  * [172] L. Atzori, A. Floris, R. Girau, M. Nitti, and G. Pau, “Towards the implementation of the Social Internet of Vehicles,” _Computer Networks_ , vol. 147, pp. 132–145, 2018.
  * [173] L. Chengzhe, D. Yangyang, G. Qili, and Z. Dong, “A Trust-based Privacy-preserving Friend Matching Scheme in Social Internet of Vehicles,” _Peer-to-Peer Networking and Applications_ , vol. 14, pp. 2011–2025, 2021\.
  * [174] C. A. Kerrache, N. Lagraa, R. Hussain, S. H. Ahmed, A. Benslimane, C. T. Calafate, J.-C. Cano, and A. M. Vegni, “TACASHI: Trust-Aware Communication Architecture for Social Internet of Vehicles,” _IEEE Internet of Things Journal_ , vol. 6, no. 4, pp. 5870–5877, 2019.
  * [175] F. Gai, J. Zhang, P. Zhu, and X. Jiang, “Trust on the Ratee: A Trust Management System for Social Internet of Vehicles,” _Wireless Communications and Mobile Computing_ , vol. 2017, pp. 1–11, 2017.
  * [176] U. Javaid and B. Sikdar, “A Secure and Scalable Framework for Blockchain Based Edge Computation Offloading in Social Internet of Vehicles,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 5, pp. 4022–4036, 2021.
  * [177] T. Wang, A. Hussain, L. Zhang, and C. Zhao, “Collaborative Edge Computing for Social Internet of Vehicles to Alleviate Traffic Congestion,” _IEEE Transactions on Computational Social Systems_ , pp. 1–13, 2021.
  * [178] X. Kong, H. Gao, G. Shen, G. Duan, and S. K. Das, “FedVCP: A Federated-Learning-Based Cooperative Positioning Scheme for Social Internet of Vehicles,” _IEEE Transactions on Computational Social Systems_ , pp. 1–10, 2021.
  * [179] L. Xing, X. Jia, J. Gao, and H. Wu, “A Location Privacy Protection Algorithm Based on Double K-Anonymity in the Social Internet of Vehicles,” _IEEE Communications Letters_ , vol. 25, no. 10, pp. 3199–3203, 2021.
  * [180] E. Ojie and E. Pereira, “Simulation Tools in Internet of Things: A Review,” in _Proceedings of the 1st ACM International Conference on Internet of Things and Machine Learning_ , 2017, pp. 1–7.
  * [181] M. Chernyshev, Z. Baig, O. Bello, and S. Zeadally, “Internet of Things (IoT): Research, Simulators, and Testbeds,” _IEEE Internet of Things Journal_ , vol. 5, no. 3, pp. 1637–1647, 2018.
  * [182] U. Wilensky, “NetLogo,” https://ccl.northwestern.edu/netlogo/, 1999, [Online; Accessed 10-March-2021].
  * [183] A. Mei and J. Stefa, “SWIM: A Simple Model to Generate Small Mobile Worlds,” in _IEEE International Conference on Computer Communications (INFOCOM)_ , 2009, pp. 2106–2113.
  * [184] G. F. Riley and T. R. Henderson, “The NS-3 Network Simulator,” in _Modeling and tools for network simulation_. Springer, 2010, pp. 15–34.
  * [185] L. Campanile, M. Gribaudo, M. Iacono, F. Marulli, and M. Mastroianni, “Computer Network Simulation with NS-3: A Systematic Literature Review,” _Electronics_ , vol. 9, p. 272, 2020.
  * [186] “Veins,” https://veins.car2x.org/, [Online; Accessed 10-March-2021].
  * [187] P. Deshpande, P. Kodeswaran, N. Banerjee, A. Nanavati, D. Chhabra, and S. Kapoor, “M4M: A Model for Enabling Social Network Based Sharing in the Internet of Things,” _7th International Conference on Communication Systems and Networks (COMSNETS)_ , pp. 1–8, 2015.
  * [188] “ThingSpeak,” https://thingspeak.com/, [Online; Accessed 10-March-2021].
  * [189] X. Zeng, R. Bagrodia, and M. Gerla, “GloMoSim: A Library for Parallel Simulation of Large-Scale Wireless Networks,” _ACM SIGSIM Simulation Digest_ , vol. 28, no. 1, p. 154–161, 1998.
  * [190] A. Dunkels, B. Gronvall, and T. Voigt, “Contiki - A Lightweight and Flexible Operating System for Tiny Networked Sensors,” in _Proceedings of the 29th IEEE International Conference on Local Computer Networks (LCN)_ , 2004, p. 455–462.
  * [191] C. Marche, L. Atzori, V. Pilloni, and M. Nitti, “How to Exploit the Social Internet of Things: Query Generation Model and Device Profiles’ Dataset,” _Computer Networks_ , vol. 174, p. 107248, 2020.
  * [192] A. K. Pietilainen and C. Diot, “CRAWDAD dataset thlab/sigcomm2009 (version: 2012-07-15),” Downloaded from https://crawdad.org/thlab/sigcomm2009/20120715, 2012.
  * [193] M. Richardson, R. Agrawal, and P. Domingos, “Trust Management for the Semantic Web,” in _International Semantic Web Conference (ISWC)_ , 2003, pp. 351–368.
  * [194] Z. Lin and L. Dong, “Clarifying Trust in Social Internet of Things,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 30, no. 2, pp. 234–248, 2018.
  * [195] S. Sagar, A. Mahmood, Q. Z. Sheng, and S. A. Siddiqui, “SCaRT-SIoT: Towards a Scalable and Robust Trust Platform for Social Internet of Things: Demo Abstract,” in _Proceedings of the 18th ACM International Conference on Embedded Networked Sensor Systems (SenSys)_ , 2020, p. 635–636.

|  Subhash Sagar received the BS in Electrical (Telecommunication) from the
COMSATS Institute of Information Technology, Islamabad, Pakistan and a
Master’s degree in Computer Science from South Asian University, New Delhi,
India in 2012 and 2016 respectively. He is currently pursuing PhD degree at
the School of Computing, Macquarie University, Sydney, Australia. Before
moving to Macquarie University, Subhash worked as a faculty member at the
Department of Computer Science, National University of Computer and Emerging
Sciences, Karachi, Pakistan from 2017 to 2019. His current research interests
include the Internet of Things, Social Internet of Things, and Trust
Management.
---|---
|  Adnan Mahmood holds a PhD degree in Computer Science and is currently a
Postdoctoral Research Fellow at the School of Computing, Macquarie University,
Sydney, Australia. Before moving to Macquarie University, Adnan has spent a
considerable number of years in the academic and research settings of Republic
of Ireland, South Korea, Malaysia, Pakistan, and People’s Republic of China.
His research interests include Software-Defined Networks, Intelligent
Transportation Systems, Internet of Things (primarily the Internet of
Vehicles), Trust Management, and the Next Generation Heterogeneous Wireless
Networks. Adnan besides serve on the Technical Program Committees of a number
of reputed International Conferences. He is a member of the IEEE, IET, and the
ACM.
---|---
|  Quan Z. (Michael) Sheng is a full Professor and Head of School of Computing
at Macquarie University. Before moving to Macquarie, Michael spent 10 years at
School of Computer Science, the University of Adelaide (UoA). Michael holds a
PhD degree in Computer Science from the University of New South Wales (UNSW)
and did his post-doc as a research scientist at CSIRO ICT Centre. From 1999 to
2001, Sheng also worked at UNSW as a visiting research fellow. Prior to that,
he spent 6 years as a senior software engineer in industries. Prof Sheng’s
research interests include the Internet of Things, big data analytics, service
computing, and Internet technologies. Dr. Michael Sheng is the recipient of
the ARC Future Fellowship (2014), Chris Wallace Award for Outstanding Research
Contribution (2012), and Microsoft Research Fellowship (2003). He is ranked by
Microsoft Academic as one of the Most Impactful Authors in Services Computing
(ranked top 5 all time). He is a member of the IEEE and the ACM.
---|---
|  Jitander Kumar Pabani received his BE degree in Telecommunication
Engineering from Mehran University of Engineering and Technology Jamshoro,
Sindh Pakistan, and Master of Engineering in Telecommunication Engineering
from Hamdard University, Karachi, Pakistan in 2011 and 2014 respectively. He
also completed his Post-Graduate Diploma in Statistics in 2017 from the
University of Karachi, Pakistan. Currently, he is pursuing his PhD studies at
the Department of Communication Engineering, Universidad de Malaga, Spain,
funded through the Faculty Development Program by Dawood University of
Engineering and Technology, Karachi, and Higher Education Commission of
Pakistan. He has been also associated with Dawood University of Engineering
and Technology in the capacity of Lecturer since 2016. He has more than 10
years of teaching experience. His area of research includes Underwater
Wireless Sensor Networks, Wireless Body Area Networks, Internet of Things,
Machine Learning, and Fuzzy Decision Making.
---|---
|  Wei (Emma) Zhang is currently a Lecturer at the School of Computer Science,
The University of Adelaide. She obtained her PhD in 2017 from the School of
Computer Science, The University of Adelaide. Her research interests include
text mining, deep learning, natural language processing, information
retrieval, and Internet of Things (IoT) applications. She has close to 100
publications to date as edited books and proceedings, refereed book chapters,
and refereed technical papers in journals and conferences including ACM
Computing Surveys, TOIT, ACM TIST, WWWJ, Communications of the ACM, ACL,
SIGIR, WWW, EDBT, CIKM, ICSOC and CAiSE. Her PhD thesis has been published by
Springer as a monograph. She is a member of the IEEE, the ACM and the ACL.
---|---