Search

In most seaports, pilotage is compulsory for incoming and outgoing vessels to use pilotage services. Maritime pilots play a critical role in providing local knowledge and assistance to ensure the safety of vessels and seafarers. Typically, pilots are classified into multiple classes on the basis of their experiences and qualifications. Moreover, pilotage duration is usually stochastic due to various factors, including harsh weather conditions, visibility, and traffic changes. In this study, we address a multi-class pilot dispatching problem with stochastic pilotage duration. We formulate this problem as a stochastic programming model that considers the expected penalty cost for late arrival at each task's location. To solve this problem, we develop a branch-and-price algorithm that integrates column generation within the branch and bound framework. Additionally, we develop a novel labelling algorithm and several effective acceleration techniques to enhance the efficiency of the proposed algorithm. Extensive numerical experiments demonstrate the effectiveness of the proposed algorithm and show that it can handle realistic-sized instances while outperforming a metaheuristic search method. [ABSTRACT FROM AUTHOR]

This paper focuses on the combined maintenance and routing optimisation problem in a multi-period environment that consists of scheduling maintenance operations for a set of geographically distributed machines, subject to non-deterministic failures with a set of technicians that perform preventive maintenance and corrective operations. This study uses a two-step approach based on column generation. The first step consists of a maintenance model that determines the optimal time until the next preventive maintenance operation, and each machine's maintenance frequency while minimising the total expected maintenance costs. The second step involves a routing model that assigns and schedules maintenance operations for each technician over the planning horizon while minimising the routing and maintenance costs. We formulate the second step problem as a periodic vehicle routing problem and to solve it, we propose a column generation approach. The master problem is a set partitioning formulation that indicates which machines must be visited in the planning horizon. This decomposition has two auxiliary problems: the first one is an elementary shortest-path problem to find a feasible path for each period and the second one finds a set of visiting periods for each machine. Our approach balances the maintenance cost, routing cost, and failure probabilities. [ABSTRACT FROM AUTHOR]

Interest in integrating lot-sizing and cutting stock problems has been increasing over the years. This integrated problem has been applied in many industries, such as paper, textile and furniture. Yet, there are only a few studies that acknowledge the importance of uncertainty to optimise these integrated decisions. This work aims to address this gap by incorporating demand uncertainty through stochastic programming and robust optimisation approaches. Both robust and stochastic models were specifically conceived to be solved by a column generation method. In addition, both models are embedded in a rolling-horizon procedure in order to incorporate dynamic reaction to demand realisation and adapt the models to a multistage stochastic setting. Computational experiments are proposed to test the efficiency of the column generation method and include a Monte Carlo simulation to assess both stochastic programming and robust optimisation for the integrated problem. Results suggest that acknowledging uncertainty can cut costs by up to 39.7%, while maintaining or reducing variability at the same time. [ABSTRACT FROM AUTHOR]

3D printing technology is fundamentally transforming how companies are run and managed today. This work analyzes the problem of integrated production and transportation of automotive spare parts in the context of 3D printing. We consider two sets of customers – scheduled and breakdown maintenance – serviced by the same resource but with distinct delivery modes. We propose a mixed-integer programming (MIP) formulation for optimally solving small problem instances. We develop an exact approach based on column generation (CG) for large cases by reformulating the MIP model as a set-covering problem through Dantzig-Wolfe decomposition. We design and deploy two acceleration strategies for the quicker convergence of the CG approach. Through extensive computational experiments, we establish the superiority and suitability of the proposed solution methodology for solving real-life problems at terse computational times. [ABSTRACT FROM AUTHOR]

The aim of this erratum is to correct an error in the computer implementation of the algorithm proposed by Dabia, Ropke, and van Woensel [Dabia S, Ropke S, van Woensel T (2013) Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Sci. 47(3):295–454]. Section 6, "Computational Results," from the original paper is rewritten to reflect the corrected implementation, the new computational setup, and the updated results. [ABSTRACT FROM AUTHOR]

In this paper, we study the pickup and delivery problem with time windows and multiple compartments (PDPTWMC). The PDPTWMC generalizes the pickup and delivery problem with time windows to vehicles with multiple compartments. In particular, we consider three compartment-related attributes: (1) compartment capacity flexibility that allows the capacities of the compartments to be fixed or flexible, (2) item-to-compartment flexibility that specifies which items are compatible with which compartments, and (3) item-to-item compatibility that considers that incompatible items cannot be simultaneously in the same compartment. To solve the PDPTWMC, we propose an exact branch-price-and-cut algorithm in which the pricing problem is solved by means of a unified bidirectional labeling algorithm. The labeling algorithm can tackle all possible combinations of the studied compartment-related attributes of the PDPTWMC. Furthermore, we implement several acceleration techniques that allow to, among others, reduce the symmetry in the label extensions with empty compartments, the symmetry in the dominance between compartments with similar attributes, and the complexity of the algorithm with fixed compartment capacity. Finally, we introduce benchmark instances for the PDPTWMC and conduct an extensive computational campaign to test the limits of our algorithm and to derive relevant managerial insights in order to highlight the applicability of considering the studied compartment-related attributes. Funding: This work was supported by Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant 439.18.459] and the Natural Sciences and Engineering Research Council of Canada [Grant 2017-06106]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0252. [ABSTRACT FROM AUTHOR]

