# Simulated Annealing for a Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows

Chao Wang, Fu Zhao, Dong Mu, John W. Sutherland

► To cite this version:

Chao Wang, Fu Zhao, Dong Mu, John W. Sutherland. Simulated Annealing for a Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows. 20th Advances in Production Management Systems (APMS), Sep 2013, State College, PA, United States. pp.170-177, 10.1007/978-3-642-41263-9_21. hal-01451752

HAL Id: hal-01451752

https://inria.hal.science/hal-01451752

Submitted on 1 Feb 2017

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>

Distributed under a Creative Commons Attribution 4.0 International License
Simulated annealing for a vehicle routing problem with
simultaneous pickup-delivery and time windows

Chao Wang¹², Fu Zhao², Dong Mu¹, John W. Sutherland²

1 School of Economics and Management, Beijing Jiaotong University, China
mudong.bjtu@gmail.com

2 College of Engineering, Purdue University, United State
{chaowang, fzhao, jwsuther}@purdue.edu

**Abstract.** A variant of vehicle routing problem in which customers require simultaneous pickup and delivery goods during specific individual time windows (VRPSPDTW) is addressed. A general mixed integer programming model focused on minimizing the number of vehicles is proposed. A simulated annealing (SA) algorithm is developed and applied to solve this NP-hard optimization problem. Computational results are reported for a set of 15 test problems from Wang and Chen's benchmark and compared with the results from a genetic algorithm (GA). It is shown that SA is an effective metaheuristic to solve the VRPSPDTW.

**Keywords:** simulated annealing, simultaneous delivery and pickup, vehicle routing problem, time windows

# 1 Introduction

The Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows (VRPSPDTW) is the important subclass of Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) where a fleet of homogenous or non-homogenous vehicles stationed at a depot are not only required to deliver from the depot to customers but also simultaneously to pickup goods at the customer location for return to the depot without violating vehicle capacity constraints and time windows constraints. Time windows define the earliest and latest service time allowed for each customer.

From a practical point of view, VRPSPDTW falls within the field of logistics re-
source integration and supply chain integration which incorporates reverse logistics
into the forward channel and has attracted more and more attention recently because
of the increasing focus on environmental protection and sustainable supply chains.
For example, Hewlett-Packard (HP) was reported to distribute the products in logis-
tics network and pick up the used IT hardware such as used original toner cartridges
and supplies from the retail location [1]. From a mathematical point of view,
VRPSPDTW is a NP-hard combinatorial optimization problem which means that
exact algorithms can only be used to find solutions for small-and-medium scale in-
stances. The commercial linear programming software CPLEX has been reported to solve the VRPSPDTW problem executed on an Intel Core2 Quad 2.4G computer with 1G memory, and was only able to solve a 10 customer instance, and a portion of 25 and 50 customer scenarios [2]. For the solved instance RCdp 1004 (10 customers instance) and RCdp5001 (50 customers instance), the computation time was 1503 seconds and 327,404 seconds respectively. To solve the computational challenge associated with applied problem that involve more customers, researchers and practitioners have to develop heuristic or metaheuristic approaches to produce high-quality solutions (but not necessarily optimal solutions) with reasonable computational times.

The technical literature on VRPSPDTW problem is somewhat limited. Angelelli and Mansini [3] was the first researchers to solve VRPSPDTW with a comprehensive exact algorithm which combined a branch-and-price and branch-and-bound approach. Lai and Cao [4] proposed an Improved Differential Evolution (IDE) algorithm for solving this problem and did numerical experiments with their own instances. Boubahri et al. [5] constructed a multi-agent colonies algorithm for this problem, but did not test with the instances. Wang and Chen [2] proposed a co-evolution genetic algorithm with variants of the cheapest insertion method for VRPSPDTW. They also developed 65 instances revised from the well-known Solomon benchmark [6] for VRPTW.

However the literature on the VRPSPD problem is better studied than the more specific class of problem noted above, i.e., research that does not consider time windows. For good reviews on the VRPSPDTW, the reader is referred to Subramanian et al. [7]. Min [8] was the first to study this problem. He solved the book distribution problem in a public library system which involved 22 customers and two vehicles. Some exact methods have been developed for the VRPSPD, including the branch-and-price technique [9] [10] and the branch-and-cut technique [11]. However, due to the problem difficulty, the design of efficient heuristics or metaheuristics which are capable of solving this problem in large scale instances has attracted many research efforts in the past few years. Some example heuristics are: Residual Capacity and Radical Surcharge (RCRS) algorithm [12], Large Neighborhood Search (LNS) [13], and GENEVNS-TS-CL-PR algorithm [14]. Some example metaheuristics are: pure or hybrid Tabu Search (TS) [15] [16], Ant Colony Optimization (ACO) [17] [18], Genetic Algorithm (GA) [19], Particle Swarm Optimization (PSO) [20], and Iterated Local Search (ILS) algorithm [7] [21].

