Balanced dynamic multiple travelling salesmen: algorithms and continuous approximations

• URL: http://arxiv.org/abs/2008.12063v2
• Date: Mon, 23 Aug 2021 15:58:52 GMT
• Title: Balanced dynamic multiple travelling salesmen: algorithms and continuous approximations
• Authors: Wolfgang Garn
• Abstract summary: Dynamic routing occurs when customers are not known in advance, e.g. for real-time routing. Twos are proposed that solve the balanced dynamic multiple travelling salesmen problem (BD-mTSP)
• Score: 0.40611352512781856
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Dynamic routing occurs when customers are not known in advance, e.g. for real-time routing. Two heuristics are proposed that solve the balanced dynamic multiple travelling salesmen problem (BD-mTSP). These heuristics represent operational (tactical) tools for dynamic (online, real-time) routing. Several types and scopes of dynamics are proposed. Particular attention is given to sequential dynamics. The balanced dynamic closest vehicle heuristic (BD-CVH) and the balanced dynamic assignment vehicle heuristic (BD-AVH) are applied to this type of dynamics. The algorithms are applied to a wide range of test instances. Taxi services and palette transfers in warehouses demonstrate how to use the BD-mTSP algorithms in real-world scenarios. Continuous approximation models for the BD-mTSP's are derived and serve as strategic tools for dynamic routing. The models express route lengths using vehicles, customers, and dynamic scopes without the need of running an algorithm. A machine learning approach was used to obtain regression models. The mean absolute percentage error of two of these models is below 3%.

Related papers

• DynamicRouteGPT: A Real-Time Multi-Vehicle Dynamic Navigation Framework Based on Large Language Models [13.33340860174857]
  Real-time dynamic path planning in complex traffic environments presents challenges, such as varying traffic volumes and signal wait times. Traditional static routing algorithms like Dijkstra and A* compute shortest paths but often fail under dynamic conditions. This paper proposes a novel approach based on causal inference for real-time dynamic path planning, balancing global and local optimality.
  arXiv  Detail & Related papers  (2024-08-26T11:19:58Z)
• Deciphering Movement: Unified Trajectory Generation Model for Multi-Agent [53.637837706712794]
  We propose a Unified Trajectory Generation model, UniTraj, that processes arbitrary trajectories as masked inputs. Specifically, we introduce a Ghost Spatial Masking (GSM) module embedded within a Transformer encoder for spatial feature extraction. We benchmark three practical sports game datasets, Basketball-U, Football-U, and Soccer-U, for evaluation.
  arXiv  Detail & Related papers  (2024-05-27T22:15:23Z)
• Trajeglish: Traffic Modeling as Next-Token Prediction [67.28197954427638]
  A longstanding challenge for self-driving development is simulating dynamic driving scenarios seeded from recorded driving logs. We apply tools from discrete sequence modeling to model how vehicles, pedestrians and cyclists interact in driving scenarios. Our model tops the Sim Agents Benchmark, surpassing prior work along the realism meta metric by 3.3% and along the interaction metric by 9.9%.
  arXiv  Detail & Related papers  (2023-12-07T18:53:27Z)
• Gradient-Based Trajectory Optimization With Learned Dynamics [80.41791191022139]
  We use machine learning techniques to learn a differentiable dynamics model of the system from data. We show that a neural network can model highly nonlinear behaviors accurately for large time horizons. In our hardware experiments, we demonstrate that our learned model can represent complex dynamics for both the Spot and Radio-controlled (RC) car.
  arXiv  Detail & Related papers  (2022-04-09T22:07:34Z)
• Dynamic Graph Convolutional Recurrent Network for Traffic Prediction: Benchmark and Solution [18.309299822858243]
  We propose a novel traffic prediction framework, named Dynamic Graph Contemporalal Recurrent Network (DGCRN) In DGCRN, hyper-networks are designed to leverage and extract dynamic characteristics from node attributes. We are the first to employ a generation method to model fine iteration of dynamic graph at each time step.
  arXiv  Detail & Related papers  (2021-04-30T11:25:43Z)
• Learning to Generate Content-Aware Dynamic Detectors [62.74209921174237]
  We introduce a newpective of designing efficient detectors, which is automatically generating sample-adaptive model architecture. We introduce a course-to-fine strat-egy tailored for object detection to guide the learning of dynamic routing. Experiments on MS-COCO dataset demonstrate that CADDet achieves 1.8 higher mAP with 10% fewer FLOPs compared with vanilla routing.
  arXiv  Detail & Related papers  (2020-12-08T08:05:20Z)
• A Multi-Agent System for Solving the Dynamic Capacitated Vehicle Routing Problem with Stochastic Customers using Trajectory Data Mining [0.0]
  E-commerce has created new challenges for logistics companies, one of which is being able to deliver products quickly and at low cost. Our work presents a multi-agent system that uses trajectory data mining techniques to extract territorial patterns and use them in the dynamic creation of last-mile routes.
  arXiv  Detail & Related papers  (2020-09-26T21:36:35Z)
• Learning Dynamic Routing for Semantic Segmentation [86.56049245100084]
  This paper studies a conceptually new method to alleviate the scale variance in semantic representation, named dynamic routing. The proposed framework generates data-dependent routes, adapting to the scale distribution of each image. To this end, a differentiable gating function, called soft conditional gate, is proposed to select scale transform paths on the fly.
  arXiv  Detail & Related papers  (2020-03-23T17:22:14Z)
• Forecasting Sequential Data using Consistent Koopman Autoencoders [52.209416711500005]
  A new class of physics-based methods related to Koopman theory has been introduced, offering an alternative for processing nonlinear dynamical systems. We propose a novel Consistent Koopman Autoencoder model which, unlike the majority of existing work, leverages the forward and backward dynamics. Key to our approach is a new analysis which explores the interplay between consistent dynamics and their associated Koopman operators.
  arXiv  Detail & Related papers  (2020-03-04T18:24:30Z)

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.