Providing first aid and other supplies (e.g., epi‐pens, medical supplies, dry food, water) during and after a disaster is always challenging. The complexity of these operations increases when the transportation, power, and communications networks fail, leaving people stranded and unable to communicate their locations and needs. The advent of emerging technologies like uncrewed autonomous vehicles can help humanitarian logistics providers reach otherwise stranded populations after transportation network failures. However, due to the failures in telecommunication infrastructure, demand for emergency aid can become uncertain. To address the challenges of delivering emergency aid to trapped populations with failing infrastructure networks, we propose a novel robust computational framework for a two‐echelon vehicle routing problem that uses uncrewed autonomous vehicles (UAVs), or drones, for the deliveries. We formulate the problem as a two‐stage robust optimization model to handle demand uncertainty. Then, we propose a column‐and‐constraint generation approach for worst‐case demand scenario generation for a given set of truck and UAV routes. Moreover, we develop a decomposition scheme inspired by the column generation approach to generate UAV routes for a set of demand scenarios heuristically. Finally, we combine the decomposition scheme within the column‐and‐constraint generation approach to determine robust routes for both trucks (first echelon vehicles) and UAVs (second echelon vehicles), the time that affected communities are served, and the quantities of aid materials delivered. To validate our proposed algorithms, we use a simulated dataset that aims to recreate emergency aid requests in different areas of Puerto Rico after Hurricane Maria in 2017. [ABSTRACT FROM AUTHOR]

In this paper, we present a column generation-based algorithm for the bi-objective gate assignment problem (GAP) to generate gate schedules that minimize squared slack time at the gates while satisfying passenger expectations by minimizing their walking distance. While most of the literature focuses on heuristic or metaheuristic solutions for the bi-objective GAP, we propose flow-based and column-based models that lead to exact or near optimal solution approaches. The developed algorithm calculates a set of solutions to approximate the Pareto front. The algorithm is applied to the over-constrained GAP where gates are a limited resource and it is not possible to serve every flight using a gate. Our test cases are based on real data from an international airport and include various instances with flight-to-gate ratios between 23.9 and 34.7. Numerical results reveal that a set of solutions representing a compromise between the passenger-oriented and robustness-oriented objectives may be obtained with a tight optimality gap and within reasonable computational time even for these difficult problems. [ABSTRACT FROM AUTHOR]

Truck-and-drone routing problems have become an important research topic in the last decade because of their applications for last-mile deliveries. Despite the many publications in this area, the most efficient exact algorithms designed thus far struggle to solve the benchmark instances with 39 or more customers. This fact holds even for one of the simplest variants involving one truck and one drone whose routes must synchronize at customers' locations: the basic traveling salesman problem with a drone (TSP-D). In this article, we devise a new algorithm for the TSP-D that solves every benchmark instance with up to 59 customers, and it scales up to 99 customers when the drone is much faster than the truck. The core of our method is a dynamic programming algorithm that is applied for column generation and variable fixing within tailored decremental state-space relaxation strategies. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Fondo para la Investigación Científica y Tecnológica [Grant PICT-2018-2961] (Ministry of Science, Argentina). Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0390. [ABSTRACT FROM AUTHOR]

In this paper, we describe a branch-and-price algorithm for the personalized nurse scheduling problem. The variants that appear in the literature involve a large number of constraints that can be hard or soft, meaning that they can be violated at the price of a penalty. We capture the diversity of the constraints on individual schedules by seven generic constraints characterized by lower and upper bounds on a given quantity. The core of the column generation procedure is in the identification of individual schedules with minimum reduced cost. For this, we solve a shortest path problem with resource constraints (SPPRC) where several generic constraints are modeled as resource constraints. We then describe dominance rules adapted to the presence of both upper and lower bounds on the resources and leverage soft constraints to improve the dominance. We also describe several acceleration techniques for the solution of the SPPRC, and branching rules that fit the specificities of the problem. Our numerical experiments are based on the instances of three benchmarks of the literature including those of the two international nurse rostering competitions (INRC-I and INRC-II). Their objective is threefold: assess the dominance rules and the acceleration techniques, investigate the capacity of the algorithm to find provable optimal solutions of instances that are still open, and conduct a comparison with best published results. The most noticeable conclusion is that the improved solution of the SPPRC allows to solve optimally all the INRC-II instances where a four-week planning horizon is considered and 40% of the eight-week instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.0019. [ABSTRACT FROM AUTHOR]

The unit commitment problem is an important optimization problem in the energy industry used to compute the most economical operating schedules of power plants. Typically, this problem has to be solved repeatedly with different data but with the same problem structure. Machine learning techniques have been applied in this context to find primal feasible solutions. Dantzig-Wolfe decomposition with a column generation procedure is another approach that has been shown to be successful in solving the unit commitment problem to tight tolerance. We propose the use of machine learning models not to find primal feasible solutions directly but to generate initial dual values for the column generation procedure. Our numerical experiments compare machine learning–based methods for warmstarting the column generation procedure with three baselines: column prepopulation, the linear programming relaxation, and coldstart. The experiments reveal that the machine learning approaches are able to find both tight lower bounds and accurate primal feasible solutions in a shorter time compared with the baselines. Furthermore, these approaches scale well to handle large instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. [ABSTRACT FROM AUTHOR]

