Solving TTRP problem based on an iterated variable neighborhood descent algorithm

WANG Chao, GAO Yang, LIU Chao

Systems Engineering - Theory & Practice ›› 2018, Vol. 38 ›› Issue (11) : 2892-2906.

PDF(7284 KB)
中国科学院数学与系统科学研究院期刊网
PDF(7284 KB)
Systems Engineering - Theory & Practice ›› 2018, Vol. 38 ›› Issue (11) : 2892-2906. DOI: 10.12011/1000-6788(2018)11-2892-15

Solving TTRP problem based on an iterated variable neighborhood descent algorithm

  • WANG Chao1,2,3, GAO Yang1,2, LIU Chao1,2
Author information +
History +

Abstract

To solve the truck and trailer routing problem (TTRP), an iterated variable neighborhood descent (IVND) algorithm was proposed. First, the T-cluster heuristic was implemented for generating an initial solution. Next, a VND based on multi-operator optimization was developed. In VND, the restricted neighborhood was introduced based on the idea of granular neighborhoods, and a perturbation strategy had been designed by switch-vehicle-type operator to help optimization escape from local minima. Computational results are reported for 21 test problems with 50~199 customers from Chao's benchmark and the results indicate that the proposed IVND algorithm could converge to the satisfactory solutions within the shortest computational time. In addition, the IVND is flexible, efficient and easy to implement, and could be extended to handle other variants of vehicle routing problem and other combinatorial optimization problem.

Key words

vehicle routing / truck and trailer / local search / variable neighborhood descent

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
WANG Chao , GAO Yang , LIU Chao. Solving TTRP problem based on an iterated variable neighborhood descent algorithm. Systems Engineering - Theory & Practice, 2018, 38(11): 2892-2906 https://doi.org/10.12011/1000-6788(2018)11-2892-15

References

