• Routes must start and end at the warehouse within the time window of the warehouse.

• Each customer should be served with a single vehicle at a time.

• The total demand of customers on the same route should not exceed the vehicle capacity.

• Customers should serve within the time window. Early arriving vehicles must wait for the customer's ready time.

Sets

C{1,2,…,n}: Customer set

N{0,1,2,…,n}: Node set (0. node represent warehouse.)

D{0,1,…V}: Days set

Decision Variables

t_i : arrival time to customer i

w_i : waiting time at customer i

s_i : service time of customer i

x_ijd : a binary variable whether the vehicle travels from point i to j on day d (1 if the vehicle is going from i customer to j customer on day d, 0 otherwise)

Parameters

d_ij : distance between customer i and customer j

Q : vehicle capacity

e_j : start time of time window of customer j

l_j : expiry time of time windowof customer j

l₀ : end time of the time window of the warehouse (maximum travel time of the vehicle)

m_i : demand quantity of customer i

Equation 1 is the objective function and aims to minimize the sum of distances. Equation 2 ensures that vehicle is assigned to each customer. Equation 3 allows that the number of vehicles leaving and entering the warehouse is equal to one for each day. In Equation 4, the total of customer demands on the route assigned for each day should not exceed the vehicle capacity. Equation 5 states that all time spent along the route should not exceed the vehicle's maximum travel time. Equation 6 shows the waiting time calculation if the vehicle arrives before the customer is ready. Equation 7 is the time window constraint and Equation 8-10 specifies the value sets for variables.

$$\sum _{i=0}^n \sum _{j=0}^n \sum _{d=0}^n d_{ij}\ast x_{ijd} (1)$$

$$\sum _{d=1}^V \sum _{i=0,i\ne j}^n x_{ijd}=1 (2)$$

$$\sum _{d=1}^V \sum _{i=1}^n x_{i0d}=\sum _{d=1}^V \sum _{j=1}^n x_{0j}=V (3)$$

$$\sum _{i=1}^n \sum _{j=0,j\ne i}^n m_i\ast x_{ijd}\le Q,\mathrm{\forall }d\in V (4)$$

$$\sum _{i=0}^n \sum _{j=0,j\ne i}^n x_{ijd}\left(d_i+s_i+w_i\right)\le l_o,\mathrm{\forall }d\in V (5)$$

$$w_i=max\left\{e_i-t_i,0\right\} (6)$$

$$e_j\le \left(t_j+w_j\right)\le l_j,\mathrm{\forall }d\in V (7)$$

$$x_{ijd}\in \{0,1\} (8)$$

$$t_j\ge 0 (9)$$

$$w_i\ge 0 (10)$$

3.3. Tabu Search Algorithm

Tabu search (TA) is a metaheuristic algorithm based on problem solving and includes the concept of 'memory'. The basic approach is to ban or punish repetition in the next cycle to prevent the step leading to the final solution from making circular motions. Thus, the Tabu Search algorithm guides the regional-heuristic research to search for solutions that are beyond the regional optimum by examining new solutions. Tabu search algorithms can be used for the problems of scheduling, investment planning, communication, design, routing, etc. (Glover and Laguna, 1998). The basic principle of TA is to create a tabu list to prevent a previous move from reversing rather than repeating it. Eq. (3.1) can be used to explain the TA:

$$Minc \left(x\right), x \in X (3.1)$$

Here each x element represents a motion, and the entire set of motions is denoted by X. The x vectors are used as the TA memory structure. Thus, depending on the memory value kept in the vector, some movements will be considered as taboo in the search for solutions, and some will focus more on others. Each movement in the vector X represents the choice of a neighbor of the current solution.

Some concepts and steps of TA method are explained in detail below (Jayaswal, 2000):

Creating a Solution: Initial solution pairs were determined randomly.

Movement Mechanism: The changes made in the solution provide a new solution. There is a stopover from the current point to the visit of all points. This event constitutes the neighbors of the current solution.

Search Neighbor: The most crucial point provided by the neighbor search concept is that it provides the best motion selection. Neighborhood is chosen by the best value chosen in each iteration. Besides, let the neighborhood of x to be N(x), it could be expressed as N*(x)⊂N(x).

Aspiration criteria: This criterion is the key factor in defining the degree of applicability of the method and allows for the action that provides better results (Salhi, 2002). If f(xtabu) <f(xbest), then current movement will be invalid.

Memory: It memorizes prohibited actions and adds them to the tabu list.

Taboo List: Tabu list adds solutions that have been visited before to avoid duplication. The size of the tabu list is very important.

Stopping Criteria: Reaching maximum iteration number or reaching the desired solution, etc. situations provide stop condition for tabu search.

The steps of the TA algorithm are simply shown below.

