論文の概要: Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering

• arxiv url: http://arxiv.org/abs/2403.14013v1
• Date: Wed, 20 Mar 2024 22:24:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-22 17:49:40.581712
• Title: Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering
• Title（参考訳）: 容量化車両ルーティング問題と制約付きセントロイドクラスタリングの接続に向けて
• Authors: Abdelhakim Abdellaoui, Loubna Benabbou, Issmail El Hallaoui,
• Abstract要約: 実用的なランタイムにおける車両ルーティングの効率的な解決は、デリバリ管理企業にとって重要な課題である。 本稿では,CVRPとCCBC(Constrainedid-Based Clustering)の理論的および実験的関係について検討する。 提案するフレームワークは,3つの段階から構成される。第1段階では,制約付きセントロイドベースのクラスタリングアルゴリズムが,ユーザの実現可能なクラスタを生成する。
• 参考スコア（独自算出の注目度）: 1.3927943269211591
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficiently solving a vehicle routing problem (VRP) in a practical runtime is a critical challenge for delivery management companies. This paper explores both a theoretical and experimental connection between the Capacitated Vehicle Routing Problem (CVRP) and the Constrained Centroid-Based Clustering (CCBC). Reducing a CVRP to a CCBC is a synonym for a transition from an exponential to a polynomial complexity using commonly known algorithms for clustering, i.e K-means. At the beginning, we conduct an exploratory analysis to highlight the existence of such a relationship between the two problems through illustrative small-size examples and simultaneously deduce some mathematically-related formulations and properties. On a second level, the paper proposes a CCBC based approach endowed with some enhancements. The proposed framework consists of three stages. At the first step, a constrained centroid-based clustering algorithm generates feasible clusters of customers. This methodology incorporates three enhancement tools to achieve near-optimal clusters, namely: a multi-start procedure for initial centroids, a customer assignment metric, and a self-adjustment mechanism for choosing the number of clusters. At the second step, a traveling salesman problem (T SP) solver is used to optimize the order of customers within each cluster. Finally, we introduce a process relying on routes cutting and relinking procedure, which calls upon solving a linear and integer programming model to further improve the obtained routes. This step is inspired by the ruin & recreate algorithm. This approach is an extension of the classical cluster-first, route-second method and provides near-optimal solutions on well-known benchmark instances in terms of solution quality and computational runtime, offering a milestone in solving VRP.
• Abstract（参考訳）: 実用的な実行環境における車両ルーティング問題(VRP)の効率的な解決は、デリバリ管理企業にとって重要な課題である。 本稿では,CVRP(Capacitated Vehicle Routing Problem)とCCBC(Constrained Centroid-Based Clustering)の理論的および実験的関係について検討する。 CVRP を CCBC に還元することは、指数関数から多項式の複雑性への移行のシノニムであり、クラスタリングの一般的なアルゴリズム、すなわち K-平均を用いる。 はじめに,この2つの問題の関連性を明らかにするための探索的解析を行い,いくつかの数学的関係の定式化と特性を同時に導出する。 第2のレベルでは,CCBCに基づくアプローチにいくつかの改良を加えて提案する。 提案するフレームワークは3つのステージで構成されている。 最初のステップでは、制約付きセントロイドベースのクラスタリングアルゴリズムが顧客の実現可能なクラスタを生成する。 この手法には,初期セントロイドのマルチスタート手順,顧客割当基準,クラスタ数を選択する自己調整機構の3つの拡張ツールが組み込まれている。 第2のステップでは、各クラスタ内の顧客の順序を最適化するために、旅行セールスマン問題(TSP)解決器が使用される。 最後に,線形および整数型プログラミングモデルの解法を求める経路切断と再リンクの手順に依存するプロセスを導入し,得られた経路をさらに改善する。 このステップは、破滅と再現のアルゴリズムにインスパイアされている。 このアプローチは、古典的なクラスタファーストのルート秒法の拡張であり、よく知られたベンチマークインスタンスに対して、ソリューションの品質と計算ランタイムの観点から、ほぼ最適なソリューションを提供し、VRPの解決におけるマイルストーンを提供します。

関連論文リスト

• A3S: A General Active Clustering Method with Pairwise Constraints [66.74627463101837]
  A3Sは、適応クラスタリングアルゴリズムによって得られる初期クラスタ結果に対して、戦略的にアクティブクラスタリングを調整する。 さまざまな実世界のデータセットにわたる広範な実験において、A3Sは、人間のクエリを著しく少なくして、望ましい結果を達成する。
  論文  参考訳（メタデータ） (2024-07-14T13:37:03Z)
• 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)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。 我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-12-17T04:41:07Z)
• Neural Capacitated Clustering [6.155158115218501]
  本稿では,クラスタセンターへのポイントの割り当て確率を予測するニューラルネットワークを学習する,容量クラスタリング問題(CCP)の新しい手法を提案する。 人工データと2つの実世界のデータセットに関する実験では、我々のアプローチは文学の最先端の数学的および解法よりも優れています。
  論文  参考訳（メタデータ） (2023-02-10T09:33:44Z)
• Fast conformational clustering of extensive molecular dynamics simulation data [19.444636864515726]
  本稿では,長い軌道の高速なコンフォーメーションクラスタリングを実現するために,教師なしのデータ処理ワークフローを提案する。 我々は密度に基づく空間クラスタリングアルゴリズム(HDBSCAN)と2つの次元削減アルゴリズム(cc_analysisとEncodermap)を組み合わせる。 4つのテストシステムの助けを借りて、このクラスタリングワークフローの機能とパフォーマンスを説明します。
  論文  参考訳（メタデータ） (2023-01-11T14:36:43Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。 我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。 一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
  論文  参考訳（メタデータ） (2020-12-01T13:17:27Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  本稿では,ミリ波通信網における車とセルの関連性について検討する。 まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。 提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
  論文  参考訳（メタデータ） (2020-01-22T08:51:05Z)

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

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