# A hybrid particle swarm optimization for the selective pickup and delivery problem with transfers

Zhihao Peng, Zaher Al Chami, Hervé Manier, Marie Manier

► To cite this version:

Zhihao Peng, Zaher Al Chami, Hervé Manier, Marie Manier. A hybrid particle swarm optimization for the selective pickup and delivery problem with transfers. Engineering Applications of Artificial Intelligence, 2019, 85, pp.99-111. 10.1016/j.engappai.2019.06.006. hal-02366746

HAL Id: hal-02366746

https://hal.science/hal-02366746

Submitted on 25 Oct 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# A hybrid particle swarm optimization for the selective pickup and delivery problem with transfers

Zhihao Peng<sup>a,*</sup>, Zaher Al Chami<sup>a</sup>, Hervé Manier<sup>a</sup>, Marie-Ange Manier<sup>a</sup>

<sup>a</sup>Univ. Bourgogne Franche-Comté FEMTO-ST Institute/CNRS, Rue Thierry-Mieg (UTBM), 90 010 Belfort Cedex, France

## Abstract

In pickup and delivery problems, all the demands should be transported from pickup points (suppliers) to delivery points (customers) by vehicles while respecting a set of constraints. Honoring all demands is sometimes impossible when taking all the constraints into account. Therefore, the selective aspect is added to relax the constraint that all the demands should be satisfied. This paper studies a variant called the selective pickup and delivery problem with transfers (SPDPT). The transfers mean that some demands can be transferred from one vehicle to another one, which gives a chance to find more solutions. A mixed integer linear program is firstly proposed to describe the studied problem. Two objectives have been considered in the paper, maximizing the profit and minimizing the distance. The model is then validated on new generated instances. Due to the complexity of the problem, large instances could not be solved to optimality in a reasonable time. As an alternative, a new metaheuristic based on a hybrid particle swarm optimization is developed to tackle this bi-objective problem. The results show that this proposed method is efficient and competitive.

**Keywords:** Transportation; Particle swarm optimization; Vehicle routing problem; Selective problem; Transfers

<footnote>*Corresponding author.</footnote>

<footnote>Email addresses: zhihao.peng@utbm.fr (Zhihao Peng), zaher.al-chami@utbm.fr (Zaher Al Chami), herve.manier@utbm.fr (Hervé Manier), marie-ange.manier@utbm.fr (Marie-Ange Manier)</footnote>
# 1. Introduction

The general pickup and delivery problem (PDP) (Savelsbergh and Sol, 1995) is an extension of the vehicle routing problem (VRP) (Dantzig and Ramser, 1959), and can be described as a problem in which a fleet of vehicles collects goods from pickup points (suppliers), and transports them to delivery points (customers). There are many variants of the PDP in the literature. One of the most studied variants is the pickup and delivery problem with time windows and paired demands (PDPTWPD) (Li and Lim, 2003) in which each site should be visited during a specified time window, and the vehicle should visit a supplier before its associated customer. One possible extension of the PDPTWPD is the adaptation of selective aspect, which relaxes the constraint that all demands should be satisfied. This problem is called the selective PDPTWPD (SPDPTWPD) (Al Chami et al., 2016). Another extension of the PDPTWPD is the introducing of intermediate facility called transfer points, at which goods can be transferred from one vehicle to another one. This problem is called the pickup and delivery problem with transfers (PDPT) (Cortés et al., 2010).

In this paper, the studied problem is a combination of the SPDPTWPD and the PDPT, called the selective pickup and delivery problem with transfers (SPDPT) which considers all the constraints previously introduced. An example is presented in figure 1 to better explain the studied problem. In this figure, there are four paired demands identified by the same color, two transfer points, and one depot of vehicles. The first vehicle collects demands one and two at their suppliers, and the second vehicle collects demand three at its supplier. In order to save traveling distance, the first vehicle uses transfer point one to drop demand two which will be collected by the second vehicle. A precedence constraint is imposed to force that the second vehicle arrives at this transfer point later than the first one. In this case, demand four is not honored due to the limited capacity of vehicle or the incompatibility in time windows.

The selective aspect maybe related with many applications in the real world. In a company with limited resources (vehicles), not all the demands could be
<figure><img src="image_2.png" /><figcaption>Figure 1: Example of the SPTPT</figcaption></figure>

satisfied. In this case, the decision maker could associate each demand with a
profit which could be interpreted in different ways, like money, credits. Max-
imizing the profit can be considered as the first objective to satisfy the most
important demands. Since several solutions may correspond to the first objec-
tive, minimizing the distance could be taken as the second objective to select
the most economical one. The transfer point could be seen as a way to improve
the solution in terms of the two objectives. For the first objective, transfer point
can enable vehicles to share their capacity. As a consequence, more demands
could be satisfied. For the second objective, clustered demands could be loaded
into the same vehicle at transfer point, which would largely save the traveling
distance.

In this context, the contributions of this paper are the following ones:

* The proposal of a mixed integer linear program for a new problem: the SPDPT (Section 3.2).

• The generation of new instances for the SPDPT (Section 5.1).

* The validation of interests of transfers in selective problems (Section 5.2).

* The elaboration of an encoding strategy when using particle swarm optimization (PSO) to solve the SPDPT (Section 4).
* The development of a metaheuristic approach to efficiently solve the SPDPT and its related problem, SPDPTWPD (Section 6).

## 2. Literature Review

In this section, we will present briefly a state of the art which is divided into three parts. The first two parts deal with two related problems: the SPDPTWPD, and the PDPT. The last part is dedicated to the applications of PSO in vehicle routing problems.

### 2.1. *Selective pickup and delivery problem with time windows and paired demands*

The PDPTWPD has been studied a lot in recent years because of its wide applications in real life such as air scheduling, logistic and maintenance support, dial-a-ride problems (Zidi et al., 2012). For more details, please refer to the works (Parragh et al., 2007, 2008). Over the last years, researchers have used various algorithms to tackle with many variants of the PDP (Dragomir et al., 2018; Sampaio and Urrutia, 2017).

In problems dealing with selective aspect, it is not necessary to satisfy all the demands. This could provide to the decision makers a good flexibility facing to different situations. In these problems, each demand is often associated with a profit, maximizing the total profit (choosing the most important demands to satisfy) is then considered as an objective. Many surveys in the literature are dedicated to selective routing problems, more particularly the Orienteering Problem (OP) which represents the single vehicle case of the well-known Team Orienteering Problem (TOP) (Gunawan et al., 2016; Vansteenwegen et al., 2011). The SPDPTWPD was first taken into account in Al Chami et al. (2016). In this paper, a three-indexes based formulation with single objective was proposed. To validate the model, several instances were generated with size varying from 20 sites to 100 sites. They also proposed several additional constraints to reduce the solving time. In Al Chami et al. (2017a), two objectives were considered
for the same problem. The first objective was to maximize the profit and the
second one was to minimize the distance. A lexicographic approach was used by
predefining executed order between the two objective functions. In Al Chami
et al. (2017b, 2018), a hybrid genetic algorithm and a simulated annealing were
also developed to study the same problem.

2.2. *Pickup and delivery problem with transfers*

The PDPT has been less studied compared to the PDPTWPD. In real life,
transfer points could be places like parking lot, retail store, etc. Most of these
places are of low cost, or free, so the cost of using a transfer point is often not
taken into account.

Although introducing transfers can bring benefits, it also makes the model
more complicated. The complexity comes from the precedence constraint which
makes two vehicles depend on each other. A survey about precedence constraint
in vehicle routing problems is presented by Drexl (2012).

A formal formulation of the PDPT was proposed in Cortés et al. (2010).
In this paper, a transfer point was divided into two virtual ones to handle the
precedence issue. However, the transfer time is considered as a constant value
for the transferred demands. The authors proposed a branch-and-cut method
which can solve instances to optimality with up to 12 sites (six demands), 1
transfer point and 2 vehicles.

Rais et al. (2014) formulated the same problem in a different way and a four-
index binary variable was used to track a demand. The service time was also
not considered. The commercial solver GUROBI was used for solving instances
with up to 14 sites (7 demands).

Several limitations can be observed when using the MILP planners to solve
the transfer-related problems: on one hand, the solving time increases exponen-
tially while increasing the number of demands; on the other hand, finding the
optimal solution for large instances (more than 7 demands) in a reasonable time
is difficult using these MILP solvers.
Since the solving time increases exponentially for large instances, an ap-
proached method is often chosen as an alternative. Mitrović-Minić and Laporte
(2006) have proposed a two-phase heuristic. In the first phase, an initial solution
was constructed by using cheapest insertion. In the second one, the best solu-
tion generated from the first phase was improved by removing and reinserting
each demand. Tests were made on some real instances from a courier company
in San Francisco. Moreover, an adaptive large neighborhood search (ALNS) was
presented by Masson et al. (2013). Several destroy and repair operators ( neigh-
borhood) have been proposed. The probability of choosing a neighborhood was
determined by its previous performance. Since their work was motivated by a
real context in which disabled people need to be transported, the algorithm was
tested on 10 related instances. The results have shown that an improvement
can be achieved up to 9% after introducing transfers. In Qu and Bard (2012),
a method combining GRASP and ALNS was developed. The former one was
used to generate an initial solution, and the latter one was used to improve it.
The experiment was made on instances with up to 50 sites (25 demands) and 1
transfer point. Solutions within 1% of optimality for 88% of the instances can
be found.

A related problem to the PDPT is the N-Echelon Location Routing Problem (NE-LRP). The basic idea is to divide the delivery procedure into N-stages. In stage $n \in 1, \dots, N$, a dedicated fleet of vehicles collects goods and delivers them to level-n facilities (corresponding to transfer points in the PDPT). In stage $n + 1 \in 1, \dots, N$, another fleet of vehicles will collect the goods from level-n facilities and deliver them to level-(n+1) facilities. A similarity can be observed between the PDPT and the NE-LRP. In the PDPT, transferring a demand through a transfer point corresponds to a two-echelon delivery procedure. If a demand is transferred N times, then the delivery procedure can be seen as $N+1$-Echelon. More details can be found in a recent survey (Drexl and Schneider, 2015).

