Endüstri Mühendisliği Bölümü Koleksiyonu

Permanent URI for this collectionhttps://hdl.handle.net/20.500.11779/1942

Browse

Filters

2023 - 20263

Settings

Start date: 2023WoS Q: search.filters.wosQuartile.Q2

Search Results

Now showing 1 - 3 of 3
  • Article
    A Comparative Study of Branch-And Algorithms for Vehicle Routing With Time Windows and Waiting Time Costs
    (Wiley, 2026-02-09) Michelini, Stefano; Kucukaydin, Hande; Arda, Yasemin
    Branch-and-price is one of the most commonly used methodologies for solving routing problems. In recent years, several studies have investigated advanced labeling algorithms to solve the related pricing problem, which is usually a variant of the elementary shortest path problem with resource constraints. Such algorithms include efficient techniques such as decremental state space relaxation, ng-route relaxation, and several hybridizations of these two relaxation methods. In this study, we compare the performance of these labeling algorithms in a branch-and-price framework when applied to the vehicle routing problem with time windows and a variant of this problem in which waiting times have a linear cost. For the latter problem, we also propose an appropriate label structure with associated resource extension functions and dominance rules. We perform these comparisons by using a rigorous methodology, which consists of parameterizing several features of these algorithms, obtaining a good parameter configuration for each algorithm, and analyzing the performance of these configurations on benchmark instances. In order to obtain good configurations, we make use of irace, which is a tool for automated parameter tuning, while statistical tests are used for performance comparisons. Our results show that a class of hybrid algorithms with certain features based on ng-route relaxation outperforms all the others.
  • Article
    Citation - WoS: 3
    Citation - Scopus: 5
    Qubo Formulations and Characterization of Penalty Parameters for the Multi-Knapsack Problem
    (IEEE-Inst Electrical Electronics Engineers Inc, 2025) Guney, Evren; Ehrenthal, Joachim; Hanne, Thomas
    The Multi-Knapsack Problem (MKP) is a fundamental challenge in operations research and combinatorial optimization. Quantum computing introduces new possibilities for solving MKP using Quadratic Unconstrained Binary Optimization (QUBO) models. However, a key challenge in QUBO formulations is the selection of penalty parameters, which directly influence solution feasibility and algorithm performance. In this work, we develop QUBO formulations for two MKP variants-the Multidimensional Knapsack Problem (MDKP) and the Multiple Knapsack Problem (MUKP)-and provide an algebraic characterization of their penalty parameters. We systematically evaluate their impact through quantum simulation experiments and compare the performance of the two leading quantum optimization approaches: Quantum Approximate Optimization Algorithm (QAOA) and quantum annealing, alongside a state-of-the-art classical solver. Our results indicate that while classical solvers remain superior, careful tuning of penalty parameters has a strong impact on quantum optimization outcomes. QAOA is highly sensitive to parameter choices, whereas quantum annealing produces more stable results on small to mid-sized instances. Further, our results reveal that MDKP instances can maintain feasibility at penalty values below theoretical bounds, while MUKP instances show greater sensitivity to penalty reductions. Finally, we outline directions for future research in solving MKP, including adaptive penalty parameter tuning, hybrid quantum-classical approaches, and practical optimization strategies for QAOA, as well as real-hardware evaluations.
  • Article
    Citation - WoS: 1
    Citation - Scopus: 2
    A Decomposition Algorithm for Single and Multiobjective Integrated Market Selection and Production Planning
    (Informs, 2023-11-01) van den Heuvel, Wilco; Ağralı, Semra; Taşkın, Z. Caner
    We study an integrated market selection and production planning problem. There is a set of markets with deterministic demand, and each market has a certain revenue that is obtained if the market's demand is satisfied throughout a planning horizon. The demand is satisfied with a production scheme that has a lot-sizing structure. The problem is to decide on which markets' demand to satisfy and plan the production simultaneously. We consider both single and multiobjective settings. The single objective problem maximizes the profit, whereas the multiobjective problem includes the maximization of the revenue and the minimization of the production cost objectives. We develop a decomposition-based exact solution algorithm for the single objective setting and show how it can be used in a proposed three-phase algorithm for the multiobjective setting. The master problem chooses a subset of markets, and the subproblem calculates an optimal production plan to satisfy the selected markets' demand. We investigate the subproblem from a cooperative game theory perspective to devise cuts and strengthen them based on lifting. We also propose a set of valid inequalities and preprocessing rules to improve the proposed algorithm. We test the efficacy of our solution method over a suite of problem instances and show that our algorithm substantially decreases solution times for all problem instances.