This paper addresses the single crew scheduling and routing problem in the context of road network repair and restoration, which is critical in assisting complex postdisaster decisions in humanitarian logistics settings. We present three novel formulations for this problem, which are the first suitable for column generation and branch-and-price (BP) algorithms. Specifically, our first formulation is based on enumerating crew schedules and routes while explicitly defining the relief paths. The second formulation relies on enumerating the schedules, routes, and relief paths. Finally, the third formulation builds upon the second one by including additional constraints and variables related to relief path decisions. Considering each formulation, we propose BP algorithms that rely on several enhancements, including a new dynamic programming labeling algorithm to efficiently solve the subproblems. Extensive computational results based on 648 benchmark instances reveal that our BP algorithms significantly outperform existing exact approaches, solving 450 instances to optimality, and remarkably 118 instances for the first time. Our framework is also very effective in improving the lower bounds, upper bounds, and optimality gaps that have been reported in the literature. Funding: This work was supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo [Grants 15/26453-7, 16/01860-1, 16/15966-6, and 19/23596-2], the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grant 313220/2020-4], and the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2023.0227. [ABSTRACT FROM AUTHOR]

Summary: Modern satellite communication systems are designed to serve dispersed users with changing operational requirements. Allocating resources to meet these requirements becomes highly complex when the size, location, and allocated frequency of satellite beams are flexible. We developed solution techniques that generate feasible beam patterns and frequency allocations to maximize the total demand met across all users. In our approach, an integer program selects an optimal set of beams from a heuristically generated pool of feasible candidate beams. The challenge is in how to efficiently build a pool of good quality candidate beams from exponentially many possible solutions. An innovative column generation‐style heuristic to generate mathematically justifiable beams is presented to address this challenge. We also derived two other heuristic candidate beam generation algorithms to compare and contrast performance and robustness characteristics of different algorithmic choices. We tested the performance of our three new approaches on 12 operational instances that vary in user distribution, user numbers, and demand distribution. While the methods performed differently under varying operational scenarios, the column generation‐based methods provided the best trade‐off between computation time and solution quality in most cases. We further tested our two best performing algorithms for scalability. Our column generation‐based methods were able to provide good quality solutions with up to 400 beams and 5,000 users. Our work provides valuable insights for real‐life implementation: an end‐user of our system can select the solution approach based on their business need, computational (time) budget, and the desired solution quality. [ABSTRACT FROM AUTHOR]

Chemotherapy scheduling at cancer treatment centres is a complex problem due to high and growing demand, diversity of treatment protocols, limitations on resources and the need to coordinate treatment session times with laboratory preparation of medication. Over a given planning horizon, treatment centres assign patients first to specific days (interday scheduling) and then to specific times within each day (intraday scheduling), the latter process including the definition of medication preparation time. This paper addresses the intraday scheduling problem using an integer programming model that attempts to schedule all patients assigned to the horizon, and the preparation of the medication to be administered, simultaneously. The linear relaxation of the model formulation, which is based on treatment patterns, is solved using column generation. The proposed approach allows for medication preparation on the day of treatment or a previous day subject to time slot availability. A case study is conducted using actual data from a Chilean cancer centre to compare through simulation the schedules generated by the proposed approach and the centre's manual method. The results show that the proposed approach performs better on makespan, treatment chair occupancy, number of overtime hours and finding solutions at high demand levels. [ABSTRACT FROM AUTHOR]

Simplicial decomposition (SD) of variational inequalities experiences the long-tail convergence property. That is, the equilibrium solution rapidly progresses at first but then tails off, making only a tiny amount of progress per column generation iteration, which is a drawback of SD-VI. In the context of Dantzig-Wolfe of LP, it is reported that the more proposals are used to initialize the algorithm, the faster the solution can be found by reducing the number of decomposition steps. Therefore, I proposed to solve multiple nonlinear column generation (mNCG) subproblems in each SD-VI iteration (SD-VI-mNCG) instead of solving only one subproblem as in SD-VI. Generating multiple column generation subproblem solutions in each SD-VI iteration enabled the corresponding convex hull to be rapidly enlarged. Consequently, the number of SD-VI iterations could be greatly reduced. A transportation network equilibrium problem was used to study the performance of the SD-VI-mNCG.

AbstractAs a new business mode for last-mile logistics services, some instant delivery platforms provide “help me buy” services mainly to satisfy urgent customer demands. Couriers travel to nearby stores, buy commodities requested by the customer, and quickly deliver them to the customer’s location. We investigate how to operate this type of platform to maximize profits. A two-stage stochastic programming model is proposed to determine whether to accept a customer’s order, how to assign accepted orders to couriers, and how to select stores where the commodities are purchased. The proposed model can be applied using a rolling horizon approach and account for the uncertain arrival of future orders in each epoch. Moreover, because the second-stage subproblem involves an integer programming model, a new primal decomposition algorithm is proposed to solve the two-stage model. Extensions are also explored so that our proposed methodology can be applied to more general and realistic platform operations. Numerical experiments based on real data are conducted to test the effectiveness of the proposed algorithm and to derive useful managerial insights for operators of help me buy services. This study indicates the necessity of applying the new decomposition to this new delivery model, considering future orders, and allowing platform collaboration, and determines the benefit of the stochastic solution. In addition, this study reveals the influences of the courier-to-order ratio; response time; distribution and radius of order, courier, and store circles; demand density; and decision frequency. [ABSTRACT FROM AUTHOR]

