Review: An annotated bibliography of combined routing and loading problems (Q6486685)

Many activities in freight transportation involve two basic optimization issues: finding the optimal routes to deliver goods, and determine the best way for loading such goods on the vehicles used for transportation. The great majority of problems arising in these two areas belongs to the class of (strongly) NP-hard problems, and is very challenging in practice. Therefore, most of the research was concentrated on solving these problems separately. In recent literature, their combined solution has attracted a number of researchers and practitioners and led to interesting theoretical, as well as practical results. The authors propose a systematic way to review the most relevant results obtained in the area of vehicle routing with loading constraints. Their main aim was to stimulate further research in this promising area.NEWLINENEWLINE At its beginning, the paper contains a brief description of both considered problems: the routing problem and the loading problem. The routing problems are related to finding the best possible routes for the vehicles transporting given items under some predefined constraints (e.g. capacities). Among routing problems, the traveling salesman problem (TSP) and the vehicle routing problem (VRP) are the most important. In the loading problems it is necessary to ensure that the transported items can be feasibly allocated within the vehicle loading space. The loading problems are usually related to the shape and/or orientation of items, and involve 2D and 3D packing. The most famous problems in this class are rectangles packing (bin packing problems, BPP) in 2D, and boxes and spheres packing in 3D. In addition to the need of obtaining a feasible placement of the demanded items in the loading space, a frequent relevant constraint is that the placement allows to perform the unloading operations without reshuffling the items. Combining the representatives of two mentioned optimization goals, various classes of problems are defined, and the recent relevant results are reviewed through the paper.