•A literature review on off-line and on-line 3D packing problems is conducted.•The main constraints and solution approaches are structured.•Practical constraints in both off-line and on-line studies ...are often oversimplified.•There is a lack of constructive heuristic methods for solving on-line problems.•The development of on-line and semi-on-line models deserves further attention.
Three-Dimensional Packing Problems (3D-PPs) can be applied to effectively reduce logistics costs in various areas, such as airline cargo management and warehouse management. In general, 3D-PP studies can be divided into two different streams: those tackling the off-line problem, where full knowledge about items is available beforehand; and those tackling the on-line (real-time) problem, where items arrive one by one and should be packed immediately without having full prior knowledge about them. During the past decades, off-line and on-line 3D-PPs have been studied in the literature with various constraints and solution approaches. However, and despite the numerous practical applications of on-line problems in real-world situations, most of the literature to date has focused on off-line problems and is quite sparse when it comes to on-line solution methods. In this regard, and despite the different nature of on-line and off-line problems, some approaches can be applied in both environments. Hence, we conducted an in-depth and updated literature review to identify and structure various constraints and solution methods employed by researchers in off-line and on-line 3D-PPs. Building on this, by bringing together the two separate streams of the literature, we identified several off-line approaches that can be adopted in on-line environments. Additionally, we addressed relevant research gaps and ways to bridge them in the future, which can help to develop this research field.
In online three-dimensional packing problems (3D-PPs), unlike offline problems, items arrive sequentially and require immediate packing decisions without any information about the quantities and ...sizes of the items to come. Heuristic methods are of great importance in solving online problems to find good solutions in a reasonable amount of time. However, the literature on heuristics for online problems is sparse. As our first contribution, we developed a pool of heuristics applicable to online 3D-PPs with complementary performance on different sets of instances. Computational results showed that in terms of the number of used bins, in all problem instances, at least one of our heuristics had a better or equal performance compared to existing heuristics in the literature. The developed heuristics are also fully applicable to an intermediate class between offline and online problems, referred to in this paper as a specific type of “semi-online with full look-ahead”, which has several practical applications. In this class, as in offline problems, complete information about all items is known in advance (i.e., full look-ahead); however, due to time or space constraints, as in online problems, items should be packed immediately in the order of their arrival. As our second contribution, we presented an algorithm selection framework, building on developed heuristics and utilizing prior information about items in this specific class of problems. We used supervised machine learning techniques to find the relationship between the features of problem instances and the performance of heuristics and to build a prediction model. The results indicate an 88% accuracy in predicting (identifying) the most promising heuristic(s) for solving any new instance from this class of problems.
•Several heuristic methods to solve online 3D-packing problems (3D-PPs) are proposed.•Proposed heuristics are applicable to semi-online 3D-PPs with full look-ahead.•An algorithm selection framework to predict the most promising heuristic is proposed.•The prediction performance of three learning algorithms is compared in the framework.•The multi-label neural network demonstrates a notably high prediction accuracy.
The negative impacts of urban freight transport have fostered the design of new distribution systems for inner city deliveries. One of the proposed city logistics solutions is the establishment of ...two-echelon distribution systems, where freight originating from the periphery of the city is transferred at intermediate locations (satellites) from larger vehicles (urban freighters) to smaller more environmentally friendly vehicles (city freighters), deemed more suited to operate in the city centre. In this paper, we address a variant of the two-echelon (capacitated) vehicle routing problem (2E-CVRP) arising in the context of city logistics encompassing characteristics such as a heterogeneous fleet of city freighters, time windows, vehicles synchronisation at satellites, direct deliveries, the possibility of freight transfers at customers, and multiple trips by city freighters. We propose a heuristic solution method for this problem based on a Variable Neighbourhood Search (VNS) heuristic, as well as a set of auxiliary evaluation metrics designed to support the decision making process. Preliminary results show the flexibility of the proposed heuristic to account for different problem characteristics, as well as the impacts of considering different best insertion criteria for the initial solution construction. Additionally, the proposed evaluation metrics have allowed for an improved assessment of the trade-offs between different city logistic solutions, and may be considered when developing decision support systems.
More than ever, the economic globalization is creating the need to increase business competitiveness. Lean manufacturing is a management philosophy oriented to the elimination of activities that do ...not create any type of value and are thus considered a waste. One of the main differences from other management philosophies is the shop-floor focus and the operators' involvement. Therefore, the training of all organization levels is crucial for the success of lean manufacturing. Universities should also participate actively in this process by developing students' lean management skills and promoting a better and faster integration of students into their future organizations. This paper proposes a single realistic manufacturing platform, involving production and assembly operations, to learn by playing many of the lean tools such as VSM, 5S, SMED, poke-yoke, line balance, TPM, Mizusumashi, plant layout, and JIT/kanban. This simulation game was built in tight cooperation with experienced lean companies under the international program "Lean Learning Academy,"http://www.leanlearningacademy.eu/ and its main aim is to make bachelor and master courses in applied sciences more attractive by integrating classic lectures with a simulated production environment that could result in more motivated students and higher study yields. The simulation game results show that our approach is efficient in providing a realistic platform for the effective learning of lean principles, tools, and mindset, which can be easily included in course classes of less than two hours.
Urban freight transport is an important enabling factor for economic growth and social activities in cities but despite its benefits, it also generates important negative externalities including ...traffic congestion, pollution, noise and overall less safety. Moreover, increased limitations on urban freight transport, including access constraints, limited kerbside and private parking spaces for loading/unloading, and the often prohibitive costs of installing logistics infrastructures in city centres, have further constrained urban freight transport. To address these issues, several city logistics solutions have been proposed, such as two-tier distribution systems and distribution systems based on mobile depots.
In this paper, we focus on two-tier urban freight distribution systems based on mobile depots, where little or no physical infrastructure is considered and where storage is not permitted at transfer locations. In these types of systems, coordination and synchronisation between vehicles are essential, and the main objective is to have vehicles at the transfer locations in a need-to-be basis as a way of minimising the negative externalities.
We review and analyse 13 cases found in the scientific literature, trial reports and online resources, and propose a classification of these systems based on the level of mobility and accessibility of transportation modes operating at the first-tier. Furthermore, we characterise the main components and operational features of the different systems, including the existence of multi-trips, the types of transport modes used at both tiers, transported loads and the organisation of the transfer sites (satellites). This work aims to contribute for a clearer characterisation of two-tier urban distribution systems based on mobile depots, to later support the development of the most adequate mathematical models and solution methods to be applied to each variant of this type of systems.
The negative impacts of urban logistics have fostered the search for new distribution systems in inner city deliveries. In this context, interesting solutions can be developed around two-echelon ...distribution systems based on mobile depots (2E-MD), where loads arriving from the periphery of the city are directly transferred, at intermediate locations, from larger to smaller vehicles more suited to operate in the city centre. Four types of 2E-MD can be identified, according to the degree of mobility of larger vehicles and their accessibility to customers.
In this paper, we propose a generic three-index arc-based mixed integer programming model, for a two-echelon vehicle routing problem, with synchronisation at the satellites and multi-trips at the second echelon. This generic base model is formulated for the most restrictive type of problems, where larger vehicles visit a a single transfer location and do not perform direct deliveries to customers, but it can be easily extended to address the other types of 2E-MD. The paper presents how these extensions account for the characteristics of the different types of 2E-MD.
The generic model, its extensions and the impact of a set of valid inequalities are tested using problem instances adapted from the VRP literature. Results show that the proposed extensions do adequately address the specific features of the different types of 2E-MD, including multiple visits to satellites, and direct deliveries to customers. Nevertheless, the resulting models can only tackle rather small instances, even if the formulations can be strengthened by adding the valid inequalities proposed in the paper.
The main focus of this thesis is to address cargo stability within the container loading problem (CLP). In the last years the transport industry has been facing increasing chal- lenges. Whether as a ...result of new regulations or of the increasing service levels demanded by customers, the pressure for high levels of performance from transportation companies will continue in the short, as well as in the long term.This combination between compliance and service level challenges, has a strong im- plication in the way cargo transportation will be addressed in the future. The need to maximize the usage of space within the different transport modes without deterioration of the cargo is one of the main problems that highlights the effect of these challenges. Given the complexity of the problem, the need for cargo planning tools that can be effectively used in practice, is expected to increase.The amount of research that has addressed the problem of optimization of the spatial arrangement of cargo inside trucks or containers has grown in the last decade. The problem, known in the literature as the CLP, belongs to the more generic combinatorial optimization class of Cutting and Packing problems.Although several approaches to this problem have been proposed, their wide adoption by transportation companies did not occur. This mainly results from the fact that the basic formulation of the problem does not address the requirements of the real-world problem, that is, it does not address a set of practical constraints that influence the way cargo is arranged inside the container. One of the most important practical constraints is cargo stability, and even though it has been addressed in the literature, it has been done in an over-simplified way that does not actually translate real-world stability.The proposed work aims to develop new algorithms for the CLP, based on heuristics and metaheuristics that will contribute to close the gap between research and the industry practice. Particular attention was given to cargo stability, which will be studied, modelled and integrated with the optimization of cargo spatial arrangement.The first part of this thesis contains a comprehensive introduction to the CLP and cargo stability. This includes CLP typologies, modelling approaches, heuristic solution methods and practical constraints. An extensive analysis of cargo stability within the CLP is also presented.The second part of this thesis reflects the defined approach to cargo stability, that is, that cargo stability should be addressed by separating static and dynamic stability. It first proposes an algorithm for evaluating static stability based on the static mechanical equilibrium conditions applied to rigid bodies and a physical packing sequence algorithm that, given a container loading arrangement, generates the actual sequence by which each box is placed inside the container, considering static stability and loading operations efficiency. Secondly, it proposes for the CLP, a multi-population biased random-key genetic algorithm that combines a genetic algorithm and a constructive heuristic algorithm. The constructive heuristic uses the proposed static stability approach to evaluate stability during the filling of the container and the proposed physical packing sequence algorithm to evaluate the feasibility of loading arrangements. Thirdly, to explore dynamic stability, a physics simulation tool is presented and its main physical parameters validated. The tool was developed to simulate the external forces to which the container is exposed during transportation. It is followed by the development of a set of dynamic stability evaluation metrics to be used within CLP algorithms.Aside from a comprehensive introduction to CLP and cargo stability, the main contributions of this thesis are the proposed static stability approach, the CLP algorithm, the physics simulation tool and a set of dynamic stability metrics.
PDF