In terms of approached method, the SPDPDTW was solved by genetic al-
gorithm and simulated annealing, which are population based and solution-
constructed based methods respectively. As far as we know, the PDPT was
only solved by ALNS which is a solution-constructed based method. PSO, a
population based method, has never been used to tackle these two problems.
Therefore, we found it interesting to adapt it into an integrated problem at
the expectation of exploring its capacity. In addition, many researchers have
proved that PSO is often more efficient than other metaheuristics (ant colony,
genetic algorithms...) in terms of computational time and/or solution quality
(Elbeltagi et al., 2005; Hassan et al., 2005; Liao et al., 2007). In those latter
studies, the authors have compared PSO with other evolutionary algorithms
(especially genetic algorithms) by applying those metaheuristics to solve the
same problem. They then conclude that PSO outperforms other approaches.
And even if other studies have shown that genetic algorithms outperforms PSO
(Kachitvichyanukul, 2012), in general, all these studies agree that PSO is easier
to implement than genetic algorithm as there are no genetic operators (crossover
and mutation) in PSO and the movement from one set of solutions to another
is done by using velocity functions. In other words, the number of parame-
ters that require adjustment in PSO is smaller than in genetic algorithms. For
vehicle routing problems, PSO has been successfully adapted and gave good
performance. A brief state-of-the-art will be given in the next section in terms
of possible applications of PSO into VRPs.

2.3. *Particle swarm optimization for vehicle routing problems*

Although particle swarm optimization (PSO) was originally designed for
continuous problem, researchers have been trying to apply it to solve different
discrete problems. A well-known technique to transform from continuous space
to discrete one is to use RK (random key). In Kachitvichyanukul et al. (2009b),
PSO was used to solve vehicle routing problem with simultaneous pickup and de-
livery. Two solution representations have been proposed by Kachitvichyanukul
et al. (2009a) for the capacitated vehicle routing problem. In Akhand et al.
(2016), prominent PSO based methods were studied and compared in solving a
large number of benchmark instances for the traveling salesman problem (TSP).
PSO combined with local search was also used to solve capacitated location routing problem (Peng et al., 2017). Furthermore, a PSO algorithm was hybridized with a greedy randomized adaptive search procedure in order to solve a variant of the VRP (Marinakis et al., 2010). Moreover, a review was done by Zhang et al. (2015) to resume all works in the literature which use swarm intelligence techniques to tackle green logistic problems.

In the context where several objectives are considered, multi-objective particle swarm optimization (called MOPSO in the literature) can be chosen as a solving method. In Govindan et al. (2014), a two-echelon vehicle routing problem has been studied. It was solved using A hybridization of MOPSO and adapted multi-objective variable neighborhood search (AMOVNS). A comparison with genetic based metaheuristics showed the good performance of their proposed hybrid method. MOPSO has also been used to solve an open vehicle routing problem (Norouzi et al., 2012). In the VRP, a particle may easily find an infeasible solution. A tailored heuristic is often developed to transform an infeasible solution into a feasible one. Mousa et al. (2012) have proved the interest of hybridizing local search methods with PSO in generating Pareto fronts for multi-objective optimization problems. An experiment has been made by Castro et al. (2009) to justify that the intelligence of PSO can lead particles to find a feasible solution of good quality starting from an infeasible solution without incorporating any tailored heuristics.

As shown in this section, several works in the literature deal with variants of PDP, but to our best knowledge, the selective pickup and delivery problem with transfers (SPDPT) was not treated yet. However, like other NP-hard problems, optimal solutions are hardly obtained in a reasonable time when dealing with large instances. Therefore, a hybridization of PSO and local search is proposed by considering the ability of diversification of PSO and intensification of local search.
### 3. Selective pickup and delivery problem with transfers

This section presents a formal definition of the SPDPT. Before the mathematical model is presented, representation and modeling of a transfer point is firstly discussed.

#### 3.1. Transfer representation and modeling

In the PDP, one demand is carried by the same vehicle during its delivery. In the SPDPT, this constraint is relaxed since a demand can be transferred between two different vehicles at a transfer point. To model this aspect, a three-index binary variable (Cortés et al., 2010) is used to track a demand when a vehicle visits a node. For PDP and in a graph model, a node represents a site to be visited.

Generally in the literature, nodes are classified into three types: depot, supplier, and customer. The behavior of vehicle varies according to the type of node. Vehicles should start and finish their routes at a depot. At a supplier, goods are loaded into vehicles. At a customer, goods are unloaded from vehicles. The SPDPT introduces a new type of node called transfer point, at which vehicles can either load or unload goods. In order to distinguish these two operations (loading and unloading goods), a transfer point was virtually divided into two nodes (Cortés et al., 2010): one for unloading goods, another one for loading goods. Thus, the precedence between two vehicles at any transfer point can be handled by adding a constraint: the first vehicle unloading goods should arrive at the transfer point before the second vehicle loading goods leaves. If the precedence needs to be treated more rigorously, the time of transferring demand (loading and unloading goods of a demand) also needs to be taken into account. The transferring time in Cortés et al. (2010) is considered as a constant value independent from the number of transferred demands. To deal with this issue, the transferred demands need to be identified. One solution proposed in this paper is to divide a transfer point b into three virtual nodes: p(b): prepare node, s(b): start node and f(b): finish node. Figure 2 shows the change of
demands in a vehicle passing transfer point b. If a vehicle chooses to pass a transfer point b, all the three virtual nodes should be visited sequentially (p(b), s(b), f(b)). It also captures demands in a vehicle during its transfer operation. When vehicle 1 visits node p(b), it carries three demands: 1, 2 and 3. When the node s(b) is visited, the remaining demands are: 1, 2. The unloaded demand 3 can be calculated by comparing demands between p(b) and s(b). Thus, a related unloading time can be calculated based on unloaded demands. Vehicle 1 then visits the last node at transfer point f(b). The demands are: 1, 2 and 4. Similarly, a related loading time associated with demand 4 can be calculated by comparing demands between s(b) and f(b).

<figure><img src="image_3.png" /><figcaption>Figure 2: Operations at transfer point b</figcaption></figure>

## 3.2. Problem formulation

A mathematical model of the SPDPT is presented in this section, all the associated parameters are listed below:

### 3.2.1. Notations

**Data:**

* $W$: Set of depots = $\{0\}$,

* $R$: Set of demands,

* *Supplier(r)*: Supplier of demand $r \in R$,

* *Customer(r)*: Customer of demand $r \in R$,

* $q_r$: Quantity of demand $r \in R$,
• Profit(r): Profit of satisfying demand r ∈ R,

• SD<sub>r</sub>: Unloading time of demand r ∈ R,

• SC<sub>r</sub>: Loading time of demand r ∈ R,

• Nodes: Set of nodes associated with demands
  Nodes = Supplier(r) ∪ Customer(r) : r ∈ R,

• T: Set of transfer points,

• p(b): Prepare node of transfer point b ∈ T,

• s(b): Start node of transfer point b ∈ T,

• f(b): Finish node of transfer point b ∈ T,

• p(T): Set of prepare nodes of transfer points
  p(T) = p(b) : b ∈ T,

• s(T): Set of start nodes of transfer points
  s(T) = s(b) : b ∈ T,

• f(T): Set of finish nodes of transfer points
  f(T) = f(b) : b ∈ T,

• N: Set of nodes N = W ∪ Nodes ∪ p(T) ∪ s(T) ∪ f(T),

• E: set of valid edges
  E = {⟨i, j⟩ | i ∈ W, j ∈ Nodes ∪ p(T)} ∪
  {⟨i, j⟩ | i ∈ Nodes, j ∈ W ∪ Nodes ∪ p(T), i ≠ j} ∪
  {⟨p(b), s(b)⟩ | b ∈ T} ∪ {⟨s(b), f(b)⟩ | b ∈ T} ∪
  {⟨i, j⟩ | i ∈ f(T), j ∈ W ∪ Nodes ∪ p(T)} / {⟨f(b), p(b)⟩ | b ∈ T},

• E': set of edges except the interior ones in transfers
  E' = E / {⟨p(b), s(b)⟩ | b ∈ T} ∪ {⟨s(b), f(b)⟩ | b ∈ T},

• d<sub>ij</sub>: Distance between node i and node j, where i, j ∈ N,
* $e_i$: Earliest arrival time at node $i \in W \cup Nodes$,

* $l_i$: Latest arrival time at node $i \in W \cup Nodes$,

* $V$: Set of available vehicles,

* $Q_k$: Capacity of $k \in V$,

* $M$: Big value.

### Variables:

$$X_{ij}^{k} = \begin{cases} 1, & \text{if vehicle } k \in V \text{ travels directly from node } i \in N \text{ to } j \in N \\ 0, & \text{else} \end{cases}$$

$$Z_{i}^{rk} = \begin{cases} 1, & \text{if demand } r \in R \text{ is in } k \in V \text{ when it visits node } i \in N \\ 0, & \text{else} \end{cases}$$

$A_i^k$: Starting service time of vehicle $k \in V$ at node $i \in N$

$D_i^k$: Departure time of vehicle $k \in V$ at node $i \in N$

### 3.2.2. Mixed integer linear program for the SPDPT

The two objective functions are: maximization of profit (F1) and minimization of distance (F2).

$$\max \sum_{r \in R} \sum_{k \in V} Z_{Supplier(r)}^{rk} * Profit(r) \quad (F1)$$

$$\min \sum_{ij \in E} \sum_{k \in V} d_{ij} * X_{ij}^{k} \quad (F2)$$

To model the vehicle routes, the variable $X_{ij}^k$ is used. The following constraints define the basic routes:

$$\sum_{i:wi \in E} X_{wi}^{k} \leq 1 \quad k \in V; w \in W \quad (1)$$

$$\sum_{j:jw \in E} X_{jw}^{k} = \sum_{i:wi \in E} X_{wi}^{k} \quad k \in V; w \in W \quad (2)$$

