Combining Vehicle Routing Optimization and Container Loading Optimization

Abstract

Vehicle routing optimization and container loading combined would produce millions of queries for the remaining capacity of the vehicles. In this situation, these approximate methods for finding the remaining capacity of the vehicle’s container are investigated. These methods reduce the time needed to approximate the remaining capacity in vehicles and will hence accelerate the overall optimization process. In this thesis we consider a solution to improve the accuracy of real-world vehicle routing optimization problems. Simple capacitated vehicle routing optimization does not capture any information about the packing of objects except by deducting the volume of the packed objects from the container’s volume. Bin packing during the routing optimization is usually slow. We combine a very fast approximation algorithm for 3D bin packing with vehicle routing optimization to speed up the whole process. Vehicle routing combined with the 3D container loading problem creates new kinds of challenges. The problem was introduced in Gendreau et al. 2006 where 3D loading space replaces the scalar capacity of the vehicles. The container loading problem attempts to obtain the best possible utilization of space, while the vehicle routing problem is concerned with finding the minimum-cost or minimum-distance route in transportation. The combined problem is about loading boxes with different symmetry into rectangular containers of the vehicles used in delivery. This problem is extremely hard because it is a combination of the two problems mentioned above, which are both NP-hard [Gendreau et al. 2006, Pisinger 2002]. Finding an exact solution for this problem is infeasible since even solving a small instance of bin packing problem alone would require more computing resources as feasible (Martello, Pisinger, and Vigo 2000). To handle this situation approximation algorithms are used as it is often not necessary to find the optimal solution for the bin packing problem. An approximate solution that is close to optimal and computed with the help of reasonable resources and time is considered a good solution. When vehicle routing optimization and container loading are combined, a high number of queries for the remaining capacity of the vehicles are performed. In this thesis we exploit this fact and perform experiments with approximate methods for finding the remaining capacity of the vehicle’s container in a fast but approximate way. In our experiments we use a slight modification of the 3D bin packing algorithm called Largest Area First Fit (LAFF) (Gürbüz et al. 2009) as a rough but fast means to determine the remaining capacity in the containers during the vehicle routing optimization process. A bounding box is used for objects which are not rectangular in shape, such as cylindrical shapes. The LAFF algorithm carries the placement of the boxes such that those with the largest surface area are placed first while keeping the height minimum from the floor of the container. The box which covers the largest ground area of the container is placed first followed by subsequent boxes that are stacked in the remaining space at the same level, the boxes with the greatest volume first. Then the level is increased and the process repeated. Boxes are rotated such that they have the largest possible footprint. This algorithm works exceptionally fast when the number and variety of the objects to be packed are small. During the LAFF stage, all real-world bin packing constraints e.g. the weight of the boxes, loading priorities, orientation, stacking, the distribution of weight in different parts of the container, stability, etc. are ignored to gain as much speed as possible.