1 Introduction

Delivery Man Problem with Time Windows (DMPTW) is a variant of Delivery Man Problem (DMP) that is seen as a “customer centric” routing problem. However, in DMP, there is no restriction on the time the service begins. That means the service begins as soon as the deliveryman reaches a location. In practice, this assumption does not always hold. If the deliveryman reaches locations before customers are available for service, he will have to wait for the beginning of the service. Informally, in DMPTW, there are a vehicle at the main depot s, and n customers. Each customer has an additional restriction that is an interval time so that it has to be supplied. The goal is to find a tour that minimizes the overall customers’ arrival time while ensuring that all customers are served. This objective has received recent attention in the literature Ban and Nghia (2017b). Another close variant of objective is a travel duration. In the case, the problem minimizes the sum of travel durations between a depot and customer locations. The travel duration of a customer is the difference between the beginning of his service and the beginning of service at the depot. DMPTW with the travel duration objective has been studied in Heilporna (2010).

DMPTW has many practical applications for scheduling tasks and logistics, etc. In logistics, it aims at finding a tour that minimizes the sum of arrival times of all customers so that each customer must be visited within a given time window. In scheduling tasks, DMPTW can model the problem of scheduling jobs on a single machine where setup times are sequence-dependent, and each job has a release and due time. Let the latency of each job be the time that it has to wait to be started. In the scheduling problem, the sum of latency of all jobs is subject to optimization.

To the best of our knowledge, there are three works for DMPTW in the literature. Tsitsiklis Tsitsiklis (1992) presented a polynomial algorithm since the number of locations are bounded. Heilporn et al. Heilporna (2010) then provided heuristic algorithms in accordance with insertion heuristic schemes or with an insertion heuristic scheme. After that, Ban et al. Ban and Nghia (2017b) proposed a metaheuristic algorithm based on Variable Neighborhood Search (VNS). Their experimental results Ban and Nghia (2017b); Heilporna (2010) were quite promising. However, these algorithms have drawbacks. The algorithm Ban and Nghia (2017b) might become trapped into cycles, and they return to the points previously explored in the solution space. Consequently, the algorithms can get stuck in local optima. The heuristic algorithms in Heilporna (2010), on the other hand, are often too greedy, and the explored solution space is not large enough. Therefore, they can get trapped into local optimum and fail to obtain the global optimum solution in many cases.

The success of any heuristic approach depends on balance between right intensification and diversification. While the above-mentioned algorithms Ban and Nghia (2017b); Heilporna (2010) meet some drawbacks, the proposed algorithm is developed to tackle them. The main contributions of this work can be summarized as follows:

  • From the algorithmic design, we develop a two-phase metaheuristic consisting of a constructive and optimization stage. The construction stage seeks a feasible solution, whereas the improvement stage tries to improve it. Our metaheuristic combines RVND with ILS, in which ILS Talbi (2009) ensures diversification while RVND maintains intensification. This combination keeps the simplicity spirit of RVND while it effectively explores the search space. Moreover, TS Talbi (2009) is incorporated into our algorithm to mainly prohibit from getting trapped into cycles.

  • From the computational perspective, extensive numerical experiments on benchmark instances show that our algorithm reaches better solutions than the-state-of-art metaheuristics in many cases.

The rest of this paper is organized as follows. Sections 2, 3 present the literature and problem definition, respectively. Section 4 describes the proposed algorithm. Computational evaluations are reported in Section 5. Sections 6, 7 discuss and conclude the paper, respectively.

2 Literature