$$\sum_{i:iu \in E} X_{iu}^{k} - \sum_{j:uj \in E} X_{uj}^{k} = 0 \quad u \in Nodes; k \in V \quad (3)$$
$$ \sum_{i:ip(b) \in E} X_{ip(b)}^k = X_{ip(b)s(b)}^k \quad b \in T; k \in V \quad (4) $$

$$ X_{p(b)s(b)}^{k} - X_{s(b)f(b)}^{k} = 0 \quad b \in T; k \in V \quad (5) $$

$$ \sum_{j:f(b)j \in E} X_{f(b)}^{k} = X_{s(b)f(b)}^{k} \quad b \in T; k \in V \quad (6) $$

Constraint (1) allows not to use all the vehicles. Constraint (2) ensures that each vehicle starts and finishes its route at the same depot. The flow conservation at nodes (suppliers or customers) is defined by constraint (3). Another flow conservation applied only to transfer point is defined by constraints (4), (5) and (6).

Since the studied problem deals with the transport of demands, the variable $Z_i^{rk}$ is employed to trace them. The following constraints define the operations related to demands:

$$ Z_w^{rk} = 0 \quad k \in V; r \in R; w \in W \quad (7) $$

$$ Z_i^{rk} - M * (1 - X_{ij}^k) \le Z_j^{rk} \\ k \in V; r \in R; ij \in E' : j \ne Supplier(r) \& j \ne Customer(r) \quad (8) $$

$$ Z_j^{rk} \le Z_i^{rk} + M * (1 - X_{ij}^k) \\ k \in V; r \in R; ij \in E' : j \ne Supplier(r) \& j \ne Customer(r) \quad (8bis) $$

$$ \sum_{i:ij \in E} X_{ij}^{k_1} \le \sum_{r \in R:Supplier(r)=j} Z_j^{rk_1} + \sum_{r \in R:Customer(r)=j} Z_{Supplier(r)}^{rk_1} + \sum_{r \in R:Customer(r)=j} \sum_{b \in T} Z_{f(b)}^{rk_1} \\ j \in Nodes; k_1 \in V \quad (9) $$

$$ Z_{Customer(r)}^{rk} = 0 \quad r \in R; k \in V \quad (10) $$

$$ \sum_{r \in R} Z_j^{rk} \le M * \sum_{i:ij \in E} X_{ij}^k \\ k \in V; j \in N \setminus W \quad (11) $$

$$ \sum_{k \in V} Z_{Supplier(r)}^{rk} \le 1 \quad r \in R \quad (12) $$
$$Z_{Supplier(r)}^{rk} \leq \sum_{k_1 \in V} \sum_{i:i \in Customer(r) \in E} X_{i Customer(r)}^{k_1} \quad r \in R; k \in V \quad (13)$$

$$Z_{s(b)}^{rk} \leq Z_{p(b)}^{rk} \quad b \in T; k \in V; r \in R \quad (14)$$

$$Z_{p(b)}^{rk} - Z_{s(b)}^{rk} \leq \sum_{k_1 \in V: k_1 \neq k} Z_{f(b)}^{rk_1} \quad b \in T; k \in V; r \in R \quad (15)$$

$$Z_{f(b)}^{rk} \geq Z_{s(b)}^{rk} \quad b \in T; k \in V; r \in R \quad (16)$$

$$\sum_{k \in V} Z_{f(b)}^{rk} = \sum_{k \in V} Z_{p(b)}^{rk} \quad b \in T; r \in R \quad (17)$$

$$\sum_{k \in V} Z_{f(b)}^{rk} \leq 1 \quad b \in T; r \in R \quad (17bis)$$

$$\sum_{k \in V} Z_{p(b)}^{rk} \leq 1 \quad b \in T; r \in R \quad (17ter)$$

$$\sum_{r \in R} Z_{i}^{rk} * q_{r} \leq Q_{k} \quad k \in V; i \in N \quad (18)$$

Constraint (7) guarantees that each vehicle departs empty from depot. Constraints (8) and (8bis) define the continuity of each demand at every site except its supplier and customer. Constraint (9) means that a vehicle should either unload or load goods if it visits a site. Constraint (10) forces the demand to be unloaded at its customer. Constraint (11) establishes that if a site j is not visited by a vehicle k, then $Z_j^{rk} = 0$ for each demand. Constraint (12) ensures that not all the demands have to be satisfied. Constraint (13) forces goods to be delivered to its customer if it has been picked up at its supplier. Constraints (14), (15), (16), (17), (17bis) and (17ter) together define the flow conservation in terms of demand at any transfer point. Constraint (18) establishes that the capacity of each vehicle should not be exceeded.

The time window constraint is considered in the studied problem. To model this aspect, the variable $A_i^k$ and $D_i^k$ are proposed to indicate the arrival and departure time at each site for every vehicle. The following equations give the calculations of these two variables, and the constraints needed to be respected:

$$D_w^k = 0 \quad w \in W; k \in V \quad (19)$$

$$A_j^k \geq D_i^k + d_{ij} - M * (1 - X_{ij}^k) \quad ij \in E; k \in V \quad (20)$$
$$
\begin{align}
D_i^k \ge A_i^k &+ \sum_{r \in R: i=\text{Supplier}(r)} SC_r * Z_i^{rk} \nonumber \\
&+ \sum_{r \in R: i=\text{Customer}(r)} SD_r * Z_j^{rk} - M * (1 - x_{ji}^k) \tag{21} \\
i \in \text{Nodes}; ji \in E; k \in V \nonumber
\end{align}
$$

$$
\begin{equation}
\begin{split}
D_i^k \le A_i^k &+ \sum_{r \in R: i=\text{Supplier}(r)} SC_r * Z_i^{rk} \\
&+ \sum_{r \in R: i=\text{Customer}(r)} SD_r * Z_j^{rk} + M * (1 - x_{ji}^k)
\end{split}
\tag{21bis}
\end{equation}
$$

$$
D_{p(b)}^{k} = A_{p(b)}^{k} \quad b \in T; k \in V \qquad (22)
$$

$$
D_{s(b)}^{k} = A_{s(b)}^{k} + \sum_{r \in R} SD_{r} * (Z_{p(b)}^{rk} - Z_{s(b)}^{rk}) \quad b \in T; k \in V \quad (23)
$$

$$
D_{f(b)}^{k} = A_{f(b)}^{k} + \sum_{r \in R} SC_{r} * (Z_{f(b)}^{rk} - Z_{s(b)}^{rk}) \quad b \in T; k \in V \quad (24)
$$

$$
A_i^k \le l_i * \sum_{j:ij \in E} x_{ij}^k \quad i \in W \cup \text{Nodes}; k \in V \quad (25)
$$

$$
A_i^k \ge e_i * \sum_{j:ij \in E} x_{ij}^k \qquad i \in W \cup \text{Nodes}; k \in V \quad (25\text{bis})
$$

$$
A_{f(b)}^{k_2} \geq D_{s(b)}^{k_1} - M * (2 - Z_{p(b)}^{rk_1} - Z_{f(b)}^{rk_2}) \quad k_1, k_2 \in V; b \in T; r \in R \quad (26)
$$

The departure time of each vehicle from depot is defined by constraint (19). The
arrival time of vehicle at each site is defined by constraint (20). Constraints (21)
and (21bis) establish the calculation of departure time at each site except at
the transfer points. Constraints (22), (23) and (24) define the departure time
at transfer points. Constraints (25) and (25bis) force each vehicle to respect a
predefined time window when it visits a site. Constraint (26) establishes the
precedence between two vehicles transferring demands.

Although the proposed model can fully describe the problematic context, it is
hard to be solved due to its complexity. Therefore, a hypothesis (consistent with
most real cases) is proposed to force that one demand can only be transfered
once. The related constraint is defined as follows:

$$ \sum_{k \in V} \sum_{b \in T} (Z_{p(b)}^{rk} - Z_{s(b)}^{rk}) \le 1 \quad r \in R \quad (27) $$

## 4. Hybrid Particle Swarm Optimization

Among the existed metaheuristic approaches in the literature, we have chosen particle swarm optimization (PSO) based on the reasons which have been presented in section 2.3. Since PSO will be used to solve a bi-objective problem, the principles of MOPSO is firstly introduced. Secondly, an encoding strategy will be presented. Lastly, local search will be explained.

### 4.1. Multi-Objective Particle Swarm Optimization

PSO (Eberhart and Kennedy, 1995) is an algorithm which imitates the behavior of a flock of birds. In the solution space, each particle (or individual) represents one solution of the specific problem. The population evolves by exchanging the best global solution ever found by the population and the best individual solution ever found by each particle. Since PSO gives good performance when dealing with single-objective problems, researchers tried to adapt it to solve multi-objective problems (Reyes-Sierra et al., 2006). In the literature, several variants have been proposed. Among them, the work in Coello et al. (2004) is taken as a reference to our method. Instead of directly applying it to our problem, we have made some modifications. Firstly, the two basic equations will be introduced:

$$ VEL_i = W * VEL_i + C_1 * R_1 * (REP\_PBEST_i[h] - POP_i) + C_2 * R_2 * (REP\_GBEST_i[h] - POP_i) \quad (28) $$

$$ POP_i = POP_i + VEL_i \quad (29) $$

where $i$ is the index of particle. $VEL_i$ and $POP_i$ are the velocity and position of particle $i$. $W$ is the inertia weight. $R_1$ and $R_2$ are random numbers in the range [0, ..., 1]. $C_1$ and $C_2$ are two parameters controlling the influence of
personal experience and global experience. *REP PBEST*<sub>*i*</sub> is the repository to store non-dominated solutions found by particle *i* at each iteration. In Coello et al. (2004), repository is not considered for personal best solution. However, in our proposed method, repository is also applied for this part. *REP GBEST* is the repository to store non-dominated solutions found by each particle at each iteration. *h* is the index of a leader particle which has been selected from the repository to represent the population. Since the way to select a leader could impact the performance of the algorithm, four different strategies are studied and detailed in the next section.

## 4.2. *Selection of a leader*

