Unified heuristics for a class of complex and practical routing problems in logistics

Abstract

Travelling Salesmen Problem (TSP) and Vehicle Routing Problem (VRP) are areas which have been widely dealt with in the last four decades. Methodologies were developed for many variants of the TSP and VRP by different researchers. This study considers yet another set of variants of the aforesaid problems normally encountered in practice but have not been given attention to hitherto. These variants of the classical TSP and VRP are a little complex and pertaining to Balanced Logistics, Reverse Logistics, Distribution Logistics and Urgency Logistics for the application of both Manufacturing and Service Industries. In addition, constraints such as multiple vehicles, workload balancing, simultaneous and mixed loads, constrained capacity and forced backhauls are also considered. While the NP-hardness of these problems mandate the use of meta-heuristics, recognition of inherent characteristics of the problem led to the development of construction heuristics to obtain good feeder solutions that speed up the intensive search. Genetic Algorithms (GA), Simulated Annealing (SA) and a hybrid of the two are the meta-heuristics proposed for the optimization. The proposed unified heuristics are evaluated by comparing it with published results using standard, derived and randomly generated data-sets. In cases where benchmarks are not available, the published best results for the simpler versions of TSP and VRP are used as substitutes for the lower bounds. The heuristics performed exceedingly well in the evaluations, recording better or equally good results in comparison to the existing methodologies. Case studies for each of the variants are also highlighted.