DMPTW is NP-hard because it is a generalization case. Despite the similarities between DMP and DMPTW, solving DMPTW is more challenging since its solution must satisfy the time windows’ constraint. M. W. Salvesbergh Salvesbergh (1985) argues that even building a feasible solution to the problem is a NP-hard problem. For NP-hard problems, there are three common approaches to solve the problem, namely, 1) exact algorithms, 2) approximation algorithms, 3) heuristic (or metaheuristic) algorithms. Firstly, the exact algorithms guarantee to find the optimal solution and take exponential time in the worst case, but they often run much faster in practice. In the literature, there is only work Heilporna (2010) to DMPTW. However, this exact algorithm only solves the problem with small sizes. Secondly, an \(\alpha \)-approximation algorithm produces a solution within some factor of \(\alpha \) of the optimal solution. Currently, no approximation work is known for DMPTW. Thirdly, heuristic algorithms perform well in practice and validate their empirical performance on an experimental benchmark of interesting instances. The metaheuristic algorithm falls into this approach. For DMPTW, there are two metaheuristic algorithms that are the algorithms of Ban et al. Ban and Nghia (2017b), and Heilporn Heilporna (2010).

Though only three works have been known for DMPTW, several classes of problems closely related to the problem were introduced in the literature: Delivery Man Problem (DMP), DMP with Profits (DMPP), Dynamic Traveling Repairman Problem (DTRP), Minimizing latency in Post-disaster Road Clearance Operations (ML-RCP), and Bi-objective Minimum Latency Problem with Profit Collection (BO-MLPPC).

  • DMP is a particular case of DMPTW without time windows. Numerous works for DMP can be found in Ban and Nguyen (2010); Ban et al. (2013); Ban and Nghia (2017a); Blum et al. (1994); Chaudhuri et al. (2003); Goemans and Kleinberg (1996). Ban et al. (2013) presented an exact algorithm to solve instances with up to 40 vertices. Several approximation algorithms Blum et al. (1994); Chaudhuri et al. (2003); Goemans and Kleinberg (1996) were proposed to solve DMP with the best approximation ratio of 3.59. In the metaheuristic approach, we can found several algorithms Ban and Nguyen (2010); Ban and Nghia (2017a); Mladenovic et al. (2012); Salehipour et al. (2011); Silva et al. (2012); Tsitsiklis (1992). In Ban and Nguyen (2010), Ban et al. used a Genetic Algorithm to solve the problem while the others Ban and Nghia (2017a); Mladenovic et al. (2012); Salehipour et al. (2011); Tsitsiklis (1992) were mainly based on Variable Neighborhood Search (VNS). Specifically, Salehipour et al. Salehipour et al. (2011) successfully combined Greedy Randomized Adaptive Search Procedure (GRASP) and VNS. Mladenovic et al. Mladenovic et al. (2012) then provided a General-VNS to improve solution quality. Later on, Silva et al. (2012) presented a multi-start approach, including a GRASP and RVNS. The algorithm finds good-quality solutions for large instances. Finally, Ban and Nghia (2017a) proposed a two-phase algorithm consisting of GRASP Feo and Resende (1995) in the construction phase and VNS+TS in the improvement phase. Their algorithm found the new best solutions in several small instances.

  • In DMPP, the aim is to find a travel plan that maximizes the total revenue. However, in contrast to DMP, in DMPP, not all the customers need to be visited. In [14], Dewilde et al. combined VNS and Tabu Search to solve the problem. M. Avci then proposed a metaheuristic that brings together GRASP, and Iterated Local Search to improve solution quality. Their metaheuristic algorithms Avci and Avci (2017); Dewilde et al. (2013) can well solve the problem with up to 500 vertices. After that, Beraldi et al. Beraldi et al. (2018) have introduced a stochastic variant of DMPP under uncertain travel times. The difference between DMPP and stochastic DMPP is that the travel times in stochastic DMPP are uncertain. Stochastic DMPP is heuristically solved by means of a beam search heuristic. Finally, Bruni et al. extended stochastic DMPP with multiple vehicles Bruni et al. (2018, 2019). The effectiveness of their algorithms was very promising through extensive experimental results.

  • In DTRP Bertsimas and Ryzin (1989), the objective function of TRP is stochastic in a dynamic environment. Currently, to the best of our knowledge, this is the only paper dealing with DTRP. However, neither metaheuristic nor exact algorithm is proposed for the problem.

  • ML-RCP Ajama et al. (2019) finds a tour with minimum latency sum in post-disaster road clearance. Unlike TRP, in disaster situations, travel costs need to be added to debris removal times. Moreover, they divide vertices in the graph into two types: 1) critical vertices must be visited; 2) non-critical vertices may or may not be visited. They provided GRASP with VNS metaheuristic that obtained optimal or near-optimal solutions on Istanbul data within seconds.

  • In BO-MLPPC Bruni (2020), routes must be constructed to maximize the collected profit and minimize the total latency. In this problem, not all the customers need to be visited and there is the presence of uncertain travel times. To address this problem, the authors proposed a Multi-Objective Iterated Local Search. The experimental results concluded that the algorithm found good-quality solutions for small and medium-size instances.

