�鶹ӰԺ

Approximate dynamic programming for a dynamic appointment scheduling problem
Z. Nenova, M. Laguna, and D. Zhang

We study a dynamic appointment scheduling problem with cancellations and overbooking motivated by a medical clinic, where appointment requests arrive over time. The objective is to balance patient waiting time with service providers' overtime and idle time. The problem is formulated as a nite-horizon stochastic dynamic program. However, the formulation suers from the curse of dimensionality as the state is the service schedule, which is inherently high dimensional. We propose a solution approach based on approximate policy iteration and value function approximation. We validate the approach with data from a public hospital in the US. We use the data to develop a Weibull accelerated failure time model to estimate the time- and patient-dependent cancellation and no-show probabilities. Our solution approach allows treating each patient as his or her own class. The approximate policy iteration approach is simulation-based and can accommodate complex system dynamics. Our numerical study shows that the approach is competitive against several computational benchmarks.

M. Laguna, R. Martí, A. Martínez Gavara, S. Pérez-Peló, and M. G. C. Resende

This is a comprehensive review of the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic and its hybridization with Path Relinking (PR). GRASP with PR has become a widely adopted approach for solving hard optimization problems since its proposal in 1999. The paper covers the historical development of GRASP with PR and its theoretical foundations, as well as recent advances in its implementation and application. The review includes a careful analysis of PR variants, paying special attention to memory-based and randomized designs, with a total of ten different implementations. It identifies the design questions that are still open in the scientific literature. The experimental section applies advanced PR implementations on two well-known combinatorial optimization problems, linear ordering and max-cut, in an effort to answer these open questions. The paper also explores the hybridization of PR and other metaheuristics, such as tabu search, scatter search, and random-keys genetic algorithms. Overall, this review provides valuable insights for researchers and practitioners seeking to implement GRASP with PR for solving optimization problems.

Laguna, M. and Martí, R. (1999) , INFORMS Journal on Computing, 11 (1), 899-1499.

R. Martín-Santamaría, A. Martínez-Gavara, A.D. López-Sánchez, and M. Laguna

We propose a reference framework to apply the multiparent path relinking (MPR) methodology. MPR is an extension of path relinking (PR) that has been proposed and described but, to the best of our knowledge, it has never been applied. PR is a trajectory-based neighborhood search strategy that explores paths that traverse pairs of solutions. PR has been widely used for search intensification purposes within metaheuristic implementations. To show how MPR can be embedded in more than one setting, our proposal consists of both employing MPR as a post-processing step in a greedy randomized adaptive search procedure (GRASP) and as the combination method in a scatter search (SS). We use the power dominating set problem (PDSP) as our testing platform because its difficulty and structure enable the design and assessment of various strategies. The PDSP seeks to find the minimum placement of measurement devices in an electrical network to monitor the entire system. Our computational experiments are designed to identify the contribution of each element of our proposed MRP implementations.

H. I. Calvete, C. Galé, J. A. Iranzo, and M. Laguna

The literature includes very few instances of scatter search applications to bilevel optimization. These implementations have been proposed for problems in the field of logistics involving integer variables and are based on a structure where scatter search sets the values of the decisions at the upper level followed by the solution of the lower level problem. In this work, we develop a scatter search for general linear bilevel problems. Our proposal employs a tailored path relinking procedure that generates solutions that are boundary feasible extreme points located in the trajectory between infeasible and feasible bilevel solutions. We perform scientific experimentation to determine the most effective configuration of our scatter search with path relinking. We also perform competitive experiments to determine where the proposed solution method stands when compared to the state of the art for tackling linear bilevel problems with metaheuristic technology.

Lot-sizing and scheduling of parallel production lines to minimize changeovers and deviations from target inventory levels
S. Cavero and M. Laguna

The production scheduling problem that we tackle concerns the manufacturing of car seats. A manufacturing facility uses molds and foam to make the inside of a seat for a variety of car models. Carriers with molds are mounted on a limited number of positions in production lines that have the shape of a racetrack. The problem consists of determining the sequence of carriers to mount in each position of each production line to keep inventory levels as close as possible to desired target values at the end of the planning horizon, while minimizing the total number of changeovers. We formulate the problem as mixed integer program and test the limits of the problem sizes that commercial mathematical programming software (Gurobi) can tackle. We also find heuristic solutions with both commercial software (LocalSolver) and a metaheuristic procedure.

Colmenar, J. M., M. Laguna, and R. Martín

Tabu Search is a metaheuristic renowned for its ability to navigate complex solution spaces by iteratively exploring neighborhoods and intelligently diversifying the search process to avoid getting trapped in local optima. We describe the main elements of the tabu search methodology in the context of finding high-quality solutions to the minimum dominating set problem (MDSP). The MDSP is a fundamental combinatorial optimization challenge with applications in various fields, including network design, social network analysis, and bioinformatics.