Multi-Point Simulated Annealing Algorithm for Solving Truck and Trailer Routing Problem with Stochastic Travel and Service Time

Seyedmehdi Mirmohammadsadeghi, S. Maryam Masoumik, Somaieh Alavi


The truck and trailer routing problem with stochastic travel and service time (TTRPSTT) is a development model of the truck and trailer routing problem (TTRP). In this case, travel and service times between customers are considered stochastic. Many researchers considered TTRP with deterministic parameters, but in real-life due to traffic congestion, different weather conditions, level of driver’s skills may be influenced by distribution technology, often travel and service times are not really deterministic between two customers and normally follow stochastic distributions. Therefore, TTRPSTT has practical significance. TTRP has been solved by different algorithms but TTRPSTT has not been addressed yet. Here multi-point simulated annealing (M-SA) is applied to solve the TTRPSTT. Forty-eight instance problems have been modified for this case and solved by using this algorithm. The purpose of the paper is to introduce and solve TTRPSTT in a reasonable time by the simulated annealing algorithm. Also, the paper gives some suggestions for further researches.


Stochastic travel and service time, Trailer routing problem, Multi-point simulated annealing, Customers

Full Text:



Bartolini, E., Schneider, M., 2020. A two-commodity flow formulation for the capacitated truck-and-trailer routing problem. Discrete Applied Mathematics 275, 3-18.

Chao, I.M., 2002. A tabu search method for the truck and trailer routing problem. Computers & Operations Research 29(1), 33-51.

Derigs, U., Pullmann, M., Vogel, U., 2013. Truck and trailer routing—Problems, heuristics and computational experience. Computers & Operations Research 40(2), 536-546.

Fallahpour, A., Olugu, E.U., Musa, S.N., Khezrimotlagh, D., Wong, K.Y., 2016. An integrated model for green supplier selection under fuzzy environment: application of data envelopment analysis and genetic programming approach. Neural Computing and Applications 27(3), 707-725.

Fallahpour, A., Udoncy Olugu, E., Nurmaya Musa, S., Yew Wong, K., Noori, S., 2017. A decision support model for sustainable supplier selection in sustainable supply chain management. Computers & Industrial Engineering 105, 391-410.

Lei, H., Laporte, G., Guo, B., 2011. The capacitated vehicle routing problem with stochastic demands and time windows. Computers & Operations Research 38(12), 1775-1783.

Li, H., Lv, T., Lu, Y., 2016. The Combination Truck Routing Problem: A Survey. Procedia Engineering 137, 639-648.

Li, X., Tian, P., Leung, S.C.H., 2010. Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm. International Journal of Production Economics 125(1), 137-145.

Miranda, D.M., Conceição, S.V., 2016. The vehicle routing problem with hard time windows and stochastic travel and service time. Expert Systems with Applications 64, 104-116.

Mirmohammadsadeghi, S., Ahmed, S., 2015. Memetic Heuristic Approach for Solving Truck and Trailer Routing Problems with Stochastic Demands and Time Windows. Networks and Spatial Economics 15(4), 1093-1115.

Mirmohammadsadeghi, S., Ahmed, S., Nadirah, E., 2014. Application of Memetic Algorithm to Solve Truck and Trailer Routing Problems. Proceedings of the 2014 International Conference on Industrial Engineering and Operations Management, Bali., 747-757.

Parragh, S.N., Cordeau, J.-F., 2017. Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows. Computers & Operations Research 83, 28-44.

Sarder, M.D., 2021. Chapter 2 - Network and cost analysis of transportation system, in: Sarder, M.D. (Ed.) Logistics Transportation Systems. Elsevier, pp. 37-58.

Wang, C., Zhang, Q., Zhang, W., 2020. Corporate social responsibility, Green supply chain management and firm performance: The moderating role of big-data analytics capability. Research in Transportation Business & Management, 100557.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.