The above algorithms are the state-of-the-art algorithms for several variants of DPMTW. However, there is no time restriction in these problems, and they cannot be adapted directly to DMPTW. That means that we cannot use the above algorithms to solve DMPTW.

3 Problem definition

In this section, we provide a formulation of the DMPTW:

Given an complete graph \(K_n = (V,E)\), where \(V = \lbrace 1, 2,\ldots , n\rbrace \) is a set of vertices representing the depot and client places, and E is the set of edges connecting the vertices. Assume that, a tour is represented as \(T = (v_1 = s, v_2 ..., v_n)\), and \(v_k\) denotes the index of the vertex at the k-th position of the tour. For each edge \((v_i, v_j) \in E\), which connects the two vertices \(v_i\) and \(v_j\), there exists a cost \(c(v_i, v_j)\). This cost describes the travel time between vertex \(v_i\) and \(v_j\). A time window \([e_i, l_i]\) is associated to each vertex \(v_i \in V\), which indicates when service time at vertex \(v_i\) can start. This implies that a vertex \(v_i\) may be reached before the start \(e_i\), but service cannot start until \(e_i\) and no latter than \(l_i\) of its time window. In addition, the deliveryman spends time to serve each customer. Let \(S(v_{i})\) be the service time at vertex \(v_{i}\). Therefore, given a particular tour T, let \(D(v_k)\) be the time at which service begins at vertex \(v_k\). It is calculated as follows: \(D(v_k) = \max {\lbrace A(v_k), e_k\rbrace }\), where \(A(v_k) = D(v_{k-1}) + S(v_{k-1}) + c(v_{k-1}, v_k)\) is the arrival time at vertex \(v_k\) in the tour. We also define the travel duration of vertex \(v_i\) as the difference between the beginning of service at \(v_i\) and the beginning of service at the depot. A tour is feasible, if and only if \(A(v_k) \le l_k\) for all vertices. DMPTW requires finding a feasible tour visiting all vertices to minimize the sum of arrival times or travel durations.

4 Two-Phase Algorithm

4.1 Neighborhoods

Several popular neighborhoods in the literature are used to explore the solution space of the problem [29]. Let Tsol be the time complexity of calculating solution’s cost. The main operation in exploring these neighborhoods is the calculation of the cost function of neighboring solutions. In straightforward implementation in the worst case, this operation requires Tsol = \(\varTheta (n)\). Assume that T, and n are a tour, and its size, respectively. We describe in more details about nine neighborhoods as follows:

  • move-up moves a vertex forward one position in T. The complexity of exploring the neighborhood is \(O(Tsol \times n)\).

  • move-down moves a vertex backward one position in T. The complexity of exploring the neighborhood is \(O(Tsol \times n)\).

  • shift relocates a vertex to another position in T. The complexity of exploring the neighborhood is \(O(Tsol \times n)\).

  • swap-adjacent attempts to swap each pair of adjacent vertices in T. The complexity of exploring the neighborhood is \(O(Tsol \times n)\).

  • swap tries to swap the positions of each pair of vertices in T. The complexity of exploring the neighborhood is \(O(Tsol \times n^{2})\).

  • 2-opt removes each pair of edges from T and reconnects them. The complexity of exploring the neighborhood is \(O(Tsol \times n^{2})\).

  • Or-opt: Three adjacent vertices are reallocated to another position of T. The complexity of exploring the neighborhood is \(O(Tsol \times n^{2})\).

  • Move-forward-k-vertices moves k consecutive vertex positions to the right of T \((k = 1, 2,\ldots , l)\). The complexity of exploring the neighborhood is \(O(Tsol \times l \times n^{2})\).

  • Move-backward-k-vertices moves k consecutive vertex positions to the left of T \((k = 1, 2,\ldots , l)\). The complexity of exploring the neighborhood is \(O(Tsol \times l \times n^{2})\).

