Article
Computer Science, Interdisciplinary Applications
Katrin Hessler, Stefan Irnich
Summary: This study considers the exact solution to the basic version of the multiple-compartment vehicle-routing problem. It focuses on clustering customers, routing vehicles, and packing customer demand into compartments. The objective is to minimize the total length of all vehicle routes. The study compares different labeling approaches for solving the shortest-path subproblem, finding that partial dominance performs better than standard labeling.
INFORMS JOURNAL ON COMPUTING
(2023)
Article
Operations Research & Management Science
Ruslan Sadykov, Eduardo Uchoa, Artur Pessoa
Summary: In this study, a new variant of bidirectional label-correcting algorithm is proposed for the vehicle routing problem, which uses bucket graph to store and extend labels, reducing dominance checks and algorithm running time significantly, especially beneficial for large vehicle capacity and time window constraints. Experiments showed significant improvements over the best algorithms in literature on instances such as distance-constrained vehicle routing and heterogeneous fleet vehicle routing, with many instances being solved for the first time.
TRANSPORTATION SCIENCE
(2021)
Article
Economics
Weibo Yang, Liangjun Ke, David Z. W. Wang, Jasmine Siu Lee Lam
Summary: This paper investigates the new variant of vehicle routing problem - VRPRD, aiming to minimize the total routing and weighted tardiness costs. By developing a new algorithm, the exact optimal solutions for over 75% of benchmark instances can be obtained within a short period of time.
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW
(2021)
Article
Computer Science, Theory & Methods
Jiayu Liu, Huaxi Gu, Wenting Wei, Ziqi Chen, Yawen Chen
Summary: Reconfigurable units like FPGAs are widely used as high-performance hardware accelerators to address power bottleneck in current multi-core processors. This study introduces a new routing algorithm called the Shortest Cycle Routing Algorithm to improve the computation efficiency of standard BFS for inter-accelerator communications. The algorithm reduces the time and space complexities for searching the shortest cycles of an acceleration task from O(n(k)) to O(1), highlighting the benefits of locality and path diversity for adaptive routing strategies.
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE
(2021)
Article
Transportation Science & Technology
Dario Bezzi, Alberto Ceselli, Giovanni Righini
Summary: This article presents a variant of the electric vehicle routing problem, where a fleet of identical vehicles with limited capacity needs to visit customers with given demands. The vehicles have limited autonomy and may need to recharge en-route at stations offering different recharge technologies. The article introduces a new branch-and-price algorithm that outperforms previous methods from the literature and is capable of solving instances with up to 30 customers, 5 stations, 7 vehicles, and 3 technologies within a few minutes on a standard PC.
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES
(2023)
Article
Operations Research & Management Science
Julia Wahlen, Timo Gschwind
Summary: The order batching problem in warehousing involves designing picking batches for customer orders, with the goal of assigning each order to exactly one batch, satisfying capacity restrictions, and minimizing the overall distance traveled by pickers. A branch-price-and-cut algorithm is proposed for exact solution, considering different routing strategies and incorporating resource constraints. The algorithm is significantly more efficient than previous methods and provides high-quality solutions.
TRANSPORTATION SCIENCE
(2023)
Article
Transportation Science & Technology
Wenqi Gao, Zhixing Luo, Houcai Shen
Summary: In this study, an exact branch-and-price-and-cut algorithm is proposed to solve the time-dependent pollution routing problem. The algorithm tackles the route selection problem and the time-dependent elementary shortest path problem to find the optimal solution. Compared to a commercial solver, the algorithm shows better performance and finds optimal solutions for more instances in less time.
TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES
(2023)
Article
Management
Borzou Rostami, Guy Desaulniers, Fausto Errico, Andrea Lodi
Summary: This paper discusses a variant of the capacitated vehicle routing problem where travel times are uncertain and statistically correlated. By adopting a mean-variance approach, the aim is to plan reliable vehicle routes by penalizing routes with high travel time variability to reduce time variability.
OPERATIONS RESEARCH
(2021)
Article
Economics
Junyoung Kim, Byungju Goo, Youngjoo Roh, Chungmok Lee, Kyungsik Lee
Summary: The airport gate assignment problem aims to efficiently allocate gates to flights, taking into account unpredictable factors such as air traffic demands and weather conditions. A robust gate assignment plan is crucial for airport operators to handle flight schedule deviations effectively.
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL
(2023)
Article
Computer Science, Interdisciplinary Applications
Roberto Bargetto, Thierry Garaix, Xiaolan Xie
Summary: This paper addresses an integrated operating room planning and scheduling problem with various constraints commonly encountered in practice. A new model is proposed for the sequence-dependent operating room cleaning times caused by surgeries with different infection levels. A branch-and-price-and-cut algorithm based on the time-indexed formulation is devised to solve the problem.
COMPUTERS & OPERATIONS RESEARCH
(2023)
Article
Management
Xiangyi Zhang, Lu Chen, Michel Gendreau, Andre Langevin
Summary: In this study, a branch-and-cut algorithm is developed for the vehicle routing problem with two-dimensional loading constraints. The algorithm is shown to be competitive through experimental results, and extensive computational analysis is conducted to investigate the impact of different factors on the algorithm.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Operations Research & Management Science
Timo Hintsch, Stefan Irnich, Lone Kiilerich
Summary: SoftCluCARP is a variant of the capacitated arc-routing problem that involves partitioning streets into clusters. The branch-price-and-cut algorithm is designed to solve SoftCluCARP by using metaheuristic and branch-and-cut-based solvers for the column-generation subproblem, resulting in an effective and accurate solution approach.
TRANSPORTATION SCIENCE
(2021)
Article
Engineering, Multidisciplinary
Akang Wang, Anirudh Subramanyam, Chrysanthos E. Gounaris
Summary: This paper discusses the integration of branch-price-and-cut solvers with the robust optimization paradigm to address parametric uncertainty in vehicle routing problems. It proposes a novel approach that combines cutting-plane techniques with an advanced branch-price-and-cut algorithm to ensure complete robust feasibility against demand and travel time uncertainty. This approach is both modular and versatile, allowing the use of advanced branch-price-and-cut technologies without major modifications.
OPTIMIZATION AND ENGINEERING
(2022)
Article
Engineering, Industrial
Negin Enayaty Ahangar, Kelly M. Sullivan, Shantih M. Spanton, Yu Wang
Summary: Rail yards are critical for freight rail transportation, and finding the shortest route for moving connected cuts of rail cars in congested yards is important. We propose theory and algorithms for the Single-Cut Routing Problem (SCRP) in rail yards, which is different from traditional shortest path problems due to space occupation and track geometry restrictions. We prove the NP-completeness of a related problem and demonstrate its polynomial solvability for Bounded Cycle Length (BCL) yard networks. We formalize a two-stage algorithm for BCL yard networks and validate it using data from CSX Transportation.
Article
Engineering, Industrial
Ece Naz Duman, Duygu Tas, Bulent Catay
Summary: This paper addresses the electric vehicle routing problem with time windows and proposes two methods based on a column generation algorithm. Experimental results indicate that the heuristic algorithm outperforms the exact algorithm in terms of computational time and number of instances solved, especially for larger instances. Both algorithms introduce new solutions to the literature.
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
(2022)
Article
Computer Science, Hardware & Architecture
Maximilian Loeffler, Guy Desaulniers, Stefan Irnich, Michael Schneider
Article
Operations Research & Management Science
Guy Desaulniers, Timo Gschwind, Stefan Irnich
TRANSPORTATION SCIENCE
(2020)
Article
Mathematics, Applied
Nicola Bianchessi, Stefan Irnich, Christian Tilk
Summary: This study discusses variants of the Multiple Vehicle Traveling Purchaser Problem (MVTPP), introduces a branch-price-and-cut algorithm, proposes a new branching rule and valid inequalities, and demonstrates how to handle product incompatibilities. Experimental results show that the new approach is highly competitive.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Mathematics, Applied
Katrin Hessler, Stefan Irnich
Summary: The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem, with a novel symmetric formulation and an asymmetric sub-model for clustering. A branch-and-cut algorithm is used to solve the new model, with problem-specific cutting planes and separation procedures introduced. Computational results show that the algorithm can now solve several previously open instances to proven optimality.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Computer Science, Interdisciplinary Applications
Timo Hintsch
Summary: The paper introduces a large multiple neighborhood search algorithm for the SoftCluVRP, utilizing various cluster destroy and repair operators and two post optimization components. Computational experiments demonstrate that the algorithm outperforms existing heuristic approaches and provides 130 new best solutions for medium-sized instances.
COMPUTERS & OPERATIONS RESEARCH
(2021)
Article
Operations Research & Management Science
Timo Hintsch, Stefan Irnich, Lone Kiilerich
Summary: SoftCluCARP is a variant of the capacitated arc-routing problem that involves partitioning streets into clusters. The branch-price-and-cut algorithm is designed to solve SoftCluCARP by using metaheuristic and branch-and-cut-based solvers for the column-generation subproblem, resulting in an effective and accurate solution approach.
TRANSPORTATION SCIENCE
(2021)
Article
Operations Research & Management Science
Katrin Hessler, Stefan Irnich, Tobias Kreiter, Ulrich Pferschy
Summary: This study tackles a packing problem in the food and beverage industry direct-shipping system, focusing on optimizing truck utilization while considering different product categories and constraints. The authors propose a heuristic and an exact solution approach, demonstrating the applicability through computational results on real-world and difficult instances.
Article
Operations Research & Management Science
Christian Tilk, Katharina Olkis, Stefan Irnich
Summary: The ongoing rise in e-commerce has increased the number of first-time delivery failures, resulting in rework and impacting carriers' delivery costs. A new vehicle routing problem with delivery options (VRPDO) is introduced to minimize costs and reach a specified service level based on customer preferences, with a focus on respecting capacities when assigning shipments. A new branch-price-and-cut algorithm is presented for solving the VRPDO and optimal solutions are provided for instances with up to 100 delivery options.
Article
Operations Research & Management Science
Katrin Hessler, Stefan Irnich
Summary: This article presents a study on the dynamic programming algorithm for optimal picker routing, which has linear complexity in the number of aisles. The algorithm is linear in solving the dynamic programming problem, but computing the cost coefficients requires considering all picking positions.
OPERATIONS RESEARCH LETTERS
(2022)
Article
Operations Research & Management Science
Jeanette Schmidt, Stefan Irnich
Summary: The generalized traveling salesman problem (GTSP) aims to find a minimum-cost cycle in a given graph that contains exactly one vertex from each cluster. This study introduces three new GTSP neighborhoods that allow for simultaneous permutation of cluster sequence and vertex selection. These neighborhoods, along with existing ones from literature, are combined to form an effective iterated local search (ILS) algorithm for GTSP. Computational experiments on standard GTSP libraries demonstrate that the ILS algorithm, with some refinements, can compete with state-of-the-art GTSP algorithms.
EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION
(2022)
Article
Mathematics, Applied
Laura Korbacher, Stefan Irnich, John Martinovic, Nico Strasdat
Summary: The skiving stock problem is a counterpart of the cutting stock problem and has become an independent branch of research in the operations research (OR) community. A graph-theoretic approach called the reflect arc-flow model has shown promising results in solving specific skiving stock instances. However, there are still challenging benchmark instances that current formulations cannot solve. In this study, a new approach based on sparse graphs and a stabilized column-generation approach is proposed, which demonstrates optimal solutions for previously unsolved benchmark instances.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Computer Science, Interdisciplinary Applications
Katrin Hessler, Stefan Irnich
Summary: This study considers the exact solution to the basic version of the multiple-compartment vehicle-routing problem. It focuses on clustering customers, routing vehicles, and packing customer demand into compartments. The objective is to minimize the total length of all vehicle routes. The study compares different labeling approaches for solving the shortest-path subproblem, finding that partial dominance performs better than standard labeling.
INFORMS JOURNAL ON COMPUTING
(2023)
Article
Computer Science, Interdisciplinary Applications
Nicola Bianchessi, Timo Gschwind, Stefan Irnichb
Summary: Many routing and scheduling problems are solved using branch-price-and-cut (BPC) algorithms, which involve variable fixing techniques to improve efficiency. Reduction of resource windows based on traversal direction can further enhance the solution process.
INFORMS JOURNAL ON COMPUTING
(2023)
Article
Computer Science, Interdisciplinary Applications
Timo Gschwind, Stefan Irnich, Fabio Furini, Roberto Wolfler Calvo
Summary: The article explores the family of problems related to partitioning and covering graphs with a minimum number of relaxed cliques, with applications in various fields. A unified framework based on branch-and-price techniques is proposed, with new pricing algorithms and branching schemes developed. Comparative studies demonstrate the effectiveness of the framework and the validity of the approach in social network instances.
INFORMS JOURNAL ON COMPUTING
(2021)
Review
Management
Vinicius N. Motta, Miguel F. Anjos, Michel Gendreau
Summary: This survey presents a review of optimization approaches for the integration of demand response in power systems planning and highlights important future research directions.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Philipp Schulze, Armin Scholl, Rico Walter
Summary: This paper proposes an improved branch-and-bound algorithm, R-SALSA, for solving the simple assembly line balancing problem, which performs well in balancing workloads and providing initial solutions.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Roshan Mahes, Michel Mandjes, Marko Boon, Peter Taylor
Summary: This paper discusses appointment scheduling and presents a phase-type-based approach to handle variations in service times. Numerical experiments with dynamic scheduling demonstrate the benefits of rescheduling.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Oleg S. Pianykh, Sebastian Perez, Chengzhao Richard Zhang
Summary: Efficient scheduling is crucial for optimizing resource allocation and system performance. This study focuses on critical utilization and efficient scheduling in discrete scheduling systems, and compares the results with classical queueing theory.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Review
Management
Hamed Jahani, Babak Abbasi, Jiuh-Biing Sheu, Walid Klibi
Summary: Supply chain network design is a large and growing area of research. This study comprehensively surveys and analyzes articles published from 2008 to 2021 to detect and report financial perspectives in SCND models. The study also identifies research gaps and offers future research directions.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Patrick Healy, Nicolas Jozefowiez, Pierre Laroche, Franc Marchetti, Sebastien Martin, Zsuzsanna Roka
Summary: The Connected Max-k-Cut Problem is an extension of the well-known Max-Cut Problem, where the objective is to partition a graph into k connected subgraphs by maximizing the cost of inter-partition edges. The researchers propose a new integer linear program and a branch-and-cut algorithm for this problem, and also use graph isomorphism to structure the instances and facilitate their resolution. Extensive computational experiments show that, if k > 2, their approach outperforms existing algorithms in terms of quality.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Victor J. Espana, Juan Aparicio, Xavier Barber, Miriam Esteve
Summary: This paper introduces a new methodology based on the machine learning technique MARS for estimating production functions that satisfy classical production theory axioms. The new approach overcomes the overfitting problem of DEA through generalized cross-validation and demonstrates better performance in reducing mean squared error and bias compared to DEA and C2NLS methods.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Stefano Nasini, Rabia Nessah
Summary: In this paper, the authors investigate the impact of time flexibility in job scheduling, showing that it can significantly affect operators' ability to solve the problem efficiently. They propose a new methodology based on convex quadratic programming approaches that allows for optimal solutions in large-scale instances.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Zhiqiang Liao, Sheng Dai, Timo Kuosmanen
Summary: Nonparametric regression subject to convexity or concavity constraints is gaining popularity in various fields. The conventional convex regression method often suffers from overfitting and outliers. This paper proposes the convex support vector regression method to address these issues and demonstrates its advantages in prediction accuracy and robustness through numerical experiments.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Kuo-Hao Chang, Ying-Zheng Wu, Wen-Ray Su, Lee-Yaw Lin
Summary: The damage and destruction caused by earthquakes necessitates the evacuation of affected populations. Simulation models, such as the Stochastic Pedestrian Cell Transmission Model (SPCTM), can be utilized to enhance disaster and evacuation management. The analysis of SPCTM provides insights for government officials to formulate effective evacuation strategies.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Qinghua Wu, Mu He, Jin-Kao Hao, Yongliang Lu
Summary: This paper studies a variant of the orienteering problem known as the clustered orienteering problem. In this problem, customers are grouped into clusters and a profit is associated with each cluster, collected only when all customers in the cluster are served. The proposed evolutionary algorithm, incorporating a backbone-based crossover operator and a destroy-and-repair mutation operator, outperforms existing algorithms on benchmark instances and sets new records on some instances. It also demonstrates scalability on large instances and has shown superiority over three state-of-the-art COP algorithms. The algorithm is also successfully applied to a dynamic version of the COP considering stochastic travel time.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Bjorn Bokelmann, Stefan Lessmann
Summary: Estimating treatment effects is an important task for data analysts, and uplift models provide support for efficient allocation of treatments. However, evaluating uplift models is challenging due to variance issues. This paper theoretically analyzes the variance of uplift evaluation metrics, proposes variance reduction methods based on statistical adjustment, and demonstrates their benefits on simulated and real-world data.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Congzheng Liu, Wenqi Zhu
Summary: This paper proposes a feature-based non-parametric approach to minimizing the conditional value-at-risk in the newsvendor problem. The method is able to handle both linear and nonlinear profits without prior knowledge of the demand distribution. Results from numerical and real-life experiments demonstrate the robustness and effectiveness of the approach.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Laszlo Csato
Summary: This paper compares the performance of the eigenvalue method and the row geometric mean as two weighting procedures. Through numerical experiments, it is found that the priorities derived from the two eigenvectors in the eigenvalue method do not always agree, while the row geometric mean serves as a compromise between them.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Guowei Dou, Tsan-Ming Choi
Summary: This study investigates the impact of channel relationships between manufacturers on government policies and explores the effectiveness of positive incentives versus taxes in increasing social welfare. The findings suggest that competition may be more effective in improving sustainability and social welfare. Additionally, government incentives for green technology may not necessarily enhance sustainability.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)