On the Complexity of Global Scheduling Constraints under Structural Restrictions

1 Introduction

This paper investigates the manpower allocation problem with time windows and job-teaming constraints (MAPTWTC), which is a combinatorial optimization problem in the realm of scheduling and routing. The MAPTWTC tries to assign a set of tasks to a set of workers with different skills or qualifications so as to minimize the total cost. Each task is characterized by a location, a required team of workers, a processing time, and a time window. All workers are initiated at the depot and to be dispatched to fulfill a series of tasks. After finishing a task, the worker will either move to fulfill his/her next task or return to the depot. The workers are allowed to arrive at the task location at different times, but a task cannot be started until all required workers are available, which is called the synchronization constraint.

Table 1 shows an MAPTWTC instance involving 6 tasks and 3 worker types; this instance was constructed by [Li et al., 2005]. In this table, the column "Worker" specifies the number of workers of each type required; the column "PT" gives the processing time of each task; the column "Successor" presents the possible successor tasks of each task; and the column "Distance" gives the traveling distance from the depot to the task location in the first entry, and the traveling distances from the task location in the first column to task locations in the fifth column. Figure 1 illustrates a feasible solution to the instance, where 6 type 1 workers, 6 type 2 workers and 9 type 3 workers are required.

The MAPTWTC was originated from the Port of Singapore and was first mentioned in literature by [Lim et al., 2004] and [Li et al., 2005]. The authors implemented simulated annealing algorithms to seek near-optimal solutions for the MAPTWTC. [Dohn et al., 2009] studied the MAPTWTC from an application of scheduling ground handling tasks in Europe's major airports. They proposed a branch-andprice algorithm to exactly solve the problem instances of small- and medium-size. If the synchronization constraint is relaxed by allowing workers to start the tasks independently, the MAPTWTC reduces to the well-studied vehicle routing problem with time windows (VRPTW) [Solomon, 1987]. Synchronizing the scheduling subjects is a "hot" topic in recent years; we refer the reader to [Drexl, 2012; Bredstr¨om and R¨onnqvist, 2008] for more applications. The MAPTWTC can also be viewed as a type of batching problem occurring in the area of machine scheduling [Brucker, 2007]. If each task is a job batch (a batch is a group of jobs which must be processed jointly), the MAPTWTC model can be used to schedule the machines to complete all batches.

In this study, we first formulate the MAPTWTC into a network flow model. We observe that the MAPTWTC solutions can be represented by trees, one of which must correspond to one of the optimal solutions. Therefore, we next propose a tabu search algorithm that seeks the tree leading to the optimal MAPTWTC solution. A tree can be transformed to an MAPTWTC solution by solving a couple of minimum cost flow models. Finally, we show by computational experiments that our tree-based tabu search algorithm is capable of producing high-quality MAPTWTC solutions.

2 Mathematical Formulation

The MAPTWTC is defined on a complete graph G = (V,E), where V = {0, 1, . . . , n} is the vertex set and E = {(i, j)|i, j ∈ V, i ̸= j} is the edge set. Vertex 0 represents the depot and VT = {1, . . . , n} denotes n task locations. Each edge (i, j) ∈ E has a non-negative traveling distance di,j, where the distance matrix [di,j] satisfies the triangle inequality. Each vertex i ∈ VT is associated with a time window [si, ei] specifying the earliest and latest service starting times of task i, and a non-negative processing time pi. For notational convenience, we set s0 = 0, e0 = +∞ and p0 = 0 for the depot. A worker can carry out task j immediately after completing task i only if the earliest service starting time of task i plus di,j does not exceed ej. Additionally, if task j is not a successor of task i, we can set their distance di,j to be +∞. Thus, the edge set E can be updated by E = {(i, j)|si + pi + di,j ≤ ej, i, j ∈ V }. We further denote by ET = {(i, j)|(i, j) ∈ E, i, j ∈ VT} the set of edges between any two distinct task locations. Moreover, we use δ-(i) = {j|(j, i) ∈ E} and δ+(i) = {j|(i, j) ∈ E} to represent the sets of vertex i's immediate predecessors and successors, respectively.

All workers are classified into K types according to their skills or qualifications. We use vk,i (1 ≤ k ≤ K) to represent the number of type k workers required by task i. The goal of the MAPTWTC is to minimize the total cost incurred by the number of workers (W) employed and the total distance traveled (D). The objective function can be written as: αW + βD, where α and β are the labor cost per worker and the traveling cost per unit distance, respectively.