In DMPTW, when the positions of vertices in T are changed, the other vertices’ arrival times may be affected later. Therefore, Tsol requires exactly \(\varTheta (n)\) time. Unfortunately, it leads to \(\varTheta (n)\) operations for each move evaluation resulting in \(\varTheta (n^3)\) operations for a full neighborhood search.

4.2 RVND+ILS with Tabu

figure a
figure b
figure c

A good metaheuristic must ensure the balance between diversification and intensification. Mladenovic et al. Mladenovic and Hansen (1997) show that RVND allows a better understanding of the characteristics and behavior of the problem. They further claim that RVND yields local optima that are nearer to the global optimum in a more straightforward manner than other metaheuristics. However, RVND only implements intensification, and it needs to be added to diversification. Our two-phase metaheuristic includes a constructive and optimization stage. Our metaheuristic combines RVND with ILS, in which ILS Talbi (2009) ensures diversification while RVND maintains intensification. This combination keeps the simplicity spirit of RVND while it effectively explores the search space. Moreover, TS Talbi (2009) is incorporated into our algorithm to mainly prohibit from getting trapped into cycles. Algorithm 1 depicts the whole process.

The construction phase: Algorithm 2 shows the constructive procedure. The objective function used here is the sum of all positive differences between the time to reach each vertex and its due time, that is, \(\min {\sum _{i=1}^{n} \max (0, A(v_i) - l_i)}\). The algorithm works until it finds a feasible solution. From lines 2 to 6, Restricted Candidate List (RCL) is determined by ordering all non-selected vertices in terms of a greedy manner that measures the benefit of including them on tour. After that, one element will be chosen randomly from RCL. The size of RCL is a parameter that controls the balance between greediness and randomness. Since all vertices are visited, we obtain a solution. In lines 7 and 8, if the solution is feasible, it is considered an initial solution, and the construction stops. In contrast, a local search procedure based on the VNS Mladenovic and Hansen (1997) is started, and the algorithm iterates until finding a feasible solution or \(level\_max\) is reached. The solution is perturbed, by making level random shift moves, to prevent it from becoming stuck at local optima in line 12. Next, the VNS is applied to the perturbed solution to create a new solution. If it is better than the best-found solution, it is set to the new current solution through lines 13 to 24. At the end of each iteration from lines 25 to 30, level is increased by one if the current solution is not improved, or reset to 1, otherwise.

The improvement phase: After the construction of the feasible initial solution, this step tries to improve it. In this phase, the objective function is to minimize \(\sum _{i=2}^{n}(D(v_k)-D(v_1))\). Our algorithm begins with the feasible solution provided by the first phase. In Step 1, in line 4, the algorithm starts with the initial solution obtained from the construction phase and consists of three main steps repeated until a stop condition is met. In Step 2, from lines 11 to 25, we introduce the structure of several neighborhoods in RVND. Moreover, to avoid tabu moves, two tabu lists are used. Step 3, from lines 26 to 39, aims at exploiting the current solution space. To explore unvisited solution space, a diversification phase is added in Step 4 from lines 41 to 42. In the remaining of this section, more details about the four steps of our algorithm are described. Some successful applications of ILS on other combinatorial optimization problems can be found in Ibaraki et al. (2008).