Repository, seen as an external archive, is a new concept in MOPSO. Three related issues need to be handled: update, capacity and selection. If a new candidate wishes to enter repository, four cases should be considered. First, if repository is empty, the candidate will be accepted. Second, if the candidate is dominated by solutions in the repository, it will be discarded. Third, if the candidate dominates some solutions in the repository, these solutions should be removed before the candidate enters the repository. Fourth, if the candidate is not dominated by any solutions in the repository, it will be accepted. The capacity of a repository can be considered as limited or unlimited. In the first case, a strategy should be proposed to decide which solutions will be discarded when the capacity is exceeded. The proposed method takes the latter case (unlimited capacity) since the number of non dominated solutions of the studied discrete problem is small. In this case, limiting the capacity could decelerate the algorithm since a strategy needs to be proposed to discard solutions.

Another important issue is the selection of a leader from the repository. A leader can be selected randomly or based on some criteria. Four selection rules related to the leader selection have been studied. The first one is random selection. The second one is First-In-First-Out(FIFO), the third one is fitness-based sharing method (Goldberg et al., 1987), and the fourth one named objective related method is proposed in this paper. The last three methods will be explained
in next subsections.

### 4.2.1. First-In-First-Out selection rule

In FIFO, a leader is selected based on the sequence of entering a queue. If no update is made in the queue, the leader selection procedure strictly respect the FIFO which is presented in figure 3(a). In this figure, solution 1 in red is initially chosen as the leader at the first iteration. After 3 iterations, solution 1 and 2 are added at the tail of the queue, and solution 3 in red is chosen as the leader. However, the insertion or removal of solutions will disturb this procedure

<figure><img src="image_4.png" /><figcaption>Figure 3: Two different cases of FIFO</figcaption></figure>

since new solutions could be found during each iteration. An example is shown in figure 3(b). In this figure, a candidate non-dominated solution 7 in green is added at the tail, and the dominated solution 2 in yellow is removed. Then the previous leader (solution 1) is added at the tail, and a new leader (solution 3 in red) is chosen for the next iteration. Briefly speaking, the update of solutions should always be made before the selection of a new leader.

### 4.2.2. Fitness-based sharing method

In fitness-based sharing method, the density of different zones is measured. A solution in a less crowed zone will have more chance to be selected as leader. The probability is calculated by using equations (30)-(33) defined below. The
density $\phi(\text{dist}_{ij})$ for each solution $i$ in the repository is firstly calculated:

$$ \phi(\text{dist}_{ij}) = \begin{cases} 1 - \left(\frac{\text{dist}_{ij}}{\sigma_{sh}}\right)^{\alpha}, & \text{dist}_{ij} < \sigma_{sh} \\ 0, & \text{Otherwise} \end{cases} \qquad (30) $$

Where $j \in \text{population}$, and population is the set of solutions from repository. $\alpha$ and $\sigma_{sh}$ are the sharing parameters. $\text{dist}_{ij}$ is the euclidean distance between solutions $i$ and $j$, which can be calculated:

$$ \text{dist}_{ij} = \sqrt{(s_i^1 - s_j^1)^2 + \dots (s_i^n - s_j^n)^2} \qquad (31) $$

Where $(s_i^1, \dots, s_i^n)$ is solution vector $i$, with $n$ corresponding to the number of objectives. For each solution $i$, an associated fitness value is calculated:

$$ \text{Fitness}_i = \frac{1}{\sum_{j \in \text{population}} \phi(\text{dist}_{ij})} \qquad (32) $$

By using the fitness value, the chance of each solution to be selected is:

$$ \text{Prob}_i = \frac{\text{Fitness}_i}{\sum_{j \in \text{population}} \text{Fitness}_j} \qquad (33) $$

According to equation (33), a solution with a greater fitness value (in less crowded zone) will have more chance to be selected.

### 4.2.3. Objective related rule

The objective related rule proposed in this paper gives more chance for high quality solution to be selected. Let us first remind that the studied problem consists of two objectives: maximizing the profit and minimizing the distance. However, a solution containing high profit and short distance does not always exist since these two objectives are against each other. Therefore, one way to select a solution is to consider only one of these two objectives. The drawback is that the selected solution cannot better reflect the studied problem. To tackle this issue, the two objectives can be considered iteratively. In one iteration, a solution with highest profit is selected as leader. In the next iteration, a solution with least distance (0 should not be taken into account) will be selected as leader. The selection process alternates between these two objectives.
Tests have been made on all the possible combinations of the proposed strategies, the results are shown in section 6.3. How to adapt PSO to the studied problem is still a question, and this will be explained in the next section.

### 4.3. *Encoding and decoding*