The purpose of the present study is to develop an efficient metaheuristic to solve the VRPSPDTW problem by using simulated annealing algorithm. The paper is organized as follows. Section 2 gives a detailed description of how the proposed simulated annealing algorithm is implemented on the VRPSPDTW problem. Section 3 provides comparisons to the VRPSPDTW benchmark. Finally, conclusions are drawn in Section 4.
## 2 Simulated Annealing (SA) Applied to VRPSPDTW

The problem-solving methodology based on the SA algorithm is presented in this section. SA implements a Metropolis sampling strategy with probability mutability, randomizes the local search procedure, and obtains the global optimum with a slow cooling schedule. The most important feature of SA compared with other local search algorithms is that SA always accepts a better or unchanged solution as a new current solution, and accepts a worse solution with a certain probability, which allows the search to escape from local minima and become a global optimum algorithm in theory.

The text below describes the steps in the simulated annealing algorithm applied to solve the VRPSPDTW problem.

### Step 1 Initialization of the solution and temperature

(1) Generate an initial heuristic solution. In order to improve the convergence speed of SA, it is better to introduce a small-size heuristic algorithm and find a high quality feasible solution as the initial solution. VRPSPDTW considers a simultaneous pickup and delivery, therefore the Push-Forward Insertion Heuristic (PFIH) and Genetic Sectoring Heuristic (GSH), which are used for solving VRPTW, are no longer applicable because the vehicles are assumed to be at full load when leaving the central depot in their algorithms. In this paper, the initial solution is constructed using the RSRC algorithm [12] proposed by Dethloff for the VRPSPDT problem, where it is noted that the load of vehicle when leaving is depot is not equal to vehicle capacity, but rather, calculated in the algorithm.

(2) Set initial annealing temperature. The setting of an initial temperature determines whether the initial stage of the annealing process can accept poorer solutions with high probability. Based on the characteristics of VRPSPDTW, and combined with the relevant literature [22] about simulated annealing theory, the following method can be used to choose the initial temperature.

The cost and cooling temperature of the VRPSPDTW solution is computed as follows:

$$ \text{cost}(s_k) = d + \sigma(c \times n + e_{\min}) \quad (1) $$

$$ T_k = \gamma \times \text{cost}(s_k) \quad (2) $$

where $s_k$ is the feasible solution, $d$ is the total travel distance of the routes, $\sigma$ is a constant, $c$ is the number of routes in solution $s_k$ (equal to the number of vehicles needed), $n$ is the number of customers, $e_{\min}$ is the number of customers in the shortest route, and $\gamma < 1$ is a constant.

Van Laarhoven and Aarts [23] proposed a method of decreasing temperature which appears to be the most widely used method reported in the literature:

$$ T_{k+1} = \beta * T_k \quad (3) $$

where $\beta$ is the coefficient controlling the cooling schedule, and a constant less than 1.
When $k = 0$, the initial temperature is:

$$T_0 = \gamma \times \cos t(s_0) \quad (4)$$

**Step 2** Repeat the following operation under the current temperature $T_k$ until it reaches the equilibrium state at $T_k$.

(1) Local search in the neighborhood of the current solution $s_k$ to generate a new feasible solution $s'_k$. We use a standard SA procedure with a random neighborhood structure which imposes three types of improvement methods, including insertion move, swap move, and 2-opt move, to solve VRPSPDTW. These moves are commonly embedded in SA heuristics, and other meta-heuristics. We define the set $N(s_k)$ to be the set of solutions neighboring of solution $s_k$. At each iteration, the next solution $s'_k$ is selected from $N(s_k)$ either by insertion move, 2-opt move, or swap/shift move. The probabilities of choosing the insertion move, 2-opt move, or swap/shift move are set to be 1/3, 1/3 and 1/3, respectively.

Insertion move is a random improvement method, which is carried out by randomly selecting the ith number of $s_k$ and inserting it into the position immediately before another randomly selected jth number of $s_k$. 2-opt move is a intra-route exchange, which tries to lower the route distance by altering the sequence of customers within a single route. It switches the route direction between two consecutive nodes. If the cost function of the route has been reduced, then the modified route is kept; other-wise, the route returns to the last condition. Swap/shift move is a inter-route exchange proposed. It either shifts a customer from one route to another, or exchanges a customer on one route with a customer on another route.

