論文の概要: Boosting Column Generation with Graph Neural Networks for Joint Rider Trip Planning and Crew Shift Scheduling

• arxiv url: http://arxiv.org/abs/2401.03692v3
• Date: Wed, 08 Jan 2025 16:05:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-09 14:52:56.205641
• Title: Boosting Column Generation with Graph Neural Networks for Joint Rider Trip Planning and Crew Shift Scheduling
• Title（参考訳）: グラフニューラルネットを用いたラウンダリング・トリプ計画とクルーシフトスケジューリングのためのブースティング・カラム生成
• Authors: Jiawei Lu, Tinghan Ye, Wenbo Chen, Pascal Van Hentenryck,
• Abstract要約: 本稿では,JRTPCSSP(Joint Rider Trip Planning and Crew Shift Scheduling Problem)とAttention and Gated GNN-Informed Column Generation(AGGNNI-CG)と呼ばれる新しい解法を提案する。 AGGNNI-CGは、列生成と機械学習をハイブリダイズして、アプリケーションの現実的な制約を伴って、JRTPCSSPのほぼ最適解を得る。 AGGNNI-CGは、ジョージア州チャタム郡のパラトランジットシステムから、挑戦的な実世界のデータセットに適用されている。
• 参考スコア（独自算出の注目度）: 17.483751895564676
• License:
• Abstract: Optimizing service schedules is pivotal to the reliable, efficient, and inclusive on-demand mobility. This pressing challenge is further exacerbated by the increasing needs of an aging population, the oversubscription of existing services, and the lack of effective solution methods. This study addresses the intricacies of service scheduling, by jointly optimizing rider trip planning and crew scheduling for a complex dynamic mobility service. The resulting optimization problems are extremely challenging computationally for state-of-the-art methods. To address this fundamental gap, this paper introduces the Joint Rider Trip Planning and Crew Shift Scheduling Problem (JRTPCSSP) and a novel solution method, called Attention and Gated GNN-Informed Column Generation (AGGNNI-CG), that hybridizes column generation and machine learning to obtain near-optimal solutions to the JRTPCSSP with real-life constraints of the application. The key idea of the machine-learning component is to dramatically reduce the number of paths to explore in the pricing problem, accelerating the most time-consuming component of the column generation. The machine learning component is a graph neural network with an attention mechanism and a gated architecture, which is particularly suited to cater for the different input sizes coming from daily operations. AGGNNI-CG has been applied to a challenging, real-world dataset from the Paratransit system of Chatham County in Georgia. It produces substantial improvements compared to the baseline column generation approach, which typically cannot produce high-quality feasible solutions in reasonable time on large-scale complex instances. AGGNNI-CG also produces significant improvements in service quality compared to the existing system.
• Abstract（参考訳）: サービスのスケジュールを最適化することは、信頼性があり、効率的で、包括的なオンデマンドモビリティにとって重要なことです。 この課題は、高齢化のニーズの増加、既存サービスの過剰な加入、効果的な解決方法の欠如によってさらに悪化している。 本研究では,複雑な動的移動サービスのための乗客旅行計画と乗務員スケジューリングを共同で最適化することで,サービススケジューリングの複雑さに対処する。 結果として生じる最適化問題は、最先端の手法では極めて困難である。 このギャップを解消するために,本論文では,JRTPCSSP に近距離最適解を求めるために,カラム生成と機械学習を併用したアテンション・ゲーテッド GNN-Informed Column Generation (AGGNNI-CG) と呼ばれる新しい解法を提案する。 機械学習コンポーネントの鍵となる考え方は、価格問題において探索するパスの数を劇的に減らし、列生成の最も時間を要するコンポーネントを加速することである。 機械学習コンポーネントは、注目機構とゲートアーキテクチャを備えたグラフニューラルネットワークであり、特に日々の操作から得られるさまざまな入力サイズに対応するのに適している。 AGGNNI-CGは、ジョージア州チャタム郡のパラトランジットシステムから、挑戦的な実世界のデータセットに適用されている。 大規模な複雑なインスタンスに対して,高品質な実現可能なソリューションを合理的に生成できないような,ベースライン列生成アプローチと比較して,大幅な改善が期待できる。 AGGNNI-CGは既存のシステムに比べてサービス品質が大幅に向上した。

