Truck and Trailer Routing Problem Solving by a Backtracking Search Algorithm
Shiyi YUAN1, Jianwen FU1, Feng CUI2, Xin ZHANG3
1. School of Economics and Management, Beijing University of Technology, Beijing 100124, China;
2. Research Department of Beijing Smarter Eye Technology Co., Ltd, Beijing 100123, China;
3. Institute of Fundamental and Interdisciplinary Sciences, Beijing Union University, Beijing 100101, China
Truck and trailer routing problem (TTRP) is one of the most frequently encountered problem in city distribution, particularly in populated and intensive downtown. This paper addresses this problem and designs a novel backtracking search algorithm (BSA) based meta-heuristics to solve it. The initial population is created by T-sweep heuristic and then based on the framework of backtracking search algorithm, four types of route improvement strategies are used as building blocks to improve the solutions of BSA in the process of mutation and crossover. The computational experiments and results indicate that the proposed BSA algorithm can provide an effective approach to generate high-quality solutions within the satisfactory computational time.
Dantzig G B, Ramser J H. The truck dispatching problem. Management Science, 1959, 6(1):80-91.
Braekers K, Ramaekers K, Van Nieuwenhuyse I. The vehicle routing problem:State of the art classification and review. Computers & Industrial Engineering, 2016, 99:300-313.
Eksioglu B, Vural A V, Reisman A. The vehicle routing problem:A taxonomic review. Computers & Industrial Engineering, 2009, 57(4):1472-1483.
Chao I M. A tabu search method for the truck and trailer routing problem. Computers & Operations Research, 2002, 29(1):33-51.
Parragh S N, Cordeau J F. Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows. Computers & Operations Research, 2017, 83:28-44.
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. Computers & Industrial Engineering, 2015, 83:111-122.
Bortfeldt A, Hahn T, Mnnel D, et al. Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints. European Journal of Operational Research, 2015, 243(1):82-96.
Scheuerer S A. Tabu search heuristic for the truck and trailer routing problem. Computers & Operations Research, 2006, 33(4):894-909.
Shih T, Yu H. Probability distribution of return and volatility in crude oil market. The Journal of Global Business Management, 2009, 5(2):210-220.
Villegas J G, Prins C, Prodhon C, et al. A GRASP with evolutionary path relinking for the truck and trailer routing problem. Computers & Operations Research, 2011, 38(9):1319-1334.
Villegas J G, Prins C, Prodhon C, et al. A matheuristic for the truck and trailer routing problem. European Journal of Operational Research, 2013, 230(2):231-244.
Derigs U, Pullmann M, Vogel U. Truck and trailer routing-Problems, heuristics and computational experience. Computers & Operations Research, 2013, 40(2):536-546.
Wang C, Zhou S, Gao Y, et al. A self-adaptive bat algorithm for the truck and trailer routing problem. Engineering Computations, 2018, 35:108-135.
Gunawan A, Lau H C, Wong E. Real-world parameter tuning using factorial design with parameter decomposition, Advances in Metaheuristics. Springer, 2013:37-59.
Modiri-Delshad M, Kaboli S H A, Taslimi-Renani E, et al. Backtracking search algorithm for solving economic dispatch problems with valve-point effects and multiple fuel options. Energy, 2016, 116:637-649.
Civicioglu P. Backtracking search optimization algorithm for numerical optimization problems. Applied Mathematics and Computation, 2013, 219(15):8121-8144.
Song X, Zhang X, Zhao S, Li L. Backtracking search algorithm for effective and efficient surface wave analysis. Journal of Applied Geophysics, 2015, 114:19-31.
El-Fergany A. Optimal allocation of multi-type distributed generators using backtracking search optimization algorithm. International Journal of Electrical Power & Energy Systems, 2015, 64:1197-1205.
Modiri-Delshad M, Rahim N A. Solving non-convex economic dispatch problem via backtracking search algorithm. Energy, 2014, 77:372-381.
Santini A, Plum C E, Ropke S. A branch-and-price approach to the feeder network design problem. European Journal of Operational Research, 2018, 264(2):607-622.
Drexl M. A branch and price algorithm for the truck and trailer routing problem. Technical Report, RWTH Aachen University, Germany. http://www.dpor.rwth-aachen.de/de/publikationen/pdf/or_2006-06.pdf. 2007.
Drexl M. Branch-and-price and heuristic column generation for the generalized truck-and-trailer routing problem. Journal of Quantitative Methods for Economics and Business Administration, 2011, 12:5-38.
Clarke G, Wright J W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964, 12(4):568-581.
Caramia M, Guerriero F. A heuristic approach for the truck and trailer routing problem. Journal of the Operational Research Society, 2010, 61(7):1168-1180.
Reed M, Yiannakou A, Evering R. An ant colony algorithm for the multi-compartment vehicle routing problem. Applied Soft Computing, 2014, 15:169-176.
Mirmohammadsadeghi S, Ahmed S. Metaheuristic approaches for solving truck and trailer routing problems with stochastic demands:A case study in dairy industry. Mathematical Problems in Engineering, 2015. http://doi.org/10.1155/2015/494019.
Lin S W, Vincent F Y, Chou S Y. Solving the truck and trailer routing problem based on a simulated annealing heuristic. Computers & Operations Research, 2009, 36(5):1683-1692.
Lin S W, Vincent F Y, Chou S Y. A note on the truck and trailer routing problem. Expert Systems with Applications, 2010, 37(1):899-903.
Lin S W, Vincent F Y, Lu C C. A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Systems with Applications, 2011, 38(12):15244-15252.
Blum C, Puchinger J, Raidl G R, et al. Hybrid metaheuristics in combinatorial optimization:A survey. Applied Soft Computing, 2011, 11(6):4135-4151.
Akhtar M, Hannan M, Begum R, et al. Backtracking search algorithm in CVRP models for efficient solid waste collection and route optimization. Waste Management, 2017, 61:117-128.
Zhang C, Zhou J, Li C, et al. A compound structure of ELM based on feature selection and parameter optimization using hybrid backtracking search algorithm for wind speed forecasting. Energy Conversion and Management, 2017, 143:360-376.
Gillett B E, Miller L R. A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 1974, 22(2):340-349.
Savelsbergh M W. The vehicle routing problem with time windows:Minimizing route duration. ORSA Journal on Computing, 1992, 4(2):146-154.
Christofides N, Mingozzi A, Toth P. The vehicle routing problem. Eds. by Christofides N M A, Toth P, Sandi C. Combinatorial Optimization. UK:Wiley, Chichester, 1979:315-338.
Cattaruzza D, Absi N, Feillet D, et al. A memetic algorithm for the multi trip vehicle routing problem. European Journal of Operational Research, 2014, 236(3):833-848.
Lin Q, Gao L, Li X, et al. A hybrid backtracking search algorithm for permutation flow-shop scheduling problem. Computers & Industrial Engineering, 2015, 85:437-446.
Tan K C, Chew Y H, Lee L. A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Computational Optimization and Applications, 2006, 34(1):115-151.
Tu W, Li Q, Li Q, et al. A spatial parallel heuristic approach for solving very large-scale vehicle routing problems. Transactions in GIS, 2017, 21(6):1130-1147.