論文の概要: Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows

• arxiv url: http://arxiv.org/abs/2402.00041v1
• Date: Sat, 20 Jan 2024 06:06:01 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-04 05:09:47.278634
• Title: Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows
• Title（参考訳）: 時間窓を用いた大規模車両経路問題の時空間クラスタリング
• Authors: Christoph Kerscher and Stefan Minner
• Abstract要約: 本稿では,クラスタリングを用いて顧客をグループ化するDRI(Decompose-route-improve)フレームワークを提案する。 その類似度基準は、顧客の空間的、時間的、需要データを含む。 本研究では,解答サブプロブレム間でプルーンド局所探索(LS)を適用し,全体の解法を改善する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several metaheuristics use decomposition and pruning strategies to solve large-scale instances of the vehicle routing problem (VRP). Those complexity reduction techniques often rely on simple, problem-specific rules. However, the growth in available data and advances in computer hardware enable data-based approaches that use machine learning (ML) to improve scalability of solution algorithms. We propose a decompose-route-improve (DRI) framework that groups customers using clustering. Its similarity metric incorporates customers' spatial, temporal, and demand data and is formulated to reflect the problem's objective function and constraints. The resulting sub-routing problems can independently be solved using any suitable algorithm. We apply pruned local search (LS) between solved subproblems to improve the overall solution. Pruning is based on customers' similarity information obtained in the decomposition phase. In a computational study, we parameterize and compare existing clustering algorithms and benchmark the DRI against the Hybrid Genetic Search (HGS) of Vidal et al. (2013). Results show that our data-based approach outperforms classic cluster-first, route-second approaches solely based on customers' spatial information. The newly introduced similarity metric forms separate sub-VRPs and improves the selection of LS moves in the improvement phase. Thus, the DRI scales existing metaheuristics to achieve high-quality solutions faster for large-scale VRPs by efficiently reducing complexity. Further, the DRI can be easily adapted to various solution methods and VRP characteristics, such as distribution of customer locations and demands, depot location, and different time window scenarios, making it a generalizable approach to solving routing problems.
• Abstract（参考訳）: いくつかのメタヒューリスティックは分解と刈り取り戦略を用いて、車両経路問題(vrp)の大規模インスタンスを解決する。 これらの複雑さ低減技術は、しばしば単純で問題固有のルールに依存します。 しかし、利用可能なデータの増加とコンピュータハードウェアの進歩により、機械学習(ML)を使用してソリューションアルゴリズムのスケーラビリティを向上させるデータベースのアプローチが可能になる。 本稿では,クラスタリングを用いて顧客をグループ化するDRIフレームワークを提案する。 その類似度指標は、顧客の空間的、時間的、需要データを含み、問題の客観的機能と制約を反映して定式化される。 結果として生じるサブルーチン問題は、任意の適切なアルゴリズムを用いて独立に解決できる。 解決された部分問題に対してpruned local search (ls) を適用し,全体の解法を改善した。 プルーニングは、分解段階で得られた顧客の類似性情報に基づいている。 本研究では,既存のクラスタリングアルゴリズムをパラメータ化して比較し,DRIをVidalらのHybrid Genetic Search (HGS)と比較した(2013)。 その結果,データに基づくアプローチは,ユーザの空間情報のみに基づく古典的クラスタファースト,ルート秒アプローチよりも優れていた。 新たに導入された類似度メトリックは、別個のVRPを形成し、改善フェーズにおけるLS移動の選択を改善する。 したがって、DRIは既存のメタヒューリスティックスをスケールし、複雑さを効率的に減らし、大規模VRPにおいてより高速な高品質のソリューションを実現する。 さらに、DRIは、顧客の位置や要求の分散、補給所の位置、異なる時間窓のシナリオなど、様々なソリューション手法やVRP特性に容易に適応でき、ルーティング問題を解決するための一般化可能なアプローチとなる。

関連論文リスト

• Multi-Agent Environments for Vehicle Routing Problems [1.0179489519625304]
  本稿では,従来の車両ルーティング問題をシミュレートするマルチエージェント環境からなるライブラリを提案する。 PyTorch上に構築されたこのライブラリは、新しいルーティング問題のカスタマイズと導入を容易にする、柔軟なモジュラーアーキテクチャ設計を提供する。
  論文  参考訳（メタデータ） (2024-11-21T18:46:23Z)
• Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering [1.3927943269211591]
  実用的なランタイムにおける車両ルーティングの効率的な解決は、デリバリ管理企業にとって重要な課題である。 本稿では,CVRPとCCBC(Constrainedid-Based Clustering)の理論的および実験的関係について検討する。 提案するフレームワークは,3つの段階から構成される。第1段階では,制約付きセントロイドベースのクラスタリングアルゴリズムが,ユーザの実現可能なクラスタを生成する。
  論文  参考訳（メタデータ） (2024-03-20T22:24:36Z)
• Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
  車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。 本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。 特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
  論文  参考訳（メタデータ） (2023-10-22T02:46:37Z)
• 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)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27:20Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。 通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。 分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。 分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
  論文  参考訳（メタデータ） (2020-10-02T10:41:59Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)
• Dynamic Federated Learning [57.14673504239551]
  フェデレートラーニング(Federated Learning)は、マルチエージェント環境における集中的なコーディネーション戦略の包括的用語として登場した。 我々は、各イテレーションにおいて、利用可能なエージェントのランダムなサブセットがそのデータに基づいてローカル更新を実行する、フェデレートされた学習モデルを考える。 集約最適化問題に対する真の最小化器上の非定常ランダムウォークモデルの下で、アーキテクチャの性能は、各エージェントにおけるデータ変動率、各エージェントにおけるモデル変動率、アルゴリズムの学習率に逆比例する追跡項の3つの要因によって決定されることを示す。
  論文  参考訳（メタデータ） (2020-02-20T15:00:54Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  本稿では,ミリ波通信網における車とセルの関連性について検討する。 まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。 提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
  論文  参考訳（メタデータ） (2020-01-22T08:51:05Z)

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

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