論文の概要: Machine-learning-based arc selection for constrained shortest path
problems in column generation
- arxiv url: http://arxiv.org/abs/2201.02535v1
- Date: Fri, 7 Jan 2022 16:49:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-10 16:19:50.691751
- Title: Machine-learning-based arc selection for constrained shortest path
problems in column generation
- Title（参考訳）: 列生成における制約付き最短経路問題に対する機械学習に基づくアーク選択
- Authors: Mouad Morabit, Guy Desaulniers, Andrea Lodi
- Abstract要約: 本研究では,機械学習に基づく新しい価格アルゴリズムを提案する。
目的は、ネットワークのサイズを小さくし、PPを加速することであり、線形緩和溶液の一部となる確率の高い弧のみを保持することである。
この方法は、公共交通機関における車両と乗員のスケジューリング問題と、時間窓による車両のルーティング問題という2つの特定の問題に適用されている。
- 参考スコア（独自算出の注目度）: 5.08128537391027
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Column generation is an iterative method used to solve a variety of
optimization problems. It decomposes the problem into two parts: a master
problem, and one or more pricing problems (PP). The total computing time taken
by the method is divided between these two parts. In routing or scheduling
applications, the problems are mostly defined on a network, and the PP is
usually an NP-hard shortest path problem with resource constraints. In this
work, we propose a new heuristic pricing algorithm based on machine learning.
By taking advantage of the data collected during previous executions, the
objective is to reduce the size of the network and accelerate the PP, keeping
only the arcs that have a high chance to be part of the linear relaxation
solution. The method has been applied to two specific problems: the vehicle and
crew scheduling problem in public transit and the vehicle routing problem with
time windows. Reductions in computational time of up to 40% can be obtained.
- Abstract（参考訳）: カラム生成は、様々な最適化問題の解決に使用される反復的手法である。
これは問題をマスター問題と1つ以上の価格問題(pp)という2つの部分に分割する。
提案手法の計算時間は, これら2つの部分に分けられる。
ルーティングやスケジューリングのアプリケーションでは、問題は主にネットワーク上で定義され、PPは通常、リソース制約のあるNPハードな最短経路問題である。
本研究では,機械学習に基づく新しいヒューリスティックな価格設定アルゴリズムを提案する。
従来の実行中に収集したデータを活用することで、ネットワークのサイズを小さくし、PPを加速し、線形緩和ソリューションの一部となる確率の高い弧のみを保持することが目的である。
この方法は、公共交通機関における車両と乗務員のスケジューリング問題とタイムウインドウによる車両の経路問題という2つの問題に適用されている。
最大40%の計算時間を短縮することができる。
関連論文リスト
- Solving the Team Orienteering Problem with Transformers [46.93254771681026]
車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。
本稿では,チームオリエンテーリング問題を高速かつ高精度に解決できる多エージェント経路計画システムを提案する。
論文 参考訳（メタデータ） (2023-11-30T16:10:35Z) - Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。
本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。
特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
論文 参考訳（メタデータ） (2023-10-22T02:46:37Z) - Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle
Routing Problem with Time Windows [58.891409372784516]
本稿では,Roulette Wheel Method (RWPSO) を用いた新しいPSO手法を提案する。
RWPSOのSolomon VRPTWベンチマークデータセットを用いた実験は、RWPSOが文学の他の最先端アルゴリズムと競合していることを示している。
論文 参考訳（メタデータ） (2023-06-04T09:18:02Z) - Rolling Horizon based Temporal Decomposition for the Offline Pickup and
Delivery Problem with Time Windows [5.818566833386833]
オフラインPDPTWのクラスを解くための新しい時間分解方式を提案する。
私たちのフレームワークはよりスケーラブルで、さまざまな難易度の問題インスタンスに対して優れたソリューションを提供することができます。
論文 参考訳（メタデータ） (2023-03-06T20:07:05Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳（メタデータ） (2022-10-31T09:46:26Z) - An Information Theory-inspired Strategy for Automatic Network Pruning [88.51235160841377]
深層畳み込みニューラルネットワークは、リソース制約のあるデバイスで圧縮されることがよく知られている。
既存のネットワークプルーニング手法の多くは、人的努力と禁忌な計算資源を必要とする。
本稿では,自動モデル圧縮のための情報理論に基づく戦略を提案する。
論文 参考訳（メタデータ） (2021-08-19T07:03:22Z) - Learned upper bounds for the Time-Dependent Travelling Salesman Problem [0.0]
時間依存トラベリングセールスマン問題(Time-Dependent Travelling Salesman Problem)は、グラフの頂点をカバーする少なくとも全期間のハミルトンツアーを見つけることである。
古典的(かつより単純な)時間非依存な非対称トラベリングセールスマン問題の解法に基づく上限化手法を考案する。
このアプローチの有効性は、2つのヨーロッパの都市の実走行時間関数に関する計算キャンペーンを通じて評価されている。
論文 参考訳（メタデータ） (2021-07-28T20:54:59Z) - Scaling the Convex Barrier with Sparse Dual Algorithms [141.4085318878354]
本稿では,ニューラルネットワークバウンダリングのための2つの新しい2重アルゴリズムを提案する。
どちらの方法も新しい緩和の強さを回復する: 厳密さと線形分離オラクル。
実行時間のほんの一部で、既製のソルバよりも優れた境界を得ることができます。
論文 参考訳（メタデータ） (2021-01-14T19:45:17Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Modeling and solving the multimodal car- and ride-sharing problem [0.0]
マルチモーダルカー・ライドシェアリング問題(MMCRP)を紹介する。
車両のプールは一連の乗車要求をカバーするために使用され、発見されていない要求は他の交通手段に割り当てられる。
カラム生成に基づく2層分解アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-15T09:43:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。