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

• arxiv url: http://arxiv.org/abs/2401.03692v1
• Date: Mon, 8 Jan 2024 06:46:39 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-09 17:44:54.449452
• 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要約: 本研究では,乗り継ぎ計画と乗務員スケジューリングを共同で最適化することで,サービススケジューリングの複雑さに対処する。 AGGNNI-CGと呼ばれる新しい解法は、カラム生成と機械学習をハイブリダイズし、ほぼ最適解を得る。 AGGNNI-CGは、ジョージア州チャタム郡のパラトランジットシステムから、挑戦的な実世界のデータセットに適用されている。
• 参考スコア（独自算出の注目度）: 19.099742921732094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 over-subscription 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 AGGNNI-CG (Attention and Gated GNN- Informed Column Generation), that hybridizes column generation and machine learning to obtain near-optimal solutions to the JRTPCSSP with the real-time 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 component, 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, that 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 dramatic improvements compared to the baseline column generation approach, which typically cannot produce feasible solutions in reasonable time on both medium-sized and large-scale complex instances. AGGNNI-CG also produces significant improvements in service compared to the existing system.
• Abstract（参考訳）: サービスのスケジュールを最適化することは、信頼性が高く、効率的で、包括的なオンデマンドモビリティに欠かせない。 この課題は、高齢化のニーズの増加、既存サービスの過剰な加入、効果的な解決方法の欠如によってさらに悪化している。 本研究は,複雑な動的移動サービスのための乗り継ぎ計画と乗務員スケジューリングを共同で最適化することで,サービススケジューリングの複雑さに対処する。 結果として生じる最適化問題は、最先端の手法では計算上極めて困難である。 このギャップを解消するために,本論文では,JRTPCSSP の最適解をリアルタイムに取得するために,コラム生成と機械学習を併用する AGGNNI-CG (Attention and Gated GNN- Informed Column Generation) と呼ばれる新しい解法を提案する。 機械学習コンポーネントのキーとなる考え方は、価格コンポーネントで探索するパスの数を劇的に減らし、列生成の最も時間を要するコンポーネントを加速することだ。 機械学習コンポーネントは、注目機構とゲートアーキテクチャを備えたグラフニューラルネットワークであり、特に日々の操作から得られるさまざまな入力サイズに対応するのに適している。 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)

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

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