In the local search procedure, the Neighborhood List (NL) is initialized with all neighborhoods. A given neighborhood is selected at random from the NL. Neighbor solutions are evaluated, and the best feasible neighboring solution is accepted if it is non-tabu, improving, or tabu but globally improving. In the case of improvement, NL is repopulated with all neighborhoods. Otherwise, we removed it from NL. The procedure terminates when NL becomes empty. Due to different neighborhood structures, two tabu lists are built. A move of the type remove-insert, swap-adjacent, move-up (down), and shift is stored in the first tabu list while the second is for 2-opt, and or moves. After each move, only the tabu list of the corresponding neighborhood is updated. The reverse move becomes tabu after some iterations that are determined dynamically. For tabu lists, a tabu tenure is a random number between 5 and 10. Specifically, the tabu lists in this work are implemented as follows:

  • Move-up (down) moved up (down) \(v_i\) forward (backward) one position cannot be applied again while it is tabu.

  • Shift applied to \(v_i\) to another position of the tour cannot be applied again while it is tabu.

  • Swap, and swap-adjacent swapped a pair of \((v_i, v_j)\) cannot swapped again while it is tabu.

  • 2-opt implemented to a pair of \((v_i, v_j)\) cannot implement again to the same vertices.

  • Or-opt applied to \((v_i, v_j)\) and \(v_k\) is prohibited from applying the same vertices.

When a better solution is found, the intensification step starts. The solution is performed with RVND without any tabu move. Since the new best-known solution is found, iterILS is set to 0. After that, the algorithm goes to the perturbation step. The Perturbation mechanism design is very important to achieve success in our algorithm. If the mechanism produces too small perturbation moves, the search procedure may return to the previously visited local optimum points. On the other hand, excessive perturbation moves may drive the search procedure to undesirable regions in the search space. To overcome these issues, we implement an adaptive perturbation mechanism. The perturbation mechanism, called double-bridge, is originally developed in Martin et al. (1991). It consists of removing and re-inserting four arcs in the tour. This mechanism can also be seen as a permutation of two disjoint segments of the tour. The detail of the step is described in Algorithm 3.

The last aspect to discuss is the stop criterium of our algorithm. A balance must be made between computation time and efficiency. Here, the algorithm stops if no improvement is found after m loops.

5 Evaluations

Table 1 Comparison between results obtained by Ban et al. Ban and Nghia (2017b) and by our algorithm on instances proposed by Dumas et al. Bruni (2020), and Silva et al. Heilporna (2010)
Full size table
Table 2 Comparison between results obtained by Ban et al. Ban and Nghia (2017b) and by our algorithm on instances proposed by Gendreau et al. Dumas et al. (1995), and Ohlmann et al. Mladenovic et al. (2012)
Full size table
Table 3 Comparison between results obtained by Heilporn et al. Fischetti et al. (1993) and by our algorithm on instances proposed by Gendreau et al. Dumas et al. (1995), and Ohlmann et al. Mladenovic et al. (2012)
Full size table
Table 4 Comparison results obtained by Ohlmann et al. Mladenovic et al. (2012), and Silva et al. Heilporna (2010) on TSPTW-instances
Full size table

Our algorithm is run on a Pentium 4 core i7 2.40 GHz processor with 8 GB of RAM. On all experiments, parameters \(\alpha \), \(level\_max\), m, and \(I_{max}\) are respectively set to 10, 5, 50, and 10. These parameters are chosen through empirical tests, and with them, the algorithm seems to produce good solutions at a reasonable amount of time compared to the other parameter values.

We also tested the performance of the proposed algorithm against the state-of-the-art algorithms Ban and Nghia (2017b); Heilporna (2010); Silva and Urrutia (2010); Ohlmann and Thomas (2007).

5.1 Instances