The MAPTWTC has been shown to be NP-hard in the strong sense by [Li et al., 2005]. The authors also presented an integer programming (IP) model for the problem. However, we find that their IP model is very inefficient as an upper bound on the number of workers of each type has to be set in advance and each worker is associated with |E| binary variables. As a result, this IP model contains a huge number of binary variables. We propose a more compact IP model for the MAPTWTC, which has a network flow structure. To present our model, we define the following three sets of decision variables, where i, j ∈ V and 1 ≤ k ≤ K.

Decision variables:

wi: the service starting time of task i;

xi,j: a binary variable which is equal to 1 if workers are allowed to move from vertex i to vertex j, and 0 otherwise;

yk,i,j: the number of type k workers dispatched to task j immediately after finishing task i, i.e., yk,i,j is the flow of type k workers on edge (i, j).

Using the above variables, the IP model for the MAPTWTC is as follows:

where M is a sufficiently large positive number. The objective (1) is to minimize the total cost consisting of labor cost and traveling cost. Constraints (2) guarantee that the demand of workers of each type must be met for each task. Constraints (3) are flow conservation constraints. Constraints (4) ensure that if any flow yk,i,j is positive, the value of xi,j must be equal to 1. That is, xi,j = 0 implies that no workers are allowed to traverse edge (i, j). Constraints (5) and (6) state that if workers are allowed to move from task i to task j, the earliest possible arrival time at task j, calculated by wi + pi + di,j , must be less than or equal to its service starting time wj . Constraints (7) are the time window constraints. It is easy to see that the model (IP) has feasible solutions if and only if d0,i ≤ ei for every i ∈ VT .

The model (IP ) can produce optimal solution value for the MAPTWTC, while it does not directly generate a schedule (or a route) for each worker. We can easily convert a feasible MAPTWTC schedule that is comprised of m routes into a feasible solution of the model (IP). Specifically, yk,i,j is set to the number of times edge (i, j) appearing in all routes of type k workers; xi,j is set to 1 if there exists at least one route that traverses edge (i, j), and 0 otherwise; and wi is set to the earliest service starting time of task i, which can be easily derived from the routes of the workers assigned to that task. On the other hand, we can generate a feasible schedule from a feasible solution of the model (IP) (denoted by a vector (x, y, w)) using the flow decomposition algorithm described in [Ahuja et al., 1993].

Constraints (3) reveal that the model (IP) includes K circulation problems ([Ahuja et al., 1993], page 7) with additional constraints. According to Flow Decomposition Theorem ([Ahuja et al., 1993], page 80), a circulation can be decomposed into a set of directed cycles (i.e., routes). The following theorem states that all these directed cycles must include the depot.

Theorem 1 For any feasible solution (x, y,w) to the model (IP), if the flow decomposition procedure is applied to the circulation yk (1 ≤ k ≤ K), all generated directed cycles must include the depot.

Proof. Suppose that there exists a directed cycle C which does not include the depot. We start from any vertex i on C and sequentially visit each vertex on C. From Constraints (5), we know the service starting time of each vertex must be larger than that of its predecessors. Hence, we will eventually derive wi < wi, leading to a contradiction; this implies that each cycle must start from and end at the depot. □

Figure 2 illustrates an example of circulation 1 (the circulation corresponding to the schedule of type 1 workers) in a solution. In this figure, the number adjacent to each edge is the value of y1,i,j. By the flow decomposition procedure, we obtained 6 worker schedules: (0-2-0),(0-3-0),(0-4-0),(0-60),(0-3-5-0) and (0-3-5-0). Note that the flow decomposition procedure may generate different MAPTWTC solutions, but their objective values must be the same.

3 The Tree Representation of the Solutions

The way of representing solutions is one of key issues in designing meta-heuristics. Due to the existence of the synchronization constraints, the solution representation for the MAPTWTC is more complicated than that for the VRPTW and some of other VRP variants. In this section, we show that the optimal solution of the MAPTWTC can be obtained from a tree with n + 1 vertices. An example of using trees to represent the solutions of a traveling salesman problem variant can be found in [Tu et al., 2010].

