Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network

• URL: http://arxiv.org/abs/2509.13227v2
• Date: Wed, 17 Sep 2025 13:17:03 GMT
• Title: Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network
• Authors: Santanu Banerjee, Goutam Sen, Siddhartha Mukhopadhyay,
• Abstract summary: 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.
• Score: 1.1470070927586018
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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. The problem arises from the real-world requirement of optimizing the disaster response time by minimizing the makespan of vehicular routes. Multiple diversely-functional vertices are considered, including Transhipment Ports as inter-modal resource transfer stations. Both simultaneous and split pickup and delivery are considered, for multiple cargo types, along with Vehicle-Cargo and Transhipment Port-Cargo compatibilities. The superiority of the proposed cascaded minimization approach is demonstrated over the existing makespan minimization approaches through our developed Mixed-Integer Linear Programming formulation. To solve the problem quickly for practical implementation in a Disaster Management-specific Decision Support System, an extensive Heuristic Algorithm is devised which utilizes Decision Tree based structuring of possible routes; the Decision Tree approach helps to inherently capture the compatibility issues, while also explore the solution space through stochastic weights. Preferential generation of small route elements is performed, which are integrated into route clusters; we consider multiple different logical integration approaches, as well as shuffling the logics to simultaneously produce multiple independent solutions. Finally, perturbations of the different solutions are done to find better neighbouring solutions. The computational performance of the PSR-GIP Heuristic, on our created novel datasets, indicates that it is able to give good solutions swiftly for practical problems involving large integer instances that the MILP is unable to solve.

Related papers

• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
  Vehicle Routing Problems (VRP) are an extension of the Traveling Salesperson Problem and are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce a novel optimization framework that uses a reinforcement learning agent - trained on prior instances - to quickly generate initial solutions, which are then further optimized by genetic algorithms.<n>For example, EARLI handles vehicle routing with 500 locations within 1s, 10x faster than current solvers for the same solution quality, enabling applications like real-time and interactive routing.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  We propose SEQUOIA, an RL algorithm that directly optimize for long-term reward over the feasible action space.<n>We empirically validate SEQUOIA on four novel restless bandit problems with constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints.
  arXiv  Detail & Related papers  (2025-03-01T21:25:21Z)
• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems.<n>We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• A Coalition Game for On-demand Multi-modal 3D Automated Delivery System [4.378407481656902]
  We introduce a coalition game for a fleet of UAVs and ADRs operating in two overlaying networks to address last-mile delivery in urban environments.<n>We investigate cooperation structures among the modes to capture how strategic collaboration can improve overall routing efficiency.<n>Several numerical experiments on last-mile delivery applications have been conducted, showing the results from the case study in the city of Mississauga.
  arXiv  Detail & Related papers  (2024-12-23T03:50:29Z)
• Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet [0.0]
  We propose an NCO approach to solve a time-constrained capacitated VRP with a finite vehicle fleet size. The method is able to find adequate and cost-efficient solutions, showing both flexibility and robust generalizations.
  arXiv  Detail & Related papers  (2024-11-07T15:16:36Z)
• TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem [47.40841984849682]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation.<n>We introduce TOP-Former, a multi-agent route planning neural network designed to efficiently and accurately solve the Team Orienteering Problem.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• Supervised Permutation Invariant Networks for Solving the CVRP with Bounded Fleet Size [3.5235974685889397]
  Learning to solve optimization problems, such as the vehicle routing problem, offers great computational advantages. We propose a powerful supervised deep learning framework that constructs a complete tour plan from scratch while respecting an apriori fixed number of vehicles. In combination with an efficient post-processing scheme, our supervised approach is not only much faster and easier to train but also competitive results.
  arXiv  Detail & Related papers  (2022-01-05T10:32:18Z)
• An SMT Based Compositional Model to Solve a Conflict-Free Electric Vehicle Routing Problem [2.64699517152535]
  The Electric Conflict-Free Vehicle Routing Problem (CF-EVRP) involves constraints such as limited operating range of the vehicles, time windows on the delivery to the customers, and limited capacity on the number of vehicles the road segments can accommodate. We develop a compositional model that breaks down the problem into smaller and simpler sub-problems and provides sub-optimal, feasible solutions.
  arXiv  Detail & Related papers  (2021-06-10T20:37:46Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  We propose Deep Policy Dynamic Programming (D PDP) to combine the strengths of learned neurals with those of dynamic programming algorithms. D PDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP) and the vehicle routing problem (VRP) and show that the neural policy improves the performance of (restricted) DP algorithms.
  arXiv  Detail & Related papers  (2021-02-23T15:33:57Z)
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem [5.057312718525522]
  This paper presents a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC) It has shown significant computational advantages in solving optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management.
  arXiv  Detail & Related papers  (2020-05-26T01:47:39Z)
• 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.