A Rolling-Space Branch-and-Price Algorithm for the Multi-Compartment Vehicle Routing Problem with Multiple Time Windows

• URL: http://arxiv.org/abs/2601.16194v1
• Date: Thu, 22 Jan 2026 18:46:46 GMT
• Title: A Rolling-Space Branch-and-Price Algorithm for the Multi-Compartment Vehicle Routing Problem with Multiple Time Windows
• Authors: El Mehdi Er Raqabi, Kevin Dalmeijer, Pascal Van Hentenryck,
• Abstract summary: This paper investigates the multi-compartment vehicle routing problem with multiple time windows (MCVRPMTW)<n>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.<n>To handle large-scale instances, we propose a rolling-space B&P algorithm that integrates clustering techniques into the solution framework.
• Score: 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.

Related papers

• Dependency-Aware Task Offloading in Multi-UAV Assisted Collaborative Mobile Edge Computing [53.88774113545582]
  This paper presents a novel multi-unmanned aerial vehicle (UAV) assisted collaborative mobile edge computing (MEC) framework.<n>It aims to minimize the system cost, and thus realize an improved trade-off between task consumption and energy consumption.<n>We show that the proposed scheme can significantly reduce the system cost, and thus realize an improved trade-off between task consumption and energy consumption.
  arXiv  Detail & Related papers  (2025-10-23T02:55:40Z)
• Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network [1.1470070927586018]
  A rich vehicle routing problem is considered, allowing multiple trips of heterogeneous vehicles stationed at geographically distributed vehicle depots having access to different modes of transportation.<n>The problem arises from the real-world requirement of optimizing the disaster response time by minimizing the makespan of vehicular routes.<n>The superiority of the proposed cascaded minimization approach is demonstrated through our developed Mixed-Integer Linear Programming formulation.
  arXiv  Detail & Related papers  (2025-09-16T16:37:18Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  Vehicle Routing Problems (VRP) are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce an optimization framework where a reinforcement learning agent is trained on prior instances and quickly generates initial solutions.<n>This framework consistently outperforms current state-of-the-art solvers across various time budgets.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• Dynamic Cross-Modal Feature Interaction Network for Hyperspectral and LiDAR Data Classification [66.59320112015556]
  Hyperspectral image (HSI) and LiDAR data joint classification is a challenging task.<n>We propose a novel Dynamic Cross-Modal Feature Interaction Network (DCMNet)<n>Our approach introduces three feature interaction blocks: Bilinear Spatial Attention Block (BSAB), Bilinear Channel Attention Block (BCAB), and Integration Convolutional Block (ICB)
  arXiv  Detail & Related papers  (2025-03-10T05:50:13Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• Territory Design for Dynamic Multi-Period Vehicle Routing Problem with Time Windows [0.0]
  Territory Design for Dynamic Multi-Period Vehicle Routing Problem with Time Windows (TD-DMPVRPTW) This problem deals with the design of contiguous and compact territories for delivery of orders from a depot to a set of customers. Customers and their demands vary dynamically over time.
  arXiv  Detail & Related papers  (2020-12-18T20:50:32Z)
• Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention [6.155158115218501]
  We develop a policy model that is able to start and extend multiple routes concurrently by using attention on the joint action space of several tours. In comprehensive experiments on three variants of the vehicle routing problem with time windows we show that our model called JAMPR works well for different problem sizes and outperforms the existing state-of-the-art constructive model.
  arXiv  Detail & Related papers  (2020-06-16T12:08:10Z)
• Solving Area Coverage Problem with UAVs: A Vehicle Routing with Time Windows Variation [0.0]
  In real life, providing security for a set of large areas by covering the area with Unmanned Aerial Vehicles (UAVs) is a difficult problem that consist of multiple objectives. We address this by considering a Vehicle Problem with Time Windows (VRPTW) variation in which capacity of agents is one and each customer (target area) must be supplied with more than one vehicles simultaneously. We present a novel algorithm that relies on clustering the target areas according to their time windows, and then incrementally generating transportation problems with each cluster and the ready UAVs.
  arXiv  Detail & Related papers  (2020-03-16T11:27:21Z)
• Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach [9.717648122961483]
  Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics systems. Traditional methods incur the dilemma between computational efficiency and solution quality. We propose a novel reinforcement learning algorithm called the Multi-Agent Attention Model that can solve routing problem instantly benefit from lengthy offline training.
  arXiv  Detail & Related papers  (2020-02-13T14:26:27Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.