The idea of using trees to represent the MAPTWTC solutions stems from the following observations. For any feasible routing schedule to the MAPTWTC, we can shift the service starting time of all tasks as early as possible while maintaining the feasibility of the original routing tour of each worker. When no tasks can be shifted, we can identify at least one critical path for each task. The properties of all these critical paths can be captured by a minimum spanning tree. The optimal solutions of the problem can be obtained by thoroughly checking all spanning trees, i.e., the search space can be restricted only to all minimum spanning trees.

We define e(x) = {(i, j)|xi,j = 1, (i, j) ∈ E} as the set of edges that the workers are allowed to traverse when vector variable x is fixed. Analogously, when vector variable w is fixed, we can derive another edge set e(w) = {(i, j)|wi+pi+ di,j ≤ wj , (i, j) ∈ ET } ∪ {(0, j)|d0,j ≤ wj , (0, j) ∈ E}).

If vector variable x is fixed, the model (IP) can be decomposed into two separate parts. The first part includes K circulation problems (namely objective (1) together with Constraints (3) and (4)) and Constraints (2). This part can be converted into K minimum cost flow problems, which will be discussed in detail in Section 4. The second part includes Constraints (5) - (7) that constitute a system of difference constraints ([Ahuja et al., 1993], page 103). When proper values are assigned to vector variable x, we can find feasible values for vector variable w in the system of difference constraints, and obtain a feasible MAPTWTC solution by solving K minimum cost flow problems. Note that the MAPTWTC might not have feasible solutions when x is set to some values. The vector x that results in a feasible w in the system of difference constraints is called feasible. The above observations reveal that the optimal MAPTWTC solution can be obtained from a certain vector x. For any two feasible vectors x1 and x2, we have:

Lemma 1 For any two feasible vectors x1 and x2, if e(x1) ⊆ e(x2), then optx(x2) ≤ optx(x1), where optx(x) is the objective value of the best MAPTWTC solution derived from vector x.

Proof. Both x1 and x2 are feasible for the system of difference constraints (5) - (7). Since x2 provides more choices to worker flows (y) than x1 (see Constraints (4)), the solution space defined by x2 is larger than or equal to that defined by x1. This can directly derive the lemma. □

The procedure of computing optx(x) will be elaborated in Section 4. We next turn to discuss the property of the model (IP) when vector variable w is fixed. We say vector w is feasible if si ≤ wi ≤ ei for all i ∈ VT . When d0,i ≤ ei for all i ∈ VT , a feasible vector w can lead to a set of feasible MAPTWTC solutions. From Constraints (5) and (6), we know that to make the model (IP) feasible, xi,j must be set to 0 if wi + pi + di,j > wj or d0,j > wj; otherwise, xi,j can be set to either 1 or 0. However, we always set xi,j = 1 if it has two choices. This is because by Lemma 1 such setting of x leads to the best MAPTWTC solution (when w is fixed). Obviously, e(w) is in fact equivalent to the largest possible e(x) with the given w. Figure 3 depicts a graph Gw = (V, e(w)), where w corresponds to the service starting times of all tasks in the solution shown in Figure 1, i.e. w = (w1, . . . ,w6) = (60, 60, 60, 70, 110, 120). Similarly, we have the following lemma related to e(w).

Lemma 2 For any two feasible vectors w1 and w2, if e(w1) ⊆ e(w2), then optw(w2) ≤ optw(w1), where optw(w) is the objective value of the best MAPTWTC solution derived from vector w.

Proof. For a given feasible vector w, there always exists a vector x′ such that e(w) = e(x′ ). Moreover, the best objective value optw(w) is equal to optx(x′ ). Hence, the statement can be directly deduced from Lemma 1. □

We divide e(w) into two edge sets, namely critical and non-critical edges. An edge (i, j) ∈ e(w) is called critical if it satisfies at least one of the following conditions: (1) wj = wi + pi + di,j for i, j ∈ VT , (2) wj = di,j for i = 0, j ∈ VT , (3) wj = sj for i = 0, j ∈ VT ; otherwise, it is called non-critical. In Figure 3, the critical and non-critical edges are denoted by solid and dash lines, respectively. We define ∆j(w), j ∈ VT as:

Obviously, a feasible vector w must have ∆j(w) ≥ 0 for all j ∈ VT . The vector w is called tight if and only if ∆j(w) = 0, ∀ j ∈ VT , i.e., there exists at least one critical incoming edge to each vertex j. For instance, the vector w shown in Figure 3 is tight. The following theorem shows that we can always obtain a tight vector wt from a feasible vector w, where optw(wt ) must be less than or equal to optw(w).

Theorem 2 There always exists a tight vector wt for any feasible vector w such that optw(wt ) ≤ optw(w).

Proof. We construct a system of difference constraints as follows.

where ¯w = ( ¯w1, . . . , ¯wn) is a vector variable. Since w is a feasible solution to the above system, this system of difference constraints must have feasible solutions. We can apply a shortest path algorithm, e.g., Bellman-Ford algorithm, to identify the shortest traveling time (denoted by wi t ) from the depot to each vertex i on the associated constraint graph. Meanwhile, by the shortest path algorithm we can also obtain a shortest path tree (note that the shortest path tree may not be unique). According to the property of the shortest path tree, we can easily observe that wt is tight, where wt = (wt1 , . . . ,wtn ). Since wt is a feasible solution to the system of difference constraints, all edges (i, j) ∈ e(w) must also be included in the edge set e(wt ), leading to e(w) ⊆ e(wt ). By Lemma 2 we therefore have optw(wt ) ≤ optw(w). □

Suppose that T is the set of all trees spanning the graph G. According to the proof of Theorem 2, we can define a function w2t : Rn → T to express the construction of a spanning tree (i.e., shortest path tree) from a vector w. On the other hand, we can also derive a vector w from a tree t ∈ T using a function t2w : T → Rn . For a given tree t, its corresponding vector w = t2w(t) can be obtained by:

where father(j) represents the father of vertex j on tree t. We say t is feasible if its corresponding vector w is feasible, namely sj ≤ wj ≤ ej for all j ∈ VT .

The relationship between the functions w2t and t2w is as follows. If the tight vector wt is obtained from a feasible vector w by the shortest path algorithm, then we must have t2w(w2t(w)) = wt . As every feasible w is associated with a feasible tree, we can achieve the optimal solution by identifying the best spanning tree on graph G; this reduces the search space of the original problem significantly. With a given tree t, we can first apply the function t2w to get the corresponding tight vector wt and then generate the best MAPTWTC solution with regard to wt by solving K minimum cost models (see Section 4). We can straightforwardly present the following theorem.

Theorem 3 If the MAPTWTC has feasible solutions, then there must exist a feasible tree t ∈ T such that optw(t2w(t)) is the optimal solution value of the MAPTWTC.

4 MinimumCost FlowModel

For a given feasible tree t, we first obtain the vector w using function t2w(t). Next, we identify an x with the largest possible e(x) so that the tree can be evaluated by optw(t2w(t)) = optx(x). In this section, we showhow to calculate optx(x) by solving minimum cost flow models. Recall that when vector variable x is fixed, the objective (1) together with Constraints (2) - (4) and (9) can be decomposed into K separate circulation problems with inflow requirement constraints (call it circulation problem for short). The circulation problem can be further transformed into a minimum cost flow model. The value of optx(x) can be obtained by summing up the optimal solution values of all K circulation problems.

The circulation problem associated with each worker type k is given as:

We denote by vector variable yk the flows on a graph Gk = (Vk,Ek), where Vk = V and Ek = e(x). A feasible vector yk must satisfy the demand required by each task (see Constraints (17)). In the following context, we construct a new graph G′k = (V ′ k ,E′k ) from Gk. The vertex set V ′ k is {0, 1, . . . , n} ∪ {0′ , 1′ , . . . , n′} and the edge set E′k is constructed as:

where cap(i, j) denotes the flow capacity on edge (i, j). We can uniquely transform y′k (the flows on the graph G′k ) to yk by the following equations:

Reversely, Equations (25) transform yk to y′k .

Note that if we substitute y′k in Equations (25) into Equations (24), we can get yk,i,j = yk,i,j, ∀ (i, j) ∈ E; this implies that there is a one-to-one correspondence between yk and y′k . By substituting Equations (24) into (16), we can rewrite the objective function of the model (CPk) as:

Equation (26) enables us to associate each edge (i, j) ∈ E′k with a cost, denoted by ck(i, j), where:

The optimal solution of the model (CPk) can be achieved by solving a minimum cost flow model on G′k . Denoting by mck the optimal solution value of the model (CPk), we can finally get:

Figure 4 pictorially demonstrates the conversion from Gk into G′k , where k = 1 and Ek is the set of all edges in Figure 3. Since {(1, 4), (1, 6), (3, 5)} ∈ ET , the edges (1, 4′ ), (1, 6′ ), (3, 5′ ) appear in G′k . The two numbers in the parenthesis adjacent to each edge are its cost ck(i, j) and capacity cap(i, j), respectively. If we set β = 0 and α = 1, the minimum cost flows on G′k shown in Figure 4 are y′k,0,3 = y′k,3,5′ = y′k,5′ ,0′ = 2 and y′k,i,j = 0 for other edges (i, j) in E′k . Hence, from Expression (24) we know that the optimal solution value of the model (CP1), namely the minimum number of type 1 workers employed, is equal to (0 + 1 + 3 + 1 + 2 + 1) - 2 = 6.

5 A Tree-based Tabu Search Algorithm

Tabu search (TS) algorithm is a meta-heuristic that combines local search with a memory scheme in order to avoid the traps of local optima. It has been successfully applied to a wide variety of vehicle routing problems, such as the VRPTW [Potvin et al., 1996], the VRP with soft time windows [Taillard et al., 1997], the split delivery VRP [Archetti et al., 2006] and the three-dimensional loading capacitated VRP [Zhu et al., 2012]. In most of the existing literature on the VRP variants, solutions are represented by lists (or sequences) of vertices complying with some additional constraints.

We refer the reader to [Glover and Laguna, 1998] for more details on the TS algorithm. We adopt the standard framework of the TS algorithm for the MAPTWTC. Recall from Section 3 that there must exist an optimal MAPTWTC solution that can be derived from a tree. Consequently, in our tree-based TS (TTS) algorithm, the search space is restricted to a set of feasible trees, from which the optimal solution can be obtained. The overview of our TTS algorithm is presented in Algorithm 1.

Algorithm 1: The tree-based tabu search algorithm.

1 Randomly generate a feasible tree t ; Set tabuList ← ∅ and best ← t ; while termination criteria are not satisfied do 2 N(t) ← all admissible and feasible neighbors of t ; t′ ← argmint′′∈N(t){optw(t2w(t′′ ))} ; 3 if the search process is trapped in a local optimum then 4 t ← diversify(t) ; 5 tabuList ← ∅ ; 6 else 7 Update tabuList for the current move ; 8 t ← t′ ; 9 if optw(t2w(t)) < optw(t2w(best)) then best ← t ; 10 end 11 end

For a given feasible tree t, N(t) is the set of its feasible and admissible neighbors (i.e., the neighbors are not in the tabu list or allowed by the aspiration criteria). The neighborhood is generated by two tree-based operators, namely vertexrelocate operator and subtree-relocate operator. Before performing the operators on a tree t, we apply the t2w function to obtain its corresponding vector w, which can help efficiently check the feasibility of its neighboring trees.

The vertex-relocate operator vertex relocate(t, i, j) works as follows. A non-root vertex i is first relocated to be a child of vertex j and its children are then linked to its father vertex such that a new tree t′ is created. We stipulate that the vertex j cannot be the descendant of vertex i. After the vertex-relocate operation, the resultant tree t′ is feasible if wj + pj + dj,i ≤ ei. Note that all infeasible trees are excluded from N(t).

The subtree-relocate operator subtree relocate(t, i, j) is analogous to the vertex-relocate operator except that the relocation is applied to subtrees instead of vertices. We first remove the subtree rooted at vertex i from t and then link vertex i to be a child of vertex j. The infeasible resultant trees are also excluded fromN(t). In order to check the feasibility of the new tree efficiently, we pre-calculate the latest time l(i) at which the task at vertex i can be started while the subtree rooted at vertex i is still feasible. The value of l(i) can be recursively calculated by:

Then, the operator subtree relocate(t, i, j) generates a feasible tree if wj + pj + dj,i ≤ l(i).

The diversification phase in line ?? is implemented as follows. Firstly, a subset of vertices in the tree is extracted. Secondly, these vertices are selected in a random order and are sequentially reinserted into the partial tree at a random position. Each relocation must ensure the feasibility of the intermediate partial trees. Since d0,i ≤ ei, it is guaranteed that all extracted vertices can be feasibly reinserted into the partial tree. This is because vertex i can be at least feasibly linked to the root vertex (i.e., the depot).