The commercial and operations planning in airlines has traditionally been a hierarchical process starting with flight schedule design, followed by fleet assignment, aircraft rotation planning and finally the crew scheduling. The hierarchical planning approach has a drawback that the optimal solution for a planning phase higher in hierarchy may either be infeasible for the subsequent phase or may lead to a sub‐optimal overall solution. In this paper, we solve a profit‐maximizing integrated planning model for clean‐sheet "rotated" schedule design with flight re‐time option and crew scheduling for a low‐cost carrier (LCC) in an emerging market. While the aircraft rotation problem has been traditionally modeled in the literature as a daily routing of individual aircraft for maintenance requirement, in this work we address the requirement of planned aircraft rotations as part of schedule design for LCCs. The planned aircraft routing is important in our case to create as many via‐flights as possible due to the underserved nature of the emerging market. We solve this large‐scale integer‐programming problem using two approaches – Benders Decomposition and Lagrangian Relaxation. For Lagrangian Relaxation, we exploit the special structure of our problem and intuitive understanding behind the Lagrangian duals to develop a multiplier adjustment approach to find an improved lower bound of integrated model solution. The crew‐pairing sub‐problem is solved using column generation through multi‐label shortest path algorithm followed by branch‐and‐price for integer solution. We test our solution methodology on a flight universe of 378 unique flights for different problem sizes by varying the number of aircraft available for operations. Our computational results show that within a reasonable run time of few hours both the approaches, Benders Decomposition and Lagrangian Relaxation, are successful in finding lower bounds of the integrated model solution, which are higher than the solution of traditional hierarchical approach by 0.5%–2.5%. We find Lagrangian Relaxation methodology to usually attain an improved solution faster than the Benders Decomposition approach, particularly for large‐scale problems. [ABSTRACT FROM AUTHOR]

Simplicial decomposition (SD) of variational inequalities experiences the long-tail convergence property. That is, the equilibrium solution rapidly progresses at first but then tails off, making only a tiny amount of progress per column generation iteration, which is a drawback of SDVI. In the context of Dantzig-Wolfe of LP, it is reported that the more proposals are used to initialize the algorithm, the faster the solution can be found by reducing the number of decomposition steps. Therefore, I proposed to solve multiple nonlinear column generation (mNCG) subproblems in each SD-VI iteration (SD-VI-mNCG) instead of solving only one subproblem as in SD-VI. Generating multiple column generation subproblem solutions in each SD-VI iteration enabled the corresponding convex hull to be rapidly enlarged. Consequently, the number of SD-VI iterations could be greatly reduced. A transportation network equilibrium problem was used to study the performance of the SDVI-mNCG. [ABSTRACT FROM AUTHOR]

The raw material purchasing (RMP) problem is to determine the purchasing quantities of raw materials in given periods or cycles. Raw material purchasing optimization is crucial for large-scale steel plants because it is closely related to the supply of raw materials and cost savings. The raw material purchasing of large-scale steel enterprises is characterized by many varieties, large quantities, and high costs. The RMP objective is to minimize the total purchasing cost, consisting of the price of raw materials, purchasing set-up costs, and inventory costs, and meet product demand. We present a mixed integer linear programming (MILP) model and a column generation (CG) solution for the resulting optimization problem. The column generation algorithm is the generalization of the branch and bound algorithm while solving the linear programming (LP) relaxation of MILP using column generation (CG), and its advantage is to handle large-sized MILPs. Experimental results show the effectiveness and efficiency of the solution. [ABSTRACT FROM AUTHOR]

We present a new model formulation for a multiproduct dynamic order quantity problem with product returns and a reprocessing option. The optimization considers the limited shelf life of sterile medical devices as well as the capacity constraints of reprocessing and sterilization resources. The time-varying demand is known in advance and must be satisfied by purchasing new medical devices or by reprocessing used and expired devices. The objective is to determine a feasible procurement and reprocessing plan that minimizes the incurred costs. The problem is solved in a heuristic manner in two steps. First, we use a Dantzig-Wolfe reformulation of the underlying problem, and a column generation approach is applied to tighten the lower bound. In the next step, the obtained lower bound is transformed into a feasible solution using CPLEX. Our numerical results illustrate the high solution quality of this approach. The comparison with a simulation based on the first-come-first-served principle shows the advantage of integrated planning. [ABSTRACT FROM AUTHOR]

An algorithm for the two-stage robust optimization surgery-to-operating room allocation problem is presented. The second-stage problem is an integer linear program whose convex hull is approximated using three types of specialized valid inequalities and Chvátal-Gomory cuts. The resulting linear relaxation of the second-stage problem is then dualized and integrated into the first-stage problem. The resulting mixed integer linear program, which is an approximation of the original problem, is then solved using a commercial solver. If the solution of this model is not optimal for the second-stage problem, valid inequalities for the second-stage problem are generated, yielding a type of column-generation based approach that we refer to as the sequential follower refinement (SFR) algorithm. Data from an academic medical center are used to compare the computational performance of SFR with the constraint and column generation (C&CG) algorithm, which is the only exact approach that has been specifically applied for this problem in the literature. An extensive numerical study of SFR and its computational characteristics is presented that shows that SFR yields better-quality solutions compared with C&CG, even as the termination criterion of SFR is met much sooner, especially for problems involving higher number of surgeries. History: Accepted by Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0191) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0191). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