We implement the algorithm in four sets of instances that include more than 160 instances as followings:

  • The first set is proposed by Dumas et al. Dumas et al. (1995) and contains 135 instances grouped in 27 test cases. Each group has five Euclidean instances, coordinates between 0 and 50, with the same number of customers and the same maximum range of time windows. For example, the instances n20w60.001, n20w60.002, n20w60.003, n20w60.004, and n20w60.005 have 20 vertices and the time window for each vertex is uniformly random, between 0 and 60.

  • The second set of instances is proposed by Gendreau et al. (1998) and contains 140 instances grouped in 28 test cases.

  • The third set of instances is proposed by Ohlmann and Thomas (2007) and contains 25 instances grouped in 5 test cases. The second and third sets, in the majority, are the instances proposed by Dumas et al. (1995) with wider time windows.

  • The fourth is proposed by Silva et al. [36] to overcome the size limitations of the others since the size of instances is more than 200 customers and has wider time windows.

5.2 Results

We define the improvement of the proposed algorithm with respect to Best.Sol (Best.Sol is the best solution found by our algorithm) in comparison with the-state-of-the-art metaheuristic algorithms for the problem as followings:

$$\begin{aligned} Gap[\%]= & {} |\frac{Best.Sol - BKS}{BKS}| \times 100\% \end{aligned}$$
(1)
$$\begin{aligned} Improv[\%]= & {} |\frac{Best.Sol - Init.Sol}{Init.Sol}| \times 100\% \end{aligned}$$
(2)

In all tables, Init.Sol, Best.Sol, Aver.Sol, T correspond to the initial solution, best solution, average solution, and average time in seconds of ten executions obtained by the proposed algorithm, respectively while BKS is the best-known solution in the literature. cTime represents scaled run times, estimated on a Pentium IV by means of the factors of Dongarra Dongarra (2011). Tables from 1, 2, 3, 4 compare the results of our algorithm with the best-known solutions of the other algorithms in Ban and Nghia (2017b); Heilporna (2010); Silva and Urrutia (2010); Ohlmann and Thomas (2007). The results of the state-of-the-art metaheuristic algorithms are directly extracted from Ban and Nghia (2017b); Heilporna (2010); Silva and Urrutia (2010); Ohlmann and Thomas (2007). Our algorithm runs on the same instances with the other algorithms. Note that: Most of the results published in Ban and Nghia (2017b) are used to compare. In addition, Ban et al. Ban and Nghia (2017b) kindly provide us with their code as well as more detailed empirical results on different instances at the link [35]. To compare with their results, we run the proposed algorithm on the same instances.

In Tables 1 and 2, it is shown that the difference in the average gap between the construction and improvement phase is \(2.49\%\). The average gap is rather small. It indicates that the construction phase returns good quality solutions fast. Although the improvement of the post phase upon the construction one is not too large, it is significant since 136 new best-known solutions are found compared with the other algorithms Ban and Nghia (2017b); Heilporna (2010). For the larger instances with up to 250 instances, our search is quite time-consuming. Hence, the first way to reduce the large running time is to run the construction phase with a slight loss of \(2.49\%\) solution quality on average.

Tables 1 and 2 show the results on the Dumas et al.’s Dumas et al. (1995) instances and compare them with the results obtained by the algorithm in Ban and Nghia (2017b). The quality of our solutions is much better than Ban et al. in Ban and Nghia (2017b) in most instances. The average result of \(-3.3 \%\) is slightly better than the one obtained by Ban et al. in Ban and Nghia (2017b), while the run time is comparable on average. For the instances with more than 200 vertices, feasible solutions have been unknown in the previous algorithms Ban and Nghia (2017b); Heilporna (2010); meanwhile, the feasible solutions for instances with up to 250 vertices can be found by our algorithm. It is also a significant result because building a feasible solution to the problem is NP-hard problem Salvesbergh (1985).

In Table 3, our result is comparable with Heilporn et al.’s algorithm Heilporna (2010). Specifically, it reaches the better solutions for 10 out of 24 instances. Besides, it obtains the same results for 4 cases. The improvement is significant when Heilporn et al.’s algorithm is one of the state-of-the-art metaheuristics for the problem.

