The increasing accumulation of solid waste worldwide has made it necessary to look for alternatives that improve the operation of recyclable waste collection systems to make waste treatment more profitable and eco-friendlier. This paper introduces a new variant of the multi-compartment vehicle routing problem (MCVRP) that considers the rearrangement or relocation of collection points and packing the demand. This problem is called the location packing multi-compartment vehicle routing problem (LPMCVRP) and is developed for a waste collection system using vehicles with flexible compartments. A mathematical formulation of the problem is proposed. A two-phase metaheuristic algorithm based on a tabu search without packing considerations and a variant that integrates a tabu search and a greedy randomized adaptive search procedure (GRASP) scheme with packing constraints have been proposed. A set of instances adapted from the literature is generated to validate the proposed solution strategy. The results obtained show the efficiency of the proposed solution scheme for optimizing collection systems.

This article presents a metaheuristic algorithm to solve the pallet-building problem and the loading of these in trucks. This approach is used to solve a real application of a Colombian logistics company. Several practical requirements of goods loading and unloading operations were modeled, such as the boxes’ orientation, weight support limits associated with boxes, pallets and vehicles, and static stability constraints. The optimization algorithm consists of a two-phase approach, the first is responsible for the construction of pallets, and the second considers the optimal location of the pallets into the selected vehicles. Both phases present a search strategy type of GRASP. The proposed methodology was validated through the comparison of the performance of the solutions obtained for deliveries of the logistics company with the solutions obtained using a highly accepted commercial packing tool that uses two different algorithms. The proposed methodology was compared in similar conditions with the previous works that considered the same constraints of the entire problem or at least one of the phases separately. We used the sets of instances published in the literature for each of the previous works. The results allow concluding that the proposed algorithm has a better performance than the most known commercial tool for real cases. The proposed algorithm managed to match most of the test instances and outperformed some previous works that only involve decisions of one of the two problems. As future work, it is proposed to adapt this work to the legal restrictions of the European community.

The vehicle routing problem combined with loading of goods, considering the reduction of fuel consumption, aims at finding the set of routes that will serve the demands of the customers, arguing that the fuel consumption is directly related to the weight of the load in the paths that compose the routes. This study integrates the Fuel Consumption Heterogeneous Vehicle Routing Problem with Two-Dimensional Loading Constraints (2L-FHFVRP). To reduce fuel consumption taking the associated environmental impact into account is a classical VRP variant that has gained increasing attention in the last decade. The objective of this problem is to design the delivery routes to satisfy the customers’ demands with the lowest possible fuel consumption, which depends on the distances of the paths, the assigned vehicles, the loading/unloading pattern and the load weight. In the vehicle routing problem literature, the approximate algorithms have had great success, especially the evolutionary ones, which appear in previous works with quite a sophisticated structure, obtaining excellent results, but that are difficult to implement and adapt to other variants such as the one proposed here. In this study, we present a specialized genetic algorithm to solve the design of routes, keeping its main characteristic: the easy implementation. By contrast, the loading of goods restriction is validated by means of a GRASP algorithm, which has been widely employed for solving packing problems. With a view of confirming the performance of the proposed methodology, we provide a computational study that uses all the available benchmark instances, allowing to illustrate the savings achieved in fuel consumption. In addition, the methodology suggested can be adapted to the version of solely minimizing the total distance traveled for serving the customers (without the fuel consumption) and it is compared to the best works presented in the literature. The computational results show that the methodology manages to be adequately adapted to this version and it is capable of finding improved solutions for some benchmark instances. As for future work, we propose to adjust the methodology to consider the three-dimensional loading problem so that it adapts to more real-life conditions of the industry.

The Vehicle Routing Problem with Loading Constraints (VRPLC) is strongly related to real life applications in distribution logistics. It addresses the simultaneous loading and routing of vehicles, which are two crucial activities in transportation. Since treating these operations separately may result in impractical solutions, the development of applications for VRPLCs has gained the attention of researchers in recent years. Several heuristic methods have been proposed, but they consider only a limited group of practical characteristics that arise in real world situations. This study proposes a hybrid heuristic method based on the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic and the Clarke and Wright Savings algorithm, to solve a VRPLC with several loading and routing constraints that have not been considered simultaneously before. Experimental results show that the proposed procedure produces competitive solutions in short processing times. Lastly, the impact of the added operational constraints is also analyzed.

