# A heuristics for Pickup-Delivery Problem with Cooperative Robots

Chi Thao Nguyen, Jean-Philippe Gayon, Viet Hung Nguyen, Anh Son Ta

► To cite this version:

Chi Thao Nguyen, Jean-Philippe Gayon, Viet Hung Nguyen, Anh Son Ta. A heuristics for Pickup-Delivery Problem with Cooperative Robots. ICAMCS 2024 (International Conference on Applied Mathematics and Computer Science), International School – Vietnam National University Hanoi, Vietnam; Hanoi University of Science and Technology, Vietnam; Laboratoire de Conception, Optimisation et Modélisation des Systèmes, Université de Lorraine, France, Dec 2024, Ha Noi, Vietnam. hal-04991987

HAL Id: hal-04991987

https://hal.science/hal-04991987v1

Submitted on 14 Mar 2025

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 heuristics for Pickup-Delivery Problem with Cooperative Robots

Chi Thao Nguyen¹[0009-0001-7097-130X], Jean-Philippe Gayon¹[0000-0003-1613-0275], Viet Hung Nguyen¹[0000-0003-2181-3847], and Anh Son Ta²[0000-0001-6009-9741]

¹ Université Clermont-Auvergne, CNRS, Mines de Saint-Etienne, Clermont Auvergne INP, LIMOS, France

`{chi_thao.nguyen,j-philippe.gayon,viet_hung.nguyen}@uca.fr`

² Hanoi University of Science and Technology, Vietnam
son.taanh@hust.edu.vn

**Abstract.** This paper presents a novel heuristic approach to solving the Pickup and Delivery Problem with Cooperative Robots (PDP-CR), a challenging optimization problem in automated warehouse logistics. The PDP-CR involves coordinating a fleet of robots to complete pickup and delivery tasks, some of which require multiple robots to cooperate. Our heuristic is designed to minimize the makespan by efficiently assigning robots to tasks while adhering to cooperation constraints. We compare the performance of our heuristic with an existing Mixed Integer Linear Programming (MILP) model through computational experiments on both small and large datasets. Results show that the proposed heuristic algorithm significantly reduces computation time while achieving good solutions, making it more suitable for large-scale applications.

**Keywords:** Pickup and Delivery Problem with Cooperative Robots · Mixed Integer Linear Programming (MILP) · heuristic algorithm.

## 1 Introduction

In the Pickup and Delivery Problem with Cooperative Robots (PDP-CR), we manage a fleet of several identical robots to complete a set of pickup and delivery tasks inside a warehouse. Each task requires a specified number of robots and involves transporting goods from a pick-up point to a destination. For example, a package inside the warehouse may be too large for a single robot to handle. In this case, multiple robots need to cooperate to complete the task. Tasks cannot begin until all required robots are present at the pick-up location. A task is considered done if all robots needed for the task reach its pick-up point and then go to the destination simultaneously. After finishing a task, the robots can be assigned to other ones. All robots start their routes at a starting depot and finish at a return depot. The goal of PDP-CR is to minimize the makespan, i.e. the time at which the last robot returns to the depot.

At a glance, one can find that PDP-CR has some similarities with other problems.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Reconfiguration of warehouse robots, from https://www.mecabotix.com/</figcaption></figure>

The Vehicle Routing Problem (VRP) [15], one of the most important combinatorial optimization challenges, focuses on efficiently distributing goods or services to customers using a fleet of vehicles, typically starting from a central depot. The Pick-up Delivery Problem (PDP) [14, 1] involves transporting goods from an origin to a destination, and its mathematical model is a variant of the VRP with added constraints to ensure certain locations are visited before others. Synchronization in VRP [3, 2, 8, 5] refers to the constraints that require two or more vehicles to complete a single task. For example, the synchronization between multiple homecare staff, they must be simultaneously present at a customer [2] or synchronization between the mailman crews and the vehicles [5]. PDP-CR can be seen as a special case of the Resource Constrained Project Scheduling Problem (RCPSP) with transfer time where there is only one resource and no precedence constraint. We can see the robots as a type of resource, and every task in PDP-CR is a job in RCPSP with transfer time.

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** An example with 2 starting robots. Left: the layout and right: the solution</figcaption></figure>

