Balanced dynamic multiple travelling salesmen: algorithms and continuous approximations
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%.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Solving The Travelling Salesmen Problem using HNN and HNN-SA algorithms
In this case study, the renowned Travelling Salesmen problem has been studied. Travelling Salesman problem is a most demanding computational problem in Computer Science. The Travelling Salesmen problem has been solved by…
ScheduleNet: Learn to Solve MinMax mTSP Using Reinforcement Learning with Delayed Reward
Combinatorial Optimization (CO) problems are theoretically challenging yet crucial in practice. Numerous works used Reinforcement Learning (RL) to tackle these CO problems. As current approaches mainly focus on single-wo…
Combinatorial OptimizationGraph Neural Networkreinforcement-learningReinforcement Learning (RL)An Effective Iterated Two-stage Heuristic Algorithm for the Multiple Traveling Salesmen Problem
The multiple Traveling Salesmen Problem (mTSP) is a general extension of the famous NP-hard Traveling Salesmen Problem (TSP), that there are m (m > 1) salesmen to visit the cities. In this paper, we address the mTSP with…
Dynamic Island Model based on Spectral Clustering in Genetic Algorithm
How to maintain relative high diversity is important to avoid premature convergence in population-based optimization methods. Island model is widely considered as a major approach to achieve this because of its flexibili…
ClusteringDiversityApplication of Multi-core Parallel Programming to a Combination of Ant Colony Optimization and Genetic Algorithm
This Paper will deal with a combination of Ant Colony and Genetic Programming Algorithm to optimize Travelling Salesmen problem (NP-Hard). However, the complexity of the algorithm requires considerable computational time…