関連論文リスト

• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  分散トレーニングは、システム設計と効率に関する重要な課題に直面します。 大規模深層ニューラルネットワーク(DNN)のトレーニング用に設計・実装された分散トレーニングシステムFusionLLMを提案する。 本システムと手法は,収束性を確保しつつ,ベースライン法と比較して1.45～9.39倍の高速化を実現可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-16T16:13:19Z)
• A Graph-based Adversarial Imitation Learning Framework for Reliable & Realtime Fleet Scheduling in Urban Air Mobility [5.19664437943693]
  本稿では,艦隊スケジューリング問題の包括的最適化について述べる。 また、代替ソリューションのアプローチの必要性も認識している。 新しい模倣アプローチは、目に見えない最悪のシナリオにおいて、パフォーマンスと顕著な改善を実現する。
  論文  参考訳（メタデータ） (2024-07-16T18:51:24Z)
• Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers [58.5711048151424]
  SPARSEK Attention(SPARSEK Attention)は、計算およびメモリ障害を克服するために設計された、新しいスパースアテンション機構である。 提案手法では,各クエリに対して一定数のKVペアを選択するために,スコアリングネットワークと差別化可能なトップkマスク演算子であるSPARSEKを統合する。 実験結果から,SPARSEK注意は従来のスパースアテンション法よりも優れていた。
  論文  参考訳（メタデータ） (2024-06-24T15:55:59Z)
• Learning-enabled Flexible Job-shop Scheduling for Scalable Smart Manufacturing [11.509669981978874]
  スマートマニュファクチャリングシステムでは、生産性を最大化するためのソリューションを最適化するために、輸送制約付きフレキシブルなジョブショップスケジューリングが不可欠である。 近年, 深部強化学習(DRL)に基づくFJSPT法の開発が, 大規模一般化の課題に直面している。 Heterogeneous Graph Scheduler (HGS) と呼ばれる新しいグラフベースのDRL法を導入する。
  論文  参考訳（メタデータ） (2024-02-14T06:49:23Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  本稿では,クラスタリングを用いて顧客をグループ化するDRI(Decompose-route-improve)フレームワークを提案する。 その類似度基準は、顧客の空間的、時間的、需要データを含む。 本研究では,解答サブプロブレム間でプルーンド局所探索(LS)を適用し,全体の解法を改善する。
  論文  参考訳（メタデータ） (2024-01-20T06:06:01Z)
• Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
  カラム生成(CG)は変数を動的に生成することで大規模問題を解決する重要な手法である。 CGの性能を高めるために,RLHHと呼ばれる強化学習に基づく超ヒューリスティックフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-15T00:05:50Z)
• Dynamic Scheduling for Federated Edge Learning with Streaming Data [56.91063444859008]
  我々は,長期的エネルギー制約のある分散エッジデバイスにおいて,トレーニングデータを時間とともにランダムに生成するフェデレーションエッジ学習(FEEL)システムを検討する。 限られた通信リソースとレイテンシ要件のため、各イテレーションでローカルトレーニングプロセスに参加するのはデバイスのサブセットのみである。
  論文  参考訳（メタデータ） (2023-05-02T07:41:16Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• Scalable Vehicle Re-Identification via Self-Supervision [66.2562538902156]
  自動車再同定は、都市規模の車両分析システムにおいて重要な要素の1つである。 車両再設計のための最先端のソリューションの多くは、既存のre-idベンチマークの精度向上に重点を置いており、計算の複雑さを無視することが多い。 推論時間に1つのネットワークのみを使用する自己教師型学習によって、シンプルで効果的なハイブリッドソリューションを提案する。
  論文  参考訳（メタデータ） (2022-05-16T12:14:42Z)
• Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search [12.457788665461312]
  本稿では,機械学習モデルと最適解法を併用したハイブリッド問題解決プランナを提案する。 我々は現実的なシナリオで実験を行い、GCNのサポートにより、より難しい問題に対して、大幅なスピードアップとスムーズなスケーリングが可能になることを示す。
  論文  参考訳（メタデータ） (2021-08-02T16:53:21Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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