This paper studies a distributionally robust multi-item newsvendor problem, where the demand distribution is unknown but specified with a general event-wise ambiguity set. Using the event-wise affine decision rules, we can obtain a conservative approximation formulation of the problem, which can typically be further reformulated as a linear program. In order to efficiently solve the resulting large-scale linear program, we develop a column generation-based decomposition scheme and speed up the computational efficiency by exploiting a special column selection strategy and stopping early based on a Karush-Kuhn-Tucker condition test. Focusing on the Wasserstein ambiguity set and the event-wise mean absolute deviation set, a computational study demonstrates both the computational efficiency of the proposed algorithm, which significantly outperforms a commercial solver and a Benders decomposition method, and the out-of-sample superiority of distributionally robust solutions relative to their sample average approximation counterparts. History: Accepted by Nicola Secomandi, Area Editor for Stochastic Models & Reinforcement Learning. Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada [492997-2016, RGPIN-2016-05208], the National Natural Science Foundation of China [71972012], Alliance de recherche numérique du Canada, and Canada Research Chairs [CRC-2018-00105]. It was also supported by Groupe d'études et de recherche en analyse des décisions (GERAD). Finally, this research was enabled in part by support provided by Digital Research Alliance of Canada (https://alliancecan.ca/en). Supplemental Material: The software that supports the findings of this study is available within the paper and its supplemental information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0010) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0010). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Some airlines use the preferential bidding system to construct the schedules of their pilots. In this system, the pilots bid on the different activities and the schedules that lexicographically maximize the scores of the pilots according to their seniority are selected. A sequential approach to solve this maximization problem is natural: The problem is first solved with the bids of the most senior pilot, and then it is solved with those of the second most senior without decreasing the score of the most senior, and so on. The literature admits that the structure of the problem somehow imposes such an approach. The problem can be modeled as an integer linear lexicographic program. We propose a new efficient method, which relies on column generation for solving its continuous relaxation and returns proven optimality gaps. To design this column generation, we prove that bounded linear lexicographic programs admit "primal-dual" feasible bases, and we show how to compute such bases efficiently. Another contribution on which our method relies is the extension of standard tools for resource-constrained longest path problems to their lexicographic versions. This is useful in our context because the generation of new columns is modeled as a lexicographic resource-constrained longest path problem. Numerical experiments show that this new method is already able to solve to proven optimality industrial instances provided by Air France, with up to 150 pilots. By adding a last ingredient in the resolution of the longest path problems, which exploits the specificity of the preferential bidding system, the method achieves for these instances computational times that are compatible with operational constraints. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0372. [ABSTRACT FROM AUTHOR]

Binary matrix factorization is an essential tool for identifying discrete patterns in binary data. In this paper, we consider the rank-k binary matrix factorization problem (k-BMF) under Boolean arithmetic: we are given an n × m binary matrix X with possibly missing entries and need to find two binary matrices A and B of dimension n × k and k × m, respectively, which minimize the distance between X and the Boolean product of A and B in the squared Frobenius distance. We present a compact and two exponential size integer programs (IPs) for k-BMF and show that the compact IP has a weak linear programming (LP) relaxation, whereas the exponential size IPs have a stronger equivalent LP relaxation. We introduce a new objective function, which differs from the traditional squared Frobenius objective in attributing a weight to zero entries of the input matrix that is proportional to the number of times the zero is erroneously covered in a rank-k factorization. For one of the exponential size Ips, we describe a computational approach based on column generation. Experimental results on synthetic and real-world data sets suggest that our integer programming approach is competitive against available methods for k-BMF and provides accurate low-error factorizations. Funding: O. Günlük was partially supported by the Office of Naval Research [Grant N00014-21-1-2575]. R. Á. Kovács was supported by a doctoral scholarship from The Alan Turing Institute under the EPSRC [Grant EP/N510129/1] and the Office for National Statistics. R. A. Hauser was supported by The Alan Turing Institute under the EPSRC [Grant EP/N510129/1]. [ABSTRACT FROM AUTHOR]

This paper introduces a multiple container loading problem with practical constraints and loading situations at several docks. In the real world, items may be stored on several loading docks in the depot. So, to pack items stored on a dock, it may be necessary to move or reload the items loaded into the container at the previous docks. We present a realistic definition of reloading conditions and design a temporary loading pattern for each dock to reduce the reloading effort. We propose a column generation‐based heuristic algorithm that uses a tree search to solve the subproblem. The proposed algorithm can solve benchmark instances with one loading dock with only a 1.3% deviation from the literature's best results. It can also solve real‐world instances with several loading docks in reasonable running times and reduce the total cost by 21.6%, compared to the case where only one loading dock is considered. [ABSTRACT FROM AUTHOR]

