1.引言：团队定向问题
团队定向问题(Team Orienteering Problem,TOP)是运筹学和优化领域的一个组合优化问题。要求一个由多个个体组成的团队访问给定区域内的一组地点。每个地点都有一个分数，表示访问该地点的价值或收益。问题目标是确定每个团队成员的最佳路线，使他们分别访问一部分地点，在给定的时间约束下最大化总分数，并返回到起始点。问题复杂度高，常使用启发式算法解决。在旅游规划、资源分配等实际领域有广泛应用。
带容量约束的团队定向问题(Capacitated Team Orienteering Problem,CTOP)最早由Archetti等人提出，是TOP的变种，增添了车辆容量限制和路径长度约束。
2.问题描述及名词解释
CTOP定义在一个无向图上，其中是顶点的集合，E是给定的边的集合。顶点1称为仓库，其余顶点的集合表示顾客的集合。每个顾客，都有服务需求和利润。每条边都有一个旅行时。我们假设距离满足三角不等式.此外，我们给出了m辆同质车辆的容量Q和最大行驶距离。每辆车从车辆段出发，服务多个客户并获取相关利润，返回车辆段。
问题是设计m条路线使得车辆收集的总利润最大化；一条路径上顾客的总服务需求不得超过车辆容量Q，且每条路径的总长度最多可以达到。此外，一个客户的利润最多可以被收集一次。
弹射池(EP,Ejection Pool):是一个缓冲区和内存池，用于临时存储被释放的数据或进程。在本文中，弹射池是一个包含未服务客户的优先级队列。在每次迭代中，我们将来自弹射池的最高优先级客户插入到一个现有的路径中。"自适应"表明弹射池可能会根据某些条件或规则动态调整其行为。
规则切换多样化(toggle-rule diversification):为了更好地让搜索过程逃离局部最优，本文中采取了三种措施，在连续多次迭代得到的解的质量没有改善时使用。
本文中使用带有自适应策略和两个优先级规则之间切换的多样化机制的弹射池框架为CTOP提出了一个新的启发式算法。
3.算法流程
总体方法：
ADEPT-RD方法
规则切换多样化自适应弹射池(Adaptive Ejection Pool with Toggle-Rule Diversification,ADEPT-RD)的大致流程如下：
每次迭代中，将弹射池中优先级最高的客户插入到一条已知路线中。此时路线可能违反容量或最大行进距离约束，因此我们进行局部搜索，恢复路线的可行性。如果搜索失败，我们就从路线中去除一些客户使路线符合条件，同时惩罚优先级值，即降低优先级，将这些客户插入弹射池中。当发现搜索过程超过最大次数dvtenture（diversification tenure）时，即认定为陷入局部最优，我们重置客户优先级，扰动当前解并改变弹射池优先级规则以防止陷入局部最优。
伪代码如下：
伪代码的解释：
- 开始时，设置一个由m条空路线(空路径定义为从车辆段出发并立即在车辆段结束的路径)组成的空方案S和包含所有客户的弹射池EP。
- 初始设定每个客户i的估值 为 (服务需求量 和利润 )，为客户(或利润密度)的单位需求量的利润。
- 算法的主循环将EP中的客户逐个插入到解中。在每次迭代中，EP中的客户按照规则R进行排序，然后选择优先级最高的客户i。接下来，利用Insert过程(第6行)将选择的客户i插入到S中。如果得到的解不可行，使用MakeFeasible过程(第8行)修复它以生成一个可行解；这个过程同时将一些客户从S中驱逐出来，并在惩罚他们的优先级后将他们放入EP中。
- 计数器nonIter记录连续非改进迭代次数(即修改后的解的质量小于已知的最优解)。当nonIter超过用户定义的最大次数dvTenure时，重新配置算法，搜索其他搜索域。
- 重复过程，直至所有客户都被EP弹出（即找到最优解）/达到最大迭代次数/超过时间限制。最后执行一个名为PostOpt的局部搜索函数，试图改进找到的最佳解S*。
对子程序的解释
1.插入函数 Insert(S,i)
ADEPT-RD的每次迭代中，从EP中选择优先级最高的客户i并将其插入到当前解S中。在S中的一个随机选择的位置上将i添加到一个随机选择的路径中。如果路线可行跳过该过程，如果不可行，我们需要尝试使用局部搜索恢复可行性。
我们定义一个有关S的成本函数来判断路径是否可行
- 路径r中所有顾客的总需求
- 路径r的长度
- 是控制容量约束和出行距离约束违反相对重要性的系数
-
函数等于0，则路径可行
成本函数的第一部分度量了容量约束违反量，第二部分度量了出行距离约束违反量。通俗地说，一个解决方案的成本是解决方案中所有路线的容量和旅行距离违规行为的加权和。
注意到意味着解S是不可行的。在这种情况下，我们使用一个简单的局部搜索，使用relocate operator，crossover operator，3-opt operator三个邻域算子来尝试恢复可行性;这些都是车辆路径问题(VRP)中常用的算子。
对于路线r中的顾客i，令i表示在路线r中紧接着i的顾客，i +表示在路线r中紧接着i的顾客。我们用记号表示路线中顾客i先于顾客j。
relocate operator
删除顾客，并在顾客后立即插入顾客i。通过去除弧段，添加弧段来实现，如图Fig.1所示
crossover operator
位于两条路线的四位顾客，交换路径(i+,...,j)和(k+,...,l)。删除删除弧段和添加弧段来实现。如下图所示
3-opt operator
该算子包括两个操作。对于三个顾客，先删除弧段。我们可以可以通过两种方式构造新的路径S'：
- (1)添加弧段
- (2)反转 中的所有弧段，添加弧段
三个算子所得解的可行性均可在O ( 1 )时间内得到验证。令，和分别表示relocate、3 - opt和crossover算子的邻域，即一次调用相应算子就可以从S中产生的所有解的集合。
经过初步试验，我们发现时的值与我们的测试数据吻合得很好。
2.MakeFeasible函数
Insert过程尝试在解S的基础上增加一个客户来产生可行解，如果无法产生可行解，则使用子程序MakeFeasible来使解可行。
MakeFeasible过程从解S的每条路径r中移除一组客户，使路径r可行，并且取最小(从而使剩余客户的估值最大化)。同时降低被移除顾客的估值，放回EP
若客户的利润密度较小(需要更多的容量来获取相同的利润)，或者客户经常被拒绝(难以与其他客户共存形成可行路线)，客户的估值较低。因此，我们的选择标准倾向于为利润密度高且易于处理的客户预留容量。
移除顾客的选取
例如，令( 1、2、3、4、5)为不可行路径r中的顾客，按照递增的估值顺序排序。初始化优先级队列PQ = ( { 1 } , { 2 } , { 3 } , { 4 } , { 5 })。在第一次迭代中，我们删除第一个元素(即{ 1 })，并检查节点1的移除是否导致r变得可行。如果不是，我们将{ 1，2 }，{ 1，3 }，{ 1，4 }和{ 1，5 }添加到PQ中并继续。如果将优先级队列PQ实现为堆，则每次迭代需要O ( log n )次，其中n为路由中的客户数。
3.多样化过程
成功的局部搜索过程需要一种方法来逃离局部最优。在ADEPT - RD方法中，当我们发现该过程很可能陷入局部最优时，我们使用三种措施来分散搜索邻域。
-
第一，将所有客户的估值重置为其利润密度；将所有估值vi重置为客户i的利润密度，即 ，消除了之前的迭代过程对估值的影响，并重新初始化弹射池。
-
第二，改变弹射池优先规则；
- 规则RA（默认规则）：该规则按照估值递减的顺序对客户进行排序，并在出现并列情况时按照利润价值递减的顺序排序。缺点是利润密度较小( )的客户不太可能被插入到解决方案中。假设当前解由两条路线r1和r2组成，负载分别为47和48，车辆容量Q = 50。在这种情况下，只有需求最多为3的客户才能被插入到解决方案中，而不会驱逐任何现有的客户。估值和利润较低的顾客会被算法忽视。
- 规则RB：使用先进先出策略对客户进行排序。当客户从解决方案中被弹出时，它们被放置在弹射池的末尾。如果有多个客户被弹出，则以随机顺序将它们插入到弹射池中。此规则的主要目的是通过增加考虑具有相对较低利润密度的客户的机会，来补充排序规则RA。由于这些客户更有可能被插入到弹射池的末尾，它们更有可能被重新评估，以便纳入解决方案。
-
第三，随机扰动解。对当前解S进行随机扰动。扰动过程随机选用Insert过程中使用的算子，然后选择一个解S'。如果S'可行，则替换S；否则丢弃。扰动过程伪代码如下：
4.PostOpt函数（后优化函数）
最后阶段，通过Post-optimization过程进一步改进最优解S*。对于EP中每个顾客i，PostOpt过程依次考虑解中每条路径r。找出r中每一个总利润小于的顾客子集。子集构成集合，中按照总利润递增的顺序排列。删除中的顾客后，检查i是否可以插入到r中。
参数设置
dvTenure(diversification tenure)设置为，其中n为顾客数量，m为车辆数量，Q为车辆容量，为车辆最大行驶距离。
迭代次数maxIter设置为10dvTenure。
4.算法优势
算法实验结果显示，makefeasible函数中降低被弹出顾客估值的步骤中，在自适应机制()下得到的解优于禁用自适应机制()得到的解使用RA,RB两个排序规则得到的解优于只有一个优先级规则的解有扰动过程得到的解优于无扰动过程的解
本文还将ADEPT-RD与分枝定价算法(一种精确算法)、VNS(变领域搜索算法)、TSF(只考虑可行解的禁忌搜索算法)、TSA(考虑可容许解的禁忌搜索算法)对比。结果ADEPT-RD将VNS的结果提高了0.095%，将TSF的结果提高了0.215%，将TSA的结果提高了0.284%。所花费时间远优于其他三种算法(精确算法)。（见table1）
同时统计了4种启发式方法找到的最优解数量，ADEPT-RD在120个测试实例中都获得了最优解，远远优于其他三种启发式算法。（见table2）
5.代码分享
本文代码量较大，具体参考论文、算例和代码的下载请移步留言区。
运行代码时需提前设置main方法中命令行参数数组args，在IDE中输入参数，例如 Data/p03.cri result/p03-2-100-100.cri 2 100.0 100.0 1000 30.0 3123或在命令行输入参数(p03-2-100-100.cri的含义为文件名称-车辆数-车辆容量-最大行驶距离)
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
//para the parameters
if(args.length!=8){
System.out.println("input error!");
System.exit(0);
}//判断args[]参数是否配置正确
// 解析命令行参数
String input_file=args[0];// 输入文件路径
String output_file=args[1];// 输出文件路径
int m=Integer.parseInt(args[2]);//车辆数
double Q=Double.parseDouble(args[3]);//每辆车最大容量
double Tmax=Double.parseDouble(args[4]);//行驶最远距离
int iterations=Integer.parseInt(args[5]);//迭代次数
double time=Double.parseDouble(args[6])*1000000000;// 参数 time，单位转换为纳秒
int seed=Integer.parseInt(args[7]);//随机种子
...
...
}
核心代码AlgFinalEx类解析 三个内部类Com、Com2和Com3用于在优先队列中进行比较排序。这些类的定义用于支持算法中的一些策略。Struct类包含了路径（Route）和要插入路径的列表。EI方法和EI2方法分别对应RA和RB规则，RB采用queue实现FIFO原则，此处不做详细解释。
public class AlgFinalEx {
...
...
public Solution squeeze(Solution solution, int id) throws IOException{
//随机选择一个路径和位置来插入一个客户，并进行局部搜索来优化解
Random random=new Random(solution.GetData().seed);
int rid=random.nextInt(solution.GetSize());
Route route=solution.GetRoute(rid);
int place=random.nextInt(route.GetSize()-1)+1;
route.Insert(place, id);
route.Update();
solution.Update();
LocalSearch ls=new LocalSearch(solution);
solution=ls.Search(solution);
return (Solution)solution.clone();
}
public void flash(Solution solution, ArrayList<Com2> pool){
//令路径中一部分用户被随机替换，引入多样性
value[0]=0;
for(int i=1;i<=data.N;i++)
value[i]=data.p[i]/Math.pow(data.q[i],1);
value[data.N+1]=0;
Purturb purturb=new Purturb();
purturb.Dversify(solution, data.purturb_time);
}
public boolean direct_insert(Solution solution, int id){
//尝试直接将顾客插入现有路径，如果可行则插入。
//scan for a feasible place to insert the customer
for(int i=0;i<solution.GetSize();i++){
Route route=solution.GetRoute(i);
//check the capacity constraint
if(route.GetLoad()+data.q[id]>data.Q)
continue;
//find the minimum cost insert place
double min_cost=Double.MAX_VALUE;
int insert_place=0;
for(int j=0;j<route.GetSize()-1;j++){
int pre=route.GetCustomer(j);
int next=route.GetCustomer(j+1);
double cost=route.GetLength()+data.t[pre][id]+
data.t[id][next]-data.t[pre][next];
if(cost<min_cost){
min_cost=cost;
insert_place=j;
}
}
//check Tmax constraint
if(min_cost<data.Tmax){
route.Insert(insert_place+1, id);
route.Update();
solution.SetRoute(i, route);
solution.Update();
return true;
}
}
return false;
}
...
...
public Solution intensify(Solution solution){
// 标记已在解决方案中的客户，iset用于存储被移除客户子集的客户索引
int[] check=new int[data.N+1];
for(int i=0;i<solution.GetSize();i++){
Route route=solution.GetRoute(i);
for(int j=1;j<route.GetSize()-1;j++)
check[route.GetCustomer(j)]=1;
}
// 优先队列用于存储未在解决方案中的客户
PriorityQueue<Com3> qpool=new PriorityQueue<Com3>();
// 初始化队列，将未在解决方案中的客户加入队列
for(int i=1;i<=data.N;i++){
if(check[i]==1)
continue;
else if(direct_insert(solution,i)==false)
qpool.add((Com3) new Com3(i,data.p[i]));
}
// 通过贪心策略尝试所有插入客户的情况
while(qpool.isEmpty()==false){
int id=qpool.poll().id;
for(int i=0;i<solution.GetSize();i++){
Route route=solution.GetRoute(i);
PriorityQueue<Com> queue=new PriorityQueue<Com>();
// 初始化队列，将客户可能插入的位置加入队列
for(int j=1;j<route.GetSize()-1;j++){
if(data.p[route.GetCustomer(j)]>=data.p[id])
continue;
ArrayList<Integer> temp=new ArrayList<Integer>();
temp.add(j);
queue.add((Com) new Com(temp,data.p[route.GetCustomer(j)]));
}
while(queue.isEmpty()==false){
Com com=queue.poll();
ArrayList<Integer> iset=com.set;
Collections.sort(iset);
Route troute=(Route) route.clone();
// 删除客户，腾出位置以供插入
for(int j=iset.size()-1;j>=0;j--)
troute.Remove(iset.get(j));
troute.Update();
// 检查容量约束
if(troute.GetLoad()+data.q[id]>data.Q){
for(int j=iset.get(iset.size()-1);j<route.GetSize()-1;j++){
if(iset.contains(j)==false){
// 检查替换该客户带来的利润增益
if(com.profit+data.p[route.GetCustomer(j)]>=data.p[id])
continue;
ArrayList<Integer> copy=(ArrayList<Integer>) iset.clone();
copy.add(j);
queue.add((Com)new Com(copy,com.profit+data.p[route.GetCustomer(j)]));
}
}
continue;
}
// 检查时间窗口约束
// 查找插入位置
double min_cost=Double.MAX_VALUE;
int insert_place=-1;
for(int j=0;j<troute.GetSize()-1;j++)
{
int now=troute.GetCustomer(j);
int next=troute.GetCustomer(j+1);
double length=troute.GetLength()+data.t[now][id]+data.t[id][next]-data.t[now][next];
if(length<min_cost){
min_cost=length;
insert_place=j;
}
}
if(min_cost>=data.Tmax){
for(int j=iset.get(iset.size()-1);j<route.GetSize()-1;j++){
if(iset.contains(j)==false){
if(com.profit+data.p[route.GetCustomer(j)]>=data.p[id])
continue;
ArrayList<Integer> copy=(ArrayList<Integer>) iset.clone();
copy.add(j);
queue.add((Com)new Com(copy,com.profit+data.p[route.GetCustomer(j)]));
}
}
continue;
}
// 改变iset，包含其他路线弹出的客户
ArrayList<Integer> ejection=new ArrayList<Integer>();
while(qpool.isEmpty()==false)
ejection.add(qpool.poll().id);
for(int j=0;j<iset.size();j++)
ejection.add(route.GetCustomer(iset.get(j)));
// 在计算的位置插入客户
troute.Insert(insert_place+1, id);
troute.Update();
// 创建一个新解决方案，以更新路线配置
Solution new_solution=(Solution) solution.clone();
new_solution.SetRoute(i, troute);
new_solution.Update();
return new_solution;
}
}
}
return null;
}
public Solution search(Solution solution, ArrayList<Integer> iset) throws IOException{
GetTime gettime=new GetTime();
Solution best_solution=(Solution) solution.clone();// 创建最优解的备份
//ArrayList<Solution> solution_pool=new ArrayList<Solution>();
ArrayList<Com2> pool=new ArrayList<Com2>();
Data data=solution.GetData();
is_reserve = false; // 初始化是否为保留解的标志为false
int time = 0; // 初始化迭代次数
int u_time = 0; // 初始化执行局部搜索的次数
int r_time = 0; // 初始化执行保留解操作的次数
double thresh_hold = 0; // 初始化阈值
//intialize the pool
for(int i=0;i<iset.size();i++){
//check the feasibility
int id=iset.get(i);//获取当前客户id
if(data.q[id]>data.Q||data.t[0][id]+data.t[id][0]>data.Tmax)
continue;
pool.add((Com2)new Com2(id));
}
Collections.sort(pool);//对pool中对象进行排序
int indicator=0;
int last_improve=0;
data.noimprove_iterations=0;// 初始化连续无改进的迭代次数
while(pool.isEmpty()==false&&++time<data.max_iteration){
double t=gettime.getCpuTime();
if(t-data.start_time>data.running_time)
break;// 如果运行时间超过了限制，则结束搜索
//Output output=new Output();
int id=pool.get(0).id;// 获取池子中的第一个顾客ID
pool.remove(0);// 移除池子中的第一个顾客
solution=squeeze(solution,id);
if(solution.isFeasible()==true){
if(solution.GetProfit()>best_solution.GetProfit()){
best_solution=(Solution) solution.clone();
System.out.println(best_solution.GetProfit());
data.best_solution_time=gettime.getCpuTime();
data.optimal_iteration=time;
if(time-last_improve>data.noimprove_iterations)
data.noimprove_iterations=time-last_improve;
last_improve=time;
if(data.A1==true)
thresh_hold=best_solution.GetProfit();
}
continue;
}
// 如果解不可行，则尝试通过EI2方法进行插入和优化
for(int i=0;i<solution.GetSize();i++){
Route route=solution.GetRoute(i);
if(route.isFeasible()==true)
continue;
Struct result=EI2(route);
solution.SetRoute(i, result.route);// 更新路径
for(int j=0;j<result.set.size();j++){
int tid=result.set.get(j);
value[tid]/=data.adapter;
pool.add(new Com2(tid));//将被队列剔除的顾客放入EP中
}
}
solution.Update();
if(solution.GetProfit()>thresh_hold){
u_time=0;
r_time=0;
thresh_hold=solution.GetProfit();
}
else{
u_time++;
r_time++;
}
//update the best solution
if(solution.GetProfit()>best_solution.GetProfit()){
best_solution=(Solution) solution.clone();
System.out.println(best_solution.GetProfit());
data.best_solution_time=gettime.getCpuTime();
data.optimal_iteration=time;
if(time-last_improve>data.noimprove_iterations)
data.noimprove_iterations=time-last_improve;
last_improve=time;
}
//update the capacity_reserve
capacity_reserve=0;
for(int i=0;i<solution.GetSize();i++){
Route route=solution.GetRoute(i);
if(capacity_reserve<data.Q-route.GetLoad())
capacity_reserve=data.Q-route.GetLoad();
}
if(u_time==data.flash_tenure){
u_time=0;
flash(solution,pool);//执行多样化操作
}
if(r_time==data.reserve_tenure){
r_time=0;
indicator++;
if(indicator%2==0){
is_reserve=false;
capacity_reserve=0;
}
else if(indicator%2==1){
is_reserve=true;
}
}
if(data.RB==true&&indicator%2==1){
capacity_reserve=0;
}
Collections.sort(pool);
}
best_solution.Update();
if(best_solution.GetProfit()<data.optimal_value){
//for(int i=0;i<solution_pool.size();i++){
//Solution new_solution=intensify(solution_pool.get(i));
Solution new_solution=intensify(best_solution);
// 如果最终解的利润小于最优解的值，尝试通过intensify方法进行强化优化，对应postopt方法
if(new_solution!=null&&new_solution.GetProfit()>best_solution.GetProfit()){
best_solution=(Solution) new_solution.clone();
System.out.println("intisify: "+best_solution.GetProfit());
}
//}
}
return best_solution;
}
...
}
欲下载本文相关代码，请移步留言区
参考论文：
Zhixing Luo, Brenda Cheang, Andrew Lim, Wenbin Zhu,An adaptive ejection pool with toggle-rule diversification approach for the capacitated team orienteering problem,European Journal of Operational Research,Volume 229, Issue 3,2013,Pages 673-682.ISSN 0377-2217.
转载自久章智能（微信公众号，久章智能于 2023-09-11 转载），内容保持原貌，版权归原作者及原账号所有。阅读原文 ↗