The primary goal of this paper is to propose a fast heuristic algorithm for solving the Pickup and Delivery Problem with Cooperative Robots (PDP-CR). We also suggest some modifications to an existing Mixed Integer Linear Programming (MILP) formulation and theoretical results for the PDP-CR. The next section will describe the problem in more detail. In Section 3, we proposed our modified version of the flow-based MILP model for PDP-CR from [12]. The
heuristic will be explained in detail in section 4. Section 5 describe the numeri-
cal results and the performance analysis of our heuristic. Finally, the conclusion,
some observations, and potential future directions are presented in Section 6.

2 Problem Definition

We have a fleet *M* of *m* identical robots and a set *N* of *n* tasks. Every task *i* is characterized by its pick-up location *p*ᵢ, destination *d*ᵢ, process time *c*ᵢ, and number of robots required *r*ᵢ. A task *i* cannot start until *r*ᵢ robots arrive at its pickup point. This implies that The early robots that visit the task must wait for all the robots required to come, and then they can start to process the task from its pick-up point to its destination. All the robots start their paths at a starting depot, denoted by 0 and finish their path at a returning depot, denoted by *n* + 1. *t*ᵢⱼ is the time for any robot to move from task *i* to task *j* on the graph, corresponding to the time a robot moves from *d*ᵢ to *p*ⱼ. The objective of PDP-CR is to minimize the makespan, i.e., when the last robot reaches the return depot.

One can look at Figure 2 to gain more intuition on the PDP-CR. The left figure illustrates a map with 3 tasks. Every task is denoted by an arc starting from its pickup point and ending at its destination. The task in the middle needs to be served by 2 robots (imagine in a warehouse, this is a large package that does not fit on a single automated guided vehicle, so two robots must come and cooperating carrying this parcel to its destination). The right figure is the optimal paths with 2 starting robots, each tour color corresponding to the path of one robot. One can observe that after two robots finish the "diagonal" tasks, they meet at the pick-up node of the "horizontal" task. If one robot comes first, it must wait for another, and then, they can start processing the task, and return to the depot together. So at some point, the robots may share the same route to perform a task or on the way to another task that needs multiple robots.

3 MILP formulation

Two formulations for PDP-CR have been proposed in [12]. Namely, the VRP-
based formulation and the flow-based formulation. In this section, we will provide
a more succinct version of the flow-based formulation in [12]. We consider a
robot as a flow unit. Let $x_{ij} = 1$ if there are a robot do task $j$ right after task $i$,
$f_{ij} \in \mathbb{R}$ denotes the number of flow going to task $j$ right after $i$. $z_i \in \mathbb{R}$ denotes
the time robots start to work task $i$. If $i = n+1$ then $z_{n+1}$ is the time all robots
return to the depot. And $z_0$ is the time robots leave the starting depot. And
let $N^+ = \{0\} \cup N$ and $N^- = N \cup \{n+1\}$. The enhanced flow-based model to
minimize the makespan of PDP-CR is as follow:

$$ \min \quad z_{n+1} \qquad (1) $$

$$ \text{s.t.} \quad \sum_{j \in N^{-}} f_{0j} = m, \qquad (2) $$

$$ \sum_{i \in N^{+}} f_{i,n+1} = m, \qquad (3) $$

$$ \sum_{i \in N^{+}} f_{ij} = r_i \quad \forall j \in N \qquad (4) $$

$$ \sum_{j \in N^{-}} f_{ij} = r_i \quad \forall i \in N \qquad (5) $$

$$ z_0 = 0, \qquad (6) $$

$$ z_j + M(1 - x_{ij}) \geq z_i + c_i + t_{ij} \quad \forall i \in N^{+}, \forall j \in N^{-}, i \neq j, \qquad (7) $$

$$ f_{ij} \geq x_{ij} \quad \forall i \in N^{+}, \forall j \in N^{-}, i \neq j, \qquad (8) $$

$$ r_i x_{ij} \geq f_{ij} \quad \forall i \in N^{+}, \forall j \in N^{-}, i \neq j, \qquad (9) $$

$$ f_{ij} \in \mathbb{R} \quad \forall i \in N^{+}, \forall j \in N^{-}, i \neq j \qquad (10) $$

$$ z_i \in \mathbb{R} \quad \forall i \in N^{-} \qquad (11) $$