Customized bus systems can improve service quality and efficiency by taking advantage of the speed regulation and capacity variation of autonomous bus systems. To address the challenges of customized bus systems design, this study proposes a collaborative optimization model of vehicle scheduling and speed regulation for the autonomous customized bus system. This model minimizes enterprise operation and passenger travel costs by considering mileage constraints, the time window of passenger travel constraints, and demand pairs coverage constraints. Based on the theoretical properties discovered in the joint design model, the problem is decomposed into a set partitioning master problem and route-selection subproblem. An algorithm combining column generation approach and genetic algorithm is proposed to solve the joint design model. To accelerate the calculation in searching for the shortest route for subproblems, hierarchical filtering strategy is used to reduce the cost of finding feasible routes and improve computational efficiency. The case study reveals that the proposed algorithm exhibits better convergence and stability according to the Wilcoxon test. In a numerical experiment with 100 demand pairs, the joint model can be solved by the algorithm proposed in the study optimally with 19% of the computation time required by the exact algorithms. The departure frequency was reduced by 22%, and the operating cost was reduced by 42% compared with those of customized bus lines serviced separately by human-driven buses. Sensitivity analyses were performed on various operating parameters, such as modular bus capacity and speed boundary, across three different scale cases. The results demonstrate that reasonable parameter settings are beneficial for reducing operating costs and vacant seats. • A collaborative optimization model of bus scheduling and speed regulation is proposed. • An algorithm combining column generation and genetic algorithm is proposed. • Hierarchical filtering strategy is used in the subproblem of the proposed algorithm. • An autonomous customized bus system can reduce corporate costs compared to human-driven buses. [ABSTRACT FROM AUTHOR]

We present an innovative extension of the Set Covering Problem, transitioning from a traditional radial covering to an angular covering structure. The decisions are based on locating the facilities and identifying the directional servers installed in each, covering a set of points in a geographic area. The strategic placement of surveillance cameras inspired this novel approach. We aim to minimize the cost of covering demand points by strategically installing directional servers on facilities. We propose an integer linear model and an initial approach based on column generation decomposition. We conducted extensive computational experiments on different test instances, including a practical case study involving positioning security cameras for surveillance in Valparaíso, Chile. The results highlight the effectiveness of column generation in achieving optimal solutions or significantly improving solution quality compared with solving the model directly with standard optimization solvers, especially for larger instances. In particular, the column generation algorithm achieves up to a 67% improvement in solution quality compared to the optimization model for real-world size instances, demonstrating its practical applicability and potential for enhancing surveillance infrastructure design.

In this paper, we address the electric vehicle routing problem with time windows and propose two branch-and-price-and-cut methods based on a column generation algorithm. One is an exact algorithm whereas the other is a heuristic method. The pricing sub-problem of the column generation method is solved using a label correcting algorithm. The algorithms are strengthened with the state-of-the-art acceleration techniques and a set of valid inequalities. The acceleration techniques include: (i) an intermediate column pool to prevent solving the pricing sub-problem at each iteration, (ii) a label correcting method employing the ng-route algorithm adopted to our problem, (iii) a bidirectional search mechanism in which both forward and backward labels are created, (iv) a procedure for dynamically eliminating arcs that connect customers to remote stations from the network during the path generation, (v) a bounding procedure providing early elimination of sub-optimal routes, and (vi) an integer programming model that generates upper bounds. Numerical experiments are conducted using a benchmark data set to compare the performances of the algorithms. The results favour the heuristic algorithm in terms of both the computational time and the number of instances solved. Moreover, the heuristic algorithm is shown to be specifically effective for larger instances. Both algorithms introduce a number of new solutions to the literature. [ABSTRACT FROM AUTHOR]

Travel times in real-world transportation networks are affected by many disruptions. When we conduct the network design optimization, the traffic condition and its resulting travel time variability should be taken into account. However, most of the previous network design optimizations adopted the lengths or expected travel times of links. Based on travel time means and standard deviations, we develop an arc-based model that is a nonlinear and concave integer program. By the Dantzig-Wolfe reformulation, we transform it into an equivalent column-based model that is an integer linear program with a large number of variables. Based on the column-based model, we develop a hybrid method based on column generation and Lagrangian relaxation. The restricted master problem can be settled by the linear programming solvers. The pricing subproblems incorporate independent reliable shortest path problems and a knapsack problem. In numerical experiments, the proposed method can generate feasible solutions with good integrality gaps. [ABSTRACT FROM AUTHOR]

This paper considers the scheduling of electric vehicles in a public transit system. Our main innovation is that we take into account that charging stations have limited capacity, while also considering partial charging. To solve the problem, we expand a connection-based network in order to track the state of charge of vehicles and model recharging actions. We then formulate the electric vehicle scheduling problem as a path-based binary program, whose linear relaxation we solve using column generation. We find integer feasible solutions using two heuristics: price-and-branch and a diving heuristic, including acceleration strategies. We test the approach using data from the concession Gooi en Vechtstreek in the Netherlands, containing up to 816 trips. The diving heuristic outperforms the other heuristic and solves the entire concession within seven hours of computation time with an optimality gap of less than 3%. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0253. [ABSTRACT FROM AUTHOR]

