論文の概要: Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints

• arxiv url: http://arxiv.org/abs/2505.02485v1
• Date: Mon, 05 May 2025 09:08:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-06 18:49:35.619028
• Title: Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints
• Title（参考訳）: 複雑な遮断制約を考慮したバスドライバスケジューリングのための列生成と大規模近傍探索の統合
• Authors: Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck,
• Abstract要約: バスドライバスケジューリング問題(バスドライバスケジューリング問題、BDSP)は、事前配置されたバスツアーをカバーするためのシフトの設計を目標とする最適化問題である。 本研究は,B&P法とLarge Neighborhood Search (LNS) フレームワークの両方を網羅的に検討した。 さらに、B&PとLNSのより深い統合を提案し、LNSサブプロブレムから生成されたカラムを保存し、他のサブプロブレムに再利用する。
• 参考スコア（独自算出の注目度）: 20.041743803403556
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimization problem with the goal to design shifts to cover prearranged bus tours. The objective takes into account the operational cost as well as the satisfaction of drivers. This problem is heavily constrained due to strict legal rules and collective agreements. The objective of this article is to provide state-of-the-art exact and hybrid solution methods that can provide high-quality solutions for instances of different sizes. This work presents a comprehensive study of both an exact method, Branch and Price (B&P), as well as a Large Neighborhood Search (LNS) framework which uses B&P or Column Generation (CG) for the repair phase to solve the BDSP. It further proposes and evaluates a novel deeper integration of B&P and LNS, storing the generated columns from the LNS subproblems and reusing them for other subproblems, or to find better global solutions. The article presents a detailed analysis of several components of the solution methods and their impact, including general improvements for the B&P subproblem, which is a high-dimensional Resource Constrained Shortest Path Problem (RCSPP), and the components of the LNS. The evaluation shows that our approach provides new state-of-the-art results for instances of all sizes, including exact solutions for small instances, and low gaps to a known lower bound for mid-sized instances. Conclusions: We observe that B&P provides the best results for small instances, while the tight integration of LNS and CG can provide high-quality solutions for larger instances, further improving over LNS which just uses CG as a black box. The proposed methods are general and can also be applied to other rule sets and related optimization problems
• Abstract（参考訳）: バスドライバスケジューリング問題(バスドライバスケジューリング問題、BDSP)は、事前配置されたバスツアーをカバーするためにシフトを設計することを目的とした組合せ最適化問題である。 目的は運転コストと運転者の満足度を考慮することである。 この問題は厳格な法的規則と集団合意によって厳しく制約されている。 本稿の目的は、異なるサイズのインスタンスに対して高品質なソリューションを提供する、最先端の正確かつハイブリッドなソリューション方法を提供することである。 本研究は,B&Pの正確な手法であるブランチ・アンド・プライス(B&P)と,B&Pやカラム・ジェネレーション(CG)を用いてBDSPを解くLarge Neighborhood Search(LNS)フレームワークを総合的に検討する。 さらに、新たなB&PとLNSのより深い統合を提案し、LNSサブプロブレムから生成されたカラムを保存し、他のサブプロブレムに再利用したり、より優れたグローバルソリューションを見つけるために評価する。 本稿では、高次元資源制約短経路問題(RCSPP)であるB&Pサブプロブレムの一般的な改善や、LNSの構成要素など、ソリューション手法のいくつかのコンポーネントとその影響について詳細に分析する。 評価の結果,本手法は,小インスタンスの厳密な解や,中サイズのインスタンスの既知の下位境界に対する低ギャップを含む,すべてのサイズのインスタンスに対して,新たな最先端結果を提供する。 結論: LNSとCGの緊密な統合はより大きなインスタンスに対して高品質なソリューションを提供し、CGをブラックボックスとして使用するLNSよりも改善する。 提案手法は汎用的であり,他のルールセットや関連する最適化問題にも適用可能である。

関連論文リスト

• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  制約,検証,選択という3つの重要な要素を持つモデルに依存しない,スケーラブルなエージェントフレームワークであるPlanGENを提案する。 具体的には、推論時間アルゴリズムの性能を向上させるために、制約誘導反復検証を提案する。
  論文  参考訳（メタデータ） (2025-02-22T06:21:56Z)
• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。 我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
  論文  参考訳（メタデータ） (2025-02-14T15:21:27Z)
• UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems [8.871356150316224]
  2段階のニューラル手法は、大規模なCO問題に対処する際の効率性を示している。 本稿では,一般の大規模CO問題の解法として,統一型ニューラルディバイド・アンド・コンカー・フレームワーク(UDC)を開発する。
  論文  参考訳（メタデータ） (2024-06-29T04:29:03Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Optimal Solutions for Joint Beamforming and Antenna Selection: From Branch and Bound to Machine Learning [47.10315221141495]
  本研究は、不完全なチャネル状態情報(CSI)の下で、継手ビームフォーミング(BF)とアンテナ選択(AS)の問題およびロバストビームフォーミング(RBF)バージョンを再検討する。 この研究の主な貢献は3つある。まず、関心事の問題を解決する効果的な分岐と境界(B&B)フレームワークを提案する。 第二に、潜在的にコストのかかるB&Bアルゴリズムを高速化するために、B&B検索ツリーの中間状態を省略する機械学習(ML)ベースのスキームが提案されている。
  論文  参考訳（メタデータ） (2022-06-11T17:43:02Z)
• sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission Planning Problems [2.191505742658975]
  いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。 本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。 このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
  論文  参考訳（メタデータ） (2020-02-20T17:07:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。