Since each solution is encoded into a particle as an array of real values, a strategy is proposed to decode it into related information. A particle can be divided into two parts according to the encoded information. The first part gives the information about demand assignment, and the second one gives visiting sequence. Figure 4 illustrates the decoding procedure for an example with 5 demands, 2 vehicles, and 2 transfers. In the first part, each demand is assigned with three dimensions. The first two dimensions (let us name them as V and V') contain the information related to vehicles and the values are in the interval [0,NV[, where NV is the number of vehicles. The third dimension (let us name it as T) indicates the chosen transfer and the value belongs to the interval [0,NT[, where NT is the number of transfers. From the figure, the encoded real values are first rounded off and transformed into integers. If the integers of V and V' are identical, the associated demand will not be transferred. In the opposite case, the demand will be transferred between the two vehicles which indicated by V and V', and the transfer is given by T. For the given example, demands 1, 2, 3 and 4 are assigned to vehicles 0 or 1, while demand 5 is transferred between these two vehicles at transfer 1.

In the second part, each demand is assigned with two dimensions, and the associated values should respect the interval [0,10]. For the given example, demand 1 occupies two dimensions (*demand*₁, *demand*₂) with real values (7.8, 7.5). The ten dimensions of the five demands are then arranged by sorting the real values in descending order. For the two dimensions of each demand in the sorted dimensions, the first one is replaced by its supplier and the second one indicates its customer. This generated visiting sequence will be used during the vehicle routing phase. It should be noticed that the transfer locations are not encoded since it could produce many infeasible solutions. Although the
<figure><img src="image_5.png" /><figcaption>Figure 4: Decoding procedure</figcaption></figure>

infeasible ones could be repaired by adding some extra operations, it would consume lot of computation time.

To construct a solution, the demand information table T and visiting sequence list L will be used. This process (named Decoding method) is described in Algorithm 1 (Appendix).

### 4.4. Local search and general framework of HPSO

There are mainly three defaults for the proposed decoding strategy. Firstly, a vehicle may not be fully used as the number of vehicles increases. Secondly,
demands could be transferred intentionally. Lastly, the unsatisfied demands
are not reinserted during the construction phase. The first two defaults could
increase the traveling distance, and the last default could make the obtained
profit low. As consequence, two local searches, LS1 and LS2 (described as
Algorithm 2 and 3 in Appendix), have been proposed to tackled these issues.

In LS1, the initial solution is destroyed firstly. Then each demand is inserted
into the route in a way the distance is minimized. A new route can be created
when feasibility cannot be reached even if all the demands have been tested.

In LS2, each unassigned demand is selected, and inserted into routes of S in
a way that distance is minimized. If the feasibility is reached for the candidate
route, the insertion of this demand is stopped. New route can be created if all
the available routes have already been tested. The general framework of HPSO
is presented as follows:

Algorithm 4 (HPSO)

Notations:

N: number of particles.

P: swarm of particles.

I: maximum number of iterations.

Input: N, I.

Output: G.

1. Initialize the velocity and position of each particle in the swarm.

2. Initialize the external archives *P* and *G*.

3. Set $i = 1$.

a. Set *particle* = *P*[i].

b. Decode *particle* into an initial solution *S* and set *S'* = *S*.

c. Improve *S* with LS1.

d. Update personal and global best solution *P*, *G* with *S*.

e. Improve *S'* with LS2, LS1 sequentially.

f. Update personal and global best solution *P*, *G* with *S'*.

g. $i = i + 1$.
h. Repeat from step 3.a until $i > N$.

4. Select a global leader $g$ from $G$.

5. Set $i = 1$.

a. Select personal best $p$ from $P$.

b. Update velocity and position of each particle.

c. $i = i + 1$.

d. Repeat from step 5.a.

6. Repeat from step 3 until $I$ is reached.

# 5. Evaluations of mathematical model

In this section, a new dataset of instances has been generated for the studied problem. Then the proposed formulation is validated on these instances. Lastly, the configurations of instances are modified to see their impacts.

## 5.1. New dataset

These instances are derived from Li and Lim (2003). As indicated in (Masson et al., 2013), the benefits of adding transfers into these instances were not significant due to their configurations. Therefore, only the coordinates from these instances were used, and the other information were re-constructed to create a new dataset (named Dataset-SPDPT). The format of new generated instances is described in table 1 and table 2. Each demand is associated with a pair of supplier and client. The profit of satisfying each demand is fixed at 20. The quantity is a random value less than 0.9*100, where 100 is the capacity of vehicle. The loading and unloading times are fixed at 10. The coordinates of each site is randomly selected from the instances of (Li and Lim, 2003). The time windows are generated in a way that each vehicle has enough time to collect and delivery one demand. Two groups of instances have been generated to test different aspects of the proposed model. For the first and second group, 20 and 5 instances were generated respectively. All of them contain 2 identical vehicles
with capacity of 100, 5 demands, 1 depot, 1 (for the first group) and 2 transfer points (for the second group). Those instances can be downloaded at: https://www.dropbox.com/sh/pmacwoumk9hta8v/AAArLNQWo5PXt-CiQLcx19KMa?dl=0

<table><caption>Table 1: Data for each demand</caption><thead><tr><td>Demand</td><td>Supplier</td><td>Customer</td><td>Profit</td><td>Quantity</td><td>Loading time</td><td>Unloading time</td></tr></thead><tbody><tr><td>1</td><td>2</td><td>1</td><td>20</td><td>36</td><td>10</td><td>10</td></tr></tbody></table>

<table><caption>Table 2: Coordinates and time windows</caption><thead><tr><td>Index(Supplier/Customer)</td><td>X</td><td>Y</td><td>Earliest arrival time</td><td>Latest arrival time</td></tr></thead><tbody><tr><td>2</td><td>35</td><td>30</td><td>278.22</td><td>318.22</td></tr></tbody></table>

## 5.2. Validation of transfers in selective problems

Since two objectives (F1 and F2) are considered in this paper, a lexicographic approach has been chosen. This method represents one among the different approaches used to tackle multi-objective optimization problems. A pre-defined order between the objective functions should be first established. And then, each function is optimized one at a time, by using the previous values found for other objectives at the previous steps (for more details, see (Collette and Siarry, 2013)). In this paper, (F1) is first maximized, then (F2) is minimized after fixing (F1) with the obtained value. Two reasons are behind the chosen order: the first one is that starting with the minimization of distance would generate a solution where no demand is honored (distance = 0) because of the selective aspect. And the second reason is that maximizing the profit should improve the quality of service.

The proposed MILP is solved in Cplex 12.7, and is run on an Intel Core i7-4810MQ CPU, 2.80 GHz processor with 16 GB of memory. First tests are made on the first group instances and the results are shown in table 3.

In this table, column 1 provides the name of each instance. For each instance, the maximal profit (the sum of all the profits) is presented in column 2. The
<table><caption>Table 3: Validation of transfers on instances of the first group (1 transfer point)</caption><thead><tr><th rowspan="2">Instances</th><th>Maximal</th><th colspan="3">Model with transfers</th><th colspan="3">Model without transfers</th><th>Gain of distance</th><th>Gain of Profit</th></tr><tr><th>profit</th><th>Profit</th><th>DistT</th><th>CPU(s)</th><th>Profit</th><th>Dist</th><th>CPU(s)</th><th>(DistT-Dist)/Dist</th><th>(ProfitT-Profit)/Profit</th></tr></thead><tbody><tr><td>SPDPT1</td><td>100</td><td>100</td><td>378.86</td><td>332.21</td><td>100</td><td>390.81</td><td>7.11</td><td>-3%</td><td>0%</td></tr><tr><td>SPDPT2</td><td>100</td><td>100</td><td>382.379</td><td>118.5</td><td>100</td><td>389.221</td><td>3.02</td><td>-2%</td><td>0%</td></tr><tr><td>SPDPT3</td><td>100</td><td>100</td><td>334.2</td><td>26.81</td><td>100</td><td>337.485</td><td>5.12</td><td>-1%</td><td>0%</td></tr><tr><td>SPDPT4</td><td>100</td><td>100</td><td>387.16</td><td>648.09</td><td>100</td><td>429.833</td><td>1.96</td><td>-10%</td><td>0%</td></tr><tr><td>SPDPT5</td><td>100</td><td>100</td><td>343.796</td><td>285.73</td><td>100</td><td>372.349</td><td>6.45</td><td>-8%</td><td>0%</td></tr><tr><td>SPDPT6</td><td>100</td><td>100</td><td>436.113</td><td>199.34</td><td>100</td><td>442.822</td><td>6.99</td><td>-2%</td><td>0%</td></tr><tr><td>SPDPT7</td><td>100</td><td>100</td><td>424.375</td><td>328.84</td><td>100</td><td>439.195</td><td>4.87</td><td>-3%</td><td>0%</td></tr><tr><td>SPDPT8</td><td>100</td><td>100</td><td>515.416</td><td>430.96</td><td>100</td><td>522.161</td><td>4.15</td><td>-1%</td><td>0%</td></tr><tr><td>SPDPT9</td><td>100</td><td>100</td><td>393.711</td><td>316.53</td><td>100</td><td>398.771</td><td>0.54</td><td>-1%</td><td>0%</td></tr><tr><td>SPDPT10</td><td>100</td><td>100</td><td>323.926</td><td>90.19</td><td>100</td><td>336.284</td><td>6.1</td><td>-4%</td><td>0%</td></tr><tr><td>SPDPT11</td><td>100</td><td>100</td><td>348.894</td><td>96.12</td><td>80</td><td>266.467</td><td>4.84</td><td>31%</td><td>25%</td></tr><tr><td>SPDPT12</td><td>100</td><td>100</td><td>481.234</td><td>15.38</td><td>80</td><td>320.114</td><td>3.44</td><td>50%</td><td>25%</td></tr><tr><td>SPDPT13</td><td>100</td><td>100</td><td>464.363</td><td>268.08</td><td>80</td><td>300.954</td><td>4.17</td><td>54%</td><td>25%</td></tr><tr><td>SPDPT14</td><td>100</td><td>60</td><td>296.503</td><td>93.41</td><td>40</td><td>174.867</td><td>3.22</td><td>70%</td><td>50%</td></tr><tr><td>SPDPT15</td><td>100</td><td>100</td><td>463.714</td><td>133.46</td><td>80</td><td>338.457</td><td>8.17</td><td>37%</td><td>25%</td></tr><tr><td>SPDPT16</td><td>100</td><td>80</td><td>338.792</td><td>424.42</td><td>60</td><td>218.629</td><td>6.33</td><td>55%</td><td>33%</td></tr><tr><td>SPDPT17</td><td>100</td><td>100</td><td>474.652</td><td>84.4</td><td>80</td><td>333.058</td><td>5.45</td><td>43%</td><td>25%</td></tr><tr><td>SPDPT18</td><td>100</td><td>100</td><td>429.544</td><td>135.24</td><td>80</td><td>258.526</td><td>5.12</td><td>66%</td><td>25%</td></tr><tr><td>SPDPT19</td><td>100</td><td>100</td><td>497.546</td><td>300.23</td><td>80</td><td>358.537</td><td>9.1</td><td>39%</td><td>25%</td></tr><tr><td>SPDPT20</td><td>100</td><td>100</td><td>402.97</td><td>234.25</td><td>80</td><td>281.027</td><td>4.36</td><td>43%</td><td>25%</td></tr></tbody></table>

results for the models with and without transfers are shown from column 3 to 8. The last two columns give the gain in terms of the two objectives (F1) and (F2). As the maximal profits for the first 10 instances are reached by the model without transfers, it is impossible to improve the profit (gain equals to 0% for this objective). However, the distance is reduced from 1% to 10% after introducing transfers. For the last 10 instances, the profit obtained by the model with transfers is improved from 25% to 50% compared to the one without transfers. However, the improvement of profit is at the cost of larger distance (increasing from 31% to 70%). This phenomenon is logical because more sites are visited. In terms of solving time, it is reasonable that it consumes more time due to the complexity after adding transfers. Indeed, the advantage of introducing transfers can be concluded from two aspects. From the economical aspect, more costs are saved due to the improvement of distance for a given profit, which can be observed for the first 10 instances. From the flexibility
aspect, more choices are available for a decision maker, which can be observed for the last 10 instances (solutions with more profit can be found).

To evaluate the complexity of transfers, second tests are made on instances of the second group. In this group, 5 instances are generated by adding one transfer at various random positions into the instance SPDPT1 of the first group. The results are shown in table 4. Since these instances are based on

<table><caption>Table 4: Validation of transfers on instances of the second group (2 transfer points)</caption><thead><tr><th rowspan="2">Instances</th><th rowspan="2">Maximal profit</th><th colspan="3">Solutions with transfer</th><th colspan="3">Solutions without transfer</th><th rowspan="2">Gain of distance (DistT-Dist)/Dist</th></tr><tr><th>ProfitT</th><th>DistT</th><th>CPU(s)</th><th>Profit</th><th>Dist</th><th>CPU(s)</th></tr></thead><tbody><tr><td>SPDPT1-1</td><td>100</td><td>100</td><td>369.902</td><td>2400</td><td>100</td><td>390.81</td><td>7.11</td><td>-5%</td></tr><tr><td>SPDPT1-2</td><td>100</td><td>100</td><td>368.047</td><td>2340</td><td>100</td><td>390.81</td><td>7.11</td><td>-6%</td></tr><tr><td>SPDPT1-3</td><td>100</td><td>100</td><td>370.207</td><td>1920</td><td>100</td><td>390.81</td><td>7.11</td><td>-5%</td></tr><tr><td>SPDPT1-4</td><td>100</td><td>100</td><td>368.189</td><td>1320</td><td>100</td><td>390.81</td><td>7.11</td><td>-6%</td></tr><tr><td>SPDPT1-5</td><td>100</td><td>100</td><td>378.267</td><td>2760</td><td>100</td><td>390.81</td><td>7.11</td><td>-3%</td></tr></tbody></table>

the same instance, the results without transfer are identical to the instance SPDPT1. The gain of distance varies from 3% to 6%. Since the profit without transfer is already the maximal one, it is impossible to improve it after adding transfers. Furthermore, the solving time increases sharply with the addition of another transfer. From these tests, it can be noticed that the position of transfer point can largely impact the results.

### 5.3. *Impacts of profit and service time*

In the initial dataset, the profit and service time for each demand are fixed with identical values. To show the impact of variable profit and service time, two additional datasets were generated. For the first one (named Dataset-SPDPT-P), the profit was varied between 1 and 40 instead of fixed at 20. As to the second one (named Dataset-SPDPT-S), the service time was varied between 1 and 20 instead of fixed at 10. These two new datasets were tested and the results are compared with the initial one Dataset-SPDPT (Table 5).

In the table, the first column gives the name of each instance. From column 2 to 4, the results on the initial dataset are presented. Column 2 gives the
<table><caption>Table 5: Comparison on the three new generated datasets</caption><thead><tr><th rowspan="2">Instance</th><th colspan="3">Dataset-SPDPT</th><th colspan="3">Dataset-SPDPT-P</th><th colspan="3">Dataset-SPDPT-S</th></tr><tr><th>Profit/n</th><th>Distance</th><th>Time(s)</th><th>Profit/n</th><th>Distance</th><th>Time(s)</th><th>Profit/n</th><th>Distance</th><th>Time(s)</th></tr></thead><tbody><tr><td>SPDPT1</td><td>100/5</td><td>378.86</td><td>332.21</td><td>86/5</td><td>378.86</td><td>217.76</td><td>100/5</td><td>378.86</td><td>300.24</td></tr><tr><td>SPDPT2</td><td>100/5</td><td>382.38</td><td>118.50</td><td>118/5</td><td>382.38</td><td>152.15</td><td>100/5</td><td>382.38</td><td>153.68</td></tr><tr><td>SPDPT3</td><td>100/5</td><td>334.20</td><td>26.81</td><td>117/5</td><td>334.20</td><td>46.69</td><td>100/5</td><td>334.20</td><td>46.11</td></tr><tr><td>SPDPT4</td><td>100/5</td><td>387.16</td><td>648.09</td><td>94/5</td><td>387.16</td><td>509.19</td><td>100/5</td><td>387.16</td><td>240.16</td></tr><tr><td>SPDPT5</td><td>100/5</td><td>343.80</td><td>285.73</td><td>94/5</td><td>343.80</td><td>170.04</td><td>100/5</td><td>343.80</td><td>216.12</td></tr><tr><td>SPDPT6</td><td>100/5</td><td>436.11</td><td>199.34</td><td>117/5</td><td>436.11</td><td>67.87</td><td>100/5</td><td><strong>406.54</strong></td><td>70.55</td></tr><tr><td>SPDPT7</td><td>100/5</td><td>424.38</td><td>328.84</td><td>125/5</td><td>424.38</td><td>110.60</td><td>100/5</td><td>424.38</td><td>134.57</td></tr><tr><td>SPDPT8</td><td>100/5</td><td>515.42</td><td>430.96</td><td>127/5</td><td>515.42</td><td>155.88</td><td>100/5</td><td>515.42</td><td>453.44</td></tr><tr><td>SPDPT9</td><td>100/5</td><td>393.71</td><td>316.53</td><td>48/5</td><td>393.71</td><td>278.03</td><td>100/5</td><td><strong>396.63</strong></td><td>248.94</td></tr><tr><td>SPDPT10</td><td>100/5</td><td>323.93</td><td>90.19</td><td>129/5</td><td>323.93</td><td>85.82</td><td>100/5</td><td>323.93</td><td>88.75</td></tr><tr><td>SPDPT11</td><td>100/5</td><td>348.89</td><td>96.12</td><td>83/5</td><td>348.89</td><td>68.72</td><td>100/5</td><td>348.89</td><td>42.45</td></tr><tr><td>SPDPT12</td><td>100/5</td><td>481.23</td><td>15.38</td><td>111/5</td><td>481.23</td><td>10.96</td><td>100/5</td><td>481.23</td><td>19.99</td></tr><tr><td>SPDPT13</td><td>100/5</td><td>464.36</td><td>268.08</td><td>99/5</td><td>464.36</td><td>199.85</td><td>100/5</td><td>464.36</td><td>169.63</td></tr><tr><td>SPDPT14</td><td>60/3</td><td>296.50</td><td>93.41</td><td>76/3</td><td><strong>305.93</strong></td><td>25.75</td><td>60/3</td><td>296.50</td><td>25.38</td></tr><tr><td>SPDPT15</td><td>100/5</td><td>463.71</td><td>133.46</td><td>63/5</td><td>463.71</td><td>80.72</td><td>100/5</td><td>463.71</td><td>123.35</td></tr><tr><td>SPDPT16</td><td>80/4</td><td>338.79</td><td>424.42</td><td>116/4</td><td><strong>402.01</strong></td><td>175.97</td><td>80/4</td><td>338.79</td><td>155.47</td></tr><tr><td>SPDPT17</td><td>100/5</td><td>474.65</td><td>84.40</td><td>52/5</td><td>474.65</td><td>21.70</td><td>100/5</td><td>474.65</td><td>11.78</td></tr><tr><td>SPDPT18</td><td>100/5</td><td>429.54</td><td>135.24</td><td>127/5</td><td>429.54</td><td>56.38</td><td>100/5</td><td>429.54</td><td>67.29</td></tr><tr><td>SPDPT19</td><td>100/5</td><td>497.55</td><td>300.23</td><td>97/5</td><td>497.55</td><td>198.40</td><td>100/5</td><td>497.55</td><td>157.93</td></tr><tr><td>SPDPT20</td><td>100/5</td><td>402.97</td><td>234.25</td><td>154/5</td><td>402.97</td><td>101.89</td><td>100/5</td><td>402.97</td><td>58.20</td></tr><tr><td>SPDPT1-1</td><td>100/5</td><td>369.90</td><td>2400.00</td><td>73/5</td><td>369.90</td><td>1101.07</td><td>100/5</td><td>369.90</td><td>1398.31</td></tr><tr><td>SPDPT1-2</td><td>100/5</td><td>368.05</td><td>2340.00</td><td>129/5</td><td>368.05</td><td>1822.33</td><td>100/5</td><td>368.05</td><td>1419.11</td></tr><tr><td>SPDPT1-3</td><td>100/5</td><td>370.21</td><td>1920.00</td><td>142/5</td><td>370.21</td><td>1912.80</td><td>100/5</td><td>370.21</td><td>1414.64</td></tr><tr><td>SPDPT1-4</td><td>100/5</td><td>368.19</td><td>1320.00</td><td>102/5</td><td>368.19</td><td>996.69</td><td>100/5</td><td><strong>370.68</strong></td><td>1623.58</td></tr><tr><td>SPDPT1-5</td><td>100/5</td><td>378.27</td><td>2760.00</td><td>89/5</td><td>378.27</td><td>2274.01</td><td>100/5</td><td>378.27</td><td>2082.78</td></tr></tbody></table>

maximal profit obtained (profit) and the associated number of demands satisfied (n). Column 3 shows the traveling distance corresponding to the related profit. Column 4 presents the time (in seconds) consumed by Cplex. The text in bold means that the obtained solution has changed compared to Dataset-SPDPT.

For the dataset with variable profit (Dataset-SPDPT-P), we could draw these conclusions: (1) In the case that all the demands can be satisfied (profit/n = 100/5), varying the profits will not influence the final delivery itinerary, which could be observed by comparing the values of the column distance. (2) In the case that not all the demands can be satisfied (SPDPT14 and SPDPT16),
varying the profits could influence the final decision since maximizing the profit is preferred to minimizing the distance in our lexicographic approach. (3) In terms of solving time, the Dataset-SPDPT-P consumes less (around 400s against 600s in average). This could be explained by the preference order obtained by varying the profit. The demands of high profit would be considered first, which could accelerate the searching process.

For the dataset with variable service time (Dataset-SPDPT-S), we may conclude that a short or long service time could make the situation more or less flexible when choosing the next demand to satisfy. In other words, it could impact the visiting sequence of sites (the traveling distance) and the number of satisfied demands. This could explain the changing of distance on SPDPT6, SPDPT9 and SPDPT1-4.

# 6. Evaluations of approached method

In this section, the four proposed strategies are firstly compared. Then the efficiency of local search is shown. Lastly, HPSO is tested on benchmarks proposed in this paper and benchmarks from the literature.

## 6.1. Running environment and parameters setting

The programming language is Java, and our method is run on an Intel Core i7-4810MQ CPU, 2.80 GHz processor with 16 GB of memory. Three parameters related to PSO are the $w$, $c_1$ and $c_2$. Chakraborty et al. (2011) have given the convergence condition of MOPSO. The theorem is stated as follows:

**Theorem 1.** If S is the initial swarm, then subject to restraints obtained in (34), in a multi-objective search space the MOPSO algorithm will cause the swarm mean to converge to the center of the Pareto optimal set $\Lambda^*$; that is, if $\mu_t$ is the expected population mean after t iterations, then $\lim_{t \to \infty} = \bar{X}^*$, where $\bar{X}^*$ denotes the center of the Pareto-optimal set.

$$w < 1, \quad 0 < \frac{c_1 + c_2}{2} < 2(1 + w) \qquad (34)$$
The three parameters ($w = 0.8, c_1 = 1, c_2 = 1$) used in this paper satisfy the convergence condition, which means that the swarm can converge to the center of the Pareto-optimal set $\Lambda^*$ when the number of iterations increases. The number of particles and iterations are set to 50 and 1000 respectively for all the experiments. In fact, these two parameters play a very similar role which decides how many fitness evaluations will be executed. A better solution could be obtained at the expense of solving time. The parameters ($\alpha$ and $\sigma_{sh}$) associated with the fitness-based method are respectively set to the value 1 and 377 (the values are determined from preliminary tests).

## 6.2. Datasets

Tests are made on two datasets. The first one has been introduced in section 5. The second dataset is generated by modifying the instances of the SPDPTWPD (Al Chami et al., 2017a) by adding one transfer point. This dataset of 23 instances was generated in a way that the distribution of sites (R: randomly, C: clustered and RC: half-random-half-clustered) and the number of sites (20, 50, 100) are considered. However, the complexity of the considered variant does not allow to find an optimal solution nor a feasible one in a reasonable time. Several previous studies on related problems have also shown the same difficulty (Cortés et al., 2010; Qu and Bard, 2012; Rais et al., 2014). It should be noticed that our studied problem can be viewed as a generalization of the SPDPTWPD. In other words, the Pareto front for the latter one can be considered as a reference Pareto front for our problem. This front is also obtained by using Cplex while limiting the solving time.

## 6.3. *Comparison between the four proposed strategies concerning leader selection*

A preliminary test was made to see the impact of the different strategies (section 4.2) on the final results in terms of profit and distance. However, no significant difference can be observed as the methods provide rather similar results depending on the considering instance. The second test studies the impact on the convergence speed. In the test, the number of iterations is limited
to 1000. If there is no update of solution after a thresh value (100 is set in the
test), the algorithm is supposed to converge.

The four strategies are FIFO (M1), Fitness-based (M2), Objective related (M3) and random (M4). The archive is used respectively for personal best and global best during the evolution of swarm. The number of combinations to be tested are then $4^2 = 16$. The test is run 5 times and the results are shown in figure 5. From the figure, the best performance is M1*M2 which corresponds to the combination of FIFO for personal archive and Fitness-based for global archive. This combination of strategies is then fixed for all the remaining tests.

<figure><img src="image_6.png" /><figcaption>Figure 5: Impact on convergence speed based on different strategies</figcaption></figure>

### 6.4. Interest of local search integration

In order to justify the efficiency of the HPSO, comparison is made between
the initial solutions, pure PSO (without hybridization), and HPSO. The initial
swarm is the same for both pure PSO and HPSO in order to make a rigorous
test. The results can be shown in the figure below:
<figure><img src="image_7.png" /><figcaption>Figure 6: Pareto fronts obtained</figcaption></figure>

In figure 6, the number of non-dominated solutions from the initial population is limited. During the evolution of the swarm, pure PSO itself has the capacity to improve the solutions. The integration of local searches pushes the Pareto front towards the optimal one. This phenomenon can be observed for all the instances we have tested. From the test, it can be concluded that HPSO performs better than pure PSO.

### 6.5. Experiments on first dataset

HPSO is firstly tested on the new datasets SPDPT, SPDPT-P, and SPDPT-S. Two metrics are chosen to assess its performance: gap and convergence speed, and solving time (in seconds). Gap is related to solution quality and can be calculated as follows:

$$ Gap(A/B) = \frac{A - B}{B} * 100\% \qquad (35) $$

Convergence speed is a value related to iterations. We suppose that the algorithm is converged if no better solution has been found during 100 successive iterations, and the related iteration number is recorded as the convergence speed of the algorithm. Let us note that the number of total iterations is also fixed to 1000, even though the algorithm is converged. The values presented in Table 6
are the averages on each dataset. The test is run 5 times, the best performance (Best), worst performance (Worst), and average performance (Average) along with the associated standard deviation (Std) are given.

<table><caption>Table 6: Results of HPSO on new datasets</caption><thead><tr><th rowspan="2">Benchmark</th><th colspan="4">Gap (HPSO/Cplex)</th><th colspan="4">Convergence speed (iterations)</th><th colspan="2">Time (s)</th></tr><tr><th>Best</th><th>Worst</th><th>Average</th><th>Std</th><th>Best</th><th>Worst</th><th>Average</th><th>Std</th><th>Cplex</th><th>HPSO</th><th>Gain</th></tr></thead><tbody><tr><td>Dataset-SPDPT</td><td>0.39%</td><td>0.52%</td><td>0.42%</td><td>0.22</td><td>115.96</td><td>182.96</td><td>149.38</td><td>28.19</td><td>612.09</td><td>3.72</td><td>99.39%</td></tr><tr><td>Dataset-SPDPT-P</td><td>0.39%</td><td>0.39%</td><td>0.39%</td><td>0</td><td>131.28</td><td>213.92</td><td>166.70</td><td>34.41</td><td>433.65</td><td>2.99</td><td>99.31%</td></tr><tr><td>Dataset-SPDPT-S</td><td>0.39%</td><td>0.50%</td><td>0.41%</td><td>0.19</td><td>117.92</td><td>186.04</td><td>146.42</td><td>28.21</td><td>448.72</td><td>3.46</td><td>99.23%</td></tr></tbody></table>

The gap on three datasets varies from 0.39% to 0.52%. On dataset-SPDPT-P where the profit varies, HPSO gives the best and stable performance with a gap of 0.39% and a standard deviation of 0. However, it takes more iterations to converge on this dataset (166.70 in average). In fact, varying the profit could decrease the number of combinations of feasible solutions which correspond to the same amount of profits. As consequence, it is harder for HPSO to find a solution of a fixed profit, which could explain why it converges slower. From another aspect, once it finds a solution corresponding to a profit, it is easier to fall into the local optimum. It could explain why HPSO gives a stable performance on this dataset (std = 0). On dataset-SPDPT-S where the service time varies, HPSO gives a similar performance compared to Dataset-SPDPT in terms of gap and convergence speed. The service time is directly linked to the time window constraint which should be respected. The variation of service time may impact the number of feasible solutions. Therefore, we could observe a tendency that the gap and solving time have been improved a little bit. In terms of solving time, HPSO consumes around 3 seconds whereas Cplex needs around 7 to 10 minutes, and the gain is up to 99.39%.

## 6.6. Experiments on second dataset

Since HPSO is developed for a bi-objective problem, it is essential to evaluate the generated pareto fronts. These tests are made on the second dataset. Figure 7 shows the compared results on 4 out of 23 instances. The red points represent
the solutions obtained by HPSO and the black line is the reference Pareto front.
For the 23 tested instances, HPSO consumed in average 133.60 seconds to obtain
the pareto front, whereas Cplex took 16630.43 seconds.

<figure><img src="image_8.png" /><figcaption>Figure 7: Results on second dataset</figcaption></figure>

The figure 7(a) represents the result on instance SPDPTWPD-C202-2. The instance contains 13 demands, 2 vehicles, 1 transfer point, and all the sites are clustered. It can be observed that the obtained results in the middle of the Pareto front are not as good as those located on the two sides. A larger number of feasible solutions in this area could be one reason that it performs not so well. The solving time for HPSO is 25.36 seconds against 12900 seconds consumed by Cplex.

The figure 7(b) shows the result on instance SPDPTWPD-RC202. The instance is of the same size as the first instance, but the sites are distributed
in a half-random-half-clustered way. The number of feasible solutions is less
compared to the first one. The Pareto front obtained by HPSO is almost on the
reference one. HPSO took 13.05 seconds to trace this pareto front while Cplex
has consumed 7200 seconds.

The figure 7(c) illustrates the result on instance SPDPTWPD-R502. The instance contains 28 demands, 10 vehicles, 1 transfer point, and the sites are randomly distributed. HPSO gives good performances in the area where the profit is low. However, its performance concerning solution quality and number of solutions degrades sharply in the middle of the Pareto front. For this instance, Cplex has taken 36000 seconds to trace the pareto front while HPSO needs only 126.13 seconds.

The figure 7(d) gives the results on instance SPDPTWPD-RC1002-1. The instance contains 57 demands, 1 vehicle, 1 transfer point, and the sites are distributed in a half-random-half-clustered way. Since the transfer operation happens between two vehicles, the transfer point will thus never be used in this instance. Consequently, the obtained results represent the solutions for the problem without transfers (SPDPTWPD). From the figure, the result is satisfactory in terms of solution quality and the distribution of Pareto front. For this instance, the solving times of HPSO and Cplex are 58.63 and 12000 seconds respectively.

7. Conclusion

This work can be viewed as the first attempt to study the selective pickup and
delivery problem with transfers (SPDPT). We first introduced a MILP model
for this new variant. Then we have tested it on 25 new generated instances. The
obtained gains for the majority of tested instances prove the advantage of using
transfer points. Taking into consideration the complexity of our considered
variant, the exact method requires a high solving time when we try to solve
big instances of the problem. To face up this drawback and in order to solve
larger instances, a metaheuristic approach based on a hybrid particle swarm
optimization (HPSO) has been proposed. HPSO is tested on the 25 generated instances and also on related instances from the literature. The computational results show the good quality of the obtained solutions generated in a small solving time.

In our future works, we will work on improving our exact method to generate the real Pareto front on related instances. In addition, we will develop several local search methods to improve the performance of our metaheuristic. Generating instances with several transfer points and finding their best locations will be also the subject of our future studies.

# Appendix

## Algorithm 1 (Decoding method)

Notations:

r: Number of demands.

P: Particle which is represented by an array of real values and the total dimension is 5\*r.

T: Table containing the assignment information for each demand.

L: List defining the visiting sequence of each site.

S: A complete solution of the problem.

A: Set of assigned demands.

U: Set of unassigned demands.

Input: P

Output: S, U, and A.

1. Construct demand assignment table (T)

a. Build $D = \{1, 2, \dots, r\}$ and $T = \emptyset$.

b. Select $d$ from set $D$ and remove it.

c. Set $v = P[(d-1)*3+1]$, $v' = P[(d-1)*3+2]$, $t = P[(d-1)*3+3]$.

d. Round off $v, v'$ and $t$.

e. If $v = v'$, add tuple {$d, v, v', no, -1$} into table $T$.
Otherwise, add tuple {$d, v, v', yes, t$} into table $T$.

f. Repeat from step 1.b until $D = \emptyset$.

2. Construct visiting sequence list (L)

a. Build $D = \{1, 2, \dots, r\}$, $L = \emptyset$ and $L' = \emptyset$.

b. Select $d$ from set $D$ and remove it

c. Create two tuples $(d, value1)$ and $(d, value2)$.

d. Set $value1 = P[3*r+(d-1)*2+1]$ and $value2 = P[3*r+(d-1)*2+2]$.

e. Add the two tuples into $L'$.

f. Repeat from step 2.b until $D = \emptyset$.

g. Sort $L'$ in descending order according to the values of tuples.

h. Set $i = 1$.

i. Read demand index from $L'$ and set $c = L'[i][1]$.

ii. If $c$ exists in $L$, add $-c$ into $L$. //negative value means customer
Otherwise, add $c$ into $L$. //positive value means supplier

iii. $i = i + 1$.

iv. Repeat from step 2.h.i until $i = 2 * r + 1$.

3. Construct a complete solution (S)

a. Set $U = \{1, 2, \dots, r\}$, $A = \emptyset$.

b. Set $i = 1$.

c. Set $c = L[i]$.

d. $i = i + 1$.

e. If $c$ is negative, repeat from 3.c until $i = 2 * r + 1$.

f. Set `supplier = c, customer = -c, demand = c`.

g. Set `vehicle1 = T[demand][2]`, `vehicle2 = T[demand][3]`, `status = T[demand][4]`, `transfer = T[demand][5]`.

h. If `status = no`, do

i. Save a copy $S' = S$.

ii. Insert supplier and customer into vehicle1 of solution $S$ by respecting
the visiting sequence $L$.

iii. If $S$ is not feasible, restore $S$ from $S'$.

Otherwise, remove demand from $U$ and add it into $A$.
i. If status = yes, do

i. Save a copy $S' = S$.

ii. Remove all the transfers in $S$.

iii. Insert supplier into vehicle1 of solution $S$ by respecting $L$.

iv. Insert client into vehicle2 of solution $S$ by respecting $L$.

v. Restore all the transfers in $S$.

vi. Insert transfer into vehicle1 and vehicle2 by testing all the possible positions. When the feasibility is met for the first time, stop.

vii. If $S$ is not feasible, restore $S$ from $S'$.
Otherwise, remove demand from $U$ and add it into $A$.

j. Repeat from 3.c until $i = 2 * r + 1$.

Algorithm 2 (LS1: minimize the distance)

Notations:

$S$: A complete solution of the problem.

$A$: Set of assigned demands.

$Nv$: number of vehicles.

$U$: set of unassigned demands.

Input: $S$.

Output: Improved $S$.

1. Save a copy, set $S' = S$.

2. Destroy solution $S$, set $S = \emptyset$.

3. If $Nv \neq 0$, create a new route $V = \emptyset$ and insert it into $S$, $Nv = Nv - 1$.
Otherwise, $S = S'$, stop the algorithm.

4. If $A$ is empty, stop the algorithm.

5. Set *Iterator* = *A*.head.

6. Select *d* indicated by the *iterator*, *iterator* → *next*.

7. Insert *d* into *V* in the position where distance is minimal.

8. If $S$ is feasible, remove $d$ from $A$.

9. If *iterator* = *A*.end, repeat from step 3.
Otherwise, repeat from step 6.

Algorithm 3 (LS2: maximize the profit)

Notations:

S: A complete solution of the problem.

Nv: number of vehicles.

U: set of unassigned demands.

Input: S.

Output: Improved S.

1. Select $d$ from $U$.

2. Set $i = 1$.

3. If $i > S.length$, create an empty route $V = \emptyset$, insert $d$ into $V$, and add $V$ into $S$.

4. Set route $V = S[i]$, insert $d$ into $V$ in the position where distance is minimal.

5. $i = i + 1$.

6. If $S$ is not feasible, repeat from step 3 until $i > Nv$.

7. repeat from step 1.

## Acknowledgments

This work is supported by the ANR (French National Research Agency) in the framework of the project TCDU (Collaborative Transportation in Urban Distribution). This project ANR-14-CE22-0017 is labeled by the Pôle Véhicule du Futur, and is jointly performed by four partners, the three french universities of technology (UTT, UTBM, UTC) and the society Share And Move Solutions. This work is also financially supported by a program of the China Scholarship Council for PhD Scholarship No. 201504490057.
References

Akhand, M., Hossain, S., Akter, S., 2016. A comparative study of prominent particle swarm optimization based methods to solve traveling salesman problem. International Journal of Swarm Intelligence and Evolutionary Computation 5, 2.

Al Chami, Z., El Flity, H., Manier, H., Manier, M.A., 2018. A new metaheuristic to solve a selective pickup and delivery problem, in: 2018 4th International Conference on Logistics Operations Management (GOL), pp. 1–5.

Al Chami, Z., Manier, H., Manier, M.A., 2016. New model for a variant of pick up and delivery problem, in: Systems, Man, and Cybernetics (SMC), 2016 IEEE International Conference on, IEEE. pp. 001708–001713.

Al Chami, Z., Manier, H., Manier, M.A., 2017a. A lexicographic approach for the bi-objective selective pickup and delivery problem with time windows and paired demands. Annals of Operations Research, 1–19.

Al Chami, Z., Manier, H., Manier, M.A., Fitouri, C., 2017b. A hybrid genetic algorithm to solve a multi-objective pickup and delivery problem. IFAC-PapersOnLine 50, 14656–14661.

Castro, J.P., Landa-Silva, D., Pérez, J.A.M., 2009. Exploring feasible and in-feasible regions in the vehicle routing problem with time windows using a multi-objective particle swarm optimization approach, in: Nature inspired cooperative strategies for optimization (NICSO 2008). Springer, pp. 103–114.

Chakraborty, P., Das, S., Roy, G.G., Abraham, A., 2011. On convergence of the multi-objective particle swarm optimizers. Information Sciences 181, 1411–1425.

Coello, C.A.C., Pulido, G.T., Lechuga, M.S., 2004. Handling multiple objectives with particle swarm optimization. IEEE Transactions on evolutionary computation 8, 256–279.
Collette, Y., Siarry, P., 2013. Multiobjective optimization: principles and case studies. Springer Science & Business Media.

Cortés, C.E., Matamala, M., Contardo, C., 2010. The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method. European Journal of Operational Research 200, 711–724.

Dantzig, G.B., Ramser, J.H., 1959. The truck dispatching problem. Management science 6, 80–91.

Dragomir, A.G., Nicola, D., Soriano, A., Gansterer, M., 2018. Multidepot pickup and delivery problems in multiple regions: a typology and integrated model. International Transactions in Operational Research 25, 569–597.

Drexl, M., 2012. Synchronization in vehicle routing—a survey of vrps with multiple synchronization constraints. Transportation Science 46, 297–316.

Drexl, M., Schneider, M., 2015. A survey of variants and extensions of the location-routing problem. European Journal of Operational Research 241, 283–308.

Eberhart, R., Kennedy, J., 1995. A new optimizer using particle swarm theory, in: Micro Machine and Human Science, 1995. MHS'95., Proceedings of the Sixth International Symposium on, IEEE. pp. 39–43.

Elbeltagi, E., Hegazy, T., Grierson, D., 2005. Comparison among five evolutionary-based optimization algorithms. Advanced engineering informatics 19, 43–53.

Goldberg, D.E., Richardson, J., et al., 1987. Genetic algorithms with sharing for multimodal function optimization, in: Genetic algorithms and their applications: Proceedings of the Second International Conference on Genetic Algorithms, Hillsdale, NJ: Lawrence Erlbaum. pp. 41–49.

Govindan, K., Jafarian, A., Khodaverdi, R., Devika, K., 2014. Two-echelon multiple-vehicle location–routing problem with time windows for optimization
of sustainable supply chain network of perishable food. International Journal of Production Economics 152, 9–28.

Gunawan, A., Lau, H.C., Vansteenwegen, P., 2016. Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research 255, 315–332.

Hassan, R., Cohanim, B., De Weck, O., Venter, G., 2005. A comparison of particle swarm optimization and the genetic algorithm, in: 46th AIAA/ASME/ASCE/AHS/ASC structures, structural dynamics and materials conference, p. 1897.

Kachitvichyanukul, V., 2012. Comparison of three evolutionary algorithms: Ga, pso, and de. Industrial Engineering and Management Systems 11, 215–223.

Kachitvichyanukul, V., et al., 2009a. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers & Industrial Engineering 56, 380–387.

Kachitvichyanukul, V., et al., 2009b. A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research 36, 1693–1702.

Li, H., Lim, A., 2003. A metaheuristic for the pickup and delivery problem with time windows. International Journal on Artificial Intelligence Tools 12, 173–186.

Liao, C.J., Tseng, C.T., Luarn, P., 2007. A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research 34, 3099–3111.

Marinakis, Y., Marinaki, M., Dounias, G., 2010. A hybrid particle swarm optimization algorithm for the vehicle routing problem. Engineering Applications of Artificial Intelligence 23, 463–472.
Masson, R., Lehuédé, F., Péton, O., 2013. An adaptive large neighborhood search for the pickup and delivery problem with transfers. Transportation Science 47, 344–355.

Mitrović-Minić, S., Laporte, G., 2006. The pickup and delivery problem with time windows and transshipment. INFOR: Information Systems and Operational Research 44, 217–227.

Mousa, A., El-Shorbagy, M., Abd-El-Wahed, W., 2012. Local search based hybrid particle swarm optimization algorithm for multiobjective optimization. Swarm and Evolutionary Computation 3, 1–14.

Norouzi, N., Tavakkoli-Moghaddam, R., Ghazanfari, M., Alinaghian, M., Salamatbakhsh, A., 2012. A new multi-objective competitive open vehicle routing problem solved by particle swarm optimization. Networks and Spatial Economics 12, 609–633.

Parragh, S.N., Doerner, K.F., Hartl, R.F., 2007. A survey on pickup and delivery problems. Part II: Transportation between pickup and delivery locations, to appear: Journal für Betriebswirtschaft.

Parragh, S.N., Doerner, K.F., Hartl, R.F., 2008. A survey on pickup and delivery problems. Journal für Betriebswirtschaft 58, 21–51.

Peng, Z., Manier, H., Manier, M.A., 2017. Particle swarm optimization for capacitated location-routing problem. IFAC-PapersOnLine 50, 14668–14673.

Qu, Y., Bard, J.F., 2012. A grasp with adaptive large neighborhood search for pickup and delivery problems with transshipment. Computers & Operations Research 39, 2439–2456.

Rais, A., Alvelos, F., Carvalho, M.S., 2014. New mixed integer-programming model for the pickup-and-delivery problem with transshipment. European Journal of Operational Research 235, 530–539.
Reyes-Sierra, M., Coello, C.C., et al., 2006. Multi-objective particle swarm optimizers: A survey of the state-of-the-art. International journal of computational intelligence research 2, 287-308.

Sampaio, A.H., Urrutia, S., 2017. New formulation and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks. International Transactions in Operational Research 24, 77-98.

Savelsbergh, M.W., Sol, M., 1995. The general pickup and delivery problem. Transportation science 29, 17-29.

Vansteenwegen, P., Souffriau, W., Van Oudheusden, D., 2011. The orienteering problem: A survey. European Journal of Operational Research 209, 1-10.

Zhang, S., Lee, C.K., Chan, H.K., Choy, K.L., Wu, Z., 2015. Swarm intelligence applied in green logistics: A literature review. Engineering Applications of Artificial Intelligence 37, 154-169.

Zidi, I., Mesghouni, K., Zidi, K., Ghedira, K., 2012. A multi-objective simulated annealing for the multi-criteria dial a ride problem. Engineering Applications of Artificial Intelligence 25, 1121-1131.