This work studies the scheduling of elective procedures, with stochastic durations, in surgery rooms. Given a set of rooms with limited availability and a set of procedures, it must be decided in which room and when each procedure will be performed. The problem’s objectives are to maximize the use of the operating rooms and to minimize the delays in starting the scheduled surgeries. A simulation-optimization approach is proposed. First, procedures’ durations are modeled as random variables and a set of test percentiles (i.e. it is assumed that all surgeries will last as many minutes as the 75th percentile of its probability density function) is selected. Subsequently, using these durations as a parameter, a greedy randomized adaptive search procedure (GRASP) is run. Consequently, as many solutions as selected test percentiles are generated. Finally, a Monte Carlo simulation is used to estimate three indicators: i) rooms utilization, ii) percentage of surgeries that had delays, and iii) average delay time of scheduled surgeries. The technique was tested by solving the elective procedures scheduling problem in a high-complexity hospital in Bogota. This hospital has 19 operating rooms and 35,000 surgeries performed annually. Currently, the scheduling process is manual. The simulation-optimization proposed approach allowed to determine the relation between utilization rate and delays in the service. As the occupation percentage increases, delay times also augment, implying a reduction of the service level. An average reduction of 5% in delay times entails a reduction between 3% and 9% of operating room occupancy.

This paper tackles an extension to the Multi-activity Combined Timetabling and Crew Scheduling Problem (MCTCSP). The goal of the original problem is to schedule the minimum number of homogenous workers required, in order to visit a set of customers characterized by services needed against schedule availability. However, since in home services it is common to have specialized workers, a mathematical model considering a heterogeneous workforce is proposed. As a solution, a GRASP-based algorithm is designed. In order to test the metaheuristic performance, 110 instances from the literature are adapted to include categorical skills. In addition, another 10 instances are randomly generated to consider large problems. The results show that the proposed GRASP finds optimal solutions in 46% of the cases and saves 40–96% computational time.

This paper addresses the scheduling problem in a Permutation Flow Shop (PFS) environment, which is associated with many types of industries such as chemical, petrochemical, automobile manufacturing, metallurgical, textile, etc. Thus, this work intends to solve a PFS scheduling problem in order to minimize the total weighted tardiness, since it is an important sequencing criterion not only for on time delivery jobs but also for customer satisfaction. To solve the problem, GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic is proposed as a solution, which has shown competitive results compared with other combinatorial problems. In addition, two utility functions called Weighted Modified Due Date (WMDD) and Apparent Tardiness Cost (ATC) are proposed to develop GRASP. These are based on dynamic dispatching rules and also known for solving the problem of total weighted tardiness for single machine scheduling problem. Next, an experimental design was carried out for comparing the GRASP performance with both utility functions and against the WEDD dispatching rule results. The results indicate that GRASP-WMDD could improve the total weighted tardiness in 47.8% compared with WEDD results. Finally, the GRASP-WMDD performance for the PFS total tardiness problem was evaluated, obtaining a relative deviation index of 13.89% and ranking the method over 26 heuristics and metaheuristics.

Stochastic scheduling addresses several forms of uncertainty to represent better production environments in the real world. Stochastic scheduling has applications on several areas such as logistics, transportation, production, and healthcare, among others. This paper aims to evaluate the performance of various greedy functions for a GRASP-based approach, under stochastic processing times. Since simulation is used for estimating the objective function, two simulation techniques, Monte Carlo simulation and Common Random Numbers (CRN), are used to compare the performance of different greedy (utility) functions within the GRASP. In order to validate the proposed methodology, the expected total weighted tardiness minimization for a single machine problem was taken as case study. Results showed that both, CRN and Monte Carlo, are not statistically different regarding the expected weighted tardiness results. However, CRN showed a better performance in terms of simulation replications and the confidence interval size for the difference between means. Furthermore, the statistical analysis confirmed that there is a significant difference between greedy functions.

This paper addresses the stochastic permutation flow shop problem (SPFSP) in which the stochastic parameters are the processing times. This allows the modeling of setups and machine breakdowns. Likewise, it is proposed a multi-objective greedy randomized adaptive search procedure (GRASP) coupled with Monte-Carlo Simulation to obtain expected makespan and expected tardiness. To manage the bi-objective function, a sequential combined method is considered in the construction phase of the meta-heuristic. Moreover, the local Search combines 2-optimal interchanges with a Pareto Archived Evolution Strategy (PAES) to obtain the Pareto front. Also, some Taillard benchmark instances of deterministic permutation flow shop problem were adapted in order to include the variation in processing times. Accordingly, two coefficients of variation (CVs) were tested: one depending on expected processing times values defined as twice the expected processing time of a job, and a fixed value of 0.25. Thus, the computational results on benchmark instances show that the variable CV provided lower values of the expected makespan and tardiness, while the con-stant CV presented higher expected measures. The computational results present insights for further analysis on the behavior of stochastic scheduling problems for a better approach in real-life scenarios at industrial and service systems.