$$ x_{ij} \in \{0, 1\}, \quad \forall i \in N^{+}, \forall j \in N^{-}, i \neq j \qquad (12) $$

In the formulation, the objective function (1) calls for minimizing the time that all robots reach the returning depot $z_{n+1}$, which is the makespan. Constraints (2) and (3) ensure that there are $m$ flow units leaving the starting depot and $m$ flow units reach the returning depot. (4) and (5) is the flow conversation constraint for each task. The starting time of all flows leaving the source is 0 is guaranteed by constraint (6). The constraint (7) is a Subtour Elimination Constraint (SEC) and is the linearization of the following constraint:

$$ x_{ij} = 1 \implies z_j \geq z_i + c_i + t_{ij} \quad \forall i \in N^{+}, \forall j \in N^{-}, i \neq j $$

The value of $M$ is obtained using Algorithm 1. And finally, constraints (8) and (9) imply the relation between $f$ and $x$.

<caption>**Algorithm 1 Choosing Big M**</caption>

```
M ← 0
for each node i on G do
    M_i ← max distan from i to other tasks
    M ← M + c_i + M_i
```
# 4 Greedy heuristics for PDP-CR

## 4.1 Constructing a PDP-CR solution from a set of paths

In this subsection, we give an algorithm to construct a PDP-CR solution from a set of paths. Concretely, let $\alpha_k$ be the schedule (or path) of robot $k$ which contains the sequence of executed tasks by robot $k$. Let also $\alpha = (\alpha_1, \dots, \alpha_m)$ the vector of all paths. The goal is to find the starting time of every task and the makespan, assuming that they start as soon as possible.

For example, in an instance with 3 starting robots and 6 tasks, tasks 2 and 5 require 2 robots, task 6 requires 3 robots, and the other tasks require one. The path of the first robot is (0, 1, 6, 2, 5, 4, 7), the second robot is (0, 6, 2, 3, 7) and the third is (0, 6, 5, 7). Find the starting time of every task.

