1. Introduction: Team Orientation Problem
The Team Orienteering Problem (TOP) is a combinatorial optimization problem in the field of operations research and optimization. A team of multiple individuals is asked to visit a set of locations within a given area. Each location has a score that represents the value or benefit of visiting that location. The problem goal is to determine the best route for each team member so that they visit a portion of the location individually, maximize the total score under a given time constraint, and return to the starting point. The complexity of the problem is high and heuristic algorithms are often used to solve it. It is widely used in practical fields such as tourism planning and resource allocation.
The Capacitated Team Orienteering Problem (CTOP) with capacity constraints was first proposed by Archetti et al. It is a variant of TOP that adds vehicle capacity constraints and path length constraints.
2. Problem description and terminology explanation
CTOP is defined on an undirected graph, where is the set of vertices and E is the given set of edges. Vertex 1 is called the warehouse, and the set of other vertices represents the set of customers. Every customer has service needs and profits. Each edge has a travel time. We assume that the distance satisfies the triangle inequality. In addition, we give the capacity Q and the maximum driving distance of m homogeneous vehicles. Each vehicle starts from the depot, serves multiple customers and obtains related profits, and returns to the depot.
The problem is to design m routes to maximize the total profit of vehicle collection; the total service demand of customers on a route must not exceed the vehicle capacity Q, and the total length of each route can be at most. Furthermore, a client's profits can be collected at most once.
Ejection Pool (EP, Ejection Pool): is a buffer and memory pool used to temporarily store released data or processes. In this article, the ejection pool is a priority queue containing unserved customers. In each iteration, we insert the highest priority customer from the ejection pool into an existing path. "Adaptive" indicates that the ejection pool may dynamically adjust its behavior based on certain conditions or rules.
Toggle-rule diversification: In order to better enable the search process to escape the local optimum, three measures are taken in this article, which are used when the quality of the solution obtained by multiple iterations has not improved.
used in this articleEjection pool framework with adaptive strategies and diverse mechanisms for switching between two priority rulesA new heuristic algorithm is proposed for CTOP.
3. Algorithm process
Overall approach:
ADEPT-RD method
The general process of Adaptive Ejection Pool with Toggle-Rule Diversification (ADEPT-RD) is as follows:
In each iteration, the highest priority customer in the ejection pool is inserted into a known route. At this point the route may violate capacity or maximum travel distance constraints, so we perform a local search to restore the feasibility of the route. If the search fails, we remove some customers from the route to make the route eligible, and at the same time penalize the priority value, i.e. reduce the priority, and insert these customers into the ejection pool. When it is found that the search process exceeds the maximum number of dvtenture (diversification tenure), it is deemed to have fallen into a local optimum. We reset the customer priority, perturb the current solution and change the ejection pool priority rules to prevent falling into a local optimum.
The pseudo code is as follows:
Explanation of pseudocode:
- At the beginning, an empty scheme S consisting of m empty routes (an empty path is defined as a path starting from the depot and ending immediately at the depot) and an ejection pool EP containing all customers are set up.
- Initial setting of the valuation of each customer i for (Service demand and profit ), is the profit per unit demand of the customer (or profit density).
- The main loop of the algorithm inserts the customers in the EP into the solution one by one. In each iteration, the customers in the EP are sorted according to the rule R, and then the customer i with the highest priority is selected. Next, the selected customer i is inserted into S using the Insert procedure (line 6). If the resulting solution is not feasible, fix it using the MakeFeasible procedure (line 8) to generate a feasible solution; this procedure simultaneously evicts some clients from S and puts them into EP after penalizing their priorities.
- The counter nonIter records the number of consecutive non-improvement iterations (that is, the quality of the modified solution is less than the known optimal solution). When nonIter exceeds the user-defined maximum number of dvTenure, reconfigure the algorithm and search other search domains.
- The process is repeated until all customers are ejected by EP (i.e. the optimal solution is found)/the maximum number of iterations is reached/the time limit is exceeded. Finally, a local search function called PostOpt is executed to try to improve the found best solution S*.
Explanation of subroutines
1. Insert function Insert(S,i)
In each iteration of ADEPT-RD, the customer i with the highest priority is selected from the EP and inserted into the current solution S. Add i to a randomly chosen path at a randomly chosen position in S. If the route is feasible skip this process, if not we need to try to restore feasibility using local search.
We define a cost function related to S to determine whether the path is feasible
- The total demand of all customers in path r
- length of path r
- is a coefficient that controls the relative importance of capacity constraint and travel distance constraint violations.
- If the function is equal to 0, the path is feasible
The first part of the cost function measures the violation of the capacity constraint, and the second part measures the violation of the travel distance constraint. Informally, the cost of a solution is the weighted sum of capacity and travel distance violations for all routes in the solution.
Note that the solution to S is infeasible. In this case, we use a simple local search to try to restore feasibility using three neighborhood operators: relocate operator, crossover operator, and 3-opt operator; these are commonly used operators in vehicle routing problems (VRP).
For customer i in route r, let i represent the customer immediately following i in route r, and i + represent the customer immediately following i in route r. We use notation to indicate that customer i precedes customer j in the route.
relocate operator
Delete the customer and insert customer i immediately after customer. This is achieved by removing arc segments and adding arc segments, as shown in Fig.1
crossover operator
Four customers located on two routes exchange paths (i+,...,j) and (k+,...,l). Delete arc segments and add arc segments to achieve this. As shown below
3-opt operator
This operator includes two operations. For three customers, delete the arc segments first. We can construct a new path S' in two ways:
- (1)Add arc segment
- (2)Reversal All arc segments in , add arc segments
The feasibility of the solutions obtained by the three operators can be verified in O (1) time. Let, and represent the neighborhoods of the relocate, 3-opt, and crossover operators respectively, that is, the set of all solutions that can be generated from S with a single call to the corresponding operator.
After preliminary experiments, we found that the value of when agrees well with our test data.
2.MakeFeasible function
The Insert process attempts to add a customer to the solution S to generate a feasible solution. If a feasible solution cannot be generated, the subroutine MakeFeasible is used to make the solution feasible.
The MakeFeasible procedure removes a set of customers from each path r of the solution S, making the path r feasible and minimizing it (thereby maximizing the valuation of the remaining customers). At the same time, the valuation of the removed customer is reduced and the EP is returned.
If the customer's profit density is smaller (more capacity is needed to obtain the same profit), or the customer is often rejected (it is difficult to coexist with other customers to form a viable route), the customer's valuation is lower. Therefore, our selection criteria favor reserving capacity for customers that are highly profit-intensive and easy to handle.
Remove customer's selection
For example, let (1, 2, 3, 4, 5) be the customers in the infeasible path r, sorted in increasing order of valuation. Initialize priority queue PQ = ( { 1 } , { 2 } , { 3 } , { 4 } , { 5 }). In the first iteration, we remove the first element (i.e. { 1 }) and check if the removal of node 1 causes r to become feasible. If not, we add {1, 2}, {1, 3}, {1, 4} and {1, 5} to the PQ and continue. If the priority queue PQ is implemented as a heap, each iteration requires O (log n) times, where n is the number of customers in the route.
3. Diversification process
A successful local search process requires a way to escape the local optimum. In the ADEPT-RD method, when we find that the process is likely to fall into a local optimum, we use three measures to spread out the search neighborhood.
-
First, reset the valuations of all customers to their profit densities; reset all valuations vi to the profit density of customer i, that is , eliminating the impact of the previous iteration process on the valuation, and reinitializing the ejection pool.
-
Second, change the ejection pool priority rules;
- Rule RA (default rule): This rule sorts customers in order of decreasing valuation and, in the case of a tie, in order of decreasing profit value. The disadvantage is that the profit density is smaller ( ) are unlikely to be plugged into the solution. Assume that the current solution consists of two routes r1 and r2, with loads 47 and 48 respectively, and vehicle capacity Q = 50. In this case, only customers with a requirement of at most 3 can be inserted into the solution without evicting any existing customers. Customers with lower valuations and lower profits are ignored by the algorithm.
- Rule RB: Sort customers using first-in-first-out strategy. When clients are ejected from the solution, they are placed at the end of the ejection pool. If multiple customers are ejected, insert them into the ejection pool in random order. The main purpose of this rule is to complement the sorting rule RA by increasing the chance of considering customers with relatively low profit density. Since these customers are more likely to be inserted at the end of the ejection pool, they are more likely to be re-evaluated for inclusion in solutions.
-
Third, randomly perturb the solution. Perform random perturbations on the current solution S. The perturbation process randomly selects the operator used in the Insert process, and then selects a solution S'. If S' is feasible, replace S; otherwise discard. The pseudo code of the perturbation process is as follows:
4.PostOpt function (post-optimization function)
In the final stage, the optimal solution S* is further improved through the Post-optimization process. For each customer i in EP, the PostOpt process considers each path r in the solution in turn. Find every customer subset in r whose total profit is less than. The subsets form a set, which are arranged in order of increasing total profit. After deleting the customer, check whether i can be inserted into r.
Parameter settings
dvTenure (diversification tenure) is set to, where n is the number of customers, m is the number of vehicles, Q is the vehicle capacity, and is the maximum driving distance of the vehicle.
The number of iterations maxIter is set to 10dvTenure.
4. Algorithm advantages
The algorithm experimental results show that in the step of reducing the valuation of ejected customers in the makefeasible function, the solution obtained under the adaptive mechanism () is better than the solution obtained by disabling the adaptive mechanism (). The solution obtained using the two sorting rules of RA and RB is better than the solution obtained by only one priority rule. The solution obtained by the perturbation process is better than the solution without perturbation process.
This article also compares ADEPT-RD with the branch pricing algorithm (an exact algorithm), VNS (variable domain search algorithm), TSF (tabu search algorithm that only considers feasible solutions), and TSA (tabu search algorithm that considers admissible solutions). Results ADEPT-RD improved the results of VNS by 0.095%, the results of TSF by 0.215%, and the results of TSA by 0.284%. The time spent is much better than the other three algorithms (exact algorithm). (see table1)
At the same time, the number of optimal solutions found by the four heuristic methods was counted. ADEPT-RD obtained the optimal solution in 120 test instances, which is far better than the other three heuristic algorithms. (see table2)
5. Code sharing
This article has a large amount of code. For specific reference papers, calculation examples and code downloads, please go to the message area.
When running the code, you need to set the command line parameter array args in the main method in advance and enter the parameters in the IDE, such as Data/p03.cri result/p03-2-100-100.cri 2 100.0 100.0 1000 30.0 3123 or enter the parameters on the command line (p03-2-100-100.cri means file name - number of vehicles - vehicle capacity - maximum driving distance)
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);
}//Determine whether the args[] parameter is configured correctly
// Parse command line parameters
String input_file=args[0];//Input file path
String output_file=args[1];//Output file path
int m=Integer.parseInt(args[2]);//Number of vehicles
double Q=Double.parseDouble(args[3]);//Maximum capacity of each vehicle
double Tmax=Double.parseDouble(args[4]);//The longest distance traveled
int iterations=Integer.parseInt(args[5]);//Number of iterations
double time=Double.parseDouble(args[6])*1000000000;// parameter time, unit converted to nanoseconds
int seed=Integer.parseInt(args[7]);//Random seed
...
...
}
Core code AlgFinalEx class analysis The three internal classes Com, Com2 and Com3 are used for comparison and sorting in the priority queue. The definitions of these classes are used to support some strategies in the algorithm. The Struct class contains the path (Route) and the list of paths to be inserted. The EI method and EI2 method correspond to RA and RB rules respectively. RB uses queue to implement the FIFO principle, which will not be explained in detail here.
public class AlgFinalEx {
...
...
public Solution squeeze(Solution solution, int id) throws IOException{
//Randomly select a path and location to insert a customer, and perform a local search to optimize the solution
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){
//Let some users in the path be randomly replaced to introduce diversity
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){
//Try to insert the customer directly into the existing path, if possible insert it.
//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){
// Mark the customers who are already in the solution, iset is used to store the customer index of the removed customer subset
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;
}
//Priority queue is used to store customers who are not in the solution
PriorityQueue<Com3> qpool=new PriorityQueue<Com3>();
// Initialize the queue and add customers who are not in the solution to the queue
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]));
}
// Try all cases of inserting customers through greedy strategy
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>();
// Initialize the queue and add the position where the customer may insert into the queue.
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();
//Delete the customer to make room for insertion
for(int j=iset.size()-1;j>=0;j--)
troute.Remove(iset.get(j));
troute.Update();
// Check capacity constraints
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){
// Check the profit gain caused by replacing this customer
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;
}
// Check time window constraints
// Find the insertion position
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;
}
//Change iset to include pop-up customers from other routes
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)));
//Insert customer at calculated position
troute.Insert(insert_place+1, id);
troute.Update();
// Create a new solution to update route configuration
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();//Create a backup of the best solution
//ArrayList<Solution> solution_pool=new ArrayList<Solution>();
ArrayList<Com2> pool=new ArrayList<Com2>();
Data data=solution.GetData();
is_reserve = false; // The initialization flag is false to retain the solution.
int time = 0; // Initialize the number of iterations
int u_time = 0; // Initialize the number of times to perform local searches
int r_time = 0; // Initialize the number of times to perform the solution-preserving operation
double thresh_hold = 0; // Initialization threshold
//intialize the pool
for(int i=0;i<iset.size();i++){
//check the feasibility
int id=iset.get(i);//Get the current customer 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);//Sort objects in the pool
int indicator=0;
int last_improve=0;
data.noimprove_iterations=0; // Initialize the number of consecutive iterations without improvement
while(pool.isEmpty()==false&&++time<data.max_iteration){
double t=gettime.getCpuTime();
if(t-data.start_time>data.running_time)
break;//If the running time exceeds the limit, end the search
//Output output=new Output();
int id=pool.get(0).id;//Get the first customer ID in the pool
pool.remove(0);//Remove the first customer in the pool
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;
}
// If the solution is not feasible, try insertion and optimization through the EI2 method
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);//Update path
for(int j=0;j<result.set.size();j++){
int tid=result.set.get(j);
value[tid]/=data.adapter;
pool.add(new Com2(tid));//Put the customers removed from the queue into 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);//Perform diversified operations
}
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);
// If the profit of the final solution is less than the value of the optimal solution, try to intensify the optimization through the intensify method, corresponding to the postopt method
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;
}
...
}
To download the code related to this article, please go to the message area
Reference papers：
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.
Machine-translated from the Chinese original 论文拾萃｜基于规则切换多样化的自适应弹射池方法解决带容量约束的团队定向问题(附Java代码) (published 2023-09-18). WeChat original ↗