(2) Determine whether to accept the new solution

The SA process proceeds by comparison of the cost of the newly generated feasible solution $s'_k$ and the current solution $s_k$. If $s'_k \le s_k$, the newly generated solution $s'_k$ becomes the current solution. If $s'_k > s_k$, $s'_k$ is accepted with the probability

$$p = \begin{cases} 1 & \cos t(s_k) > \cos t(s'_k) \\ \exp\left(\frac{\cos t(s_k) - \cos t(s'_k)}{T_k}\right) & \cos t(s_k) < \cos t(s'_k) \end{cases} \quad (5)$$

where $T_k (k = 0, 1, ..., k_{max})$ is a parameter called temperature of annealing. This temporary deterioration of the objective function value is an uphill move process, which avoids the metaheuristic to trap into a local optimum.

(3) Determine whether to terminate the inner loop

Metropolis sampling stability criterion is used to determine the number of candidate solutions produced at the respective temperatures. Here we set L steps as the maximum number of iterations at temperature T. If the iterations counter for temperature T is not exceed L, return to **Step 2** (1) and continue the procedure of generating and accepting new feasible solution, otherwise, the inner loop is terminated, the temperature is decreased according to Equation (3) and transferred to **Step 3**.
**Step 3** End the procedure if the stopping criterion is met

The common stopping criteria are: (i) specify a determined maximum number of total iterations the search proceeds; (ii) set the final temperature $T_F$, below $T_F$ the SA procedure is terminated; (iii) specify a maximum number of successive iterations $\omega_{max}$ which remains the non-improving best solution found so far for a consecutive temperature reduction stages. This paper uses the third stop criterion, which determines whether to stop the outer loop based on whether the gradually lowered temperature during the search procedure is able to continue to improve the current optimal solution or not.

**Step 4** Output the optimal solution.

Output the optimal solution, and terminate the algorithm.

## 3 Computation and Evaluation

In this section, we demonstrate the effectiveness of our SA metaheuristic by testing it on the benchmark datasets, namely Wang and Chen's instances [2]. All experiments are executed on a 32 core Redhat Linux server (8 × quad core 2.3 Mhz, Opteron 8346) with 64G of RAM.

In the proposed SA, parameters must be specified and appropriately adjusted: parameter $\sigma$ in Equation (1), parameter $\gamma$ represents relations between cost and temperature, the constant of decreasing temperature $\beta$, $\Delta$ which represents the probability of accepting worse solutions, parameter $L$ which is the maximum number of iterations for temperature $T$, parameter $\omega_{max}$ which is the maximum number of iterations of non-improving the current best solution, parameters $lamda$ and $alpha$ in RCRS insertion criterion proposed by Dethloff [12]. The above parameter values were obtained through fine tuning and are listed in Table 1. In general the performance of the SA algorithms is sensitive to the above cooling schedule.

<table><caption>**Table 1.** Parameters used in the SA</caption><thead><tr><th>SA parameter</th><th>σ</th><th>γ</th><th>β</th><th>L</th><th>ω<sub>max</sub></th><th>Δ</th><th>lamda</th><th>alpha</th></tr></thead><tbody><tr><td>Value</td><td>1</td><td>1</td><td>0.97</td><td>30</td><td>200</td><td>0.6</td><td>0.8</td><td>0.8</td></tr></tbody></table>

Wang and Chen's instances<fnref n="1" /> about VRPSPDTW were revised from Solomon's VRPTW benchmarks<fnref n="2" />. Six different sets of problems were generated. The geographical data are randomly generated in problem sets R1 and R2, clustered in problem sets C1 and C2, and a mix of random and clustered structures in problem sets by RC1 and RC2. Problem sets R1, C1 and RC1 have a narrow scheduling horizon, and the sets R2, C2 and RC2 have a large scheduling horizon. Three 10-customer instances, three

<footnote n="1">¹ Download of Wang and Chen's benchmark instances from Y. Y. Chen: http://oz.nthu.edu.tw/~d933810/test.htm</footnote>

<footnote n="2">² Download of Solomon's benchmark instances from M. M. Solomon: http://w.cba.neu.edu/~msolomon/problems.htm</footnote>
best of our knowledge, this is the first simulated annealing approach proposed to solve this problem. Comparisons from the results of the GA algorithm and the proposed SA show that the proposed method is effective for solving VRPSPDTW problem.

High-quality solutions are guaranteed by the tight cooling schedule, particularly when a sufficiently high initial temperature, slow annealing speed, a large number of iterations, and holding time at the same temperature are utilized. This is usually at the price of a high computation resources and times. Therefore, further work will concentrate on parallelization of SA to accelerate the proposed algorithm.

## Acknowledgements

This work has been supported by the National Natural Science Foundation of China (Grant No. 71132008), China Scholarship Council (201207090034), and the Fundamental Research Funds for the Central Universities (2012YJS034). Also, this research was supported in part by the computational resources provided by the Division of Environmental and Ecological Engineering at Purdue University.

## References

1. HP Global citizenship, http://www8.hp.com/us/en/hp-information/environment/product-recycling.html#.UVH59pHEovw.

2. Wang, H.F., Chen, Y.Y.: A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers & Industrial Engineering 62(1), 84-95 (2012).

3. Angelelli, E., Mansini, R.: A branch-and-price algorithm for a simultaneous pickup and delivery problem. Quantitative Approaches to Distribution Logistics and Supply Chain Management, 249-267 (2003).

4. Lai, M.Y., Cao, E.B.: An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Engineering Applications of Artificial Intelligence 23(2), 188-195 (2010). doi:http://dx.doi.org/10.1016/j.engappai.2009.09.001

5. Boubahri, L., Addouche, S.A., El Mhamedi, A.: Multi-ant colonies algorithms for the VRPSPDTW. In: Communications, Computing and Control Applications (CCCA), 2011 International Conference on, 3-5 March 2011 2011, pp. 1-6

6. Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35(2), 254-265 (1987).

7. Subramanian, A., Drummond, L.M.A., Bentes, C., Ochi, L.S., Farias, R.: A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computers & Operations Research 37(11), 1899-1911 (2010). doi:http://dx.doi.org/10.1016/j.cor.2009.10.011

8. Min, H.: The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General 23(5), 377-386 (1989). doi:http://dx.doi.org/10.1016/0191-2607(89)90085-X
9. Dell'Amico, M., Righini, G., Salani, M.: A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation Science 40(2), 235-247 (2006).

10. Subramanian, A., Uchoa, E., Pessoa, A.A., Ochi, L.S.: Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Operations Research Letters 39(5), 338-341 (2011).

11. Rieck, J., Zimmermann, J.: A Branch-and-Cut Approach to the Vehicle Routing Problem with Simultaneous Delivery and Pick-up. Operations Research Proceedings 2008, 301-306 (2009).

12. Dethloff, J.: Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. Or Spectrum 23(1), 79-96 (2001).

13. Ropke, S., Pisinger, D.: A unified heuristic for a large class of vehicle routing problems with backhauls. Eur. J. Oper. Res. 171(3), 750-775 (2006).

14. Cruz, R., Silva, T., Souza, M., Coelho, V., Mine, M., Martins, A.: GENVNS-TS-CL-PR: A heuristic approach for solving the vehicle routing problem with simultaneous pickup and delivery. Electronic Notes in Discrete Mathematics 39, 217-224 (2012).

15. Montane, A.T.F., Galvao, R.D.: A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research 33(3), 595-619 (2006).

16. Zachariadis, E.E., Kiranoudis, C.T.: A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Systems with Applications 38(3), 2717-2726 (2011).

17. Gajpal, Y., Abad, P.: An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Computers & Operations Research 36(12), 3215-3223 (2009).

18. Çatay, B.: A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Expert Systems with Applications 37(10), 6809-6817 (2010).

19. Tasan, A.S., Gen, M.: A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries. Computers & Industrial Engineering (2011).

20. Ai, T.J., Kachitvichyanukul, V.: A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research 36(5), 1693-1702 (2009).

21. Subramanian, A., Cabral, L.D.A.F.: An ILS based heuristic for the vehicle routing problem with simultaneous pickup and delivery and time limit. Evolutionary Computation in Combinatorial Optimization, 135-146 (2008).

22. Czech, Z.J., Czarnas, P.: Parallel simulated annealing for the vehicle routing problem with time windows. In: Parallel, Distributed and Network-based Processing, 2002. Proceedings. 10th Euromicro Workshop on 2002, pp. 376-383. IEEE

23. van Laarhoven, P.J., Aarts, E.H.: Simulated annealing: theory and applications, vol. 37. Springer, (1987)