Consider the directed graph $\mathcal{F} = (A, V)$ with $V = N \cup \{0, n+1\}$. Arcs in $A$ are constructed as follows. For every path $\alpha_i = (j_1^{\alpha_i}, j_2^{\alpha_i}, \dots, j_{k_i}^{\alpha_i})$, we have $(j_1^{\alpha_i}, j_2^{\alpha_i}), (j_2^{\alpha_i}, j_3^{\alpha_i}), \dots, (j_{k_i-1}^{\alpha_i}, j_{k_i}^{\alpha_i}) \in A$. This implies that if $(j, j') \in A$, then there is at least one robot going to task $j'$ after it finishes task $j$. For the graph $\mathcal{F}$ in the previous example, we have the arcs set $A = \{(0, 1), (1, 6), (6, 2), (2, 5), (5, 4), (4, 7), (0, 6), (2, 3), (3, 7), (6, 5), (5, 7)\}$ To acquire the solution from the path set $\alpha$, we need 2 steps:

- **Step 1:** Check if the paths are valid and construct the topological sorted sequence of the vertices in $\mathcal{F}$.

- **Step 2:** Apply Algorithm 3.

There are several cases when the paths in $\alpha$ are invalid for a solution. For example, if a path of robot 1 is (3, 2, 5, 4) and robot 2 travels (1, 5, 2) then there won't exist a feasible solution. Or if a task requires 2 robots, but is only traversed by one. Proposition 1 gives a condition for the validity of the paths.

**Proposition 1.** The path set $\alpha$ are valid for a solution of PDP-CR if and only if:

- There exists a topological ordering of $\mathcal{F}$.

- task $j$ appears in exact $r_j$ paths in $\alpha$.

A topological sort is a graph traversal in which each node $j$ is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

We call $L$ the topological ordering of all the tasks in $\mathcal{F}$. To construct $L$, we can apply *Kahn' algorithm* (Algorithm 2). Note that a graph may have multiple topological ordering. In the above example, both (0, 1, 6, 2, 5, 3, 4, 7) and (0, 1, 6, 2, 5, 4, 3, 7) are the topological-sorted order of the graph $\mathcal{F}$ of these paths.

After the paths are all valid and $L$ is acquired. We can move to step 2, find the starting time of every task and the makespan by applying Algorithm 3. It's a slightly modified version of finding the longest distance in the DAG algorithm.
**Algorithm 2** Kahn's algorithm

**Require:** a graph *G*

**Ensure:** *L*: a topological sorted order of nodes in *G*

1. *L*: an empty list that will contain the sequence of topological sorted tasks

2. *S*: set of all nodes with no incoming edge

3. **while** *S* is not empty **do**

4. Remove a node *j* from *S*

5. add *j* to *L*

6. **for** each node *j'* with an edge from *j* to *j'* **do**

7. Remove edge (*j*, *j*') from the *G*

8. **if** *j*' has no other incoming edges **then**

9. Insert *j*' into *S*

10. **end if**

11. **end for**

12. **end while**

13. **if** *G* has edges **then**

14. **return** error (*G* has at least one cycle)

15. **else**

16. **return** *L* (a topologically sorted order)

17. **end if**=0

**Algorithm 3** Construct solution from paths

**Require:**

A graph *G*

A topological sorted order *L* of nodes in *G*

The transportation time between every pair of tasks and and between every task and the depot *c*<sub>jj'</sub>

The process time *c*<sub>j</sub> of every task

**Ensure:**

The starting time of every task *z*<sub>j</sub> and the makespan *z*<sub>n+1</sub>

1. *z*<sub>0</sub> ← 0;

2. *z*<sub>j</sub> ← -∞ for all *j* ∈ *N*<sup>-</sup>

3. **for** each vertex *j* in *L* **do**

4. **for** each task *j*' such that (*j*, *j*') ∈ *G* **do**

5. *z*<sub>cur</sub> ← *z*<sub>j</sub> + *c*<sub>j</sub> + *c*<sub>jj'</sub>

6. **if** *z*<sub>j</sub> < *z*<sub>cur</sub> **then**

7. *z*<sub>j'</sub> ← *z*<sub>cur</sub>

8. **end if**

9. **end for**

10. **end for**

11. **return** *z*<sub>j</sub> for *j* and makespan *z*<sub>n+1</sub>
## 4.2 Greedy algorithm

This section describes a greedy heuristic to acquire a solution for PDP-CR quickly. The idea of algorithm 4 is to append tasks iteratively to the path of the robots; based on which task, after appending it to its number of required paths, the makespan increases the least.

<caption>**Algorithm 4 Greedy append**</caption>

**Require:**
A set $N$ of $n$ tasks.
A set $M$ of $m$ robots.
**Ensure:** Paths of each robot, and the makespan of the solution.
1: $N^u \leftarrow N$ \quad ▷ $N^u$ contains un-inserted tasks
2: $\alpha_k = [0]$ for $k = 1, \dots, m$ \quad ▷ Initially, every robot starts at a depot
3: $l_k = 0$ for $k = 1, \dots, m$ \quad ▷ Initialize length of each path are 0
4: **while** $N^u$ is not empty **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;$c_{max} \leftarrow +\infty$
6: &nbsp;&nbsp;&nbsp;&nbsp;**for** each task $i$ in $N^u$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$L \leftarrow$ an empty list
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** each robot $k = 1, \dots, m$ **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$i_k \leftarrow$ last task visited by $k$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$l'_{ki} \leftarrow l_k + t_{i_k}$ \quad ▷ $l'_{ki}$ is the length of $l$ if append $i$ to $k$.
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Append $l'_{ki}$ to $L$
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end for**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$c_{temp} \leftarrow r_i$-th smallest value in $L$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$R \leftarrow$ corresponding tasks of $r_i$ smallest values in $L$ ▷ $R$ is the list of best paths for the current tasks
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $c_{temp} < c_{max}$ **then**
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$c_{max} \leftarrow c_{temp}$
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$i^* \leftarrow i$
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$R^* \leftarrow R$
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end for**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** each robot $k \in R^*$ **do**
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Append $i^*$ to $\alpha_k$
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$l_k \leftarrow c_{max} + c_{i^*}$
24: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end for**
25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Remove $i^*$ from $N^u$
26: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end while**
27: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$C_{max} \leftarrow \max_{k=1...I}(l_k)$
28: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $\alpha_k$ for $k = 1, \dots, m$ and $C_{max}$

In the following explanation, we use the word “iteration” to refer the loop starting at line 4. Each robot $k$ starts with an initial path containing only the starting depot. For each pair of (robot, task), $l'_{ki}$ save the temporary time of path of robot $k$. We have the set $L$ to store the data of this temporary length. Since
a task *i* needs $r_i$ robots and the task cannot start before a sufficient number of
robots arrive, $c_{temp}$ is the best possible value of the makespan of task *i* in the
current iteration, which is when we append *i* to $r_i$ paths that have its temporary
time smaller or equal to $c_{temp}$ (line 13). At each iteration, we want to append
the task that has the smallest value of $c_{temp}$ to the corresponding paths (line
15).

5 Computational Result

We test our algorithms and formulation on a device equipped with Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz chipset. The MILP model and the heuristics were implemented using Python 3.9 and the formulation was solved using CPLEX 22.1.0. The small-size data was generated as follows.

- Number of robots $m \in \{1, 2\}$.

- Number of tasks $n \in \{5, 10, 15\}$.

For each pair of chosen (number of tasks, number of robots), we generated 5
random instances according to the following:

- Robot required for each task $r_j \in \{1, 2, \dots, m\}, \forall j \in N$.

- Coordinate of pickup, destination for each task $(x_j, y_j) \in ([0, 500], [0, 500]), \forall j \in N$.

To further test our work, we also acquire large-size instances by adapting
data in [10]. The data already have information about the pick-up point and
corresponding location of each task. In each instance, we generated a number of
robots $r_j \in [1, 5]$ for each task $j$. In the tables, the column *obj* is the objective
value found by each method, *time* is the solving time in second. *gap* is the opti-
mal gap reported in CPLEX. Table 1 presents results for small-sized, randomly
generated datasets where CPLEX can achieve optimal solutions. One can see
that the MILP consistently achieves better objective values, indicating optimal
solutions. However, it requires significantly more computation time compared
to the heuristic, especially as the number of tasks increases. The heuristic pro-
vides near-optimal solutions in much less time, making it a practical alternative
for larger instances. Table 2 compares performance on larger datasets. Here,
CPLEX struggles with higher objective values and reaches the maximum pre-
set solve time (1 hour). In contrast, the heuristic yields better objective values
(up to 25% smaller) while maintaining low computation times. The heuristics
outperform the exact method in both solution quality and solving time, demon-
strating the heuristic's effectiveness in handling large-scale problems where exact
methods are computationally limited.

6 Conclusion

In this paper, we introduced a heuristic to address the Pickup and Delivery
Problem with Cooperative Robots (PDP-CR), offering a practical solution to
<table><caption>**Table 1.** Comparisions between CPLEX and Greedy heuristics on small size, generated data</caption><thead><tr><th rowspan="2">Data</th><th rowspan="2">Robots</th><th rowspan="2">Tasks</th><th colspan="3">MILP</th><th colspan="2">Heuristics</th></tr><tr><th>obj</th><th>time</th><th>gap</th><th>obj</th><th>time</th></tr></thead><tbody><tr><td>g0</td><td>1</td><td>5</td><td>2142</td><td>0.06</td><td>0.0</td><td>2554</td><td>0.01</td></tr><tr><td>g1</td><td>1</td><td>5</td><td>1668</td><td>0.05</td><td>0.0</td><td>2108</td><td>0.01</td></tr><tr><td>g2</td><td>1</td><td>5</td><td>2007</td><td>0.03</td><td>0.0</td><td>2603</td><td>0.01</td></tr><tr><td>g3</td><td>1</td><td>5</td><td>2405</td><td>0.05</td><td>0.0</td><td>2875</td><td>0.01</td></tr><tr><td>g4</td><td>1</td><td>10</td><td>3990</td><td>57.73</td><td>0.0</td><td>5110</td><td>0.03</td></tr><tr><td>g5</td><td>1</td><td>10</td><td>3796</td><td>48.77</td><td>0.0</td><td>4654</td><td>0.03</td></tr><tr><td>g6</td><td>1</td><td>10</td><td>4055</td><td>65.94</td><td>0.0</td><td>4597</td><td>0.03</td></tr><tr><td>g7</td><td>1</td><td>10</td><td>4511</td><td>76.23</td><td>0.0</td><td>4966</td><td>0.03</td></tr><tr><td>g12</td><td>2</td><td>5</td><td>2872</td><td>0.64</td><td>0.0</td><td>3161</td><td>0.01</td></tr><tr><td>g13</td><td>1</td><td>5</td><td>2572</td><td>0.38</td><td>0.0</td><td>2613</td><td>0.01</td></tr><tr><td>g14</td><td>2</td><td>5</td><td>1533</td><td>0.63</td><td>0.0</td><td>1922</td><td>0.01</td></tr><tr><td>g15</td><td>2</td><td>5</td><td>2272</td><td>0.64</td><td>0.0</td><td>2424</td><td>0.01</td></tr><tr><td>g16</td><td>2</td><td>10</td><td>2509</td><td>125.22</td><td>0.0</td><td>2675</td><td>0.02</td></tr><tr><td>g18</td><td>2</td><td>10</td><td>3072</td><td>188.06</td><td>0.0</td><td>3917</td><td>0.03</td></tr><tr><td>g19</td><td>2</td><td>10</td><td>3641</td><td>6450.69</td><td>0.0</td><td>4041</td><td>0.02</td></tr></tbody></table>

<table><caption>**Table 2.** Comparisions between MILP and Greedy heuristics on large data, every instance have approximately 50 tasks</caption><thead><tr><th rowspan="2"></th><th rowspan="2">Data</th><th rowspan="2">Robots</th><th colspan="2">MILP</th><th colspan="2">Greedy Heuristics</th></tr><tr><th>obj</th><th>time</th><th>obj</th><th>time</th><th>diff</th></tr></thead><tbody><tr><td>0</td><td>lc101-5</td><td>10</td><td>444</td><td>3600</td><td><strong>421</strong></td><td>0.94</td><td>0.05</td></tr><tr><td>1</td><td>lc102-5</td><td>10</td><td>476</td><td>3600</td><td><strong>419</strong></td><td>0.85</td><td>0.12</td></tr><tr><td>2</td><td>lc103-5</td><td>10</td><td>438</td><td>3600</td><td><strong>418</strong></td><td>0.83</td><td>0.05</td></tr><tr><td>3</td><td>lc104-5</td><td>10</td><td>438</td><td>3600</td><td><strong>407</strong></td><td>0.81</td><td>0.07</td></tr><tr><td>4</td><td>lc105-5</td><td>10</td><td>461</td><td>3600</td><td><strong>425</strong></td><td>0.79</td><td>0.08</td></tr><tr><td>5</td><td>lc106-5</td><td>10</td><td>454</td><td>3600</td><td><strong>449</strong></td><td>0.79</td><td>0.01</td></tr><tr><td>6</td><td>lc107-5</td><td>10</td><td><strong>424</strong></td><td>3600</td><td>438</td><td>0.79</td><td>-0.03</td></tr><tr><td>7</td><td>lc108-5</td><td>10</td><td><strong>474</strong></td><td>3600</td><td>475</td><td>0.80</td><td>-0.00</td></tr><tr><td>8</td><td>lc109-5</td><td>10</td><td>492</td><td>3600</td><td><strong>418</strong></td><td>0.79</td><td>0.15</td></tr><tr><td>9</td><td>lc201-5</td><td>10</td><td>871</td><td>3600</td><td><strong>739</strong></td><td>0.75</td><td>0.15</td></tr><tr><td>10</td><td>lc202-5</td><td>10</td><td>993</td><td>3600</td><td><strong>852</strong></td><td>0.73</td><td>0.14</td></tr><tr><td>11</td><td>lc203-5</td><td>10</td><td>1112</td><td>3600</td><td><strong>958</strong></td><td>0.73</td><td>0.14</td></tr><tr><td>12</td><td>lc204-5</td><td>10</td><td>890</td><td>3600</td><td><strong>671</strong></td><td>0.74</td><td>0.25</td></tr><tr><td>13</td><td>lc205-5</td><td>10</td><td>832</td><td>3600</td><td><strong>762</strong></td><td>0.74</td><td>0.08</td></tr><tr><td>14</td><td>lc206-5</td><td>10</td><td>873</td><td>3600</td><td><strong>751</strong></td><td>0.73</td><td>0.14</td></tr><tr><td>15</td><td>lc207-5</td><td>10</td><td>719</td><td>3600</td><td><strong>632</strong></td><td>0.73</td><td>0.12</td></tr></tbody></table>
the computational challenges posed by the problem. Our heuristic algorithm outperforms the MILP model in terms of computation time, especially for large problem instances, while maintaining solution quality close to optimal. The results suggest that our approach is effective for real-world applications in automated warehouses, where quick and efficient decision-making is critical. Future work could explore the improvement in the MILP formulations and have metaheuristics to improve the starting solution.

## References

1. Berbeglia, G., Cordeau, J.F., Laporte, G.: Dynamic pickup and delivery problems. European Journal of Operational Research **202**(1), 8–15 (Apr 2010).
https://doi.org/10.1016/j.ejor.2009.04.024

2. Bredström, D., Rönnqvist, M.: Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. European Journal of Operational Research **191**(1), 19–31 (Nov 2008).
https://doi.org/10.1016/j.ejor.2007.07.033

3. Drexel, M.: Synchronization in Vehicle Routing—A Survey of VRPs with Multiple Synchronization Constraints. Transportation Science **46**(3), 297–316 (Aug 2012).
https://doi.org/10.1287/trsc.1110.0400

4. Haddadene, S.A., Labadie, N., Prodhon, C.: NSGAII enhanced with a local search for the vehicle routing problem with time windows and synchronization constraints. IFAC-PapersOnLine **49**(12), 1198–1203 (2016).
https://doi.org/10.1016/j.ifacol.2016.07.671

5. Hollis, B.L., Forbes, M.A., Douglas, B.E.: Vehicle routing and crew scheduling for metropolitan mail distribution at Australia Post. European Journal of Operational Research **173**(1), 133–150 (Aug 2006).
https://doi.org/10.1016/j.ejor.2005.01.005

6. Hurkens, C.A., Woeginger, G.J.: On the nearest neighbor rule for the traveling salesman problem. Operations Research Letters **32**(1), 1–4 (2004).
https://doi.org/https://doi.org/10.1016/S0167-6377(03)00093-2

7. Kahn, A.B.: Topological sorting of large networks. Commun. ACM **5**(11), 558–562 (nov 1962).
https://doi.org/10.1145/368996.369025

8. Kim, B.I., Koo, J., Park, J.: The combined manpower-vehicle routing problem for multi-staged services. Expert Systems with Applications **37**(12), 8424–8431 (Dec 2010).
https://doi.org/10.1016/j.eswa.2010.05.036

9. Laporte, G.: The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research **59**(2), 231–247 (Jun 1992).
https://doi.org/10.1016/0377-2217(92)90138-Y

10. Li, H., Lim, A.: A metaheuristic for the pickup and delivery problem with time windows. In: Proceedings 13th IEEE International Conference on Tools with Artificial Intelligence. ICTAI 2001. pp. 160–167 (2001).
https://doi.org/10.1109/ICTAI.2001.974461

11. Liu, R., Tao, Y., Xie, X.: An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits. Computers & Operations Research **101**, 250–262 (Jan 2019).
https://doi.org/10.1016/j.cor.2018.08.002

12. Nguyen, C.T., Gayon, J.P., Nguyen, V.H., Quilliot, A., Ta, A.S.: Pickup and Delivery Problem with Cooperative Robots. In: Proceedings of the 12th International Symposium on Information and Communication Technology. pp. 695–700.
SOICT '23, Association for Computing Machinery, New York, NY, USA (Dec 2023). https://doi.org/10.1145/3628797.3628988

13. Parragh, S.N., Doerner, K.F., Hartl, R.F.: A survey on pickup and delivery problems. Journal für Betriebswirtschaft **58**(1), 21–51 (Apr 2008). https://doi.org/10.1007/s11301-008-0033-7

14. Parragh, S.N., Doerner, K.F., Hartl, R.F.: A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations. Journal für Betriebswirtschaft **58**(2), 81–117 (Jun 2008). https://doi.org/10.1007/s11301-008-0036-4

15. Toth, P., Vigo, D. (eds.): The vehicle routing problem. SIAM monographs on discrete mathematics and applications, Society for Industrial and Applied Mathematics, Philadelphia, Pa (2002)