論文の概要: A Rolling-Space Branch-and-Price Algorithm for the Multi-Compartment Vehicle Routing Problem with Multiple Time Windows
- arxiv url: http://arxiv.org/abs/2601.16194v1
- Date: Thu, 22 Jan 2026 18:46:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-23 21:37:20.695169
- Title: A Rolling-Space Branch-and-Price Algorithm for the Multi-Compartment Vehicle Routing Problem with Multiple Time Windows
- Title（参考訳）: 複数時間Windowsを用いたマルチコンパートメント車両ルーティング問題に対するローリングスペース分岐・価格アルゴリズム
- Authors: El Mehdi Er Raqabi, Kevin Dalmeijer, Pascal Van Hentenryck,
- Abstract要約: 本稿では,複数時間ウィンドウ(MCVRPMTW)を用いたマルチコンパートメント車両ルーティング問題について検討する。
この問題には、(i)コンパートメント数の柔軟性、(ii)アイテム・ツー・コンパートメントの互換性、(iii)アイテム・ツー・イテムの互換性の3つの主要なコンパートメント関連機能が含まれている。
大規模インスタンスを扱うために,クラスタリング手法をソリューションフレームワークに統合するローリングスペースB&Pアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 14.940040480107633
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This paper investigates the multi-compartment vehicle routing problem with multiple time windows (MCVRPMTW), an extension of the classical vehicle routing problem with time windows that considers vehicles equipped with multiple compartments and customers requiring service across several delivery time windows. The problem incorporates three key compartment-related features: (i) compartment flexibility in the number of compartments, (ii) item-to-compartment compatibility, and (iii) item-to-item compatibility. The problem also accommodates practical operational requirements such as driver breaks. To solve the MCVRPMTW, we develop an exact branch-and-price (B&P) algorithm in which the pricing problem is solved using a labeling algorithm. Several acceleration strategies are introduced to limit symmetry during label extensions, improve the stability of dual solutions in column generation, and enhance the branching process. To handle large-scale instances, we propose a rolling-space B&P algorithm that integrates clustering techniques into the solution framework. Extensive computational experiments on instances inspired by a real-world industrial application demonstrate the effectiveness of the proposed approach and provide useful managerial insights for practical implementation.
- Abstract（参考訳）: 本稿では、複数時間窓(MCVRPMTW)による複数区画の車両経路問題について検討し、複数区画の車両と複数の配送時間窓をまたぐサービスを必要とする顧客を考慮に入れた時間窓による古典的な車両経路問題の拡張について考察する。
問題には3つの重要なコンパートメント関連機能が含まれている。
一 コンパートメントの数におけるコンパートメントの柔軟性
(ii)アイテム・ツー・コンパートメントの互換性、及び
(iii)項目間互換性。
この問題は、ドライバーの故障のような実用的な運転要件にも適合する。
MCVRPMTWを解くために,ラベル付けアルゴリズムを用いて価格問題を解くB&Pアルゴリズムを開発した。
ラベル拡張中に対称性を制限し、カラム生成における双対解の安定性を改善し、分岐過程を強化するために、いくつかの加速戦略が導入された。
大規模インスタンスを扱うために,クラスタリング手法をソリューションフレームワークに統合するローリングスペースB&Pアルゴリズムを提案する。
実世界の産業アプリケーションにインスパイアされたインスタンスに対する大規模な計算実験は,提案手法の有効性を実証し,実践的実装に有用な管理的洞察を提供する。
関連論文リスト
- Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network [1.1470070927586018]
地理的に分散した車両基地に複数台の異種車両を配置し、異なる交通手段を利用できるような、豊富な車両経路問題も検討されている。
この問題は、車両経路の等間隔を最小化することで災害応答時間を最適化する現実的な要件から生じる。
提案手法の優位性は,Mixed-Integer Linear Programmingの定式化によって実証された。
論文 参考訳（メタデータ） (2025-09-16T16:37:18Z) - Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。
本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。
このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
論文 参考訳（メタデータ） (2025-04-08T15:21:01Z) - Dynamic Cross-Modal Feature Interaction Network for Hyperspectral and LiDAR Data Classification [66.59320112015556]
ハイパースペクトル画像(HSI)とLiDARデータ共同分類は難しい課題である。
DCMNet(Dynamic Cross-Modal Feature Interaction Network)を提案する。
BSAB(Bilinear Spatial Attention Block)、BCAB(Bilinear Channel Attention Block)、ICB(Integration Convolutional Block)の3つの機能相互作用ブロックを導入している。
論文 参考訳（メタデータ） (2025-03-10T05:50:13Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - 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) - Territory Design for Dynamic Multi-Period Vehicle Routing Problem with
Time Windows [0.0]
タイムウインドウ(TD-DMPVRPTW)を用いた動的多周期車両ルーティング問題の準位設計
この問題は、デポから一連の顧客への注文を配信するための連続的でコンパクトな領域の設計を扱う。
顧客と要求は時間とともに動的に変化する。
論文 参考訳（メタデータ） (2020-12-18T20:50:32Z) - Learning to Solve Vehicle Routing Problems with Time Windows through
Joint Attention [6.155158115218501]
複数のツアーの協調行動空間に注意を払って複数のルートを同時に開始・拡張できる政策モデルを開発する。
時間窓付き車両経路問題の3つの変種に関する総合的な実験において、我々のモデルであるJAMPRは、異なる問題サイズでうまく機能し、既存の最先端建設モデルより優れていることを示す。
論文 参考訳（メタデータ） (2020-06-16T12:08:10Z) - Solving Area Coverage Problem with UAVs: A Vehicle Routing with Time
Windows Variation [0.0]
現実には、無人航空機(UAV)で地域を覆い隠すことで、広い範囲の安全を確保することは、複数の目的から成り立っている難しい問題である。
エージェントの容量を1つにし、各顧客(ターゲットエリア)に同時に複数の車両を供給しなければならないVRPTW変動を考慮し、この問題に対処する。
本稿では,対象エリアを時間ウィンドウに従ってクラスタリングし,各クラスタと準備可能なUAVの輸送問題を段階的に生成するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-16T11:27:21Z) - Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent
Reinforcement Learning Approach [9.717648122961483]
ソフトタイムウインドウ(MVRPSTW)を用いたマルチ車両ルーティング問題は、都市ロジスティクスシステムにおいて不可欠である。
従来の手法は計算効率と解の質のジレンマを引き起こす。
そこで本研究では,ルーティング問題の解決に要する時間的オフライントレーニングのメリットを即時評価する,Multi-Agent Attention Modelと呼ばれる新しい強化学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-13T14:26:27Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。