Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit

• URL: http://arxiv.org/abs/2204.11992v1
• Date: Mon, 25 Apr 2022 23:17:34 GMT
• Title: Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit
• Authors: Amutheezan Sivagnanam, Salah Uddin Kadir, Ayan Mukhopadhyay, Philip Pugliese, Abhishek Dubey, Samitha Samaranayake, Aron Laszka
• Abstract summary: We introduce a novel formulation of the offline vehicle routing problem with online bookings. This problem is very challenging computationally since it faces the complexity of considering large sets of requests. We propose a novel computational approach, which combines an anytime algorithm with a learning-based policy for real-time decisions.
• Score: 5.8521525578624916
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Vehicle routing problems (VRPs) can be divided into two major categories: offline VRPs, which consider a given set of trip requests to be served, and online VRPs, which consider requests as they arrive in real-time. Based on discussions with public transit agencies, we identify a real-world problem that is not addressed by existing formulations: booking trips with flexible pickup windows (e.g., 3 hours) in advance (e.g., the day before) and confirming tight pickup windows (e.g., 30 minutes) at the time of booking. Such a service model is often required in paratransit service settings, where passengers typically book trips for the next day over the phone. To address this gap between offline and online problems, we introduce a novel formulation, the offline vehicle routing problem with online bookings. This problem is very challenging computationally since it faces the complexity of considering large sets of requests -- similar to offline VRPs -- but must abide by strict constraints on running time -- similar to online VRPs. To solve this problem, we propose a novel computational approach, which combines an anytime algorithm with a learning-based policy for real-time decisions. Based on a paratransit dataset obtained from our partner transit agency, we demonstrate that our novel formulation and computational approach lead to significantly better outcomes in this service setting than existing algorithms.

Related papers

• Solving the Team Orienteering Problem with Transformers [46.93254771681026]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation. This paper presents a multi-agent route planning system capable of solving the Team Orienteering Problem in a very fast and accurate manner.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach [49.00137468773683]
  Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents. We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2023-10-26T15:42:29Z)
• Hybrid Genetic Search for Dynamic Vehicle Routing with Time Windows [0.0]
  We adapt the Hybrid Genetic Search (HGS) algorithm, a successful solution for VRPTW, to the dynamic variant. Our approach modifies these components for DVRPTW, attempting to balance solution quality and constraints on future customer arrivals.
  arXiv  Detail & Related papers  (2023-07-21T11:16:49Z)
• 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)
• A deep learning Attention model to solve the Vehicle Routing Problem and the Pick-up and Delivery Problem with Time Windows [0.0]
  SNCF, the French public train company, is experimenting to develop new types of transportation services by tackling vehicle routing problems. We use an Attention-Decoder structure and design a novel insertion for the feasibility check of the CPDPTW. Our models yields results that are better than best known learning solutions on the CVRPTW.
  arXiv  Detail & Related papers  (2022-12-20T16:25:55Z)
• An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services [5.649212162857776]
  We propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) It is difficult to batch paratransit requests together as they are temporally sparse. We use Monte Carlo tree search to evaluate actions for any given state.
  arXiv  Detail & Related papers  (2022-03-28T22:15:52Z)
• A Case Study of Vehicle Route Optimization [2.2101681534594237]
  In this work, we incorporate the main relevant real-world constraints and requirements. We propose a two-stage strategy and a Timeline algorithm for time windows and pause times. Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.
  arXiv  Detail & Related papers  (2021-11-17T13:10:55Z)
• Offline-to-Online Reinforcement Learning via Balanced Replay and Pessimistic Q-Ensemble [135.6115462399788]
  Deep offline reinforcement learning has made it possible to train strong robotic agents from offline datasets. State-action distribution shift may lead to severe bootstrap error during fine-tuning. We propose a balanced replay scheme that prioritizes samples encountered online while also encouraging the use of near-on-policy samples.
  arXiv  Detail & Related papers  (2021-07-01T16:26:54Z)
• Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World [49.80905654161763]
  The Flatland competition aimed at finding novel approaches to solve the vehicle re-scheduling problem (VRSP) The VRSP is concerned with scheduling trips in traffic networks and the re-scheduling of vehicles when disruptions occur. The ever-growing complexity of modern railway networks makes dynamic real-time scheduling of traffic virtually impossible.
  arXiv  Detail & Related papers  (2021-03-30T17:13:29Z)
• Computation Offloading in Heterogeneous Vehicular Edge Networks: On-line and Off-policy Bandit Solutions [30.606518785629046]
  In a fast-varying vehicular environment, the latency in offloading arises as a result of network congestion. We propose an on-line algorithm and an off-policy learning algorithm based on bandit theory. We show that the proposed solutions adapt to the traffic changes of the network by selecting the least congested network.
  arXiv  Detail & Related papers  (2020-08-14T11:48:13Z)
• 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.