論文の概要: Exact algorithms and heuristics for capacitated covering salesman problems
- arxiv url: http://arxiv.org/abs/2403.06995v1
- Date: Sun, 3 Mar 2024 07:50:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 06:00:28.676531
- Title: Exact algorithms and heuristics for capacitated covering salesman problems
- Title（参考訳）: セールスマン問題の容量化のための厳密なアルゴリズムとヒューリスティックス
- Authors: Lucas Porto Maziero, Fábio Luiz Usberti, Celso Cavellucci,
- Abstract要約: 本稿では,CCSP(Capacitated Covering Salesman Problem)を紹介する。
目的は、車両が横断する距離を最小化しながら、車両群を補給することである。
ILP(Integer Linear Programming)とBRKGA(Biased Random-Key Genetic Routing)のメタヒューリスティックに基づくCCSPの最適化手法を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper introduces the Capacitated Covering Salesman Problem (CCSP), approaching the notion of service by coverage in capacitated vehicle routing problems. In CCSP, locations where vehicles can transit are provided, some of which have customers with demands. The objective is to service customers through a fleet of vehicles based in a depot, minimizing the total distance traversed by the vehicles. CCSP is unique in the sense that customers, to be serviced, do not need to be visited by a vehicle. Instead, they can be serviced if they are within a coverage area of the vehicle. This assumption is motivated by applications in which some customers are unreachable (e.g., forbidden access to vehicles) or visiting every customer is impractical. In this work, optimization methodologies are proposed for the CCSP based on ILP (Integer Linear Programming) and BRKGA (Biased Random-Key Genetic Algorithm) metaheuristic. Computational experiments conducted on a benchmark of instances for the CCSP evaluate the performance of the methodologies with respect to primal bounds. Furthermore, our ILP formulation is extended in order to create a novel MILP (Mixed Integer Linear Programming) for the Multi-Depot Covering Tour Vehicle Routing Problem (MDCTVRP). Computational experiments show that the extended MILP formulation outperformed the previous state-of-the-art exact approach with respect to optimality gaps. In particular, optimal solutions were obtained for several previously unsolved instances.
- Abstract（参考訳）: 本稿では,静電容量被覆セールスマン問題 (CCSP) を紹介する。
CCSPでは、車両の移動が可能な場所が提供されており、一部には需要のある顧客がいる。
目的は、車両が横断する距離を最小化し、補給所をベースとした車両群を通じて顧客にサービスを提供することである。
CCSPは、顧客がサービスを受けるためには、車両を訪問する必要がなくなるという意味でユニークである。
代わりに、車両のカバー範囲内であればサービスを行うことができる。
この仮定は、一部の顧客が到達不可能な(例えば、車両へのアクセスを禁止している)アプリケーションや、すべての顧客を訪問するアプリケーションによって動機付けられている。
Integer Linear Programming(ICP)とBRKGA(Biased Random-Key Genetic Algorithm)のメタヒューリスティックに基づくCCSPの最適化手法を提案する。
CCSPのインスタンスのベンチマークで行った計算実験は、原始境界に対する方法論の性能を評価する。
さらに, MDCTVRP(Multi-Depot Covering Tour Vehicle Routing Problem)のためのMILP(Mixed Integer Linear Programming)を新たに作成するために, ILPの定式化を拡張した。
計算実験により、拡張MILPの定式化は、最適性ギャップに対する従来の最先端の正確なアプローチよりも優れていることが示された。
特に、未解決のいくつかのインスタンスに対して最適解が得られた。
関連論文リスト
- Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem [12.34897099691387]
本稿では,旅行セールスマン問題(TSP)の学習方法を提案する。
1対1のピックアップ・アンド・デリバリノードのシーケンスで一番短いツアーを見つける。
PDTSPでは、各ピックアップノードを対応する配信ノードの前に訪問しなければならないという優先的な制約を満たさなければならない。
論文 参考訳（メタデータ） (2024-04-17T15:05:51Z) - 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) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - Energy-Guided Continuous Entropic Barycenter Estimation for General Costs [95.33926437521046]
任意のOTコスト関数に対して連続的エントロピーOT(EOT)バリセンタを近似する新しいアルゴリズムを提案する。
本手法は、弱いOTに基づくEOT問題の二重再構成に基づいている。
論文 参考訳（メタデータ） (2023-10-02T11:24:36Z) - A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
CVRP(Capacitated Vehicle Routing Problem)は、輸送や物流など様々な分野で発生するNP最適化問題である。
本稿では,CVRPの車両容量制約を回避できる最短経路を最小化する目的機能を備えた,CVRP用の新しいバイナリエンコーディングを提案する。
本稿では,量子交換演算子Ansatzの変種に基づく符号化の有効性について論じる。
論文 参考訳（メタデータ） (2023-08-17T05:14:43Z) - Safe Model-Based Multi-Agent Mean-Field Reinforcement Learning [48.667697255912614]
平均場強化学習は、同一エージェントの無限集団と相互作用する代表エージェントのポリシーに対処する。
モデルベースの平均場強化学習アルゴリズムであるSafe-M$3$-UCRLを提案する。
本アルゴリズムは,低需要領域におけるサービスアクセシビリティを確保しつつ,重要な領域における需要を効果的に満たす。
論文 参考訳（メタデータ） (2023-06-29T15:57:07Z) - Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。
ソフトマージン条件下でのバニラQ関数の類似した結果を示す。
我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
論文 参考訳（メタデータ） (2023-02-05T14:22:41Z) - Off-line approximate dynamic programming for the vehicle routing problem
with stochastic customers and demands via decentralized decision-making [0.0]
本稿では,顧客の位置と需要が不確実な車両経路問題(VRP)の変種について検討する。
目的は、車両の容量と時間制限を満たしながら、提供された要求を最大化することである。
本稿では,Replay MemoryやDouble Q Networkといった最先端のアクセラレーション技術を用いたQラーニングアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-09-21T14:28:09Z) - Offline Model-Based Optimization via Normalized Maximum Likelihood
Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。
この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。
我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文 参考訳（メタデータ） (2021-02-16T06:04:27Z) - Optimizing Planning Service Territories by Dividing Into Compact Several
Sub-areas Using Binary K-means Clustering According Vehicle Constraints [0.0]
VRP(Vehicle Routing Problem)はNPの問題であり、多くの研究の関心を集めている。
本稿では,車両の最大容量を超えないクラスタ/グループを新たに生成するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-21T12:19:08Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。