A line replaceable unit (LRU) is a collection of connected parts in a system that is replaced when any part of the LRU fails. Companies use LRUs as a mechanism to reduce downtime of systems following a failure. The design of LRUs determines how fast a replacement is performed, so a smart design reduces replacement and downtime cost. A firm must purchase/repair a LRU upon failure, and large LRUs are more expensive to purchase/repair. Hence, a firm seeks to design LRUs such that the average costs per time unit are minimized. We formalize this problem in a new model that captures how parts in a system are connected, and how they are disassembled from the system. Our model optimizes the design of LRUs such that the replacement (and downtime) costs and LRU purchase/repair costs are minimized. We present a set partitioning formulation for which we prove a rare result: the optimal solution is integer, despite a nonintegral feasible polyhedron. Second, we formulate our problem as a binary linear program (BLP). The article concludes by numerically comparing the computation times of both formulations and illustrates the effects of various parameters on the model's outcome. [ABSTRACT FROM AUTHOR]

Many routing and scheduling problems are modeled through variables that represent paths (routes, schedules, etc.). For such extensive formulations, branch-price-and-cut (BPC) algorithms nowadays constitute the leading exact solution technique, and most of the time, the pricing problem is a shortest-path problem with resource constraints that can be solved by a dynamic-programming labeling algorithm. For this setting, variable fixing techniques based on the reduced costs of the paths have been proposed with the aim of eliminating arcs from the underlying network and speeding up the solution process of the pricing problem as well as of the overall BPC algorithm. For an efficient variable fixation, bidirectional labeling must be possible. We move one step forward and show how the reduced costs of paths can also be exploited to reduce the resource windows for many types of resources, including the time resource and a load-related resource. This can be achieved without modifying the pricing problem network and altering the structure of the pricing problem itself. Moreover, different resources can be considered simultaneously. A straightforward reduction of the resource windows associated with the vertices of the network can tighten them, but this reduction does not translate into savings in computation times. On the contrary, the reduction of the resource windows is effective when distinct forward and backward resource windows are defined for each arc and reduced independently based on the traversal direction of the arc itself. Moreover, an arc can be eliminated when one of its arc-specific resource windows becomes empty, and the explicit use of variable fixing techniques can be avoided. Computational results obtained for benchmark instances of the vehicle-routing problem with time windows show that the overall computation times of the BPC algorithm can be significantly reduced compared with a fully fledged BPC algorithm using variable fixing techniques. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This research was supported by the Deutsche Forschungsgemeinschaft (DFG) [Grants GS 83/1-1 and IR 122/10-1] of Project 418727865. This support is gratefully acknowledged. [ABSTRACT FROM AUTHOR]

In this article, we propose extensions of the general mean-risk portfolio selection models to limit the spillover effect of risk. We use the conditional value at risk (CoVaR) as a measure to identify the spillover risk contribution of securities. The goal is to find a portfolio that minimizes general risk measures while the spillover risk contribution is limited. Based on the frameworks of the general mean-risk models, we additionally guarantee that a portfolio has limited spillover risk contributions. To solve these problems efficiently, we propose a Dantzig-Wolfe decomposition reformulation that yields a strong continuous relaxation bound by introducing a set of feasible investment patterns. We develop an algorithm that incorporates a column generation procedure to reduce the spillover effect of tail risk in subproblems. Finally, we present the performance of the portfolios using real historical data. The results show that our model can provide better portfolios than the general mean-risk models. [ABSTRACT FROM AUTHOR]

In the era of e-commerce, a new business mode—e-grocery platform has become popular in recent years. An e-grocery platform need not own and operate shops. The platform assigns the orders that customers release on the platform to the part-time couriers; then the couriers go to some nearby shops, buy the commodities required by orders, and deliver them to the orders' shipping address. This study proposes a mathematical model on selecting and accepting customer orders, assigning the accepted orders to couriers, selecting shops for buying each order's required commodities, and routing each courier among her/his visited shops and assigned order's shipping address. Moreover, the uncertain arrivals of future orders is taken into account by the proposed model. For solving the proposed two-stage stochastic integer programming model with the integer recourse function, this study also designs a novel algorithm based on column generation. Based on the real data from platform operators in Shanghai and Hangzhou, numerical experiments are conducted to validate the efficiency of the proposed algorithm. Sensitivity analysis based on the real data are also conducted to derive potentially useful managerial implications for practitioners who operate third-party e-grocery platforms. [ABSTRACT FROM AUTHOR]

Transshipment yards are not usually considered in optimization approaches proposed for solving the log transportation problem. However, they may provide substantive advantages with respect to the usual logistics practice of direct delivering from supply forests to mills. Therefore, this paper evaluates, at the operational level, different supply chain topologies with the purpose of assessing potential costs savings associated to the use of intermediate storage facilities. The researched problem is defined by stated sets of log-suppliers, storage and transshipment yards, and facilities demanding several types of logs over a known planning horizon. The optimal transportation and inventory plan must be found. An optimization algorithm based on Column Generation + GRASP pricing metaheuristic was developed to compute minimal operation costs associated to different supply-chain topologies over a bank of instances generated from realistic information of the forestry activity in the Argentinean province of Misiones. [ABSTRACT FROM AUTHOR]