[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1):80-91.
[2] Chao I M. A tabu search method for the truck and trailer routing problem[J]. Computers & Operations Research, 2002, 29(1):33-51.
[3] Lin S W, Yu V F, Chou S Y. Solving the truck and trailer routing problem based on a simulated annealing heuristic[J]. Computers & Operations Research, 2009, 36(5):1683-1692.
[4] M'Hallah R. An iterated local search variable neighborhood descent hybrid heuristic for the total earliness tardiness permutation flow shop[J]. International Journal of Production Research, 2014, 52(13):3802-3819.
[5] Yazdani M, Amiri M, Zandieh M. Flexible job-shop scheduling with parallel variable neighborhood search algorithm[J]. Expert Systems with Applications, 2010, 37(1):678-687.
[6] Martins I C, Pinheiro R G S, Protti F, et al. A hybrid iterated local search and variable neighborhood descent heuristic applied to the cell formation problem[J]. Expert Systems with Applications, 2015, 42(22):8947-8955.
[7] Martins A X, Duhamel C, Mahey P, et al. Variable neighborhood descent with iterated local search for routing and wavelength assignment[J]. Computers & Operations Research, 2012, 39(9):2133-2141.
[8] Chen P, Huang H, Dong X Y. Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem[J]. Expert Systems with Applications, 2010, 37(2):1620-1627.
[9] Kytöjoki J, Nuortio T, Bräysy O, et al. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems[J]. Computers & Operations Research, 2007, 34(9):2743-2757.
[10] Polat O, Kalayci C B, Kulak O, et al. A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery with time limit[J]. European Journal of Operational Research, 2015, 242(2):369-382.
[11] Polat O. A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups[J]. Computers & Operations Research, 2017, 85:71-86.
[12] Drexl M. On some generalized routing problems[D]. Aachen:RWTH Aachen University, 2007.
[13] Drexl M. A branch-and-price algorithm for the truck-and-trailer routing problem[R]. Technical Report. Aachen:RWTH Aachen University, 2007.
[14] Drexl M. Branch-and-price and heuristic column generation for the generalized truck and trailer routing problem[J]. Revista De Métodos Cuantitativos Para La Economía Y La Empresa, 2011, 12(1):5-38.
[15] Parragh S N, Cordeau J F. Branch-and-price for the truck and trailer routing problem with time windows[R]. CIRRELT-2015-54. CIRRELT, Montréal, 2015.
[16] Scheuerer S. A tabu search heuristic for the truck and trailer routing problem[J]. Computers & Operations Research, 2006, 33(4):894-909.
[17] Caramia M, Guerriero F. A milk collection problem with incompatibility constraints[J]. Interfaces, 2010, 40(40):130-143.
[18] Caramia M, Guerriero F. A heuristic approach for the truck and trailer routing problem[J]. Journal of the Operational Research Society, 2010, 61(7):1168-1180.
[19] Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computer & Operations Research, 1986, 13(5):533-549.
[20] Braekers K, Ramaekers K, Van Nieuwenhuyse I. The vehicle routing problem:State of the art classification and review[J]. Computers & Industrial Engineering, 2016, 99:300-313.
[21] Mirmohammadsadeghi S, Ahmed S. Metaheuristic approaches for solving truck and trailer routing problems with stochastic demands:A case study in dairy industry[J]. Mathematical Problems in Engineering, 2015, 2015:1-14.
[22] Lin S W, Yu V F, Chou S Y. A note on the truck and trailer routing problem[J]. Expert Systems with Applications, 2010, 37(1):899-903.
[23] Lin S W, Yu V F, Lu C C. A simulated annealing heuristic for the truck and trailer routing problem with time windows[J]. Expert Systems with Applications, 2011, 38(12):15244-15252.
[24] Villegas J G, Prins C, Prodhon C, et al. A GRASP with evolutionary path relinking for the truck and trailer routing problem[J]. Computers & Operations Research, 2011, 38(9):1319-1334.
[25] Derigs U, Pullmann M, Vogel U. Truck and trailer routing-Problems, heuristics and computational experience[J]. Computers & Operations Research, 2013, 40(2):536-546.
[26] Villegas J G, Prins C, Prodhon C, et al. A matheuristic for the truck and trailer routing problem[J]. European Journal of Operational Research, 2013, 230(2):231-244.
[27] Salhi S, Nagy G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J]. Journal of the Operational Research Society, 1999, 50(10):1034-1042.
[28] Crainic T G, Mancini S, Perboli G, et al. Clustering-based heuristics for the two-echelon vehicle routing problem[R]. CIRRELT-2008-48, CIRRELT, Montréal, 2008.
[29] Savelsbergh M W P. The vehicle routing problem with time windows:Minimizing route duration[J]. INFORMS Journal on Computing, 1992, 4(2):146-154.
[30] Chen J F, Wu T H. Vehicle routing problem with simultaneous deliveries and pickups[J]. Journal of the Operational Research Society, 2006, 57(5):579-587.
[31] Toth P, Vigo D. The granular tabu search and its application to the vehicle-routing problem[J]. INFORMS Journal on Computing, 2003, 15(4):333-346.
[32] Wang C, Mu D, Zhao F, et al. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows[J]. Computers & Industrial Engineering, 2015, 83(C):111-122.
[33] Christofides N, Mingozzi A, Toth P. The vehicle routing problem[C]//Christofides N, Mingozzi A, Toth P, et al. Combinatorial Optimization, Chichester, UK:Wiley, 1979:315-338.
[34] Chen P, Huang H K, Dong X Y. Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem[J]. Expert Systems with Applications, 2010, 37(2):1620-1627.
[35] Wang C, Zhou S, Gao Y, et al. A self-adaptive bat algorithm for the truck and trailer routing problem[J]. Engineering Computations, 2018, 35(1):108-135.
[36] Dongarra J J, Wade R, McMahan P. Linpackbenchmark-Java version[EB/OL].[2016-06-12]. http://www.netlib.org/benchmark/linpackjava/.
[37] PASSMARK software. http://www.passmark.com/.[2016-07-23].
[38] 何小锋,马良. 带时间窗车辆路径问题的量子蚁群算法[J]. 系统工程理论与实践, 2013, 33(5):1255-1261. He X F, Ma L. Quantum-inspired ant colony algorithm for vehicle routing problem with time windows[J]. Systems Engineering-Theory & Practice, 2013, 33(5):1255-1261.

Funding

National Natural Science Foundation for Young Scholars of China (61603011, 61603010); National Natural Science Foundation of China (61773029, 71772016); The International Postdoctoral Exchange Fellowship Program (20170016)
PDF(7284 KB)

633

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