Table 4 shows that most algorithms are developed for a specific variant that does not apply to the other variants. Our algorithm still runs well to TSPTW, although it was not designed for solving it. In comparison with the best-known solution in Silva and Urrutia (2010); Ohlmann and Thomas (2007), our algorithm’s solutions obtain the optimal solutions for the instances with up to 100 vertices. The average gap between the best-known solution and our result is about 0.0%. It shows that our result reaches the best-known solutions for all instances.

The algorithm in Ban and Nghia (2017b) was executed on the nearly similar configuration with the proposed algorithm. However, G. Heilporna et al’s and the proposed algorithm were executed on computers with different configurations. To compare the running time of them, a scaled running time (cTime) estimated on an AMD Opteron 275/2.2 Ghz (this configuration is almost the same as one used in Heilporna (2010)) by means of the factors of Dongarra Dongarra (2011) is used. In this case, the running time comparison is evaluated in a relative manner. From the experimental results, the running time of the proposed algorithm grows quite moderate compared to the Heilporn et al.’s algorithm Heilporna (2010) while it is comparable with the one of Ban et al.’s algorithm Ban and Nghia (2017b).

6 Discussions

According to our observation, there are numerous local optima and only one global optimal solution in DMPTW. The search space overall seems to exhibit the big-valley structure. The big valley hypothesis suggests that, in combinatorial optimization, local optima of good quality are clustered and surround the global optimum. It is an important characteristic of many hard problems from combinatorial optimization Reeves (1999). The structure suggests the idea of the hybrid approach between RVND with ILS, and Tabu, as follows. Firstly, the combination between RVND and ILS, in which ILS ensures diversification while RVND maintains intensification, generates many good locally optimal solutions dispersed over the global optimal solution. Secondly, TS is entirely attracted to the global optimal. Even though the initial solution is set far from the global optimal solution, TS is capable to prevent from getting trapped into cycles to drive the search to the global optimal solution.

With respect to the instances, the algorithm finds better solutions than Ban et al.’s algorithm Ban and Nghia (2017b) for 136 out of 160 instances. Moreover, for 24 instances, it obtains better solutions for 10 cases and the same quality for 4 cases when comparing with Heilporn et al.’s algorithm Heilporna (2010). For the large instances with up to 250 customers, this is the first time our algorithm has provided feasible solutions. It is a significant improvement because finding a feasible solution is also NP-hard problem. In TSPTW, our algorithm obtains the optimal solutions for the instances with up to 100 vertices. Moreover, it also reaches the best-known solutions for all instances. Although our purpose is not to provide metaheuristic for TSPTW, the obtained results for this problem show the efficiency and broad applicability of our algorithm.

Our algorithm performs better than the others thanks to two reasons as followings:

  1. (1)

    Heuristic algorithms such as Heilporna (2010) are often too greedy, therefore, it can get stuck into a local optimum in many cases. On the other hand, the metaheuristic approach is not greedy and may even accept a temporary deterioration of solution, which allows it to explore the solution space more thoroughly, and thus the chance to get better solutions is higher.

  2. (2)

    The algorithm in Ban and Nghia (2017b) can get trapped into cycles in some cases, by using Tabu lists our algorithm overcomes their drawback and obtains better solutions. Moreover, the proposed algorithm uses more neighborhoods than the algorithm in Ban and Nghia (2017b); therefore, the explored solution space is larger. As a result, the chances of finding better solutions are higher.

7 Conclusions

In this work, DMPTW is studied. As our main contribution, we propose a metaheuristic algorithm that combines ILS, RNVD, and Tabu for DMPTW. We tested the algorithm on the benchmark dataset, comparing it to several state-of-the-art metaheuristic algorithms. Our algorithm is comparable with the state-of-the-art metaheuristic algorithms and it is able to find optimal solutions for instances with up to 100 vertices in a short time. In addition, for 136 instances, it provides new best-known solutions. In the future, we intend to extend the algorithm by including more neighborhoods and carefully studying the effectiveness of each neighborhood. Increasing the efficiency as well as the running time of our algorithm, even more, to allow even larger problems to be solved, is another future research topic.