4. Computational Results

4.1. Data Sets

The data set is obtained from http://vrp.galgos.inf.puc-rio.br/index.php/en/ called as Benchmark: Set A. The pseudo code of the proposed TA model was given in Javascript in detail. The processor model of the computer used is Intel® XEON® CPU E5-2660 V2. It also has 2.2 GHz processor base frequency. The pseudo code of the TA which is employed to solve the routing problem is given in Figure 1. At the same, the progress of the algorithm is given as flow chart in Figure 2. Some performance criteria are used to analyze mathematical models. In this study, average solution time was chosen as a performance criterion.

Figure 1. Pseudocode of the proposed algorithm

Figure 2. Process Flow Chart

Customer coordinates and demands are presented in Table 1 and Table 2.

The calculation of the cost was made as the sum of the distances on the route assigned to the vehicle. Euclidean distance is used in calculating the distance as shown in Eq.11.

$$d(A, B) = \surd (11)$$

The results of the algorithm has summarized in the tables below. Table 3 shows on which day the vehicle will go to which points. For example, on day 1, the vehicle for customer number 16 should leave from the warehouse. The demand for this visit is seen as 16 (See Table 4). Again, on the 2nd day, a demand for 22 units must be delivered to the customer number 25 from the warehouse. The costs for all warehouses are shown in Table 5.

The assigned route for first day is visualized in Figure 3. As explained in the definition of the problem, each route starts with the warehouse and ends with the warehouse. Considering that the maximum capacity of the vehicles is 100 units, it can be said that the vehicle capacity is 97% on the 1st day. The total cost covering all days was found as 664.29 units of road, end of the analysis for the vehicle routing problem. The total solution time of the problem was calculated as 57 seconds.

Figure 3. Assigned routes on day 1

5. Results and Discussions

This study proposed a tabu search heuristic for the VRPTWs. The heuristic minimizes total distance traveled using tabu search algorithm. The application of tabu search algorithm, one of the metaheuristic methods frequently encountered in the international literature, to VRPTWs has not been adequately studied in the literature. In order to eliminate this deficiency, information was given about the time windowed vehicle routing problem in the study. In addition, the algorithm obtained the best known solution on every instance of a set of 38 instances of the VRPTWs.

In future work, we plan to solve our tabu search algorithm to the VRPTW problem with Phyton. Additionally, we programe to compare our method with other metaheuristic algorithms such as genetic algorithm. This study is assumed that the results of this study will provide various benefits to the practice and the literature.

6. References

Belfiore, P. Tsugunobu, H. and Yoshizaki, Y. (2008). Scatter search for Vehicle Routing Problem with Time Windows and Split Deliveries. Vehicle Routing Problem, Book edited by: Tonci Caric and Hrvoje Gold, ISBN 978-953-7619-09-1, pp. 142.

Bramel, J. and Simchi-Levi, D. (1997). The Logic of Logistics: Theory, Algorithms and Applications for Logistics Management.

Braysy, O. and Gendreau, M. (2002). Tabu Search Heuristics for The Vehicle Routing Problem with Time Windows, Sociedad de Estadística e Investigación Operativa, 10 (2), 211–237.

Cordeau, J.F., Laporte, G., Savelsbergh, M.W.P. and Vigo, D. (2007). Vehicle Routing Transportation, Handbooks in Operations Research and Management Science, 14, 367–428.

Crainic, T.G. and Laporte, G. (1998). Fleet Management and Logistics, Springer.

Glover, F., Laguna, M. (1998). Tabu Search. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-0303-9_33

Gmira, M., Gendreau, M., Lodi, A. and Potvin, J.Y. (2021). Tabu Search for The Time Dependent Vehicle Routing Problem with Time Windows on A Road Network, European Journal of Operational Research, 1(1), 129–140.

Ho, S. and Haugland, D. (2004). A Tabu Search Heuristic for The Vehicle Routing p-Problem with Time Windows and Split Deliveries, Computers & Operations Research, 32, 1947–1964.

Jayaswal, S. (2000). A Comparative Study of Tabu Search and Simulated Annealing for Travelling Salesman Problem.

Moccia, L., Cordeau, J.F. and Laporte, G. (2012). An Incremental Tabu Search Heuristic for The Generalized Vehicle Routing Problem with Time Windows, Journal of the Operational Research Society, 63(2), 232–244.

Nguyen, P.K., Crainic, T.G. and Toulouse, M. (2013). Tabu Search for The Time Multi-zone Multi-trip Vehicle Routing Problem with Time Windows, European Journal of Operational Research, 231, 43–56.

Salhi, S. (2002). Defining Tabu List Size and Aspiration Criterion Within Tabu Search Methods, Computers & Operations Research, 29(1), 67–68.