Simulated Annealing Algorithm for Vehicle Routing Problem with Transshipment

Main Article Content

Sukanya Thonethong
Jirachai Buddhakulsomsiri


This paper considers the vehicle routing problem with transshipment. Customer demands are of two types: regular demands that are satisfied by the depot and transshipment demands of items from other customers. A simulated annealing (SA) algorithm to generate delivery routes in which both demands can be met in the same delivery routes is developed. The objective is to minimize the transportation cost. Preliminary results from testing the algorithm using numerical examples shows that allowing transshipment incurs additional cost of 0.48%-1.68%, depending on the level of transshipment demand, with the benefit of reducing delivery lead time.


Download data is not yet available.

Article Details

Research Article


G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science, vol. 6, no. 1, pp. 80–91, Oct. 1959.

M. M. Alipour, “A Learning Automata Based Algorithm For Solving Capacitated Vehicle Routing Problem,” IJCSI International Journal of Computer Science Issues, vol. 9, no. 1, pp. 138–145, 2012.

S. Zhang, C. Zhu, J. K. O. Sin, and P. K. T. Mok, “A novel ultrathin elevated channel low-temperature poly-Si TFT,” IEEE Electron Device Letters, vol. 20, no. 11, pp. 569–571, Nov. 1999.

M. Gendreau, G. Laporte, and R. Séguin, “Stochastic vehicle routing,” European Journal of Operational Research, vol. 88, no. 1, pp. 3–12, Jan. 1996.

J. Brandão, “A new tabu search algorithm for the vehicle routing problem with backhauls,” European Journal of Operational Research, vol. 173, no. 2, pp. 540–555, Sep. 2006.

F. Alfredo Tang Montané and R. D. Galvão, “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service,” Computers & Operations Research, vol. 33, no. 3, pp. 595–619, Mar. 2006.

Y. Nagata, O. Bräysy, and W. Dullaert, “A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows,” Computers & Operations Research, vol. 37, no. 4, pp. 724–737, Apr. 2010.

F. YANG and H. XIAO, “Models and Algorithms for Vehicle Routing Problem with Transshipment Centers,” Systems Engineering - Theory & Practice, vol. 27, no. 3, pp. 28–35, Mar. 2007.

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, no. 4598, pp. 671–680, May 1983.

P. Augerat, J. M. Belenguer, E. Benavent, A. Corberan, D. Naddef, and G. Rinaldi, “Computational results with a branch and cut code for the capacitated vehicle routing problem,” Istituto di analisi de sistemi ed informatica consiglio nazionale delle ricerche, no. 495, 1998.