Combining Vehicle Routing Optimization and Container Loading Optimization
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.
...
Keywords
Metadata
Show full item recordCollections
- Pro gradu -tutkielmat [29684]
License
Related items
Showing items with similar title or keywords.
-
Algorithmic issues in computational intelligence optimization : from design to implementation, from implementation to design
Caraffini, Fabio (University of Jyväskylä, 2016)The vertiginous technological growth of the last decades has generated a variety of powerful and complex systems. By embedding within modern hardware devices sophisticated software, they allow the solution of complicated ... -
On automatic algorithm configuration of vehicle routing problem solvers
Rasku, Jussi; Musliu, Nysret; Kärkkäinen, Tommi (Springer, 2019)Many of the algorithms for solving vehicle routing problems expose parameters that strongly influence the quality of obtained solutions and the performance of the algorithm. Finding good values for these parameters is a ... -
Application of a Knowledge Discovery Process to Study Instances of Capacitated Vehicle Routing Problems
Kärkkäinen, Tommi; Rasku, Jussi (Springer, 2020)Vehicle Routing Problems (VRP) are computationally challenging, constrained optimization problems, which have central role in logistics management. Usually different solvers are being developed and applied for different ... -
Memory-saving optimization algorithms for systems with limited hardware
Iacca, Giovanni (University of Jyväskylä, 2011) -
Multilayer perceptron training with multiobjective memetic optimization
Nieminen, Paavo (University of Jyväskylä, 2016)Machine learning tasks usually come with several mutually conflicting objectives. One example is the simplicity of the learning device contrasted with the accuracy of its performance after learning. Another common example ...