解决基于遗传算法的最小-最大集群旅行销售员问题
Xiaoguang Bao1, Guojun Wang1, Lei Xu1
1College of Information Technology, Shanghai Ocean University, Shanghai 201306, China.
这项研究引入了一种新的两阶段遗传算法,以解决最小至最大集群旅行销售员问题 (MMCTSP). 该方法有效地确定了访问集群顶点的最佳路线,最大限度地降低了旅游重量.
科学领域:
- 运营研究 运营研究
- 计算机科学 计算机科学
- 组合优化的优化.
背景情况:
- 最少-最大集群旅行销售员问题 (MMCTSP) 是经典旅行销售员问题 (TSP) 的复杂变体.
- 它涉及将图的顶点划分为集群,并找到在分配的集群中连续访问所有顶点的游览.
- 目标是尽量减少所有销售人员的最大巡回重量.
研究的目的:
- 开发一个有效的算法来解决MMCTSP.
- 在集群的TSP场景中,尽量减少最大的旅游重量.
- 为复杂的路由问题提供强大的解决方法.
主要方法:
- 一种利用遗传算法的两阶段解决方法.
- 阶段1:为每个集群解决一个TSP,以确定集群内部访问顺序.
- 第二阶段:模型集群作为节点,构建一个MTSP,并应用基于分组的遗传算法来进行集群间的分配和排序.
主要成果:
- 拟议的两阶段遗传算法有效地解决了MMCTSP.
- 该算法在各种实例尺度上展示了卓越的解决方案质量.
- 它展示了良好的计算性能和解决方案效率.
结论:
- 开发的算法为解决MMCTSP提供了一种有效的方法.
- 与现有的方法相比,它为复杂的路由问题提供了改进的解决方案.
- 这种方法对物流和运营研究中的实际应用有希望.
更多相关视频
12:27Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations
Published on: February 15, 2017
07:35Selecting Multiple Biomarker Subsets with Similarly Effective Binary Classification Performances
Published on: October 11, 2018
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Cluster Sampling Method
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
Maxwell-Boltzmann Distribution: Problem Solving
This distribution function f(v) is defined by saying that the expected number N (v1,v2) of particles with speeds between v1 and v2 is given by
Distributed Loads: Problem Solving
Genetic Drift
Collisions in Multiple Dimensions: Problem Solving
A small car of mass 1,200 kg traveling east at 60 km/h collides at an intersection with a truck of mass 3,000 kg traveling due north at 40 km/h. The two vehicles are locked together. What is the...