The technician routing and scheduling problem (TRSP) optimizes routes for technicians serving tasks subject to qualifications, time constraints, and routing costs. In the literature, the TRSP is solved either to provide actual technician work schedules or to perform what‐if analyses on different TRSP scenarios. A TRSP scenario consists of a given number of tasks, technicians, skills, working hours and so forth. We present a method which builds optimal TRSP scenarios with respect to technician fleet, their skills, their working hours and digitization of task equipment. The scenarios are built such that the combined TRSP costs (OPEX) and investment costs (CAPEX) are minimized. By using a holistic approach we can generate scenarios that would not have been found by studying the investments individually. The proposed method consists of a matheuristic based on column generation. To reduce computational time, the routing costs of a technician are estimated instead of solved to optimality. The proposed method is evaluated on data from the literature and on real‐life data from a telecommunication company. The evaluation shows that the proposed method successfully suggests attractive scenarios. The method especially excels in ensuring that more tasks are serviced, but also in reducing travel time with around 16% in the real‐life instance. We believe that the proposed method could constitute an important strategic tool for routing companies. In the conclusion, we propose future research directions to extend the applicability. [ABSTRACT FROM AUTHOR]

Demographic changes, urbanization and increasing vehicle ownership at unprecedented rates put a lot of strain on cities particularly on urban mobility and transportation and overwhelm transportation network infrastructures and current transportation systems, which are not built to cope with such a fast increasing demand. Traffic congestion is considered as the most difficult challenge to tackle for sustainable urban mobility and is aggravated by the increased freight activity due to e-commerce and on-demand delivery and the explosive growth in transportation network companies and ride-hailing services. There is a need to implement a combination of policies to ensure that increased urban traffic congestion does not lower the quality of life and threaten global climate and human health and to prevent further economic losses. This study aims to contribute to the United Nations (UN) climate action and sustainable development goals in tackling recurring traffic congestion problem in urban areas to achieve a sustainable urban mobility in that it offers a solution methodology for traffic assignment problem. We introduce an exact generalized solution methodology based on reformulation of existing traffic assignment problems as a second order cone programming (SOCP) problem and propose column generation (CG) and cutting plane (CP) algorithms to solve the problem effectively for large scale road network instances. We conduct numerical experiments to test the performance of the proposed algorithms on realistic road networks. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of data routing in backhaul networks using Unmanned Aerial Vehicles (UAVs) to relay data from Small Cells (SCs) to the core network. The objective is to maximize the total fulfilled demand of data to be routed, while ensuring technical requirements such as hop constraints and edge capacity. The problem is formulated using a compact mixed-integer programming model, which can solve small- and medium-sized topologies. In addition, a fast constructive heuristic based on a maximal tree is developed to solve large-scale topologies, resulting in a significant reduction in CPU time. The quality of the heuristic is evaluated by using column generation for solving the linear programming relaxation of an exponential formulation. The computational study shows the effectiveness and value of the proposed compact model and constructive heuristic for various topology sizes. Furthermore, experiments demonstrate that by keeping the network setup constant and updating the demand vector only, the computational time of the compact model can be drastically reduced for all topology sizes. [ABSTRACT FROM AUTHOR]

This research looks at the production planning of hollow-core slabs integrated to the optimisation problem of the use of moulds. Considering the production process of these structures, two mathematical models are proposed for the arising problem, which consists of a one-dimensional multi-period cutting stock problem with innovative aspects regarding the multiple manufacturing modes that can be used to produce the slabs. In addition, a theoretical analysis of the proposed models is presented. These models are solved using heuristic methods, both aiming to minimise production and inventory costs. Using data based on real information provided by a company, the computational results showed that the heuristic based on the compact model performed better than the one based on the extended model, due to some characteristics specific to the problem being studied. [ABSTRACT FROM AUTHOR]

This paper deals with the Generalised Workforce Scheduling and Routing Problem (GWSRP) where 9 temporal constraints ensuring visit dependencies are all together taken into account and where customer and worker's quality of service are taken into consideration. A Constraint-Programming based Decomposition Method (CPDM) is proposed, firstly based on a relaxation of coordination constraints and a column generation, and secondly with an iterative insertion of coordination constraint by constraint programming solver. Numerical experiments are achieved on huge instances derived from WSRP benchmark instances with up to 177 customers, 59 vehicles and coordination constraints. The CPDM is able to find nearly optimal solution for medium-size instances and find high-quality solution for huge-size instances whereas CPLEX solver applied to a mixed integer linear model is not able to give a solution in this case. [ABSTRACT FROM AUTHOR]

This study investigates a variant of the Vehicle Routing Problem (VRP) for customized on-demand bus service platforms. In this problem, the platform plans customized bus routes upon receiving a batch of orders released by passengers and informs the passengers of the planned pick-up and drop-off locations. The related decision process takes into account some passenger-side time window-related requirements, walking limits, the availability and capacities of various types of buses. A mixed-integer linear programming model of this new VRP variant with floating targets (passengers) is formulated. To solve the model efficiently, a solution method is developed that combines the branch-and-bound and column generation algorithms and also includes embedded acceleration techniques such as the multi-labeling algorithm. Experiments based on real data from Dalian, China are conducted to validate the effectiveness of the proposed model and efficiency of the algorithm; the small-scale experimental results demonstrate our algorithm can obtain optimal results in the majority of instances. Additionally, sensitivity analysis is conducted, and model extensions are investigated, to provide customized bus service platform operators with potentially useful managerial insights; for example, a platform need not establish as many candidate stops as possible, a wide range of walking distance may not bring early arrival at destinations for customers, more mini-buses should be deployed than large buses in our real-world case. Moreover, the rolling horizon-based context and zoning strategies are also investigated by extending our proposed methodology. [ABSTRACT FROM AUTHOR]