論文の概要: Capacitated Vehicle Routing Problem Using Conventional and Approximation
Method
- arxiv url: http://arxiv.org/abs/2208.00046v1
- Date: Fri, 29 Jul 2022 19:25:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-19 10:13:32.679523
- Title: Capacitated Vehicle Routing Problem Using Conventional and Approximation
Method
- Title(参考訳): 従来手法と近似手法によるキャパシテーション車両の経路問題
- Authors: Apurv Choudhari, Ameya Ekbote, Prerona Chaudhuri (Vishwakarma
Institute of Technology Pune, India)
- Abstract要約: 本稿では, 静電容量化車両, 単線, 距離などの制約を考慮し, 有名な車両経路問題の解決を試みる。
ノードのクラスタリングにはDBSCANアルゴリズムを採用し,近似アルゴリズムであるChristofideのアルゴリズムを用いてルーティングを行う。
生成されたソリューションは、さまざまな需要ノードで構成されるデリバリシステムのような、現実の状況の解決に使用することができる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: This paper attempts to solve the famous Vehicle Routing Problem by
considering multiple constraints including capacitated vehicles, single depot,
and distance using two approaches namely, cluster first and route the second
algorithm and using integer linear programming. A set of nodes are provided as
input to the system and a feasible route is generated as output, giving
clusters of nodes and the route to be traveled within the cluster. For
clustering the nodes, we have adopted the DBSCAN algorithm, and the routing is
done using the approximation algorithm, Christofide's algorithm. The solution
generated can be employed for solving real-life situations, like delivery
systems consisting of various demand nodes.
- Abstract(参考訳): 本稿では,キャパシテーション車両,単一車庫,距離といった複数の制約を,クラスタファーストと第2アルゴリズムのルーティングと整数線形計画という2つのアプローチを用いて考慮し,有名な車両経路問題を解くことを試みる。
システムへの入力としてノードのセットが提供され、実行可能なルートが出力として生成され、ノードのクラスタとクラスタ内を移動するルートが提供される。
ノードをクラスタリングするために,我々はdbscanアルゴリズムを採用し,christofideの近似アルゴリズムを用いてルーティングを行う。
生成されたソリューションは、さまざまな要求ノードからなるデリバリシステムのような現実の状況を解決するために利用することができる。
関連論文リスト
- A Neural Column Generation Approach to the Vehicle Routing Problem with Two-Dimensional Loading and Last-In-First-Out Constraints [3.9594431485015096]
2次元負荷制約 (2L-CVRP) を持つ車両ルーティング問題は, 実用的, アルゴリズム的に重要な課題である。
本稿では,高度な機械学習技術,特に注意と再発機構の新たな組み合わせを統合した,正確なアルゴリズムを提案する。
提案アルゴリズムは、標準テストベッドにおけるオープンインスタンスの解決に成功し、機械学習モデルの導入による大幅な改善を実証する。
論文 参考訳(メタデータ) (2024-06-18T09:58:29Z) - 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) - 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) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-03-28T21:34:16Z) - Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
絡み合いルーティングは、2つの任意のノード間のリモート絡み合い接続を確立する。
量子ネットワークにおける複数のソース・デスティネーション(SD)ペアの忠実性を保証するために、精製可能な絡み合わせルーティング設計を提案する。
論文 参考訳(メタデータ) (2021-11-15T14:07:22Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳(メタデータ) (2021-02-23T15:33:57Z) - A Hybrid Multi-Objective Carpool Route Optimization Technique using
Genetic Algorithm and A* Algorithm [0.0]
本研究では,カープール問題に対する最適経路を求めるためのGA-A*ハイブリッドアルゴリズムを提案する。
得られた経路は、ピックアップ/ドロップコストだけでなく、旅行・出先距離を最小化し、サービス提供者の利益を最大化する。
提案アルゴリズムはコルカタのソルトレイク地域に実装されている。
論文 参考訳(メタデータ) (2020-07-11T14:13:20Z) - A New Arc-Routing Algorithm Applied to Winter Road Maintenance [0.0]
本稿では, 比較的一般的なアークルーティング問題の大規模インスタンスについて検討し, 実用的制約を取り入れた。
そこで我々は,数千の交差点や道路セグメント上の道路網を数分で解き,良好なスケーリングが可能なビンパッキングに基づく新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2020-01-23T08:44:42Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳(メタデータ) (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。