Formulating and solving stochastic truck and trailer routing problems using meta-heuristic algorithms / Seyedmehdi Mirmohammadsadeghi - Seyedmehdi, Mirmohammadsadeghi (2015)
Manufacturers and services providers often encounter stochastic parametric scenarios. Researchers have, thus far, considered deterministic truck and trailer routing problems (TTRP) that cannot address the prevailing demand, travel time, service time uncertainties and other pertinent complexities. The purpose of this research is to expand the deterministic TTRP models by introducing stochastic parameters to bring these models closer to the reality. In this research, firstly, truck and trailer routing problems with stochastic demands (TTRPSD) is introduced and modeled. Since the demands are not fixed, the failure may occur when the cumulative demands exceed or attain exactly the truck or vehicle capacities, which is again subject to the types of route. For solving TTRP, a variety of algorithms have been applied earlier but TTRPSD programming has not yet solved. Therefore, multi-point simulated annealing (M-SA), memetic algorithm (MA) and tabu search (TS) algorithms are applied to solve the TTRPSD. Twenty one benchmark-instances have been modified for this case and solved by using the aforesaid algorithms. Afterward, the TTRPSD is extended by considering the time window constraints. Since special operational restrictions or requirements may exist in some real applications such as customer‘s working period that some customers must be serviced during a specified time interval and there can be no delays in servicing those customers. Therefore, truck and trailer routing problem with stochastic demands and time window (TTRPSDTW) is more realistic and thus modeled. Another purpose of this model is to solve it in a reasonable timeframe by administering the MA, M-SA and TS methods. Here, firstly, two experimental tests have been carried out to show the validity and consistency of the applied algorithms for solving TTRPSDTW. The results is compared with vehicle routing problem with stochastic demands and time window (VRPSDTW) solution obtained by large neighborhood search (LNS) by an earlier researcher. The results indicate that the applied algorithms can generate the useful results. Therefore, iv MA, M-SA and TS are found suitable for solving TTRPSDTW as well. Moreover, fifty four benchmark instances have been modified for this case. The initial feasible solutions have been generated for this purpose. The solutions have then been significantly improved by the algorithms. In addition, travel and service times between customers may not be deterministic in real life applications. So, truck and trailer routing problem with stochastic travel and service times with time window (TTRPSTTW) are considered. For solving this problem, the aforesaid algorithms have been applied. One hundred and forty four benchmark instances in six levels have been modified for this study. The initial feasible solutions have been generated for this purpose. The solutions have been significantly improved by the algorithms. This issue has been formulated under chance constrained programming (CCP) model and stochastic programming model with recourse (SPR). Since the CCP model is completely depended on the confidence level and sometimes makes the solutions infeasible, in this case no feasible solution for CCP model is found. Therefore, the problems are only solved within the framework of SPR. Also, all of the aforesaid problems have been tested by sensitivity analysis to understand the effects of parameters as well as to make comparison between the respective best results and sensitivity analysis. Since the differences between the results are insignificant, the algorithms are found appropriate and suitable for solving TTRPSDTW. All those models have been applied in a real company. This study has been carried out with the collaboration of Pegah Co, a large dairy products distribution company in Iran. One hundred customers with their demands that follow the Poisson distribution are considered for this study. Methods such as MA, M-SA and TS have been applied. The problems are solved by using the MA, M-SA and TS. In addition, these problems also have been tested using the sensitivity analysis.