6 Computational Results

To evaluate our TTS algorithm, we conducted experiments on two sets of test instances. The first instance set, introduced by [Li et al., 2005], was generated using the geometric data of Hong Kong and Singapore. The number of task vertices in these instances ranges from 79 to 106, and the number of worker types (i.e., K) is fixed to 5. The second instance set was generated by us from 56 well-known Solomon's VRPTW instances [Solomon, 1987]. All instances in this set have 100 vertices and 5 worker types. For each worker type, the number of workers required was generated using the similar way to that of the first instance set (refer to [Li et al., 2005] for details). For all instances, we set α ≫ β (to be precise, we set α = 106 , β = 1), implying that labor cost dominates the traveling cost.

Our TTS algorithm was coded in C++ and all experiments were conducted on a Dell server with Intel Xeon E5520 2.66 GHz CPU, 8 GB RAM and Linux operating system. For each instance, we executed our TTS algorithm 5 times using different random seeds. By some preliminary experiments, we set the tabu tenure to 100. If no improvements can be achieved after 30 consecutive iterations, we believe that the search is trapped in a local optimum and therefore activate the diversification phase. We also applied ILOG CPLEX 11.1 with default settings to solve the model (IP) for each instance. A time limit of 2 CPU hours was imposed on CPLEX for each execution. We find that CPLEX could only optimally solve some of the test instances. In addition, when we conducted experiments on several instances with more than 150 tasks, CPLEX encountered "Out of memory" exception for most of these instances.

The computational results of the first instance set is shown in Table 2, where the columns with headings "# W." and "Dist." report the numbers of workers employed and the total distance traveled, respectively. We collected the results of our TTS algorithm at 10 and 30 minutes since its start, and then present the best results of 5 runs in the blocks "TTS (10 min)" and "TTS (30 min)". The results of CPLEX are displayed in the block "CPLEX". The instances that were optimally solved by CPLEX are marked with an asterisk (*) in the first column. As a comparison, we put in Table 2 the results of the algorithms Simple-Append with simulated annealing (A + SA) and Block-Insertion with simulated annealing (I + SA) reported by [Li et al., 2005]. As they did not report the total traveling distance in their article, we can only show the number of workers employed ("# W.") and the computation times ("CPU (s)") consumed by their algorithms. Note that the values in the columns "CPU (s)" were obtained on a Pentium IV 2.0GHz machine. As clearly shown in this tables, both TTS and CPLEX outperform two SAs in terms of solution quality. However, TTS algorithm did not show too much superiority over CPLEX on this set of instances.

To further compare the TTS algorithm with CPLEX, we conducted experiments on the second instance set, and report the results in Table 3. This set of instances is divided into six groups: C1 (9 instances), C2 (8 instances), R1 (12 instances), R2 (11 instances), RC1 (8 instances) and RC2 (8 instances). Due to space limitations, we only report the average results of each instance group. The columns "Avg. # W. " and "Avg. dist." give the average numbers of workers employed and the average total traveling distance, respectively. The results generated by the TTS algorithm with 10 minutes of computation time are already very competitive, compared to the results generated by CPLEX with 2 hours of computation time. When the computation time increases to 30 minutes, the results produced by the TTS algorithm are superior to those found by CPLEX solutions; TTS is able to reduce the numbers of workers generated by CPLEX by 4.1% on average. After 2 hours of computation time, the TTS algorithm further improved the solutions and the percentage reduction of "Avg. #W." increases to 6.6%.

7 Conclusion

The main contribution of this study is the tree representation of solutions for the MAPTWTC. Its optimal solution can be obtained from a tree by solving a minimum cost flow problem for each worker type. As a result, we can get the optimal MAPTWTC solution by identifying the best tree. This observation enables us to restrict the search space to the set of spanning trees on the graph, significantly reducing the scale of the solution space of the problem. To highlight the importance and effectiveness of the new solution representation, we proposed a simple and standard tabu search algorithm to solve the problem. The computational results show that our treebased tabu search algorithm not only outperforms the simulated algorithms proposed in [Li et al., 2005], but also is superior to CPLEX.

Our work presents a new thinking on solving the VRP models with synchronization constraints. In addition, future research can consider developing more sophisticated metaheuristics by making use of this tree representation.