dus*_*zma 27 algorithm heuristics traveling-salesman
我有一个问题,已经有效地减少到多个推销员的旅行推销员问题.我有一个从初始位置访问的城市列表,并且必须访问所有销售人员数量有限的城市.
我试图想出一个启发式,并想知道是否有人可以伸出援助之手.例如,如果我有20个城市有2个推销员,我想采取的方法是两步法.首先,将20个城市随机划分为10个城市,每个城市为2个销售人员,我会发现每个城市的旅行,好像它是独立的几次迭代.之后,我想交换或指定一个城市给另一个推销员并找到旅游.实际上,它是一个TSP,然后是最小的完工时间问题.问题在于它太慢了,交换或分配城市的邻里生成很难.
任何人都可以就如何改进上述内容提出建议吗？
编辑:
每个城市的地理位置都是已知的,销售人员在同一个地方开始和结束.目标是最小化最大行程时间,使这种最小完工时间问题.因此,例如,如果salesman1需要10个小时而salesman2需要20个小时,则最长行程时间为20个小时.
ysd*_*sdx 10
TSP是一个难题.多TSP可能更糟糕.我不确定你能用这样的特殊方法找到好的解决方案.你尝试过元启发式方法吗？我首先尝试使用Cross Entropy方法:它不应该太难用于你的问题.否则寻找通用算法,蚁群优化,模拟退火......
参见Boer等人的"交叉熵方法教程".他们解释了如何在TSP上使用CE方法.对您的问题进行简单的调整可能是为每个推销员定义一个不同的矩阵.
您可能希望假设您只想在销售人员之间找到城市的最佳分区(并将每个销售员的最短旅行委托给经典的TSP实施).在这种情况下,在交叉熵设置中,您考虑每个城市Xi在推销员A:P(A中的Xi)= pi中的概率.你在p =(p1,... pn)的空间工作.(我不确定它是否能很好地工作,因为你必须解决许多TSP问题.)