Inverse Vertex Obnoxious 1-center Location Problem

Location problem is one of the classic problems in operations research,which is widely used in production and life,logistics and even military affairs.In this paper,we mainly study the inverse vertex obnoxious 1-center location problem（IVO1C）,which is described as follows.Given an undirected and weighted connected graph G=（V,E,l,c,d）and one of its vertices s,we adjust the edge weights of graph G with the least cost under different norms,so that ver-tex s becomes the obnoxious 1-center of graph G.This paper specifically studies the inverse vertex obnoxious 1-center location problem under the weighted l_∞norm and the weighted bot-tleneck type Hamming distance.For each problem,two cases are considered:the edge weight adjustment with upper and lower bound constraint or not.For the problem（IVO1C_∞）,we first solve the monotonically increasing cost function cor-responding to the adjacent edge of vertex s and the monotonically decreasing cost function corresponding to the adjacent edges of the remaining vertex v_i,then calculate the unique inter-section of the above cost functions respectively.Therefore,the problem（IVO1C_∞）is solved by finding the maximum value of the ordinate of the intersection point.For the bounded problem（BIVO1C_∞）,similarly,first solve the monotonically increasing cost function corresponding to the adjacent edges of vertex s and the monotonically decreasing cost function corresponding to the adjacent edges of the remaining vertices v_i.Since the adjustment amount of edge weight is limited by the upper and lower bounds,the cost function may have a breakpoint,which makes it impossible to directly calculate the intersection point,instead of solving the transcendence point of the above cost function.The bounded problem（BIVO1C_∞）is solved by finding the maxi-mum value of the ordinate of the transcendental point.Finally,for the above two problems,we propose an algorithm in O（n³）time respectively,the n is the number of vertices in the graph G.Based on the above two algorithms,specific examples are given to illustrate the running process of the algorithm.For the problem(IVO1C_BH)and the bounded problem(BIVO1C_BH)under weighted bot-tleneck type Hamming distance,the problem(IVO1C_BH)must be feasible,when the bounded problem(BIVO1C_BH)is feasible,the optimal value C^*must be a certain element of the cost vector c or d.After reordering the values in c,d non-decreasingly,we use a binary search method.In each iteration,for a given specific cost,judge whether the problem is feasible under the cost.If it is feasible,seek a feasible solution with a smaller target value in the left half of the search interval,otherwise continue to search for the optimal value in the right half of the search interval.The above process iterates until there is only one value in the search interval,and this value is the optimal value.When the edge weight adjustment is limited by the upper and lower bounds,it may cause the problem infeasible at this time,but it is feasible in the un-bounded case.Finally,for the above two problems,we propose an algorithm in O（m log m）and O（n²log m）time respectively,the m is the number of edges in the graph G.Based on the above two algorithms,specific examples are given to illustrate the running process of the algorithm.At the end of the paper,numerical experiments are carried out for the four algorithms respectively.By setting different number of vertices and edges,6 types of random graphs are obtained,300 random instances are generated on each type of random graph and the average,minimum and maximum CPU time are recorded.After analyzing numerical results,it can be found that the running time required to solve the problem（IVO1C_∞）and the bounded problem（BIVO1C_∞）is not much different.Solving the problem(IVO1C_BH)basically takes slightly less running time than solving the bounded problem(BIVO1C_BH),but both are smaller than the running time required to solve the problem（IVO1C_∞）and the bounded problem（BIVO1C_∞）.Therefore,their effectiveness is verified.